信息计算2019级2班6号李靓

李靓

李靓

李靓

RSA（大数版本）

一、算法描述

1.输入p、q，满足：p，q是两个不同的素数

2.计算n=p*q，m=(p-1)(q-1)

3.输入满足条件的e：e与(p-1)*(q-1)互质

4.计算d，要求(e*d)≡1(mod m)

5.生成密钥：公钥为（m，e），私钥为（m，d）

6.选择加密则输入明文生成密文；选择解密则输入密文生成明文

二、源代码

1. #include <stdio.h>  
   
2. 
   
3. int RSA(int a,int b,int c)  //计算密文
   
4. 
   
5. {
   
6.         int code=1;  
   
7.        
   
8.         for(b=b+1;b!=1;b--)
   
9.         {
   
10.                 code=code*a;  
    
11.                 code=code%c;
    
12.         }  
    
13. 
    
14.         return code;  
    
15. 
    
16. }  
    
17. 
    
18. int IsPrime(int x) //判断是否为素数
    
19. {
    
20.         int i=2;
    
21.         for(i=2;i<x+1;i++)
    
22.         {
    
23.                 if(x%i==0)
    
24.                 break;
    
25.          }
    
26.          if(i<x)
    
27.          return 0;
    
28.                 
    
29. 
    
30. }
    
31. int main()  
    
32. {
    
33.         int p,q,m,n,e,d,x,y,z;  
    
34.         printf("\n生成密钥\n\n");   
    
35.         printf("请输入素数p,q: ");    //输入两个素数q,p
    
36.         scanf("%d%d",&p,&q);
    
37.         if(!IsPrime(p)||!IsPrime(q))
    
38.                 printf("输入错误！请输入素数！");
    
39.         else{
    
40.        
    
41.         n=p*q;
    
42.         printf("n为%d\n",n);
    
43.         m=(p-1)*(q-1);
    
44.         printf("m为%d\n",m);
    
45.         printf("请输入合适的整数e: ");
    
46.         scanf("%d",&e);
    
47.         if(e<1||e>m)
    
48.         {
    
49.                 printf("e输入错误，请重新输入: ");
    
50.                 scanf("%d",&e);
    
51.         }
    
52.        
    
53.         d=1;
    
54.         while((e*d)%m!=1)
    
55.                 d++;  
    
56.         printf("密钥已生成！");
    
57.         printf("\n\n");
    
58.         printf("\t1.加密\n");   
    
59.         printf("\t2.解密\n");
    
60.         printf("\t3.退出\n");
    
61.         printf("\n请选择功能：");   
    
62.         scanf("%d",&z);
    
63.         while(1)
    
64.         {
    
65.                 if(z==1)
    
66.                 {
    
67.                         printf("\t请输入明文: ");  //计算密文
    
68.                         scanf("%d",&x);
    
69.                         y=RSA(x,e,n);
    
70.                         printf("\t密文为:%d\n",y);
    
71.                 }
    
72.                 else if(z==2)
    
73.                 {
    
74.                         printf("\t请输入密文: ");  //计算明文
    
75.                         scanf("%d",&y);
    
76.                         x=RSA(y,d,n);
    
77.                         printf("\t明文为%d\n",x);
    
78.                 }
    
79.                 else break;
    
80.                 printf("\n\n");
    
81.                 printf("\t1.加密\n");   
    
82.                 printf("\t2.解密\n");
    
83.                 printf("\t3.退出\n");
    
84.                 printf("\n请选择功能：");   
    
85.                 scanf("%d",&z);
    
86.                 }
    
87. 
    
88.          return 0;
    
89. 
    
90. }
    
91. }

复制代码

二、运行结果

李靓