信息计算2019陆慧明

信息计算陆慧明

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

复制代码