最近学习了一下RSA加密算法:)

chai2010

1. 
   
2. 
   
3. // RSA加密系统:
   
4. // 1. 随机选取2个大的素数p和q
   
5. // 2. 根据n=p*q式计算出n的值
   
6. // 3. 选取一个与f(n)互素的小奇数e. 其中f(n)为欧拉装载函数, 值为(p-1)(q-1)
   
7. // 4. 对于模f(n), 计算e的乘法逆元d
   
8. // 5. 公开对P=(e,n), 并把它作为RSA公开秘钥
   
9. // 6. 把对S=(d,n)进行保密, 并把它作为RSA的机密秘钥
   
10. 
    
11. // 加密过程: C = (M^e)%n
    
12. // 解秘过程: M = (C^d)%n
    
13. 
    
14. 
    
15. #include <stdio.h>
    
16. #include <assert.h>
    
17. #include <stdlib.h>
    
18. #include <time.h>
    
19. 
    
20. // 返回一个位于low和high之间的随机数
    
21. 
    
22. #define ran(low,high) ((rand()%((high)-(low)+1))+(low))
    
23. 
    
24. // 计算数组的元素个数
    
25. 
    
26. #define NELEMS(x) ((sizeof(x)) / (sizeof((x)[0])))
    
27. 
    
28. // 构造素数序列primes[]
    
29. 
    
30. void makePrimes(int primes[], int num)
    
31. {
    
32.     primes[0] = 2;
    
33.    
    
34.     for(int p = 3, cnt = 1; cnt < num; p += 2)
    
35.     {
    
36.         for(int k = 0; ; ++k)
    
37.         {
    
38.             // 可以在div时得到余数
    
39.             div_t dt = div(p, primes[k]);
    
40. 
    
41.             if(dt.rem == 0) break;
    
42.             if(dt.quot <= primes[k]) { primes[cnt++] = p; break; }
    
43.         }
    
44.     }
    
45. }
    
46. 
    
47. // 返回2个随机素数, 在10000~40000之间
    
48. 
    
49. void rand_pq(int& p, int& q)
    
50. {
    
51.     // [2, 2^16]范围内有6542个素数
    
52.    
    
53.     static int primes[1024*8];
    
54.     static int low, high;
    
55.    
    
56.     // 初始化(只处理一次)
    
57.    
    
58.     if(low == 0 && high == 0)
    
59.     {
    
60.         // 生成素数序列
    
61.         
    
62.         makePrimes(primes, NELEMS(primes));
    
63.         
    
64.         // 计算10000和40000附近的素数下标
    
65.         
    
66.         for(int i = 0; i < NELEMS(primes); ++i)
    
67.         {
    
68.             if(!low && primes[i] > 10000) { low = i; continue; }
    
69.             if(!high && primes[i] > 40000) { high = i; break; }
    
70.         }
    
71.         
    
72.         // 设置随机数种子
    
73.         
    
74.         srand(time(NULL));
    
75.     }
    
76.    
    
77.     // 在low, high之间返回2个不同的随机数
    
78.    
    
79.     int r1 = ran(low,high);
    
80.     int r2 = ran(low,high);
    
81.    
    
82.     // r1和r2不能相等
    
83.    
    
84.     while(r2 == r1) r2 = ran(low,high);
    
85.    
    
86.     // 返回r1,r2位置对应的素数
    
87.    
    
88.     p = primes[r1];
    
89.     q = primes[r2];
    
90. }
    
91. 
    
92. // 扩展的欧几里得算法
    
93. 
    
94. int xgcd(int a, int b, int& x, int& y)
    
95. {
    
96.     if(b == 0) { x = 1, y = 0; return a; }
    
97.    
    
98.     int d = xgcd(b, a%b, x, y);
    
99.     int t = x-(a/b)*y; x = y; y = t;
    
100.    
     
101.     return d;
     
102. }
     
103. 
     
104. // 针对(p-1)(q-1)产生e和d
     
105. 
     
106. void rand_ed(int p, int q, int& e, int &d)
     
107. {
     
108.     int n = (p-1)*(q-1);
     
109.     int x, y;
     
110.    
     
111.     // 选择一个小的互素奇数e
     
112.    
     
113.     for(e = 37; ; e += 2)
     
114.     {
     
115.         if(xgcd(e, n, x, y) == 1) break;
     
116.     }
     
117.    
     
118.     // 将d转换到[0, n-1]之间
     
119.    
     
120.     while(x > 0) x -= n;
     
121.     while(x < 0) x += n;
     
122.    
     
123.     d = x;
     
124. }
     
125. 
     
126. // 计算(u*v)%m
     
127. 
     
128. unsigned mul_mod(unsigned u, unsigned v, unsigned z)
     
129. {
     
130.     // 如果u*v没有溢出, 则直接计算
     
131. 
     
132.     if((u*v)/u == v) return (u*v)%z;
     
133. 
     
134.     // 进行长乘法(结果为64位)
     
135. 
     
136.     unsigned u0, v0, w0;
     
137.     unsigned u1, v1, w1, w2, t;
     
138. 
     
139.     u0 = u & 0xFFFF;  u1 = u >> 16;
     
140.     v0 = v & 0xFFFF;  v1 = v >> 16;
     
141.     w0 = u0*v0;
     
142.     t  = u1*v0 + (w0 >> 16);
     
143.     w1 = t & 0xFFFF;
     
144.     w2 = t >> 16;
     
145.     w1 = u0*v1 + w1;
     
146. 
     
147.     // x为高32位, y为低32位
     
148. 
     
149.     unsigned x = u1*v1 + w2 + (w1 >> 16);
     
150.     unsigned y = u*v;
     
151. 
     
152.     // 进行长除法(被除数为64位)
     
153. 
     
154.     for (int i = 1; i <= 32; i++)
     
155.     {
     
156.         t = (int)x >> 31;           // All 1's if x(31) = 1.
     
157. 
     
158.         x = (x << 1) | (y >> 31);   // Shift x || y left
     
159.         y <<= 1;                    // one bit.
     
160.         
     
161.         if((x|t) >= z) { x -= z; y++; }
     
162.     }
     
163. 
     
164.     return x;    // y为商, x为余数
     
165. }
     
166. 
     
167. // 计算(a^p)%n
     
168. 
     
169. unsigned pow_mod(unsigned a, unsigned p, unsigned n)
     
170. {
     
171.     unsigned k = 1;
     
172.    
     
173.     // 反复平方法
     
174.    
     
175.     while(p > 1)
     
176.     {
     
177.         if(p&1) k = mul_mod(k, a, n);
     
178.         a = mul_mod(a, a, n); p >>= 1;
     
179.     }
     
180.    
     
181.     return mul_mod(k, a, n);
     
182. }
     
183. 
     
184. // 产生RSA需要的所有参数
     
185. 
     
186. void rsa_rand(int& e, int& d, int& n)
     
187. {
     
188.     int p, q;
     
189.    
     
190.     rand_pq(p, q);
     
191.     rand_ed(p, q, e, d);
     
192.     n = p*q;
     
193. }
     
194. 
     
195. // 加密和解密的过程
     
196. 
     
197. int rsa_encryp(int m, int ed, int n)
     
198. {
     
199.     assert(m > 0 && m < n);
     
200.     return pow_mod(m, ed, n);
     
201. }
     
202. 
     
203. // RSA加密测试
     
204. 
     
205. int main(void)
     
206. {
     
207.     int e, d, n;
     
208.     int m = 119; // 需要加密的数据
     
209. 
     
210.     printf("RSA加密系统.\n\n");
     
211. 
     
212.     // 产生秘钥
     
213. 
     
214.     rsa_rand(e, d, n);
     
215.     printf("秘钥: e = %d, d = %d, n = %d\n\n", e, d, n);
     
216. 
     
217.     while(1)
     
218.     {
     
219.         printf("\n输入数据M(0<M<n): ");
     
220.         if(scanf("%d", &m) != 1) break;
     
221.         if(m <= 0 || m >= n) break;
     
222. 
     
223.         // 加密前数据
     
224. 
     
225.         printf("加密前: %d\n", m);
     
226. 
     
227.         // 加密文件, 秘钥为(e, n)
     
228. 
     
229.         printf("加密后: %d\n", m = rsa_encryp(m, e, n));
     
230. 
     
231.         // 解密文件, 秘钥为(d, n)
     
232. 
     
233.         printf("解密后: %d\n", m = rsa_encryp(m, d, n));
     
234.     }
     
235. 
     
236.     return 0;
     
237. }
     

复制代码

chai2010

关于学习RSA的几点体会：

1. 该实现的RSA密码强度很低, 可能仅满足于学习需要.

   具体地n = p*q, n为32位int类型数据, 则p/q中必然
   有一个值小于等于sqrt(n) <= sqrt(2^32) == 2^16.
   而[0,2^16]范围内只有6542个素数, 因此因式分解n的
   难度很低.

2. 实际产生大的随机素数时, 一般采用费马小定理.

   费马定理只是一种概率测试. 由于这里涉及的素数范围
   很小, 因此直接从素数表中随机选取. 素数表的构造过
   程很有意思, makePrimes从第一个素数2开始, 根据已知
   的素数逐步扩充未知的素数.

3. 关于GCD

   这里采用了扩展的GCD算法, 为的是得到下面的等式:
   x*a + y*b == gcd(a,b).
   根据x可以得到模线形方程a*x=1(mod b)的解.
   GCD还有一种二进制的实现, 这里采用的是Euclid给的
   算法.

   观察代码可以发现, a/b和x/y参数的传递方向是相反:
   a/b在进栈的时候向栈内传递信息; x/y则是在出栈的
   时候从栈底向外传递信息.

4. 关于与(p-1)*(q-1)互素的小奇数e.

   满足e的条件的基数很多, 但是具体取哪个呢? 最小的
   是否可以?

   个人觉得e的值最好不要小于log2(n). 因为如果e的值
   太小, 比如为3, 那么当m^3也小于n时就相当于没有加密
   了. 针对这里n为int型数据的话, e大于32应该就可以了.

5. m为1和n-1时.

   m为1的话, 加密解密都是1, 因为1的x次幂依然为1.
   m为n-1, 测试了一些数据, 加密后的值依然为n-1,
   我想应该可以从数论角度给出证明, 数学比较强的朋友
   可以尝试证明一下.

6. m < 0 or m >= n

   因为RSA需要用模n运算, 因此如果m超出n范围的话, 解密
   肯定会出现错误. 最好回避.

7. m为0

   这个情况也比较特殊, 回避.

8. (a^p)%n运算

   由于a^p结果可能溢出, 因此采用了长乘法(乘积为64位数).

9. 函数f(a) = (a^p)%n的循环周期

   由于函数f的值域固定(0,n-1), 因此这个函数必然有循环周期.
   大家有感兴趣可以自己测试一下循环周期.