RSA

简介

一种基于大合数因子分解困难性的公开密钥密码，用于加密和数字签名

特点：

非对称：有一个公钥对和私钥对，公钥对可以公开，减少了密钥传递的风险

分组加密

理论基础

RSA加解密算法的步骤如下：

1. 随机选择两个大素数p和q且保密

2. 计算n=pq, 将n公开

3. 计算$$\varphi(n)=(p - 1)(q - 1)$$

4. 随机地选取一个正整数e, $$1 < e < \varphi(n)$$，且$$(e, \varphi(n))=1$$, 将e公开

5. 根据$$ed=1mod\varphi(n)$$, 求出d，并对d保密

6. 加密运算：
   $$
   C = M^emod\space n
   $$

7. 解密运算：
   $$
   M = C^d mod \space n
   $$

其中，正整数e一般选择3或者65537

第5步求解乘法逆元时，可以使用扩展欧几里得算法降低复杂度

欧几里得算法

$$gcd(a, b) = gcd(b, a % b)$$

扩展欧几里得算法

求$$a * x + b * y = gcd(a, b)$$的一组解x0, y0

原理见具体实现

求解a * b = 1 (mod m)中a的逆元b, b为正整数，且尽量为最小值

原理见具体实现

加解密运算时，可使用快速幂避免大数求模

具体实现

// main.c

#include<stdio.h>
#include"rsa.h"

int main()
{
    int64_t M = 688;
    int64_t C = 1570;
    int64_t resM;
    int64_t resC;

    p = 47;
    q = 71;
    e = 79;

    cal_key_pair();

    rsa_encrypt(M,    e, n, &resC);
    rsa_decrypt(resC, d, n, &resM);

    printf("public  key: (%lld, %lld)\n", n, e);
    printf("private key: (%lld, %lld)\n", n, d);
    printf("encode C:%lld\ndecode M:%lld\n", resC, resM);

    return 0;
}

#ifndef RSA_H
#define RSA_H

typedef long long int64_t;

// PRIVATE
extern int64_t p;
extern int64_t q;
extern int64_t d;

// PUBLIC
extern int64_t n;
extern int64_t e;

void cal_key_pair();

// rsa加密
// M的长度不能大于n的长度，否则需要分组
void rsa_encrypt(int64_t M, int64_t e, int64_t n, int64_t* C);

// rsa解密
// C的长度不能大于n的长度，否则需要分组
void rsa_decrypt(int64_t C, int64_t d, int64_t n, int64_t* M);

#endif

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include"rsa.h"

// PRIVATE
int64_t p;
int64_t q;
int64_t d;

// PUBLIC
int64_t n;
int64_t e = 65537;

// 欧几里得算法 求最大公约数
// gcd(a, b) = gcd(b, a % b)
int64_t gcd(int64_t a, int64_t b)
{
    if(b == 0)return a;
    else return gcd(b, a % b);
}

// 扩展欧几里得算法 求a * x + b * y = gcd(a, b)的一组解x0, y0
// 通解为 x = x0 + (b / gcd) * t, y = y0 - (a / gcd) * t
// 求解方法：
// 设 a * x + b * y = gcd(a, b)
// 则当a = gcd, b = 0时， x = 1, y = 0，此为gcd(a, b)的递归出口
// 令b * x1 + (a % b) * y1 = gcd(b, a % b)
// 因为 a % b = a - (floor)(a / b) * b
// 所以 a * x1 + (a % b) * y1
//   = a * x1 + (a - (floor)(a / b) * b) * y1
//   = a * y1 + b * (x1 - (floor)(a / b) * y1)
// 而   gcd(a, b) == gcd(b, a % b)
// 因此 x = y1
//     y = x1 - (int)(a / b) * y1
// 递归出口为b == 0, x = 1, y = 0
int64_t e_gcd(int64_t a, int64_t b, int64_t* x, int64_t* y)
{
    if(b == 0)
    {
        *x = 1;
        *y = 0;
        return a;
    }
    int64_t x1, y1;
    int64_t gcd = e_gcd(b, a % b, &x1, &y1);
    *x = y1;
    *y = x1 - (a / b) * y1;
    return gcd;
}

// 求解a * b = 1 (mod m)中a的逆元b, b为正整数，且尽量为最小值
// a*b=1(mod m) == a*b + m*y0 = 1
// 则 e_gcd(a, m, &b, &y0) => b = x0
// 此时 x = x0 + (m / gcd) * t = x0 + m*t
// 要使b最小，则需保证x0 > 0, 那么b = x0 % m
// 若 x0 < 0, 则令 xs = x0 % abs(m), -m < xs < 0
// 则 b = xs + m, 0 < b < m, 此为所求结果
int64_t inv1(int64_t a, int64_t m)
{
    int64_t x0, y0, xs, b;
    int64_t gcd = e_gcd(a, m, &x0, &y0);
    if(gcd != 1)return -1;
    if(x0 < 0)
    {
        xs = x0 % m;
        b = xs + m;
    }
    else
    {
        b = x0 % m;
    }
    return b;
}

// 快速幂运算 b^exp(mod m)
// a * b % m == (a % m) * (b % m) % m
// b^exp mod m = 
// b^(exp - 1) * b mod m,      e % 2 == 1
// b^(exp/2) * b(exp/2) mod m, e % 2 == 0
// 优化：改成非递归迭代算法
int64_t pow_mod(int64_t b, int64_t exp, int64_t m)
{
    if(exp == 0)return 1;
    if(exp % 2 == 1)
    {
        return (pow_mod(b, exp - 1, m) * b) % m;
    }
    else
    {
        int64_t tmp = pow_mod(b, exp / 2, m);
        return (tmp * tmp) % m;
    }
}

void cal_key_pair()
{
    n = p * q;
    int64_t Fn = (p - 1) * (q - 1);

    // e * d = 1 (mod Fn)
    d = inv1(e, Fn);
    if(d == -1)
    {
        printf("e, Fn have gcd != 1!\n");
        exit(0);
    }
}

void rsa_encrypt(int64_t M, int64_t e, int64_t n, int64_t* C)
{
    *C = pow_mod(M, e, n);
}

void rsa_decrypt(int64_t C, int64_t d, int64_t n, int64_t* M)
{
    *M = pow_mod(C, d, n);
}