信息计算2019级1班3号刘丹丹

2019-1刘丹丹

                                                                                                            ECC-椭圆曲线加密算法一.简介：
椭圆加密算法（ECC）是一种公钥加密体制，最初由Koblitz和Miller两人于1985年提出，其数学基础是利用椭圆曲线上的有理点构成Abel加法群上椭圆离散对数的计算困难性。公钥密码体制根据其所依据的难题一般分为三类：大素数分解问题类、离散对数问题类、椭圆曲线类。有时也把椭圆曲线类归为离散对数类。
ECC的主要优势是在某些情况下它比其他的方法使用更小的密钥——比如RSA加密算法——提供相当的或更高等级的安全。ECC的另一个优势是可以定义群之间的双线性映射，基于Weil对或是Tate对；双线性映射已经在密码学中发现了大量的应用，例如基于身份的加密。不过一个缺点是加密和解密操作的实现比其他机制花费的时间长。

二.基本原理：
设私钥、公钥分别为d、Q，即Q = dG，其中G为基点，椭圆曲线上的已知G和dG，求d是非常困难的，也就是说已知公钥和基点，想要算出私钥是非常困难的。
公钥加密：选择随机数r，将消息M生成密文C，该密文是一个点对，C = {rG, M+rQ}，其中Q为公钥。
私钥解密：M + rQ - d(rG) = M + r(dG) - d(rG) = M，其中d、Q分别为私钥、公钥。

椭圆曲线签名算法(ECDSA)。设私钥、公钥分别为d、Q，即Q = dG，其中G为基点。
私钥签名
选择随机数r，计算点rG(x, y)。
根据随机数r、消息M的哈希h、私钥d，计算s = (h + dx)/r。　　
将消息M、和签名{rG, s}发给接收方。


公钥验证签名：
接收方收到消息M、以及签名{rG=(x,y), s}。　　
根据消息求哈希h。　　
使用发送方公钥Q计算：hG/s + xQ/s，并与rG比较，如相等即验签成功。
原理：hG/s + xQ/s = hG/s + x(dG)/s = (h+xd)G/s = r(h+xd)G / (h+dx) = rG


三.运用的数学知识：
1.阿贝尔群     2.椭圆曲线的加法     3.椭圆曲线的二倍运算     4.同余运算     5.有限域        6.乘法逆元

2019-1刘丹丹

四.代码

1. # include <stdio.h>
   
2. # include <math.h>
   
3. using System.Drawing;
   
4. 
   
5. int xy[22];
   
6. 
   
7. #define N 23
   
8. #define A 1
   
9. #define M 29
   
10. #define a1 1
    
11. #define b1 4
    
12. typedef struct point
    
13. {
    
14.         int x;
    
15.         int y;
    
16. }
    
17. Point;
    
18. typedef struct ecc
    
19. {
    
20.         struct point p[100];
    
21.         int len;
    
22. }
    
23. ECCPoint;
    
24. typedef struct generator
    
25. {
    
26.         Point p;
    
27.         int p_class;
    
28. }
    
29. GENE_SET;
    
30. ECCPoint eccPoint;
    
31. Point mul(Point p1, Point p2);
    
32. Point add_two_points(Point p1, Point p2);
    
33. GENE_SET geneSet[100];
    
34. int geneLen;
    
35. //判断平方根是否为整数
    
36. int int_sqrt(int s)
    
37. {
    
38.         int temp;
    
39.         temp = (int)sqrt(s);//转为整型
    
40.         if (temp * temp == s)
    
41.         {
    
42.                 return temp;
    
43.         }
    
44.         else
    
45.         {
    
46.                 return -1;
    
47.         }
    
48. }
    
49. //取模函数
    
50. int mod_p(int s)
    
51. {
    
52.         int i;  //保存s/p的倍数
    
53.         int result; //模运算的结果
    
54.         i = s / N;
    
55.         result = s - i * N;
    
56.         if (result >= 0)
    
57.         {
    
58.                 return result;
    
59.         }
    
60.         else
    
61.         {
    
62.                 return result + N;
    
63.         }
    
64. }
    
65. //打印点集
    
66. void print()
    
67. {
    
68.         int i;
    
69.         int len = eccPoint.len;
    
70.         printf("\n该椭圆曲线上共有%d个点(包含无穷远点)\n", len + 1);
    
71.         for (i = 0; i < len; i++)
    
72.         {
    
73.                 if (i % 8 == 0)
    
74.                 {
    
75.                         printf("\n");
    
76.                 }
    
77.                 printf("(%2d,%2d)\t", eccPoint.p[i].x, eccPoint.p[i].y);
    
78.         }
    
79.         printf("\n");
    
80. }
    
81. //task1:求出椭圆曲线上所有点
    
82. void get_all_points()
    
83. {
    
84.         int i = 0;
    
85.         int j = 0;
    
86.         int s, y = 0;
    
87.         int n = 0, q = 0;
    
88.         int modsqrt = 0;
    
89.         int flag = 0;
    
90.         if (a1 * a1 * a1 + b1 * b1 + 4 != 0)
    
91.         {
    
92.                 for (i = 0; i <= N - 1; i++)
    
93.                 {
    
94.                         flag = 0;
    
95.                         n = 1;
    
96.                         y = 0;
    
97.                         s = i * i * i + a1 * i + b1;
    
98.                         while (s < 0)
    
99.                         {
    
100.                                 s += N;
     
101.                         }
     
102.                         s = mod_p(s);
     
103.                         modsqrt = int_sqrt(s);
     
104.                         if (modsqrt != -1)
     
105.                         {
     
106.                                 flag = 1;
     
107.                                 y = modsqrt;
     
108.                         }
     
109.                         else
     
110.                         {
     
111.                                 while (n <= N - 1)
     
112.                                 {
     
113.                                         q = s + n * N;
     
114.                                         modsqrt = int_sqrt(q);
     
115.                                         if (modsqrt != -1)
     
116.                                         {
     
117.                                                 y = modsqrt;
     
118.                                                 flag = 1;
     
119.                                                 break;
     
120.                                         }
     
121.                                         flag = 0;
     
122.                                         n++;
     
123.                                 }
     
124.                         }
     
125.                         if (flag == 1)
     
126.                         {
     
127.                                 eccPoint.p[j].x = i;
     
128.                                 eccPoint.p[j].y = y;
     
129.                                 j++;
     
130.                                 if (y != 0)
     
131.                                 {
     
132.                                         eccPoint.p[j].x = i;
     
133.                                         eccPoint.p[j].y = (N - y) % N;
     
134.                                         j++;
     
135.                                 }
     
136.                         }
     
137.                 }
     
138.                 eccPoint.len = j;//点集个数
     
139.                 print(); //打印点集
     
140.         }
     
141. }
     
142. 
     
143. //task3:求生成元以及阶
     
144. void get_generetor_class()
     
145. {
     
146.         int i, j = 0;
     
147.         int count = 1;
     
148.         Point p1, p2;
     
149.         get_all_points();
     
150.         printf("\n**********************************输出生成元以及阶：*************************************\n");
     
151.         for (i = 0; i < eccPoint.len; i++)
     
152.         {
     
153.                 count = 1;
     
154.                 p1.x = p2.x = eccPoint.p[i].x;
     
155.                 p1.y = p2.y = eccPoint.p[i].y;
     
156.                 while (1)
     
157.                 {
     
158.                         p2 = add_two_points(p1, p2);
     
159.                         if (p2.x == -1 && p2.y == -1)
     
160.                         {
     
161.                                 break;
     
162.                         }
     
163.                         count++;
     
164.                         if (p2.x == p1.x)
     
165.                         {
     
166.                                 break;
     
167.                         }
     
168.                 }
     
169.                 count++;
     
170.                 if (count <= eccPoint.len + 1)
     
171.                 {
     
172.                         geneSet[j].p.x = p1.x;
     
173.                         geneSet[j].p.y = p1.y;
     
174.                         geneSet[j].p_class = count;
     
175.                         printf("(%d,%d)--->>%d\t", geneSet[j].p.x, geneSet[j].p.y, geneSet[j].p_class);
     
176.                         j++;
     
177.                         if (j % 6 == 0)
     
178.                         {
     
179.                                 printf("\n");
     
180.                         }
     
181.                 }
     
182.                 geneLen = j;
     
183.         }
     
184. }
     
185. 
     
186. // 求 a mod b 的逆元
     
187. void exGcd(int a, int b)
     
188. {
     
189.         if (b == 0)
     
190.         {
     
191.                 xy[0] = 1;
     
192.                 xy[1] = 0;
     
193.         }
     
194.         else
     
195.         {
     
196.                 exGcd(b, a % b);
     
197.                 int x = xy[0];
     
198.                 xy[0] = xy[1];
     
199.                 xy[1] = x - (a / b) * xy[1];
     
200.         }
     
201. 
     
202. }
     
203. int calculate3(int y, int k, int p)
     
204. {
     
205. 
     
206.         int l = 1;
     
207.         for (int i = 0; i < k; i++)
     
208.         {
     
209.                 l = l * y;
     
210.                 l = l % p;
     
211.         }
     
212. 
     
213.         return l;
     
214. }
     
215. 
     
216. Point eccmutiply(int n, Point p)
     
217. {
     
218.         int a, b, l, k, m;
     
219.         a = p.x;
     
220.         b = p.y;
     
221.         for (int i = 0; i < n - 1; i++)
     
222.         {
     
223. 
     
224.                 if (a == p.x && b == p.y)
     
225.                 {
     
226.                         exGcd(2 * p.y, N);
     
227.                         k = xy[0];
     
228.                         if (k < 0) k = k + N;
     
229.                         printf("逆元=%d\n", k);
     
230.                         l = (3 * p.x * p.x + A) * k;
     
231.                         l = calculate3(l, 1, N);
     
232.                         if (l < 0)
     
233.                         {
     
234.                                 l = l + N;
     
235.                         }
     
236.                 }
     
237.                 else
     
238.                 {
     
239.                         exGcd(a - p.x + N, N);
     
240.                         k = xy[0];
     
241.                         if (k < 0) k = k + N;
     
242.                         printf("else逆元=%d\n", k);
     
243.                         l = (b - p.y) * k;
     
244.                         l = calculate3(l, 1, N);
     
245.                         if (l < 0)
     
246.                         {
     
247.                                 l = l + N;
     
248.                         }
     
249.                         printf("l=%d\n", l);
     
250.                 }
     
251.                 m = p.x;
     
252.                 a = l * l - a - p.x;
     
253.                 a = calculate3(a, 1, N);
     
254.                 if (a < 0)
     
255.                 {
     
256.                         a = a + N;
     
257.                 }
     
258.                 b = l * (m - a) - p.y;
     
259.                 b = calculate3(b, 1, N);
     
260. 
     
261.                 if (b < 0)
     
262.                 {
     
263.                         b = b + N;
     
264.                 }
     
265.                 printf("%d(a,b)=(%d,%d)\n", i + 2, a, b);
     
266.                 //if(a==4&&b==5)break;
     
267.         }
     
268.         Point p3;
     
269.         p3.x = a;
     
270.         p3.y = b;
     
271.         return p3;
     
272. }
     
273. Point mul(Point p1, Point p2)
     
274. {
     
275.         int k, l;
     
276.         exGcd(p2.x - p1.x + N, N);
     
277.         k = xy[0];
     
278.         if (k < 0) k = k + N;
     
279.         //printf("else逆元=%d\n",k);
     
280.         l = (p2.y - p1.y) * k;
     
281.         l = calculate3(l, 1, N);
     
282.         if (l < 0)
     
283.         {
     
284.                 l = l + N;
     
285.         }
     
286.         //printf("l=%d\n",l);       
     
287.         Point p3;
     
288.         p3.x = l * l - p1.x - p2.x;
     
289.         p3.x = calculate3(p3.x, 1, N);
     
290.         if (p3.x < 0) p3.x = p3.x + N;
     
291. 
     
292.         p3.y = l * (p1.x - p3.x) - p1.y;
     
293.         p3.y = calculate3(p3.y, 1, N);
     
294.         if (p3.y < 0) p3.y = p3.y + N;
     
295.         return p3;
     
296. }
     
297. 
     
298. //求b关于n的逆元
     
299. int inverse(int n, int b)
     
300. {
     
301.         int q, r, r1 = n, r2 = b, t, t1 = 0, t2 = 1, i = 1;
     
302.         while (r2 > 0)
     
303.         {
     
304.                 q = r1 / r2;
     
305.                 r = r1 % r2;
     
306.                 r1 = r2;
     
307.                 r2 = r;
     
308.                 t = t1 - q * t2;
     
309.                 t1 = t2;
     
310.                 t2 = t;
     
311.         }
     
312.         if (t1 >= 0)
     
313.                 return t1 % n;
     
314.         else
     
315.         {
     
316.                 while ((t1 + i * n) < 0)
     
317.                         i++;
     
318.                 return t1 + i * n;
     
319.         }
     
320. }
     
321. //两点的加法运算
     
322. Point add_two_points(Point p1, Point p2)
     
323. {
     
324.         long t;
     
325.         int x1 = p1.x;
     
326.         int y1 = p1.y;
     
327.         int x2 = p2.x;
     
328.         int y2 = p2.y;
     
329.         int tx, ty;
     
330.         int x3, y3;
     
331.         int flag = 0;
     
332.         //求
     
333.         if ((x2 == x1) && (y2 == y1))
     
334.         {
     
335.                 //相同点相加
     
336.                 if (y1 == 0)
     
337.                 {
     
338.                         flag = 1;
     
339.                 }
     
340.                 else
     
341.                 {
     
342.                         t = (3 * x1 * x1 + a1) * inverse(N, 2 * y1) % N;
     
343.                 }
     
344.                 //printf("inverse(p,2*y1)=%d\n",inverse(p,2*y1));
     
345.         }
     
346.         else
     
347.         {
     
348.                 //不同点相加
     
349.                 ty = y2 - y1;
     
350.                 tx = x2 - x1;
     
351.                 while (ty < 0)
     
352.                 {
     
353.                         ty += N;
     
354.                 }
     
355.                 while (tx < 0)
     
356.                 {
     
357.                         tx += N;
     
358.                 }
     
359.                 if (tx == 0 && ty != 0)
     
360.                 {
     
361.                         flag = 1;
     
362.                 }
     
363.                 else
     
364.                 {
     
365.                         t = ty * inverse(N, tx) % N;
     
366.                 }
     
367.         }
     
368.         if (flag == 1)
     
369.         {
     
370.                 p2.x = -1;
     
371.                 p2.y = -1;
     
372.         }
     
373.         else
     
374.         {
     
375.                 x3 = (t * t - x1 - x2) % N;
     
376.                 y3 = (t * (x1 - x3) - y1) % N;
     
377.                 //使结果在有限域GF(P)上
     
378.                 while (x3 < 0)
     
379.                 {
     
380.                         x3 += N;
     
381.                 }
     
382.                 while (y3 < 0)
     
383.                 {
     
384.                         y3 += N;
     
385.                 }
     
386.                 p2.x = x3;
     
387.                 p2.y = y3;
     
388.         }
     
389.         return p2;
     
390. }
     
391. //task2:倍点运算的递归算法
     
392. Point timesPiont(int k, Point p0)
     
393. {
     
394.         if (k == 1)
     
395.         {
     
396.                 return p0;
     
397.         }
     
398.         else if (k == 2)
     
399.         {
     
400.                 return add_two_points(p0, p0);
     
401.         }
     
402.         else
     
403.         {
     
404.                 return add_two_points(p0, timesPiont(k - 1, p0));
     
405.         }
     
406. }
     
407. main(){
     
408.         get_generetor_class();
     
409.         Point p1, p2, p, p4, p5, p6, p7, p8, p9, p10;
     
410.         int na, k, h, r, s, u1, u2;
     
411.         printf("选择生成元");
     
412.         scanf("%d%d", &p1.x, &p1.y);
     
413.         int j = 0;
     
414.         while (j < N)
     
415.         {
     
416. 
     
417.                 if (geneSet[j].p.x == p1.x && geneSet[j].p.y == p1.y)
     
418.                 {
     
419.                         break;
     
420.                 }
     
421.                 printf("j=%d\n", j);
     
422.                 ++j;
     
423.         }
     
424.         int M = geneSet[j].p_class;
     
425.         printf("M=%d", M);
     
426.         //        p1.x=0;
     
427.         //        p1.y=2;
     
428.         //p.x=20;
     
429.         //p.y=1;
     
430.         printf("请输入私钥");
     
431.         scanf("%d", &na);
     
432.         p2 = eccmutiply(na, p1);
     
433.         printf("公钥为（%d,%d)", p2.x, p2.y);
     
434.         //p2=mul(p,p1);
     
435. 
     
436.         //printf("(%d,%d)",p2.x,p2.y);
     
437. 
     
438.         //签名过程
     
439.         printf("输入随机数k\n");
     
440.         scanf("%d", &k);
     
441.         printf("输入hash\n");
     
442.         scanf("%d", &h);
     
443. 
     
444. 
     
445.         p4 = eccmutiply(k, p1);
     
446.         r = calculate3(p4.x, 1, N);
     
447.         if (r < 0) r = r + N;
     
448.         s = inverse(M, k) * (h + na * r) % M;
     
449.         if (s < 0) s = s + N;
     
450.         printf("签名为(%d,%d)\n", r, s);
     
451.         printf("========================");
     
452.         //验证过程
     
453.         u1 = h * inverse(M, s) % M;
     
454. 
     
455.         if (u1 < 0) u1 = u1 + M;
     
456.         u2 = r * inverse(M, s) % M;
     
457. 
     
458.         if (u2 < 0) u2 = u2 + M;
     
459. 
     
460.         printf("u1u2=%d,%d\n", u1, u2);
     
461. 
     
462.         p5 = eccmutiply(u1, p1);
     
463.         printf("sG=(%d,%d)\n", p5.x, p5.y);
     
464. 
     
465.         p6 = eccmutiply(u2, p2);
     
466.         printf("HP=(%d,%d)\n", p6.x, p6.y);
     
467. 
     
468.         p7 = add_two_points(p5, p6);
     
469.         printf("sG+HP=(%d,%d)\n", p7.x, p7.y);
     
470.         if (calculate3(p7.x, 1, N) == r)
     
471.         {
     
472.                 printf("通过");
     
473.         }
     
474.         else
     
475.         {
     
476.                 printf("失败");
     
477.         }
     
478. 
     
479. }
     

复制代码