信息计算2019陆慧明

信息计算陆慧明

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. #include<string.h>
   
4. #include<time.h>
   
5. //将十进制转二进制，用于检验大素数p,q
   
6. int zh(int b,int a[],int k)
   
7. {
   
8.         int t,temp=-1;
   
9.         while(b>0)
   
10.         {
    
11.                 t=b%2;
    
12.                 temp++;
    
13.                 a[temp]=t;
    
14.                 b=b/2;
    
15.         }
    
16.         return temp;
    
17. }
    
18. //欧几里得求逆元，求解密指数d
    
19. int extend(int n,int b)
    
20. {
    
21.         int q,r,r1=n,r2=b,t,t1=0,t2=1,i=1;
    
22.         while(r2>0)
    
23.         {
    
24.                 q=r1/r2;
    
25.                 r=r1%r2;
    
26.                 r1=r2;
    
27.                 r2=r;
    
28.                 t=t1-q*t2;
    
29.                 t1=t2;
    
30.                 t2=t;
    
31.         }
    
32.         if(t1>0) return t1%n;
    
33.         else{
    
34.                 while((t1+i*n)<0)
    
35.                         i++;
    
36.                 return t1+i*n;
    
37.         }
    
38. }
    
39. //检验大素数
    
40. int Witness(int a,int n)
    
41. {
    
42.         int d=1,k,r=n-1,i,x,b[1000];
    
43.         k=zh(r,b,1000);
    
44.         for(i=k;i>=0;i--)
    
45.         {
    
46.                 x=d;
    
47.                 d=(d*d)%n;
    
48.                 if((d==1)&&(x!=1)&&(x!=n-1)) return 0;
    
49.                 if(b[i]==1)
    
50.                         d=(d*a)%n;
    
51.         }
    
52.         if(d!=1) return 0;
    
53.         else return 1;
    
54. }
    
55. //快速计算模指数
    
56. int mod(int a,int b,int n)
    
57. {
    
58.         int x=0,y=1,k,i,s[1000];
    
59.         k=zh(b,s,1000);
    
60.         for(i=k;i>=0;i--)
    
61.         {
    
62.                 x=2*x;
    
63.                 y=(y*y)%n;
    
64.                 if(s[i]==1)
    
65.                 {
    
66.                         x++;
    
67.                         y=(y*a)%n;
    
68.                 }
    
69.         }
    
70.         return y;
    
71. }
    
72. 
    
73. void main()
    
74. {
    
75.         int p,q,e,d,n,yn,m[1000],c[10000],mw[1000];
    
76.         int yinzi[1000],e1[1000];
    
77.         int i,j=0,j1;
    
78.         char min_wen[1000],mi_wen[1000],re_min_wen[1000];
    
79.         //密钥生成
    
80.         char zimu_biao[52]="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    
81.         char shuzi_biao[10]="0123456789";
    
82.         printf("输入明文，小英表示：\n");
    
83.         gets(min_wen);
    
84.         //随机生成p,q
    
85.         while(1)
    
86.         {
    
87.                 srand((unsigned)time(NULL));
    
88.                 p=rand()%500+2;
    
89.                 if(Witness(2,p)==1)
    
90.                 {
    
91.                         printf("生成p：%d \n",p);
    
92.                         break;
    
93.                 }
    
94.         }
    
95.        
    
96.         while(i){
    
97.                 srand((unsigned)time(NULL));
    
98.                 q=rand()%600+2;
    
99.                 if(Witness(2,q)==1)
    
100.                 {
     
101.                         printf("生成q：%d \n",q);
     
102.                         break;
     
103.                 }
     
104.         }
     
105.         n=p*q;
     
106.         yn=(p-1)*(q-1);
     
107.         //生成e
     
108.         for(i=2;i<=yn;i++)
     
109.         {
     
110.                 if(yn%i==0)
     
111.                 {
     
112.                         yinzi[j]=i;
     
113.                         j++;
     
114.                 }
     
115.                 j1=j;
     
116.         }
     
117.         srand(time(NULL));
     
118.         for(i=0;i<j1+1;i++)
     
119.         {
     
120.                 e1[i]=rand()%(yn-2)+2;
     
121.                 for(j=0;j<i;j++)
     
122.                 {
     
123.                         if(e1[j]==e1[i])
     
124.                         {
     
125.                                 i--;
     
126.                                 break;
     
127.                         }
     
128.                 }
     
129.         }
     
130.         for(i=0;i<j1+1;i++)
     
131.         {
     
132.                 for(j=j1;j>i;j--)
     
133.                 {
     
134.                         int x;
     
135.                         if(e1[i]>e1[j])
     
136.                         {
     
137.                                 x=e1[i];
     
138.                                 e1[i]=e1[j];
     
139.                                 e1[j]=x;
     
140.                         }
     
141.                 }
     
142.         }
     
143.         for(i=0;i<j1+1;j++)
     
144.         {
     
145.                 for(j=0;j<j1;j++)
     
146.                 {
     
147.                         if(e1[i]==yinzi[j])
     
148.                         {
     
149.                                 e1[i]=0;break;
     
150.                         }
     
151.                 }
     
152.                 if(e1[i]!=0)
     
153.                 {
     
154.                         e=e1[i];
     
155.                         break;
     
156.                 }
     
157.         }
     
158.         d=extend(yn,e);
     
159.         printf("\ne=%d",e);
     
160.         printf("\nd=%d",d);
     
161.         //明文转换过程
     
162.         for(i=0;i<strlen(min_wen);i++){
     
163.                 for(j=0;j<51;j++){
     
164.                        
     
165.                         if(min_wen[i]==zimu_biao[j])
     
166.                                 m[i]=j;}
     
167.         }
     
168.         //加密过程
     
169.         for(i=0;i<strlen(min_wen);i++)
     
170.                 c[i]=mod(m[i],e,n);
     
171.         printf("\n输出密文:\n");
     
172.         for(i=0;i<strlen(min_wen);i++)
     
173.                 printf("%d",c[i]);
     
174.         //解密过程
     
175.         printf("\n输入待解密密文:\n");
     
176.         gets(mi_wen);
     
177. 
     
178.         for(i=0;i<strlen(mi_wen);i++)
     
179.                 for(j=0;j<9;j++)
     
180.                         if(mi_wen[i]==shuzi_biao[j])
     
181.                                 mw[i]=j;
     
182.                         printf("解密结果：");
     
183.                        
     
184.                         for(i=0;i<strlen(min_wen);i++)
     
185.                                 m[i]=mod(mw[i],d,n);
     
186.                         for(i=0;i<strlen(min_wen);i++)
     
187.                                 re_min_wen[i]=zimu_biao[m[i]];
     
188.                         for(i=0;i<strlen(min_wen);i++)
     
189.                                 printf("%c",re_min_wen[i]);
     
190.                         printf("\n\n");}

复制代码