信息计算2019级1班7号徐佳颖

徐佳颖

RSA加密解密及数字签名

一、RSA简介

     RSA是目前应用最广泛地一种非对称秘码体制。它的安全性基于大整数的因式分解问题。RSA是由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）在1977年一起提出的.PSA对极大整数做因数分解的难度决定了 RSA 算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用 RSA 加密的信息的可靠性就会极度下降。

二、算法实现（C#）

1. using System;
   
2. using System.Security.Cryptography;
   
3. using System.Text;
   
4. 
   
5. namespace RSACryption
   
6. {
   
7.     class RSACSPSample
   
8.     {
   
9.         static void Main()
   
10.         {
    
11.             try
    
12.             {
    
13. 
    
14.                 string str_DataToSign = @"Data to Sign!Data to Sign!Data to Sign!";
    
15.                 Console.WriteLine("原文：" + str_DataToSign);
    
16.                 Console.WriteLine("长度：" + str_DataToSign.Length.ToString());
    
17.                 Console.WriteLine();
    
18. 
    
19.                 RSACryptoServiceProvider RSAalg = new RSACryptoServiceProvider();
    
20. 
    
21.                 string str_Private_Key = Convert.ToBase64String(RSAalg.ExportCspBlob(true));
    
22.                 string str_Public_Key = Convert.ToBase64String(RSAalg.ExportCspBlob(false));
    
23.                 Console.WriteLine("公钥：" + str_Public_Key);
    
24.                 Console.WriteLine();
    
25.                 Console.WriteLine("私钥：" + str_Private_Key);
    
26.                 Console.WriteLine();
    
27. 
    
28.                 string str_SignedData = HashAndSign(str_DataToSign, str_Private_Key);// Hash and sign the data.
    
29.                 Console.WriteLine("签名数据：" + str_SignedData);
    
30.                 Console.WriteLine();
    
31. 
    
32.                 if (VerifySignedHash(str_DataToSign, str_SignedData, str_Public_Key))
    
33.                 {
    
34.                     Console.WriteLine("验证签名OK.");
    
35.                 }
    
36.                 else
    
37.                 {
    
38.                     Console.WriteLine("签名不匹配!");
    
39.                 }
    
40.                 Console.WriteLine();
    
41. 
    
42.             }
    
43.             catch (ArgumentNullException)
    
44.             {
    
45.                 Console.WriteLine("The data was not signed or verified");
    
46. 
    
47.             }
    
48.         }
    
49. 
    
50.         //对数据签名
    
51.         public static string HashAndSign(string str_DataToSign, string str_Private_Key)
    
52.         {
    
53.             ASCIIEncoding ByteConverter = new ASCIIEncoding();
    
54.             byte[] DataToSign = ByteConverter.GetBytes(str_DataToSign);
    
55.             try
    
56.             {
    
57.                 RSACryptoServiceProvider RSAalg = new RSACryptoServiceProvider();
    
58.                 RSAalg.ImportCspBlob(Convert.FromBase64String(str_Private_Key));
    
59.                 byte[] signedData = RSAalg.SignData(DataToSign, new SHA1CryptoServiceProvider());
    
60.                 string str_SignedData = Convert.ToBase64String(signedData);
    
61.                 return str_SignedData;
    
62.             }
    
63.             catch (CryptographicException e)
    
64.             {
    
65.                 Console.WriteLine(e.Message);
    
66.                 return null;
    
67.             }
    
68.         }
    
69. 
    
70.         //验证签名
    
71.         public static bool VerifySignedHash(string str_DataToVerify, string str_SignedData, string str_Public_Key)
    
72.         {
    
73.             byte[] SignedData = Convert.FromBase64String(str_SignedData);
    
74. 
    
75.             ASCIIEncoding ByteConverter = new ASCIIEncoding();
    
76.             byte[] DataToVerify = ByteConverter.GetBytes(str_DataToVerify);
    
77.             try
    
78.             {
    
79.                 RSACryptoServiceProvider RSAalg = new RSACryptoServiceProvider();
    
80.                 RSAalg.ImportCspBlob(Convert.FromBase64String(str_Public_Key));
    
81. 
    
82.                 return RSAalg.VerifyData(DataToVerify, new SHA1CryptoServiceProvider(), SignedData);
    
83. 
    
84.             }
    
85.             catch (CryptographicException e)
    
86.             {
    
87.                 Console.WriteLine(e.Message);
    
88. 
    
89.                 return false;
    
90.             }
    
91.         }
    
92.     }
    
93. 
    
94. }
    

复制代码

三、运行截图

徐佳颖

椭圆曲线加密算法（ECC）

一、ECC简介        椭圆曲线加密算法，简称ECC，是基于椭圆曲线数学理论实现的一种非对称加密算法。相比RSA，ECC优势是可以使用更短的密钥，来实现与RSA相当或更高的安全，RSA加密算法也是一种非对称加密算法，在公开密钥加密和电子商业中RSA被广泛使用。


二、算法实现（C）

1. /*
   
2. (1)编程计算该椭圆曲线上所有在有限域GF(89)上的点；
   
3. (2)编程实现椭圆曲线上任意一个点P(例如P=(12,5))的倍点运算的递归算法，即计算k*P( k=2,3,…)；（重点！）
   
4. (3)利用此递归算法找出椭圆曲线上的所有生成元G以及它们的阶n，即满足n*G=O；
   
5. (4)设计实现某一用户B的公钥、私钥算法，即得到public key=(n, G, PB, Ep(a, b))
   
6. secure key=nB(小于n)
   
7. (5)假如用户A发送明文消息“yes”并加密传输给用户B，用户B接收消息后要能解密为明文。试用ECC密码体制实现此功能。
   
8. */
   
9. 
   
10. 
    
11. #include<stdio.h>
    
12. #include<stdlib.h>
    
13. #include<string.h>
    
14. #include<math.h>
    
15. #include<time.h>
    
16. #define MAX 100
    
17. 
    
18. typedef struct point {
    
19.         int point_x;
    
20.         int point_y;
    
21. }Point;
    
22. typedef struct ecc {
    
23.         struct point p[MAX];
    
24.         int len;
    
25. }ECCPoint;
    
26. typedef struct generator {
    
27.         Point p;
    
28.         int p_class;
    
29. }GENE_SET;
    
30. 
    
31. void get_all_points();
    
32. int int_sqrt(int s);
    
33. Point timesPiont(int k, Point p);
    
34. Point add_two_points(Point p1, Point p2);
    
35. int inverse(int n, int b);
    
36. void get_generetor_class();
    
37. void encrypt_ecc();
    
38. void decrypt_ecc();
    
39. int mod_p(int s);
    
40. void print();
    
41. int isPrime(int n);
    
42. 
    
43. char alphabet[26] = "abcdefghijklmnopqrstuvwxy";
    
44. int a = -1, b = 0, p = 89;//椭圆曲线为E89(-1,0)： y2=x3-x (mod 89)
    
45. ECCPoint eccPoint;
    
46. GENE_SET geneSet[MAX];
    
47. int geneLen;
    
48. char plain[] = "yes";
    
49. int m[MAX];
    
50. int cipher[MAX];
    
51. int nB;//私钥
    
52. Point P1, P2, Pt, G, PB;
    
53. Point Pm;
    
54. int C[MAX];
    
55. 
    
56. int main()
    
57. {
    
58.         get_generetor_class();
    
59.         encrypt_ecc();
    
60.         decrypt_ecc();
    
61.         return 0;
    
62. }
    
63. //task4:加密
    
64. void encrypt_ecc()
    
65. {
    
66.         int num, i, j;
    
67.         int gene_class;
    
68.         int num_t;
    
69.         int k;
    
70.         srand(time(NULL));
    
71.         //明文转换过程
    
72.         for (i = 0; i < strlen(plain); i++)
    
73.         {
    
74.                 for (j = 0; j < 26; j++) //for(j=0;j<26;j++)
    
75.                 {
    
76.                         if (plain[i] == alphabet[j])
    
77.                         {
    
78.                                 m[i] = j;//将字符串明文换成数字，并存到整型数组m里面
    
79.                         }
    
80.                 }
    
81.         }
    
82.         //选择生成元
    
83.         num = rand() % geneLen;
    
84.         gene_class = geneSet[num].p_class;
    
85.         while (isPrime(gene_class) == -1)//不是素数
    
86.         {
    
87.                 num = rand() % (geneLen - 3) + 3;
    
88.                 gene_class = geneSet[num].p_class;
    
89.         }
    
90.         //printf("gene_class=%d\n",gene_class);
    
91.         G = geneSet[num].p;
    
92.         //printf("G:(%d,%d)\n",geneSet[num].p.point_x,geneSet[num].p.point_y);
    
93.         nB = rand() % (gene_class - 1) + 1;//选择私钥
    
94.         PB = timesPiont(nB, G);
    
95.         printf("\n公钥：\n");
    
96.         printf("{y^2=x^3%d*x+%d,%d,(%d,%d),(%d,%d)}\n", a, b, gene_class, G.point_x, G.point_y, PB.point_x, PB.point_y);
    
97.         printf("私钥：\n");
    
98.         printf("nB=%d\n", nB);
    
99.         //加密
    
100.         //
     
101.         k = rand() % (gene_class - 2) + 1;
     
102.         P1 = timesPiont(k, G);
     
103.         //
     
104.         num_t = rand() % eccPoint.len; //选择映射点
     
105.         Pt = eccPoint.p[num_t];
     
106.         //printf("Pt:(%d,%d)\n",Pt.point_x,Pt.point_y);
     
107.         P2 = timesPiont(k, PB);
     
108.         Pm = add_two_points(Pt, P2);
     
109.         printf("加密数据：\n");
     
110.         printf("kG=(%d,%d),Pt+kPB=(%d,%d),C={", P1.point_x, P1.point_y, Pm.point_x, Pm.point_y);
     
111.         for (i = 0; i < strlen(plain); i++)
     
112.         {
     
113.                 //                num_t=rand()%eccPoint.len; //选择映射点
     
114.                 //                Pt=eccPoint.p[num_t];
     
115.                 C[i] = m[i] * Pt.point_x + Pt.point_y;
     
116.                 printf("{%d}", C[i]);
     
117.         }
     
118.         printf("}\n");
     
119. }
     
120. //task5:解密
     
121. void decrypt_ecc()
     
122. {
     
123.         Point temp, temp1;
     
124.         int m, i;
     
125.         temp = timesPiont(nB, P1);
     
126.         temp.point_y = 0 - temp.point_y;
     
127.         temp1 = add_two_points(Pm, temp);//求解Pt
     
128. //        printf("(%d,%d)\n",temp.point_x,temp.point_y);
     
129. //        printf("(%d,%d)\n",temp1.point_x,temp1.point_y);
     
130.         printf("\n解密结果：\n");
     
131.         for (i = 0; i < strlen(plain); i++)
     
132.         {
     
133.                 m = (C[i] - temp1.point_y) / temp1.point_x;
     
134.                 printf("%c", alphabet[m]);//输出密文
     
135.         }
     
136.         printf("\n");
     
137. }
     
138. //判断是否为素数
     
139. int isPrime(int n)
     
140. {
     
141.         int i, k;
     
142.         k = sqrt(n);
     
143.         for (i = 2; i <= k; i++)
     
144.         {
     
145.                 if (n % i == 0)
     
146.                         break;
     
147.         }
     
148.         if (i <= k) {
     
149.                 return -1;
     
150.         }
     
151.         else {
     
152.                 return 0;
     
153.         }
     
154. }
     
155. //task3:求生成元以及阶
     
156. void get_generetor_class()
     
157. {
     
158.         int i, j = 0;
     
159.         int count = 1;
     
160.         Point p1, p2;
     
161.         get_all_points();
     
162.         //        p1.point_x=p2.point_x=3;
     
163.         //        p1.point_y=p2.point_y=2;
     
164.         //        while(1)
     
165.         //        {
     
166.         //                printf("(%d,%d)+(%d,%d)---%d\n",p1.point_x,p1.point_y,p2.point_x,p2.point_y,count);
     
167.         //                p2=add_two_points(p1,p2);
     
168.         //                count++;
     
169.         //                if(p2.point_x==-1 && p2.point_y==-1)
     
170.         //                {
     
171.         //                        break;
     
172.         //                }
     
173.         //        }
     
174.         //        printf("\n\n(%d,%d)---%d\n",p1.point_x,p1.point_y,count);
     
175.                 //
     
176.         //        do{
     
177.         //                        printf("(%d,%d)+(%d,%d)---%d\n",p1.point_x,p1.point_y,p2.point_x,p2.point_y,count);
     
178.         //                        p2=add_two_points(p1,p2);
     
179.         //                        count++;
     
180.         //                       
     
181.         //        } while(!((p2.point_x==p1.point_x)&&(p2.point_y==p1.point_y)));
     
182.         //        printf("(%d,%d)+(%d,%d)---%d\n",p1.point_x,p1.point_y,p2.point_x,p2.point_y,count);
     
183.         //        count ++ ;
     
184.         //        printf("\n\n(%d,%d)---%d\n",p1.point_x,p1.point_y,count);
     
185.         printf("\n**********************************输出生成元以及阶：*************************************\n");
     
186.         for (i = 0; i < eccPoint.len; i++)
     
187.         {
     
188.                 count = 1;
     
189.                 p1.point_x = p2.point_x = eccPoint.p[i].point_x;
     
190.                 p1.point_y = p2.point_y = eccPoint.p[i].point_y;
     
191.                 while (1)
     
192.                 {
     
193.                         p2 = add_two_points(p1, p2);
     
194.                         if (p2.point_x == -1 && p2.point_y == -1)
     
195.                         {
     
196.                                 break;
     
197.                         }
     
198.                         count++;
     
199.                         if (p2.point_x == p1.point_x)
     
200.                         {
     
201.                                 break;
     
202.                         }
     
203.                 }
     
204.                 count++;
     
205.                 if (count <= eccPoint.len + 1)
     
206.                 {
     
207.                         geneSet[j].p.point_x = p1.point_x;
     
208.                         geneSet[j].p.point_y = p1.point_y;
     
209.                         geneSet[j].p_class = count;
     
210.                         printf("(%d,%d)--->>%d\t", geneSet[j].p.point_x, geneSet[j].p.point_y, geneSet[j].p_class);
     
211.                         j++;
     
212.                         if (j % 6 == 0) {
     
213.                                 printf("\n");
     
214.                         }
     
215.                 }
     
216.                 geneLen = j;
     
217.         }
     
218. }
     
219. 
     
220. //task2:倍点运算的递归算法
     
221. Point timesPiont(int k, Point p0)
     
222. {
     
223.         if (k == 1) {
     
224.                 return p0;
     
225.         }
     
226.         else if (k == 2) {
     
227.                 return add_two_points(p0, p0);
     
228.         }
     
229.         else {
     
230.                 return add_two_points(p0, timesPiont(k - 1, p0));
     
231.         }
     
232. }
     
233. 
     
234. //两点的加法运算
     
235. Point add_two_points(Point p1, Point p2)
     
236. {
     
237.         long t;
     
238.         int x1 = p1.point_x;
     
239.         int y1 = p1.point_y;
     
240.         int x2 = p2.point_x;
     
241.         int y2 = p2.point_y;
     
242.         int tx, ty;
     
243.         int x3, y3;
     
244.         int flag = 0;
     
245.         //求
     
246.         if ((x2 == x1) && (y2 == y1))
     
247.         {
     
248.                 //相同点相加
     
249.                 if (y1 == 0)
     
250.                 {
     
251.                         flag = 1;
     
252.                 }
     
253.                 else {
     
254.                         t = (3 * x1 * x1 + a) * inverse(p, 2 * y1) % p;
     
255.                 }
     
256.                 //printf("inverse(p,2*y1)=%d\n",inverse(p,2*y1));
     
257.         }
     
258.         else {
     
259.                 //不同点相加
     
260.                 ty = y2 - y1;
     
261.                 tx = x2 - x1;
     
262.                 while (ty < 0)
     
263.                 {
     
264.                         ty += p;
     
265.                 }
     
266.                 while (tx < 0)
     
267.                 {
     
268.                         tx += p;
     
269.                 }
     
270.                 if (tx == 0 && ty != 0)
     
271.                 {
     
272.                         flag = 1;
     
273.                 }
     
274.                 else {
     
275.                         t = ty * inverse(p, tx) % p;
     
276.                 }
     
277.         }
     
278.         if (flag == 1)
     
279.         {
     
280.                 p2.point_x = -1;
     
281.                 p2.point_y = -1;
     
282.         }
     
283.         else {
     
284.                 x3 = (t * t - x1 - x2) % p;
     
285.                 y3 = (t * (x1 - x3) - y1) % p;
     
286.                 //使结果在有限域GF(P)上
     
287.                 while (x3 < 0)
     
288.                 {
     
289.                         x3 += p;
     
290.                 }
     
291.                 while (y3 < 0)
     
292.                 {
     
293.                         y3 += p;
     
294.                 }
     
295.                 p2.point_x = x3;
     
296.                 p2.point_y = y3;
     
297.         }
     
298.         return p2;
     
299. }
     
300. //求b关于n的逆元
     
301. int inverse(int n, int b)
     
302. {
     
303.         int q, r, r1 = n, r2 = b, t, t1 = 0, t2 = 1, i = 1;
     
304.         while (r2 > 0)
     
305.         {
     
306.                 q = r1 / r2;
     
307.                 r = r1 % r2;
     
308.                 r1 = r2;
     
309.                 r2 = r;
     
310.                 t = t1 - q * t2;
     
311.                 t1 = t2;
     
312.                 t2 = t;
     
313.         }
     
314.         if (t1 >= 0)
     
315.                 return t1 % n;
     
316.         else {
     
317.                 while ((t1 + i * n) < 0)
     
318.                         i++;
     
319.                 return t1 + i * n;
     
320.         }
     
321. }
     
322. //task1:求出椭圆曲线上所有点
     
323. void get_all_points()
     
324. {
     
325.         int i = 0;
     
326.         int j = 0;
     
327.         int s, y = 0;
     
328.         int n = 0, q = 0;
     
329.         int modsqrt = 0;
     
330.         int flag = 0;
     
331.         if (4 * a * a * a + 27 * b * b != 0)
     
332.         {
     
333.                 for (i = 0; i <= p - 1; i++)
     
334.                 {
     
335.                         flag = 0;
     
336.                         n = 1;
     
337.                         y = 0;
     
338.                         s = i * i * i + a * i + b;
     
339.                         while (s < 0)
     
340.                         {
     
341.                                 s += p;
     
342.                         }
     
343.                         s = mod_p(s);
     
344.                         modsqrt = int_sqrt(s);
     
345.                         if (modsqrt != -1)
     
346.                         {
     
347.                                 flag = 1;
     
348.                                 y = modsqrt;
     
349.                         }
     
350.                         else {
     
351.                                 while (n <= p - 1)
     
352.                                 {
     
353.                                         q = s + n * p;
     
354.                                         modsqrt = int_sqrt(q);
     
355.                                         if (modsqrt != -1)
     
356.                                         {
     
357.                                                 y = modsqrt;
     
358.                                                 flag = 1;
     
359.                                                 break;
     
360.                                         }
     
361.                                         flag = 0;
     
362.                                         n++;
     
363.                                 }
     
364.                         }
     
365.                         if (flag == 1)
     
366.                         {
     
367.                                 eccPoint.p[j].point_x = i;
     
368.                                 eccPoint.p[j].point_y = y;
     
369.                                 j++;
     
370.                                 if (y != 0)
     
371.                                 {
     
372.                                         eccPoint.p[j].point_x = i;
     
373.                                         eccPoint.p[j].point_y = (p - y) % p;
     
374.                                         j++;
     
375.                                 }
     
376.                         }
     
377.                 }
     
378.                 eccPoint.len = j;//点集个数
     
379.                 print(); //打印点集
     
380.         }
     
381. }
     
382. 
     
383. //取模函数
     
384. int mod_p(int s)
     
385. {
     
386.         int i;        //保存s/p的倍数
     
387.         int result;        //模运算的结果
     
388.         i = s / p;
     
389.         result = s - i * p;
     
390.         if (result >= 0)
     
391.         {
     
392.                 return result;
     
393.         }
     
394.         else
     
395.         {
     
396.                 return result + p;
     
397.         }
     
398. }
     
399. 
     
400. //判断平方根是否为整数
     
401. int int_sqrt(int s)
     
402. {
     
403.         int temp;
     
404.         temp = (int)sqrt(s);//转为整型
     
405.         if (temp * temp == s)
     
406.         {
     
407.                 return temp;
     
408.         }
     
409.         else {
     
410.                 return -1;
     
411.         }
     
412. }
     
413. //打印点集
     
414. void print()
     
415. {
     
416.         int i;
     
417.         int len = eccPoint.len;
     
418.         printf("\n该椭圆曲线上共有%d个点(包含无穷远点)\n", len + 1);
     
419.         for (i = 0; i < len; i++)
     
420.         {
     
421.                 if (i % 8 == 0)
     
422.                 {
     
423.                         printf("\n");
     
424.                 }
     
425.                 printf("(%2d,%2d)\t", eccPoint.p[i].point_x, eccPoint.p[i].point_y);
     
426.         }
     
427.         printf("\n");
     
428. }

复制代码

三、运行截图