RSA 公钥机密体制

在 Diffie 和 Hellman 提出公钥密码体制的设想后,Merkle 和 Hellman 首先共同提出 MH 背包公钥加密体制，随后 Rivest,Shamir ,Adleman 联合提出RSA公加密体制。RSA虽晚于MH背包公钥加密体制,但它是第一个安全、实用的公钥加密算法,已经成为国际标准,是目前应用广泛的公钥加密体制。RSA的基础是数论的欧拉定理,它的安全性依赖于大整数因子分解的困难性。因为加解密次序可换,RSA 公钥加密体制既可用于加密,也可用于设计数字签名体制，加密体制又可以分为密钥生成算法、加密算法和解密算法三部分。

数论基础

  1. 欧拉函数：$1 \sim N$中与 N 互质的数的个数成为欧拉函数，记为$\varphi(N)$，若在算数基本定理中,$N = p_1^{a_1}p_2^{a_2} \ldots p_m^{a_m}$,则：

    $$\varphi(N) = N \times \frac{p_1 - 1}{p_1} \times \frac{p_2 - 1}{p_2} \times \ldots \times \frac{p_m - 1}{p_m}$$

  2. 欧拉定理：$a^{\varphi(n)} \equiv 1(modn)$,其中 a 和 n 都是正整数，且 a 和 n 互质

    小费马定理：假设 p 是一个质数，且 a 和 p 互质（即两者只有一个公约数 1），那么$a^{p-1} \equiv 1(mod p)$恒成立。

  3. 同余的一些基本性质：

    (a + b) % p = (a % p + b % p) % p
    (a - b) % p = (a % p - b % p) % p
    (a _ b) % p = (a % p _ b % p) % p
    但对于除法却不成立，即(a / b) % p 不等于 (a % p / b % p) % p ,但如果利用乘法逆元便可以

    如需证明，点击直达（￣︶￣）↗ 　

  4. 贝祖定理(裴蜀等式)：

    ​ 即如果 a、b 是整数，那么一定存在整数 x、y 使得 ax+by=gcd(a,b)。

  5. 扩展欧几里得算法：可以快速求出 ax+by=gcd(a,b)中的 x 和 y 的值（可以用于下面求逆元）

  6. 逆元(很重要！！！！)：$ab \equiv 1(mod p)$,那么 a，b 互为模 n 意义下的逆元

  7. 快速幂（用于解决 mod 时溢出的问题，速度也大大加快 ψ(｀ ∇´)ψ

    所有 a^b 的 b 都能转换为二进制

    即如果 b 的二进制表示的第 0 位为 1,则乘上当前的 a

    b 右移一位

    更新 a,a 依次为 a^{2^0},a^{2^1},a^{2^2},…,a^{2^logb}

    因此举个例子

    $$
    4^5mod10 = 4^{(101)_2} mod 10 = 4 ^{2^0 + 2^2} mod 10 = (4 mod 10 + 96mod10)mod10=(24) mod 10 = 4
    $$

    在次方的同时进行 mod 运算，中间数不会太大

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    LL qmi(LL a, LL k, LL p) //快速幂求余数
    {
        LL res = 1;
        while(k)
        {
            if(k & 1) res = (LL)res * a % p;
            k >>= 1;
            a = (LL)a * a % p;
        }
        return res;
    }

1. RSA 密钥生成算法

密钥生成算法为用户生成加解密算法中使用的公私密钥对,分为以下几个步骤:

  1. 选取两个安全大素数p和q(“大”指其长度要足够长目前推荐长度为至少 1024 比
    特);

  2. 计算乘积$ n=p \times q,\varphi(n)=(p-1)(q-1)$,其中 $\varphi(n)$为n的欧拉函数;

    公式由来：因为 n 包含两个质因子 p，q，所以在 1 到 n-1 中包含 p，q 因子的数均与 n 不互素。包含 p 因子的有 p，2p，3p 一直到 p（q-1）即（q-1)个，同理含 q 的有（p-1)个。一共 p+q-2 个数与 n 不互素

    则在这 n-1 个数中与 n 互素的数一共有 n-1-（p+q-2）=n-p-q+1，且 n 可以写作 p*q，可以得到（p-1)(q-1)

  3. 随机选取整数$ e(1<e< \varphi (n))$作为公钥,要求满足 $gcd(e,\varphi(n))=1$,即$e与\varphi(n)$互素;

  4. 用Euclid 扩展算法(欧几里得扩展算法）计算私钥d,以满足$d \times e\equiv1(mod\varphi(n))$,即$d\equiv e^{-1}(mod \varphi(n))$则e和n 是公钥,d 是私钥。

    给定 n 和正整数$a_i,b_i$，利用欧几里得扩展算法可快速求出$x_i,y_i$满足$a_i \times x_i + b_i \times y_i = gcd(a_i, b_i)$.

    直达欧几里得扩展算法题解及 c++代码

    因为$d \times e\equiv1(mod\varphi(n))$，所以$(e)d + (-k) \varphi(n)) = 1$,d 与-k 分别为欲求的 x，y，可直接用欧几里得扩展算法直接求 ，下面样例给出 c++代码

注意,加解密算法中两个素数p和q不再需要,可销毁,但绝不能泄露。

样例

下面举例说明 RSA 公钥/私钥对的具体产生过程(注,在公钥密码体制中,参数长度都比较长,而为方便计算,实例中选取参数都较小,重在说明算法流程)。

假设 p=13,q=17;

计算 $n=p\times q=13\times17=221$;则$\varphi(n)=(p-1)\times(q-1)=(13-1)\times(17-1)=192$。选取公钥 e=11(一般为素数),满足$1<e<\varphi(n)$,且满足 $gcd(e,\varphi(n))=1$。通过 Euclid 扩展算法求得满足公式 $d\times e\equiv1(mod 192)$的 d=35。所以,得到公钥(e,n)为(11,221),私钥 d 为 35。

C++代码

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
#include <iostream>
#include <algorithm>
#include <ctime> //用它来获取当前时间，作为随机数生成器的种子。
#include <cstdlib> //rand()和srand()，这两个函数用于生成随机数。

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PII;

const LL N = 110;

PII public_key;
LL private_key;
LL p, q;
LL Euler;// 欧拉函数

// 获取1-110的质数
LL primes[N];
LL cnt;
bool st[N];

void get_primes(){ // 质数筛算法获取质数（速度比较快）
    for(LL i=2;i<=N;i++){
        if(!st[i]) primes[cnt++]=i;
        for(LL j=0;primes[j]<=N/i;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}

LL gcd(LL a, LL b) // 欧几里得算法判断最小公共因子
{
    return b?gcd(b, a % b):a;
}

LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }

    LL d, x1, y1;
    d = exgcd(b, a % b, x1, y1);
    x = y1, y = x1 - a / b * y1;

    return d;
}

int get_Rand(int min, int max){
    return (rand() % (max - min)) + min;
}

//e*d + Euler*k = 1 类比 a*x + b*y=1
void get_public_private_key(LL p, LL q)
{
    LL k, d;
    srand(time(0));
    LL n = p * q;
    Euler = (p - 1) * (q - 1);

    cout <<cnt <<endl;
    int e = get_Rand(0, cnt - 1);
    cout << e <<endl;
    while(e >= Euler || gcd(e, Euler) != 1)// 随机选择公钥,不满足条件继续随机
    {
        e = get_Rand(0, cnt - 1);
    }
    exgcd(e, Euler, d, k);
    public_key.x = e, public_key.y = n;
    private_key = d;
}

int main()
{
    cout << "请输入素数p和q" << endl;
    cin >> p >> q;
    get_primes();
    get_public_private_key(p, q);
    cout << "公钥为：(" << public_key.x << "," << public_key.y << ")" << endl <<
    "私钥为：(" << private_key << ")" << endl;
    return 0;
}

结果

1
2
3
4
5
6
//为了方便说明这里结果为上面例子一致，但实际上因为公钥e是随机生成的
//因此只要满足条件，每次结果应该都不一样
请输入素数p和q
13 17
公钥为：(11,221)
私钥为：(35)

2.RSA 加解密算法

1.加密过程

加密时首先将明文比特串分组,使得每个分组对应的十进制数小于 n,即分组长度小于$log_2^n$，然后对每个明文分组 $m_i$;作加密运算，具体过程分为如下几步:
(1)获得接收方公钥(e,n);
(2)把消息 M 分组为长度为$L(L<log_2^n)$的消息分组 $M=m_1m_2···m_t$;
(3)使用加密算法 $c_i\equiv m_i^e(mod n)(1 \leq i \leq t)$计算出密文$ C=c_1c_2···c_t$;
(4)将密文 C 发送给接收方。

2.解密过程

(1)接收方收到密文 $ C=c_1c_2···c_t$;
(2)使用私钥d 逐一恢复明文分组 $m_i$,$m\equiv c_i^d(mod n)(1 \leq i \leq t)$;
(3)得明文消息$M=m_1m_2···m_t$;

3.正确性

说实话我是看的头晕 😵

下面证明若算法严格按步骤执行,接收者可以使用私钥及解密算法恢复出明文。

由公式$c_i\equiv m_i^e(mod n)$,可得

$c_i^d(mod n)=m_i^{ed}(mod n)\equiv m_i^{\varphi(n) + 1}(mod n)$因为$ed\equiv 1 (mod \varphi(n))$,故存在 $k \in Z$,使得$ed=k\times \varphi(n)+1$,下面分两种情况讨论:

  1. $gcd(m_i,n)=1$,则由欧拉定理得

    $$
    m_i^{\varphi(n)}\equiv 1 (mod n) \Rightarrow m_i^{\varphi(n)}\equiv 1(mod n),m_i^{\varphi(n) + 1}\equiv m_i(mod n)
    $$

    又因为$m_i < n,所以,c_i^dmodn\equiv m_i^{k\varphi(n) + 1} \equiv m_i(modn)$。

  2. $gcd(m_i,n)\neq 1$,可得 $gcd(m_i,n)>1$。由于$n=p\times q$,所以$gcd(m_i,n)$必含 p 或 q。

    不妨设$ gcd(n,m_i)=p$,则有 $m_i=tp,1\leq t < q$,由欧拉定理得

    $$
    m_i^{\varphi(q)} \equiv 1(mod q)
    $$

    因此，

    $$
    m_i^{\varphi(q)}\equiv 1 (mod q) \Rightarrow [m_i^{\varphi(q)}]^{\varphi( p)}\equiv 1(mod q) \Rightarrow m_i^{\varphi(n)}\equiv 1(mod q)
    $$

    因此存在一整数 r,使得 $m_i^{\varphi(n)} = 1十rq$,两边同时乘以$m_i=tp$得:
    左边$=m_i^{\varphi(n) + 1}$;右边$=tp+rq·tp=m_i+rtpq-m_i十rtn$。
    上面等式两边同时进行模 n 运算,得 $m_i^{\varphi(n)+1}=(m_i+rtn)\equiv m_i(mod n)$。
    又因为$m_i < n$,得$m_i^{\varphi(n) + 1}mod n=m_i$。
    故由(1)、(2)验证了解密算法的正确性。

    下表是总结

    1.png

4.实例

下面举一个简单的例子来说明如何用 RSA 公钥加密体制来对一段消息进行加解密
设接收方 B 选择 p=43,q=59,e=13。发送方 A 有消息 m=cybergreatwall,我英文字母表顺序 a=00,01,···25 进行编码。A 欲用 RSA 公钥加密体制加密后传送给 B,求 B 的私钥并描述加解密过程。
解 密钥生成:$n=p×g=43×59=2537,\varphi(2537)=42\times 58=2436$

e=13,则根据 $d\equiv e^{-1}(mod 2436)$,得:d=937

则公钥(n=2 537,e=13 ),私钥 d=937。
A 的加密过程:先将消息分块为:cy、be、rg、re、at、wa、ll。(m1-m6)

利用英文字母表的顺序编码将明文数字化得:
0224 0104 1706 1704 0019 2200 1111
利用公钥(n=2537,e=13)和加密算法 $c_i \equiv m^e_i(mod n)$进行加密
对第一个分组 m 的加密过程为:

$$
0224^{13}mod2537=1692=c_1
$$

同理对其他分组进行加密,得密文:C=C1C2C3C4C5C6=1692 0803 1093 1943 2299 1254 0724

解密过程:解密消息时用私钥 d=937 和解密算法 $m_i\equiv c_i^d(mod n)$进行解密对第一组密文 C1 进行解密的过程为:

$$
1692^{937}mod 2537=0224
$$

0224 对应的明文分组为 $m_1=cy$,所以密文 C1 所对应的明文为 cy。

消息的其余部分用同样的方法就可以恢复出来,得明文 mcyber greatwall。

5.RSA 的快速计算

应用 RSA 算法进行加解密计算的时候,可以使用下列方法加快计算速度

  1. 利用模运算的性质:每次乘积后即进行模运算,可以使得中间结果长度小于 n 的长度

    $$
    [(amod n)\times (bmod n)]mod n=(ab)mod n
    $$

    每次乘积后即进行模运算,可以使得中间结果长度小于 n 的长度。

  2. 使用快速取模指数算法可以很有效地减少模乘的次数,对此算法描述如下

    e 的二进制表示为$b_kb_{k-1}···b_0$,其中 $b_i \in {0,1}(i=0,1,···,k)$,则

    $$
    e = \sum_{i = 0}^{k}{b_{i}2^i} = \sum_{b_i = 1}{2^i}
    $$

    因此有

    $$
    m^emod n = m^{\sum_{b_i = 1}{2^i}} mod n =
    $$

    $$
    (( \ldots((m^{b_k})^2modn · m^{b_{k - 1}})^2mod n \ldots)^2mod n · m^{b_0}) mod n
    $$

    这就是快速取模指数算法，计算$c \equiv m^e(mod n) $的快速取模指数算法的伪代码如下

    1
    2
    3
    4
    5
    6
    7
    t <- 0; c <- 1
    for i <- k down to 0
    do	t <- 2 × t
        c <- (c × c) mod n
        if bi = 1 then t <- t + 1
                       c <- (c × m) mod n
    return c

6.C++代码

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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <sstream>

#define x first
#define y second

using namespace std;

const int N = 100010;

typedef long long LL;

string alphabet[26] = {
"00", "01", "02", "03", "04", "05",
"06", "07", "08", "09", "10",
"11", "12", "13", "14", "15",
"16", "17", "18", "19", "20",
"21", "22", "23", "24", "25"};

string clear_text; //明文
string secret_text; //密文

LL p, q;//两个安全大素数
LL e, n;//公钥
LL private_key; //私钥
LL Euler;// 欧拉函数

int group; // 分组长度（这里取的是小于10的因子主要是能被整除，比较方便）
int res; //选择加密还是解密

vector<string> encode_Int;//加密时明文数字化
vector<string> encrypt_Int; // 解密时密文数字化

LL qmi(LL a, LL k, LL p) //快速幂求余数
{
    LL res = 1;
    while(k)
    {
        if(k & 1) res = (LL)res * a % p;
        k >>= 1;
        a = (LL)a * a % p;
    }
    return res;
}

void init_group(string s) // 获取分组的大小
{
    int len = s.size();
    int cnt = 1;
    group = cnt;
    while(len % cnt == 0 && cnt < 10)
    {
        group = cnt;
        cnt ++ ;
    }
}

LL exgcd(LL a, LL b, LL &x, LL &y) // 欧几里得扩展算法
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }

    LL d, x1, y1;
    d = exgcd(b, a % b, x1, y1);
    x = y1, y = x1 - a / b * y1;

    return d;
}

void encrypt(string s) // 加密
{
    init_group(s);
    LL k, d;
    n = p * q;
    Euler = (p - 1) * (q - 1);

    exgcd(e, Euler, d, k); // 利用欧几里得扩展算法获取私钥d
    private_key = d;
    cout << "公钥为：(" << e << "," << n << ")" << endl <<
    "私钥为：(" << private_key << ")" << endl;

    for(int i = 0; i < s.size(); i += group )
    {
        int t = 0;
        string cnt = "";
        while(t < group)
        {
            cnt += alphabet[s[i + t] - 'a'];
            t ++ ;
        }
        encrypt_Int.push_back(cnt);
    }
    for(auto t : encrypt_Int) // 求加密后的c
    {
        LL num, sum; // 用于求加密后的cn
        string c; // 记录c1-cn
        std::istringstream ss(t);
        ss >> num;
        sum = qmi(num, e, n);
        c = to_string(sum);
        while(c.size() < group*2) c.insert(0,"0");
        secret_text += c;
    }
    cout << "加密后的密文为：" << secret_text << endl;
}

void encode(string s) //解密
{
    init_group(s);
    n = p * q;
    for(int i = 0; i < s.size(); i += group * 2 )
    {
        int t = 0;
        string tmp = "";
        int num, sum;
        string m;// 记录明文
        while(t < group * 2)
        {
            tmp += s[i + t];
            t ++ ;
        }
        std::istringstream ss(tmp);
        ss >> num;
        sum = qmi(num, private_key, n);
        m = to_string(sum);
        while(m.size() < group*2) m.insert(0,"0");
        for(int j = 0; j < group*2; j += 2 ) // 将每一组的数字，每两位存在encrypt_Int里面
        {
            string cnt = "";
            int t = 0;
            while(t < 2)
            {
                cnt += m[j + t];
                t ++ ;
            }
            encrypt_Int.push_back(cnt);
        }
    }
    for(auto t : encrypt_Int) // 求解密后的m
    {
        int num;
        std::istringstream ss(t);
        ss >> num;
        clear_text += ('a' + num);
    }
    cout << "解密后的明文：" << clear_text << endl;
}

int main()
{
    cout << "请给出两个大素数p，q和公钥e" << endl;
    cin >> p >> q >> e;

    cout << "请输入1选择加密，或者输入2选择解密" << endl;
    cin >> res;

    if(res == 1)
    {
        cout << "请输入明文" << endl;
        cin >> clear_text;
        encrypt(clear_text);
    }
    else if(res == 2)
    {
        cout << "请输入密文和私钥" << endl;
        cin >> secret_text >> private_key;
        encode(secret_text);
    }

    return 0;
}

结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//加密
请给出两个大素数p，q，和公钥e
请输入1选择加密，或者输入2选择解密
请输入明文
公钥为：(13,2537)
私钥为：(937)
加密后的密文为：1692080310931943229912540724

// 解密
请给出两个大素数p，q和公钥e
43 59 13
请输入1选择加密，或者输入2选择解密
2
请输入密文和私钥
1692080310931943229912540724 937
解密后的明文：cybergreatwall

3.RSA 安全性

RSA 在安全性方面，容易遭到因子分解发，针对参数选择中的共模攻击，低指数攻击等等等

因此需要我们加强保护意思，在防范措施上主要体现在下面两点

  1. 密钥长度

    首先,在 RSA 密钥长度方面,应以达到使得攻击者在现有计算能力条件下不可破解为基本原则，同时，选择时需要考虑被保护的数据类型、数据保护期限、威胁类型以及最可能的攻击第方面。目前大多数标准要求使用 1024 比特 RSA 密不再使用 512 比特密钥。数域筛方法是比较有效的因子分解方法，并常用于确定 RSA 密钥长度的下限。在 2000 年,Silverman 依此推断 1024 比特密钥在未来 20 年内还是安全的。但是,NIST(The NationalInstitute ofStandard and Technology)的《Key Managemen Guideline》草案中只推荐使用 RSA1024 比特长密钥来加密保存要求不超过 2015 年保密要求期限的数据,如果保密期限超过 2015 年,则建议至少使用 2048 比特长密钥。另外,也要考虑密钥长度对密钥生成、加密和解密运算效率的
    影响

  2. 参数选择

    除了需要选取足够大的大整数 n 外,对素数 p 和 q 的选取应该满足以下要求

    1. 为避免椭圆曲线因子分解法,p 和 g 的长度相差不能太大。如使用 1024 比特的模数 n,则 p 和 g 的模长都大致在 512 比特左右。
    2. p 和 q 差值不应该太小。
    3. gcd(p-1,q-1)应该尽可能小。
    4. p 和 q 应为强素数,即 p-1 和 q-1 都应有大的素因子。
    5. 为了防止低指数攻击,加密指数 e 和解密指数 d 都不能选取太小的数

4.总结

关于 RSA 的优点缺点

优点：

  1. 安全性高：RSA 算法基于数学难题，使得即使在今天的高性能计算机环境中，也很难进行有效的破解。因此，RSA 在保证信息安全性方面表现出色。
  2. 适用范围广：RSA 算法适用于多种应用场景，如互联网、电子邮件、数据存储等。它可以用于数据加密、数字签名、身份验证等任务。
  3. 灵活性好：RSA 算法支持多种密钥长度，可以根据实际需求选择不同的密钥长度来平衡安全性和性能。此外，RSA 还支持多种填充方案和摘要算法，具有较强的灵活性。

缺点：

  1. 加密和解密速度慢：相比于对称加密算法，如 AES，RSA 算法的加密和解密速度较慢。这是因为 RSA 算法需要进行大量的数学运算，尤其是在处理大块数据时。
  2. 密钥管理困难：由于 RSA 算法使用的是非对称密钥，因此需要管理两个密钥（公钥和私钥）。如果密钥丢失或被盗，可能会对信息安全造成威胁。此外，在分布式系统中，如何安全地分发和管理密钥也是一个难题。
  3. 实现成本高：RSA 算法需要使用大量的数学运算和内存资源，因此在一些资源受限的环境中，实现 RSA 算法可能会比较困难。此外，RSA 算法也需要较高的计算能力，因此在一些老旧或性能较低的设备上，可能会影响其性能表现。