首页
社区
课程
招聘
[原创]RSA的数学原理与实现
2023-4-17 23:34 13401

[原创]RSA的数学原理与实现

2023-4-17 23:34
13401

经常看到各位大佬挥毫泼墨,就算法和密码问题各抒己见,小弟今天斗胆也来上一课。

关于RSA的数学原理和实现,本文根据数论中的知识给出了证明,然后是自己手撸的64位RSA算法。

1.基础知识

辗转相除法:

a=bx+c,(a,b)=(b,c)若a = bx + c,则(a,b) = (b,c)a=bx+c,(a,b)=(b,c)

证明略。

欧拉函数:

ϕ(n)=n(/p)(/q)=(p)(q)\phi(n) = n*(1 - 1 /p)(1 - 1/q) = (p - 1)*(q - 1)ϕ(n)=n(11/p)(11/q)=(p1)(q1)

证明自行百度。

2. RSA加解密的条件

  1. p和q是两个大素数,欧拉函数值ϕ(n)=n()()=(p)(q)\phi(n)=n(1 -\frac{1}{p})(1 - \frac{1}{q})=(p-1)(q-1)ϕ(n)=n(1p1)(1q1)=(p1)(q1)
  2. w与ϕ(n)\phi(n)ϕ(n)互素,d是w的模欧拉值逆,即dw=1(mod n)

3. 加解密过程

加密:c=E(m)=mwmodnc = E(m) = m ^w mod \quad nc=E(m)=mwmodn

解密:m=D(c)=cdmodnm = D(c) = c^d mod \quad nm=D(c)=cdmodn

4. 证明过程:

(mwmodn)dmodn=mwdmodn[mw=an+b,(mwmodn)dmodn=bdmodnmwdmodn=(an+b)dmodn=(an)n+Cdn(an)nb+...+bdmodn=bdmodn](m^w mod\quad n)^d mod \quad n = m^{wd} mod \quad n\\ [\\ 证明:\\ 假设m^w = a n + b,则(m^w mod \quad n)^d mod \quad n = b ^ d mod \quad n\\ 而m^{wd} mod \quad n = (an+b)^d mod \quad n = (an)^n + \mathrm{C}_d^{n-1}(an)^{n-1}b + ... + b^d mod \quad n = b^d mod \quad n\\ ](mwmodn)dmodn=mwdmodn[证明:假设mw=an+b,(mwmodn)dmodn=bdmodnmwdmodn=(an+b)dmodn=(an)n+Cdn1(an)n1b+...+bdmodn=bdmodn]

所以,要证明加解密过程的正确性,即证明:
mwdmodn=mm^{wd} mod \quad n = mmwdmodn=m
因为:
wd(modϕ(n))wd \equiv 1(mod \quad \phi(n))wd1(modϕ(n))
所以
wd=Aϕ(n)+wd = A \phi(n) + 1wd=Aϕ(n)+1

(1). 若m与n互素
根据欧拉定理可得:
mϕ(n)(modn)mkϕ(n)+m(modn)m^{\phi(n)} \equiv 1(mod \quad n) \\ m^{k \phi(n)+1} \equiv m(mod \quad n)mϕ(n)1(modn)mkϕ(n)+1m(modn)

(2). 若m与n不互素
因为m是合数,n=pq, 根据算数基本定理,m必包含p或者q,假设m包含q,则根据fermat定理可得,
mp(modp)m ^{p -1} \equiv 1(mod \quad p)mp11(modp)

等式得证。

屈婉玲等几位老师的《离散数学》证明如下:
图片描述

例子程序(仅支持64位以内的密钥长度)

代码是自己根据数学公式一行一行写的,因为对照公式可以很容易识别各个函数的用途,所以没写注释,请大家见谅。
只是为了学习验证,可能有所缺陷,敬请批评指正。

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
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
#include "rsa.h"
#include <windows.h>
#include <stdio.h>
 
myInt64 g_n = 0;
 
myInt64 g_d = 0;
 
myInt64 g_w = 0;
 
int g_blocksize = 0;
 
int g_blocksize_src = 1;
 
myInt64 pow_i_old(myInt64 a, myInt64 b, myInt64 p) {
    myInt64 res = 1;
    for (myInt64 i = 0; i < b; i++)
    {
        res = (res * a) % p;
        if (res == 0)           //caution here: avert to overlow
        {
            break;
        }
    }
 
    return res;
}
 
 
myInt64 pow_i(myInt64 x, myInt64 n, myInt64 p)
{
    if (n == 0)
    {
        return 1;
    }
    myInt64 temp = pow_i((x * x) % p, n / 2, p); //递归计算(X*X)^[N/2]
    if ((n & 1) != 0) //判断n的奇偶性
    {
        temp = (temp * x) % p;
    }
    return temp;
}
 
 
myInt64 pow_ii(myInt64 a, myInt64 b, myInt64 g_n) {
    myInt64 res = 1;
    for (myInt64 i = 0; i < b; i++)
    {
        res = (res * a) % g_n;
        if (res == 0)           //caution here: avert to overlow
        {
            //break;
        }
    }
 
    return res;
}
 
 
int isMutualPrime(myInt64 n, myInt64 m) {
    return 1;
}
 
int isPrimeNumber(myInt64 n) {
    for (myInt64 i = 2; i < n; i++)
    {
        myInt64 quotient = n % i;
        if (quotient == 0)
        {
            return FALSE;
        }
    }
 
    return TRUE;
}
 
 
 
int rsaInit(myInt64 p, myInt64 q)
{
    if (p == q || p <= 2 || q <= 2 || isPrimeNumber(p) == 0 || isPrimeNumber(q) == 0)
    {
        return FALSE;
    }
 
    g_n = p * q;
    if (g_n < 128)
    {
        return FALSE;
    }
 
    myInt64 mi64 = 0x8000000000000000;
    int bh = 63;
    for (int i = 63; i >= 0; i--)
    {
        if (g_n & mi64)
        {
            bh = i;
            break;
        }
        mi64 = mi64 >> 1;
    }
 
    if (bh >= 32)
    {
        g_blocksize = 8;
    }
    else if (bh >= 16)
    {
        g_blocksize = 4;
    }
    else if (bh >= 8)
    {
        g_blocksize = 2;
    }
    else
    {
        g_blocksize = 1;
    }
 
 
    myInt64 fai_n = (p - 1) * (q - 1);
 
    myInt64 w = 2;
    myInt64 d = 2;
    for (w = 2; w < fai_n; w++)
    {
        int result = isPrimeNumber(w);
        if (result)
        {
            for (d = 2; d < fai_n; d++)
            {
                result = isPrimeNumber(w);
                if (result) {
                    myInt64 m = w * d;
                    if ((d != w) && (m % fai_n == 1))
                    {
                        g_d = d;
                        g_w = w;
                        return TRUE;
                    }
                }
            }
        }
    }
    return FALSE;
}
 
//g_w is used to encrypt and g_d used to decrypt,and g_w must be primer to fai(n)
int rsa_encrypt(char* data, int size, char* dst) {
    if (g_n == 0 || g_w == 0 || g_d == 0)
    {
        return FALSE;
    }
    int block_cnt = size / g_blocksize_src;
    int mod = size % g_blocksize_src;
 
    unsigned char* s = (unsigned char*)data;
    myInt64* d = (myInt64*)dst;
    for (int i = block_cnt; i > 0; i--)
    {
        myInt64 tmp = 0;
        if (g_blocksize == 8)
        {
            tmp = *s;
            tmp = (tmp & 0xffffffffffffffff);
            tmp = (pow_i_old(tmp, g_w, g_n));
            *d = tmp;
        }
        else if (g_blocksize == 4)
        {
            tmp = *s;
            tmp = tmp & 0xffffffff;
            tmp = (pow_i_old(tmp, g_w, g_n));
            *(DWORD*)d = *(DWORD*)&tmp;
        }
        else if (g_blocksize == 2)
        {
            tmp = *s;
            tmp = tmp & 0xffff;
            tmp = (pow_i_old(tmp, g_w, g_n));
            *(WORD*)d = *(WORD*)&tmp;
        }
        else if (g_blocksize == 1)
        {
            tmp = *(unsigned char*)s;
            tmp = (tmp & 0xff);
            tmp = (pow_i_old(tmp, g_w, g_n));
            *(unsigned char*)d = *(unsigned char*)&tmp;
        }
 
        s = (unsigned char*)((unsigned char*)s + g_blocksize_src);
        d = (myInt64*)((unsigned char*)d + g_blocksize);
    }
 
    if (mod)
    {
        myInt64 tmp = 0;
        memcpy(&tmp, s, mod);
        if (g_blocksize_src == 8)
        {
            tmp = tmp & 0xffffffffffffffff;
        }
        else if (g_blocksize_src == 4)
        {
            tmp = tmp & 0xffffffff;
        }
        else if (g_blocksize_src == 2)
        {
            tmp = tmp & 0xffff;
        }
        else if (g_blocksize_src == 1)
        {
            tmp = tmp & 0xff;
        }
        tmp = pow_i_old(tmp, g_w, g_n);
        memcpy(d, &tmp, mod);
    }
    return size;
}
 
int rsa_decrypt(char* data, int size, char* dst) {
    if (g_n == 0 || g_w == 0 || g_d == 0)
    {
        return FALSE;
    }
    int block_cnt = size / g_blocksize_src;
    int mod = size % g_blocksize_src;
 
    myInt64* s = (myInt64*)data;
    unsigned char* d = (unsigned char*)dst;
    for (int i = block_cnt; i > 0; i--)
    {
        myInt64 tmp = 0;
        if (g_blocksize == 8)
        {
            tmp = *s;
            tmp = (tmp & 0xffffffffffffffff);
            tmp = (pow_i_old(tmp, g_d, g_n));
            *d = (unsigned char)tmp;
        }
        else if (g_blocksize == 4)
        {
            tmp = *(DWORD*)s;
            tmp = tmp & 0xffffffff;
            tmp = (pow_i_old(tmp, g_d, g_n));
            *d = (unsigned char)tmp;
        }
        else if (g_blocksize == 2)
        {
            tmp = *(WORD*)s;
            tmp = tmp & 0xffff;
            tmp = (pow_i_old(tmp, g_d, g_n));
            *d = (unsigned char)tmp;
        }
        else if (g_blocksize == 1)
        {
            tmp = *(unsigned char*)s;
            tmp = (tmp & 0xff);
            tmp = (pow_i_old(tmp, g_d, g_n));
            *d = (unsigned char)tmp;
        }
        s = (myInt64*)((unsigned char*)s + g_blocksize);
        d = (unsigned char*)((unsigned char*)d + g_blocksize_src);
    }
 
    if (mod)
    {
        myInt64 tmp = 0;
        memcpy(&tmp, s, mod);
        if (g_blocksize == 8)
        {
            tmp = tmp & 0xffffffffffffffff;
        }
        else if (g_blocksize == 4)
        {
            tmp = tmp & 0xffffffff;
        }
        else if (g_blocksize == 2)
        {
            tmp = tmp & 0xffff;
        }
        else if (g_blocksize == 1)
        {
            tmp = tmp & 0xff;
        }
        tmp = pow_i_old(tmp, g_d, g_n);
        memcpy(d, &tmp, mod);
    }
    return size;
}

头文件:

1
2
3
4
5
6
7
8
9
10
11
#pragma once
 
#define  myInt64 unsigned long long
 
myInt64 pow_i(myInt64 a, myInt64 b);
 
int rsaInit(myInt64 p, myInt64 q);
 
int rsa_encrypt(char* data, int size, char* dst);
 
int rsa_decrypt(char* data, int size, char* dst);

调用方式是在main函数中执行那个如下代码,main函数就先省略了:)

1
2
3
4
5
6
7
rsaInit(11, 23);
const char* myteststr = "Hello!\r\n Hi! \r\nHow are you ?\r\n Fine,thank you, and you ? \r\nI am fine, too!\r\n";
int teststrlen = lstrlenA(myteststr);
char dst0[1024];
rsa_encrypt((char*)myteststr, teststrlen + 1, dst0);
char dst1[1024];
rsa_decrypt((char*)dst0, teststrlen + 1, dst1);

问题和注意事项:

1.pow_i函数中为什么要取余数?为了防止溢出?数学知识不扎实。

2.加密之前与解密之后的bit位数应该长度相同,加密之后的bit数与解密之前的bit位长度应该相同。


[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》,视频+靶场+题目!助力进入CTF世界

最后于 2024-2-2 09:59 被satadrover编辑 ,原因:
收藏
点赞4
打赏
分享
最新回复 (11)
雪    币: 17901
活跃值: (25552)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
秋狝 2023-4-18 09:12
2
1
感谢分享
雪    币: 11816
活跃值: (15010)
能力值: ( LV12,RANK:240 )
在线值:
发帖
回帖
粉丝
pureGavin 2 2023-4-18 09:31
3
0
感谢分享
雪    币: 555
活跃值: (142)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
Conney 2023-4-19 00:22
4
0
请问楼主有用过Python实现吗?
雪    币: 555
活跃值: (142)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
Conney 2023-4-19 00:23
5
0
Conney 请问楼主有用过Python实现吗?
我在用Python3实现rsa解密的时候遇到些问题,在此真诚请教楼主
雪    币: 2418
活跃值: (2853)
能力值: ( LV5,RANK:70 )
在线值:
发帖
回帖
粉丝
satadrover 2023-4-19 18:10
6
0
Conney 我在用Python3实现rsa解密的时候遇到些问题,在此真诚请教楼主
python不熟悉呀
雪    币: 10845
活跃值: (1018)
能力值: (RANK:190 )
在线值:
发帖
回帖
粉丝
看场雪 3 2024-2-1 12:31
7
0
是一个好的入门帖
雪    币: 2418
活跃值: (2853)
能力值: ( LV5,RANK:70 )
在线值:
发帖
回帖
粉丝
satadrover 2024-2-2 09:52
8
0
看场雪 是一个好的入门帖[em_63]
谢谢版主大人夸奖,懂一点点,还差得远呢
雪    币: 2
能力值: ( LV1,RANK:0 )
在线值:
发帖
回帖
粉丝
pingbo 2024-2-2 15:21
9
0
RSA已经被人废了,别用了;
雪    币: 2418
活跃值: (2853)
能力值: ( LV5,RANK:70 )
在线值:
发帖
回帖
粉丝
satadrover 2024-2-3 15:48
10
0
pingbo RSA已经被人废了,别用了;
我觉得,rsa算法本身没有问题,有问题的是对其安全标准的遵守。
雪    币: 92
能力值: ( LV1,RANK:0 )
在线值:
发帖
回帖
粉丝
史D芬周 2024-2-15 13:13
11
0
为什么中文和英文数字加密会失效,可是查看内存,可以正常解密英文数字,中文就失败
雪    币: 2418
活跃值: (2853)
能力值: ( LV5,RANK:70 )
在线值:
发帖
回帖
粉丝
satadrover 2024-2-17 11:59
12
0
史D芬周 为什么中文和英文数字加密会失效,可是查看内存,可以正常解密英文数字,中文就失败
使用大一点的素数,例子里的素数比较小
游客
登录 | 注册 方可回帖
返回