RSA

发表于 更新于 分类于
  • RSA

RSA

RSA加密系统

RSA加密系统中，公钥和密钥的产生：

  1. 随机选取两个大质数$p$和$q$，使得$p \ne q$。
  2. 计算$n=p\cdot q$。
  3. 选取一个与$\phi (n)$互质的小奇数$e$，其中$\phi(n)$为欧拉函数，因此$\phi (n)=(p-1)(q-1)$，
  4. 对模$\phi (n)$，计算出e的乘法逆元d的值。即$ed\equiv 1\pmod {\phi(n)}$
  5. 将$p=(e,n)$公开作为RSA公钥
  6. 将$s=(d,n)$公开作为RSA密钥

假设密文为 $c$ ，明文为 $m$

RSA的加密过程为：$c = m^e\pmod n$

RSA的解密过程为：$m = c^d\pmod n$

这里是公钥加密，私钥解密。

如果用于数字签名，则与之相反，即私钥加密公钥解密。

如何获取大质数

素数分布函数$\pi(n)$描述了小于或等于n的素数的数目。例如$\pi(n) = 4$，分别为$2,3,5,7$

素数定理

$\lim \limits_{n \rightarrow \infty}\frac{\pi(n)}{n/\ln n} = 1$

对于较小的n，近似式$n/\ln n$能精确的给出$\pi(n)$的估计值，如：$n=10^9$，误差不超过6%

为了找一个长度与$n$相同的质数大概需要在$n$的附近找大约$\ln n$个数，如找一个1024位长度的质数，大约需要测试$\ln 2^{1024} \approx 710$个随机选取的长度为1024位长的整数素性。

1
2
3
4
5
6
7
8
9
// rand big prime in 2^15
ll rand_prime(ll rd) {
    ll prime = time(NULL) * rd % (2LL << 15);
    while (!miller_rabin(prime, 10)) {
        prime++;
        // cout << prime << endl;
    }
    return prime;
}

素数的测试

简单的方法是试除。最坏时间复杂度为$O(\sqrt n)$。

费马小定理

如果p是质数，则$a^{p-1}\equiv 1\pmod {p}$，其中$a = 1, 2, \cdots, p-1$

如果能找到任意的$a \in \bold z^{+}_{n}$，使得n不满足$a^{n-1}\equiv 1\pmod {n}$，那么n就是合数。

令人惊讶的是它的逆否命题几乎成立。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// is a^(n-1) = 1 (mod n)
bool witness(ll a, ll n) {
    ll u = n - 1, t = 0;
    while (u & 1 == 0)
        u >>= 1, t++;
    // n - 1 = 2^t * u

    ll x = modular_exponentiation(a, u, n);
    // 二次探测定理
    // 如果一个数p是质数，对于一个x∈(0,p)且x∈Z，方程x^2≡1(modp)的解有且只有两个：x=1或x=p−1。
    for (int i = 0; i < t; i++) {
        int xp = x;
        x = x * x % n;
        if (x == 1 && xp != 1 && xp != n - 1)
            return true;
    }
    if (x != 1)
        return true;
    return false;
}

// test n times a^(n-1) = 1 (mod n), rand a
bool miller_rabin(ll n, ll s) {
    for (int i = 0; i < s; i++) {
        ll a = time(NULL) * (ll)rand() % (n - 1) + 1;
        // cout << "a " << a << "n " << n << endl;
        if (witness(a, n))
            return false;
    }
    return true;
}

反复平方法求数的幂

求$a^{b}\pmod {n}$的高效算法，时间复杂度$O(logb)$

1
2
3
4
5
6
7
8
9
10
ll modular_exponentiation(ll a, ll b, ll n) {
    ll rt = 1;
    while (b) {
        if (b & 1)
            rt = rt * a % n;
        a = a * a % n;
        b >>= 1;
    }
    return rt;
}

比如$a=3,b=13 = 1101_2$

如果直接for循环则需要13次。

但是可以预处理出$a,a^2,a^4,a^8\cdots$，然后根据b的二进制位进行选择。

$a^{13} = a^{1101_2} = a^{1000_2}a^{100_2}a^{1_2} = a^{8}a^{4}a^1$

拓展欧几里得算法求解模线性方程

已知$a,b,n$求解$x$，满足$ax\equiv b\pmod {n}$，这样的方程可能没有解，可能有一个或多个解。

该式子实际上可以转化为$ax+kn=b$，如果$b$是$gcd(a,b)$的倍数就有解，解的个数是$\frac{b}{gcd(a,b)}$

而对于已知的$a,b$，拓展欧几里得可以计算出满足$d = gcd(a,b) = ax+by$

1
2
3
4
5
6
7
8
9
10
11
12
13
// extend eculid , d = gcd(a,b) = ax+by
void ex_gcd(ll a, ll b, ll* d, ll* x, ll* y) {
    if (b == 0) {
        *d = a;
        *x = 1;
        *y = 0;
    } else {
        ex_gcd(b, a % b, d, x, y);
        ll t = *x;
        *x = *y;
        *y = t - (a / b) * (*y);
    }
}

在RSA密钥生成过程中

  • 选取一个与$\phi (n)$互质的小奇数e，其中$\phi (n)=(p-1)(q-1)$
  • 对模$\phi (n)$，计算出$e$的乘法逆元$d$的值。即$ed\equiv 1\pmod {\phi(n)}$

$ed + k\phi(n) = gcd(e, \phi(n)) = 1$

有唯一解

1
2
3
4
5
6
7
// e*d = 1 (mod phi_n)  => e*d +k*phi_n = 1
//  rsa private key
ll private_key(ll e, ll phi_n) {
    ll d, x, y;
    ex_gcd(e, phi_n, &d, &x, &y);
    return (x + phi_n) % phi_n;
}

RSA实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#define ll long long
using namespace std;
#define print(a, b) cout << a << ": " << b << endl

// extend eculid , d = gcd(a,b) = ax+by
void ex_gcd(ll a, ll b, ll* d, ll* x, ll* y) {
    if (b == 0) {
        *d = a;
        *x = 1;
        *y = 0;
    } else {
        ex_gcd(b, a % b, d, x, y);
        ll t = *x;
        *x = *y;
        *y = t - (a / b) * (*y);
    }
}

// a^b%n
////a<n a*n < MAX  n*n < MAX
ll modular_exponentiation(ll a, ll b, ll n) {
    ll rt = 1;
    while (b) {
        if (b & 1)
            rt = rt * a % n;
        a = a * a % n;
        b >>= 1;
    }
    return rt;
}

// is a^(n-1) = 1 (mod n)
bool witness(ll a, ll n) {
    ll u = n - 1, t = 0;
    while (u & 1 == 0)
        u >>= 1, t++;
    // n - 1 = 2^t * u

    ll x = modular_exponentiation(a, u, n);
    // 二次探测定理
    // 如果一个数p是质数，对于一个x∈(0,p)且x∈Z，方程x^2≡1(modp)的解有且只有两个：x=1或x=p−1。
    for (int i = 0; i < t; i++) {
        int xp = x;
        x = x * x % n;
        if (x == 1 && xp != 1 && xp != n - 1)
            return true;
    }
    if (x != 1)
        return true;
    return false;
}

// test n times a^(n-1) = 1 (mod n), rand a
bool miller_rabin(ll n, ll s) {
    for (int i = 0; i < s; i++) {
        ll a = time(NULL) * (ll)rand() % (n - 1) + 1;
        // cout << "a " << a << "n " << n << endl;
        if (witness(a, n))
            return false;
    }
    return true;
}

// rand big prime in 2^15
ll rand_prime(ll rd) {
    ll prime = time(NULL) * rd % (2LL << 15);
    while (!miller_rabin(prime, 10)) {
        prime++;
        // cout << prime << endl;
    }
    return prime;
}

// e*d = 1 (mod phi_n)  => e*d +k*phi_n = 1
//  rsa private key
ll private_key(ll e, ll phi_n) {
    ll d, x, y;
    ex_gcd(e, phi_n, &d, &x, &y);
    return (x + phi_n) % phi_n;
}

// rsa public key
ll public_key(ll phi_n) {
    ll e = rand();
    while (gcd(e, phi_n) != 1)
        e++;
    return e;
}

void test() {
    srand((unsigned int)time(NULL));
    ll p = rand_prime(rand());
    ll q = rand_prime(rand());
    ll e = rand_prime(rand());
    // public_key e>max(p,q)  so gcd(e, phi_n=(p-1)(q-1)) = 1
    if (p > e)
        swap(e, p);
    if (q > e)
        swap(e, q);
    ll n = p * q;
    ll phi_n = (p - 1) * (q - 1);
    // ll e = public_key(phi_n);
    ll d = private_key(e, phi_n);
    print("p", p);
    print("q", q);
    print("n", n);
    print("phi_n", phi_n);
    print("e", e);
    print("d", d);
    ll msg = 1314;
    ll code_msg = modular_exponentiation(msg, e, n);
    ll decode_msg = modular_exponentiation(code_msg, d, n);
    print("code_msg", code_msg);
    print("decode_msg", decode_msg);

    /*
        e*d = 1 (mod phi_n)
        m^e = c
        c^d = m
        m^{e*d} = m (mod n)
    */

}

int main() {
    //	cout << pow_mod(2, 10, 2000);
    test();

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
p: 16649
q: 32831
n: 546603319
phi_n: 546553840
e: 59809
d: 136453409
code_msg: 365022407
decode_msg: 1314

p: 17519
q: 18047
n: 316165393
phi_n: 316129828
e: 63211
d: 294359675
code_msg: 15110090
decode_msg: 1314

p: 22073
q: 4441
n: 98026193
phi_n: 97999680
e: 27647
d: 86011583
code_msg: 17550476
decode_msg: 1314

RSA的正确性

设密文为 $c$ ，明文为 $m$，$c = m^e\pmod n$，$m = c^d\pmod n$

所以有$m\equiv m^{ed}\pmod {n}$

由于$ed\equiv 1\pmod {\phi(n)}$，其中$\phi(n) = (p-1)(q-1)$，所以$ed = 1+k(p-1)(q-1)$$\begin{array}{llllc}
m^{ed} & \equiv & m(m^{p-1})^{k(q-1)} & \pmod p & \\
& \equiv & m((m \mod p))^{p-1})^{k(q-1)} & \pmod p & \\
& \equiv & m(1)^{k(q-1)} & \pmod p & 费马小定理\\
& \equiv & m & \pmod p & \\
\end{array}$

类似地，有$m^{ed} \equiv m \pmod q$

根据中国剩余定理，$m^{ed} \equiv m \pmod n$

RSA的安全性

对外公开公钥$p=(e,n)$，已知$n$是两个质数$p$和$q$的乘积，如果能分解找到$p$和$q$。那么便可以通过拓展欧几里得算法求出$ed\equiv 1\pmod {(p-1)(q-1)}$的$d$。从而可以得到密钥$s=(d,n)$

RSA的加密系统的安全性主要来源于对于大整数进行因式分解的困难性。如果对方能够对公钥中的模$n$进行分解，就可以更具公钥推出密钥，这是因为对方和公钥创建者以相同的方法使用因子$p$和$q$。因此，如果能够轻易分解大整数，也就能轻易打破RSA加密系统。

经过20多年的研究，人们还没有发现比分解模$n$更容易的方法来打破RSA加密系统。

通过随机选取两个1024为的质数并求它们的积，就可以创造无法用可行技术可行时间内破解的公钥。所以在数论算法的设计方法还缺乏根本突破的情况下，RSA算法加密系统可以为实际应用提供高度的安全性。

RSA的局限性

RSA从提出到至今，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。

但RSA算法也是有缺点的。

  • 第一，RSA的安全性目前并没有理论上的证明；
  • 第二，密钥的生成过程比较麻烦，受素数产生技术的限制，难以做到一次一密；
  • 第三，就是RSA的运算速度，速度是RSA目前最大的缺陷，相同的安全级别下，RSA的速度比相应的对称加密算法慢大约1000倍。

因此，RSA通常只用于少量数据加密。实际应用中一般用来加密对称算法的密钥，而密文多用对称加密算法加密传输。