RSA 算法

admin

1. #include <iostream.h>
   
2. #include <math.h>
   
3. long code(long m,long e,long n)//-----------加解密函数:用c=m^e(modn)加密，用m=c^d(modn)解密
   
4. { long c=1;
   
5.   e=e+1;
   
6.   while(e!=1)
   
7.   {
   
8.     c=c*m;
   
9.     c=c%n;
   
10.     e--;
    
11.   }
    
12. 
    
13.   return c;
    
14. }
    
15. int gcd(long a,long b)//--------------------判断两个数是否互素
    
16. {
    
17.         long r0=a;
    
18.         long r1=b;
    
19.         int q,temp;
    
20.         while(r1!=0)
    
21.         {
    
22.                 q=r0/r1;
    
23.                 temp=r0;
    
24.                 r0=r1;
    
25.                 r1=temp-q*r1;
    
26.         }
    
27.         if(r0==1)//------------------------------最大公因数为1时两数互素
    
28.         return 1;            
    
29.         else return 0;        
    
30. }
    
31. 
    
32. 
    
33. long privatekey(long a,long b)//-------------用欧几里德算法求私钥d
    
34.    
    
35. {
    
36.         long r,r1=1;
    
37.         long r0=b;
    
38.         long s0,t0,e,s1,q,temprivatekey;
    
39.         r1=a;
    
40.         t0=0;
    
41.         e=1;
    
42.         s0=1;
    
43.         s1=0;
    
44.         q=r0/r1;
    
45.         r=r0-q*r1;
    
46.         while(r>0)         
    
47.         {
    
48.                 temprivatekey=t0-q*e;
    
49.             t0=e;
    
50.                 e=temprivatekey;
    
51.                 temprivatekey=s0-q*s1;
    
52.                 s0=s1;
    
53.                 s1=temprivatekey;
    
54.                 r0=r1;
    
55.                 r1=r;
    
56.                 q=r0/r1;
    
57.                 r=r0-q*r1;
    
58.         }
    
59.         while(e<0)
    
60.         {
    
61.                 e=e+b;
    
62.         }
    
63.         return e;   
    
64. }
    
65. void main()//----------------------------------------主函数
    
66. {
    
67. long p,q,e,d,m,n,t;
    
68.   
    
69.   cout<<"请输入两个素数 p,q: ";
    
70.   cin>>p>>q;
    
71.   
    
72.   n=p*q;
    
73.   cout<<"n为 :"<<n<<endl;
    
74.   t=(p-1)*(q-1);//------------------------------------欧拉函数值
    
75.   cout<<"n的欧拉函数值 :"<<t<<endl;
    
76.   cout<<"请输入公钥e: ";
    
77.   cin>>e;//-------------------------------------------输入公钥e,满足t>e>1
    
78. int u;
    
79. u=gcd(e,t);//----------------------------------------判断e是否与n的欧拉函数值互素
    
80.   if(1<e&&e<t&&u==0)
    
81.   {
    
82.      cout<<"请重新输入: ";
    
83.      cin>>e;
    
84.   }
    
85. int w;
    
86. cout<<"输入1加密,输入2解密:";
    
87. cin>>w;
    
88. switch(w)//--------------------------------------------w为1时加密，为2时解密
    
89. {
    
90. case 1 ://----------------------------------------------加密
    
91. {
    
92.             cout<<"请输入明文:";
    
93.         cin>>m;//---------------------------------------输入明文
    
94.         if(m<=n)
    
95.         cout<< "密文为:"<<code(m,e,n)<<endl;//----------明文数值小于n时直接加密
    
96.         else
    
97.          {
    
98.             long i=0,g,h;
    
99.         g=n;
    
100.             h=m;
     
101.    while(g!=0)//----------------------------------------求n的长度
     
102.          {
     
103.       g/=10;
     
104.       i++;
     
105.          }
     
106.          long j=0;
     
107.    while(h!=0)//----------------------------------------求明文长度
     
108.         {
     
109.       h/=10;
     
110.       j++;
     
111.         }
     
112.     long x=0,long c[1000];//-----------------------------数组c用来存放加密后的各个分组
     
113.         int k=0;//-------------------------------------------k将记录明文分的组数
     
114.    while(j!=0)
     
115.    {
     
116.      x=m/pow(10,j-i);
     
117.      if(x>n)
     
118.          {
     
119.       x=x/10;
     
120.       c[k]=code(x,e,n);
     
121.       m=m-x*pow(10,j-i+1);
     
122.       j=j-1;
     
123.           k++;
     
124.          }
     
125.    else
     
126.    {
     
127.         c[k]=code(x,e,n);
     
128.     m=m-x*pow(10,j-i);
     
129.     j=j-2;
     
130.         k++;
     
131.    }
     
132.    if(i>j)//----------------------------------------------最后一个分组的长度小于n的长度时直接加密
     
133. 
     
134.           c[k]=code(m,e,n);
     
135.    }
     
136.    cout<<"密文输出:";
     
137.    for(long l=0;l<k;l++)
     
138.            cout<<c[l];
     
139.    cout<<endl;
     
140.    }
     
141.          break;
     
142.          }
     
143. case 2 ://------------------------------------------------解密
     
144.         {
     
145.                 cout<<"请输入密文:"<<endl;
     
146.                 cin>>m;
     
147.             long d;
     
148.        d=privatekey(e,t);
     
149.            if(m<=n)
     
150.    cout<< "密文为:"<<code(m,d,n)<<endl;
     
151.   else
     
152.    {
     
153.          long i=0,g,h;
     
154.      g=n;
     
155.          h=m;
     
156.      while(g!=0)
     
157.          {
     
158.       g/=10;
     
159.       i++;
     
160.          }
     
161.          long j=0;
     
162.     while(h!=0)
     
163.         {
     
164.       h/=10;
     
165.       j++;
     
166.         }
     
167.      
     
168.         long x=0,long c[1000];
     
169.         int k=0;
     
170.    while(j!=0)
     
171.    {
     
172.      x=m/pow(10,j-i);
     
173.    
     
174.      if(x>n)
     
175.          {
     
176.       x=x/10;
     
177.       c[k]=code(x,d,n);
     
178.       m=m-x*pow(10,j-i+1);
     
179.       j=j-1;
     
180.           k++;
     
181.          }
     
182.    else
     
183.    {
     
184.           c[k]=code(x,d,n);
     
185.     m=m-x*pow(10,j-i);
     
186.     j=j-2;
     
187.         k++;
     
188.    }
     
189.    if(i>j)
     
190. 
     
191.           c[k]=code(m,d,n);
     
192.    }
     
193.    for(long l=0;l<k;l++)
     
194. 
     
195.    cout<<c[l];
     
196.    cout<<endl;
     
197.   }
     
198.    break;
     
199.         }
     
200.        
     
201. }
     
202. 
     
203. }

复制代码