信息计算2019级1班30号刘毅扬

刘毅扬

RSA加密和签名

（1）加密过程。在秘钥生成过程中，首先生成两个大的质数（素数）p和q，令n=p*q;m=(p-1)*(q-1),选取较小的数e,使e 和m互质，即e和m的最大公约数为1，然后生成d，使d*emod m=1,最后丢弃P,q,m,则公钥为e,n,私钥为d和n.

（2）加密过程。将明文x加密成密文y的计算公式为：x=y^d mod n。从公式可见，加密牵涉到明文和公钥。因此，密文即使被截获，也无法被解读。

（3） 解密过程。将密文y解密成明文x的计算公式为：x=y^d mod n。从公式可见，解密至牵涉到私钥和密文。因此，只要保管好私钥，不泄密，就可以放心地把密文和公钥公开。

1. #include <stdio.h>  
   
2. 
   
3. int candp(int a,int b,int c)  //计算密文
   
4. 
   
5. {
   
6. 
   
7.     int r=1;  
   
8. 
   
9. b=b+1;  
   
10. 
    
11. while(b!=1)  
    
12. 
    
13. {  
    
14. 
    
15.   r=r*a;  
    
16. 
    
17.   r=r%c;  
    
18. 
    
19.   b--;  
    
20. 
    
21. }  
    
22. 
    
23. return r;  
    
24. 
    
25. }  
    
26. 
    
27. 
    
28. 
    
29. int main()  
    
30. 
    
31. {  
    
32. 
    
33. int p,q,m,n,e,d,x,y,r;  
    
34. 
    
35. printf("请输入 p,q: ");    //输入两个素数q,p
    
36. 
    
37. scanf("%d%d",&p,&q);  
    
38. 
    
39. n=p*q;  
    
40. 
    
41. printf("n为%d\n",n);  
    
42. 
    
43. 
    
44. 
    
45. m=(p-1)*(q-1);
    
46. 
    
47. printf("m为%d\n",m);  
    
48. 
    
49. 
    
50. 
    
51. printf("请输入e: ");  
    
52. 
    
53. scanf("%d",&e);  
    
54. 
    
55. if(e<1||e>m)  
    
56. 
    
57. {  
    
58. 
    
59.   printf("e输入错误，请重新输入: ");  
    
60. 
    
61.   scanf("%d",&e);  
    
62. 
    
63. }  
    
64. 
    
65. d=1;  
    
66. 
    
67. while(((e*d)%m)!=1) d++;  
    
68. 
    
69. printf("计算出d为:%d\n",d);  
    
70. 
    
71. printf("加密请输入1,解密请输入2,输入其他退出\n");   
    
72. 
    
73. scanf("%d",&r);  
    
74. 
    
75. while(1)
    
76. 
    
77. {
    
78. 
    
79. 
    
80. 
    
81.   if(r==1)
    
82. 
    
83.   {
    
84. 
    
85. printf("请输入x: ");  //计算密文
    
86. 
    
87. scanf("%d",&x);  
    
88. 
    
89. y=candp(x,e,n);  
    
90. 
    
91. printf("密文为:%d\n",y);
    
92. 
    
93.   }
    
94. 
    
95.   else if(r==2)
    
96. 
    
97. {
    
98. 
    
99. printf("请输入密文: ");  //计算明文
    
100. 
     
101. scanf("%d",&y);  
     
102. 
     
103. x=candp(y,d,n);  
     
104. 
     
105. printf("明文为%d\n",x);
     
106. 
     
107.   }
     
108. 
     
109.   else break;
     
110. 
     
111. printf("加密请输入1,解密请输入2,输入其他退出\n");   
     
112. 
     
113. scanf("%d",&r);
     
114. 
     
115. }
     
116. 
     
117.          return 0;
     
118. 
     
119. }
     

复制代码

刘毅扬

ECC椭圆曲线密码

公私钥生成：
1.Alice首先构造一条椭圆曲线E，在曲线上选择一点G作为生成元，并求G的阶为n，要求n必须为质数；
2.Alice选择一个私钥k(k<n)，生成公钥Q=kG；
3.Alice将公钥组E、Q、G发送给Bob。
加密过程：
1.Bob收到信息后，将明文编码为M，M为曲线上一点，并选择一个随机数r rr（r < n , n r < n, nr<n,n为G GG的阶）；
2.Bob计算点Cipher1与Cipher2即两段密文，计算方法如下
Cipher1=M+rQ
Cipher2=rG
3.Bob把Cipher1和Cipher2发给Alice。
解密过程：
Alice收到密文后，为了获得M，只需要Cipher1−k⋅Cipher2，因为Cipher1−k∗Cipher2=M+rQ−krG=M+rkG−krG=M
将M解码即可。

刘毅扬

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. #include<string.h>
   
4. #include<math.h>
   
5. #include<time.h>
   
6. #define MAX 100
   
7. 
   
8. typedef struct point{
   
9.         int point_x;
   
10.         int point_y;
    
11. }Point;
    
12. typedef struct ecc{
    
13.         struct point p[MAX];
    
14.         int len;
    
15. }ECCPoint;
    
16. typedef struct generator{
    
17.         Point p;
    
18.         int p_class;
    
19. }GENE_SET;
    
20. 
    
21. void get_all_points();
    
22. int int_sqrt(int s);
    
23. Point timesPiont(int k,Point p);
    
24. Point add_two_points(Point p1,Point p2);
    
25. int inverse(int n,int b);
    
26. void get_generetor_class();
    
27. void encrypt_ecc();
    
28. void decrypt_ecc();
    
29. int mod_p(int s);
    
30. void print();
    
31. int isPrime(int n);
    
32. char alphabet[26]="abcdefghijklmnopqrstuvwxyz";
    
33. int a=-1,b=0,p=89;
    
34. ECCPoint eccPoint;
    
35. GENE_SET geneSet[MAX];
    
36. int geneLen;
    
37. char plain[]="yes";
    
38. int m[MAX];
    
39. int cipher[MAX];
    
40. int nB;
    
41. Point P1,P2,Pt,G,PB;
    
42. Point Pm;
    
43. int C[MAX];
    
44. int main()
    
45. {        
    
46.         get_generetor_class();
    
47.         encrypt_ecc();
    
48.         decrypt_ecc();
    
49.         return 0;
    
50. }
    
51. void encrypt_ecc()
    
52. {
    
53.         int num,i,j;
    
54.         int gene_class;
    
55.         int num_t;
    
56.         int k;
    
57.         srand(time(NULL));
    
58.         for(i=0;i<strlen(plain);i++)
    
59.         {
    
60.                 for(j=0;j<26;j++)
    
61.                 {
    
62.                         if(plain[i]==alphabet[j])
    
63.                         {
    
64.                                 m[i]=j;
    
65.                         }
    
66.                 }         
    
67.         }
    
68.         num=rand()%geneLen;
    
69.         gene_class=geneSet[num].p_class;
    
70.         while(isPrime(gene_class)==-1)
    
71.         {
    
72.                  num=rand()%(geneLen-3)+3;
    
73.                  gene_class=geneSet[num].p_class;
    
74.         }
    
75.         G=geneSet[num].p;
    
76.         nB=rand()%(gene_class-1)+1;
    
77.         PB=timesPiont(nB,G);
    
78.         printf("\n公钥：\n");
    
79.         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);
    
80.         printf("私钥：\n");
    
81.         printf("nB=%d\n",nB);
    
82.         k=rand()%(gene_class-2)+1;
    
83.         P1=timesPiont(k,G);
    
84.         num_t=rand()%eccPoint.len;
    
85.         Pt=eccPoint.p[num_t];
    
86.         P2=timesPiont(k,PB);
    
87.         Pm=add_two_points(Pt,P2);
    
88.         printf("加密数据：\n");
    
89.         printf("kG=(%d,%d),Pt+kPB=(%d,%d),C={",P1.point_x,P1.point_y,Pm.point_x,Pm.point_y);
    
90.         for(i=0;i<strlen(plain);i++)
    
91.         {
    
92.                 C[i]=m[i]*Pt.point_x+Pt.point_y;
    
93.                 printf("{%d}",C[i]);
    
94.         }        
    
95.         printf("}\n");
    
96. }
    
97. void decrypt_ecc()
    
98. {
    
99.         Point temp,temp1;
    
100.         int m,i;
     
101.         temp=timesPiont(nB,P1);
     
102.         temp.point_y=0-temp.point_y;
     
103.         temp1=add_two_points(Pm,temp);
     
104.         printf("\n解密结果：\n");
     
105.         for(i=0;i<strlen(plain);i++)
     
106.         {
     
107.                 m=(C[i]-temp1.point_y)/temp1.point_x;
     
108.                 printf("%c",alphabet[m]);
     
109.         }
     
110.         printf("\n");
     
111. }
     
112. int isPrime(int n)
     
113. {
     
114.         int i,k;
     
115.     k = sqrt(n);
     
116.     for (i = 2; i <= k;i++)
     
117.     {
     
118.             if (n%i == 0)
     
119.                         break;
     
120.         }      
     
121.     if (i <=k){
     
122.             return -1;
     
123.         }
     
124.     else {
     
125.              return 0;
     
126.         }
     
127. }
     
128. void get_generetor_class()
     
129. {        
     
130.         int i,j=0;
     
131.         int count=1;
     
132.         Point p1,p2;
     
133.         get_all_points();
     
134.         printf("\n**********************************输出生成元以及阶：*************************************\n");
     
135.         for(i=0;i<eccPoint.len;i++)
     
136.         {
     
137.                 count=1;
     
138.                 p1.point_x=p2.point_x=eccPoint.p[i].point_x;
     
139.                 p1.point_y=p2.point_y=eccPoint.p[i].point_y;               
     
140.                 while(1)
     
141.                 {        
     
142.                         p2=add_two_points(p1,p2);                                       
     
143.                         if(p2.point_x==-1 && p2.point_y==-1)
     
144.                         {
     
145.                                 break;
     
146.                         }
     
147.                         count++;
     
148.                         if(p2.point_x==p1.point_x)
     
149.                         {
     
150.                                 break;
     
151.                         }                                                
     
152.                 }
     
153.                 count++;
     
154.                 if(count<=eccPoint.len+1)
     
155.                 {
     
156.                         geneSet[j].p.point_x=p1.point_x;
     
157.                         geneSet[j].p.point_y=p1.point_y;
     
158.                         geneSet[j].p_class=count;
     
159.                         printf("(%d,%d)--->>%d\t",geneSet[j].p.point_x,geneSet[j].p.point_y,geneSet[j].p_class);
     
160.                         j++;
     
161.                         if(j % 6 ==0){
     
162.                                 printf("\n");
     
163.                         }
     
164.                 }
     
165.                 geneLen=j;        
     
166.         }
     
167. }
     
168. Point timesPiont(int k,Point p0)
     
169. {
     
170.         if(k==1){
     
171.                 return p0;
     
172.         }                 
     
173.         else if(k==2){
     
174.                 return add_two_points(p0,p0);
     
175.         }else{
     
176.                 return add_two_points(p0,timesPiont(k-1,p0));
     
177.         }
     
178. }
     
179. Point add_two_points(Point p1,Point p2)
     
180. {
     
181.         long t;
     
182.         int x1=p1.point_x;
     
183.         int y1=p1.point_y;
     
184.         int x2=p2.point_x;
     
185.         int y2=p2.point_y;
     
186.         int tx,ty;
     
187.         int x3,y3;
     
188.         int flag=0;
     
189.         if((x2==x1)&& (y2==y1) )
     
190.         {
     
191.                 if(y1==0)
     
192.                 {
     
193.                         flag=1;
     
194.                 }else{
     
195.                         t=(3*x1*x1+a)*inverse(p,2*y1) % p;
     
196.                 }
     
197.         }else{
     
198.                 ty=y2-y1;
     
199.                 tx=x2-x1;
     
200.                 while(ty<0)
     
201.                 {
     
202.                         ty+=p;
     
203.                 }
     
204.                 while(tx<0)
     
205.                 {
     
206.                         tx+=p;
     
207.                 }
     
208.                 if(tx==0 && ty !=0)
     
209.                 {
     
210.                         flag=1;
     
211.                 }else{
     
212.                         t=ty*inverse(p,tx) % p;
     
213.                 }
     
214.         }
     
215.         if(flag==1)
     
216.         {
     
217.                 p2.point_x=-1;
     
218.                 p2.point_y=-1;
     
219.         }else{
     
220.                 x3=(t*t-x1-x2) % p;
     
221.                 y3=(t*(x1-x3)-y1) % p;
     
222.                 while(x3<0)
     
223.                 {
     
224.                         x3+=p;
     
225.                 }
     
226.                 while(y3<0)
     
227.                 {
     
228.                         y3+=p;
     
229.                 }
     
230.                 p2.point_x=x3;
     
231.                 p2.point_y=y3;
     
232.         }        
     
233.         return p2;
     
234. }
     
235. int inverse(int n,int b)
     
236. {
     
237.         int q,r,r1=n,r2=b,t,t1=0,t2=1,i=1;
     
238.         while(r2>0)
     
239.         {
     
240.                 q=r1/r2;
     
241.                 r=r1%r2;
     
242.                 r1=r2;
     
243.                 r2=r;
     
244.                 t=t1-q*t2;
     
245.                 t1=t2;
     
246.                 t2=t;
     
247.         }
     
248.         if(t1>=0)
     
249.                 return t1%n;
     
250.         else{  
     
251.                 while((t1+i*n)<0)
     
252.                         i++;
     
253.                 return t1+i*n;
     
254.         }
     
255. }
     
256. void get_all_points()
     
257. {
     
258.         int i=0;
     
259.         int j=0;
     
260.         int s,y=0;
     
261.         int n=0,q=0;
     
262.         int modsqrt=0;
     
263.         int flag=0;
     
264.         if (4 * a * a * a + 27 * b * b != 0)
     
265.         {
     
266.                 for(i=0;i<=p-1;i++)
     
267.                 {
     
268.                         flag=0;
     
269.                         n=1;
     
270.                         y=0;
     
271.                         s= i * i * i + a * i + b;
     
272.                         while(s<0)
     
273.                         {
     
274.                                 s+=p;
     
275.                         }
     
276.                         s=mod_p(s);
     
277.                         modsqrt=int_sqrt(s);
     
278.                         if(modsqrt!=-1)
     
279.                         {
     
280.                                 flag=1;
     
281.                                 y=modsqrt;
     
282.                         }else{
     
283.                                 while(n<=p-1)
     
284.                                 {
     
285.                                         q=s+n*p;
     
286.                                         modsqrt=int_sqrt(q);
     
287.                                         if(modsqrt!=-1)
     
288.                                         {
     
289.                                                 y=modsqrt;
     
290.                                                 flag=1;
     
291.                                                 break;
     
292.                                         }
     
293.                                                 flag=0;
     
294.                                                 n++;
     
295.                                 }
     
296.                         }
     
297.                         if(flag==1)
     
298.                         {
     
299.                                 eccPoint.p[j].point_x=i;
     
300.                                 eccPoint.p[j].point_y=y;
     
301.                                 j++;
     
302.                                 if(y!=0)
     
303.                                 {
     
304.                                         eccPoint.p[j].point_x=i;
     
305.                                         eccPoint.p[j].point_y=(p-y) % p;
     
306.                                         j++;
     
307.                                 }                                
     
308.                         }
     
309.                 }
     
310.                 eccPoint.len=j;
     
311.                 print();
     
312.         }        
     
313. }
     
314. int mod_p(int s)
     
315. {
     
316.         int i;
     
317.         int result;
     
318.         i = s / p;
     
319.         result = s - i * p;
     
320.         if (result >= 0)
     
321.         {
     
322.                 return result;
     
323.         }
     
324.         else
     
325.         {
     
326.                 return result + p;
     
327.         }
     
328. }
     
329. 
     
330. int int_sqrt(int s)
     
331. {
     
332.         int temp;
     
333.         temp=(int)sqrt(s);
     
334.         if(temp*temp==s)
     
335.         {
     
336.                 return temp;
     
337.         }else{
     
338.                 return -1;
     
339.         }
     
340. }
     
341. void print()
     
342. {
     
343.         int i;
     
344.         int len=eccPoint.len;
     
345.         printf("\n该椭圆曲线上共有%d个点(包含无穷远点)\n",len+1);
     
346.         for(i=0;i<len;i++)
     
347.         {
     
348.                 if(i % 8==0)
     
349.                 {
     
350.                         printf("\n");
     
351.                 }
     
352.                 printf("(%2d,%2d)\t",eccPoint.p[i].point_x,eccPoint.p[i].point_y);
     
353.         }
     
354.         printf("\n");
     
355. }

复制代码