信息计算2019级2班10号蔡冉平

信计2班蔡冉平

4月19日
4.1——4.4

信计2班蔡冉平

4月22日
4.4——4.7

信计2班蔡冉平

2022年4月29日

信计2班蔡冉平

1. <div class="blockcode"><blockquote> #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <time.h>
   
4. #include <string.h>
   
5.    
   
6. #define ACCURACY 5
   
7. #define SINGLE_MAX 250
   
8. #define EXPONENT_MAX 1
   
9. #define BUF_SIZE 1024
   
10. //计算a^b mod c
    
11. int modpow( long a, long b, int c) {
    
12.      int res = 1;
    
13.      while(b > 0) {
    
14.          if(b & 1) {
    
15.             res = (res * a) % c;
    
16.          }
    
17.          b = b >> 1;
    
18.          a = (a * a) % c;
    
19.      }
    
20.      return res;
    
21. }  
    
22. //计算Jacobi符号（a,n）
    
23. int jacobi(int a, int n) {
    
24.      int twos, temp;
    
25.      int mult = 1;
    
26.      while(a > 1 && a != n) {
    
27.          a = a % n;
    
28.          if(a <= 1 || a == n) break;
    
29.          twos = 0;
    
30.          while(a % 2 == 0 && ++twos) a /= 2; //减去2的倍数
    
31.          if(twos > 0 && twos % 2 == 1) mult *= (n % 8 == 1 || n % 8 == 7) * 2 - 1;
    
32.         if(a <= 1 || a == n) break;
    
33.          if(n % 4 != 1 && a % 4 != 1) mult *= -1;//翻转系数
    
34.          temp = a;
    
35.          a = n;
    
36.          n = temp;
    
37.      }
    
38.      if(a == 0) return 0;
    
39.      else if(a == 1) return mult;
    
40.      else return 0;
    
41. }
    
42. //检查a是否为n的欧拉见证
    
43. int solovayPrime(int a, int n) {
    
44.     int x = jacobi(a, n);
    
45.      if(x == -1) x = n - 1;
    
46.      return x != 0 && modpow(a, (n - 1)/2, n) == x;
    
47. }
    
48. //用k的精度检查n是否可能是素数
    
49. int probablePrime(int n, int k) {
    
50.      if(n == 2) return 1;
    
51.      else if(n % 2 == 0 || n == 1) return 0;
    
52.      while(k-- > 0) {
    
53.          if(!solovayPrime(rand() % (n - 2) + 2, n)) return 0;
    
54.      }
    
55.      return 1;
    
56. }
    
57. // 在3和（n-1）之间找一个随机素数
    
58. int randPrime(int n) {
    
59.      int prime = rand() % n;
    
60.      n += n % 2;
    
61.      prime += 1 - prime % 2;
    
62.      while(1) {
    
63.          if(probablePrime(prime, ACCURACY)) return prime;
    
64.          prime = (prime + 2) % n;
    
65.      }
    
66. }
    
67. //计算gcd（a,b）
    
68. int gcd(int a, int b) {
    
69.      int temp;
    
70.      while(b != 0) {
    
71.          temp = b;
    
72.          b = a % b;
    
73.          a = temp;
    
74.      }
    
75.      return a;
    
76. }
    
77. 
    
78. //在3和n-1之间找到随机指数x，使得gcd(x,phi)=1，这种分布同样不接近制服
    
79.   int randExponent(int phi, int n) {
    
80.      int e = rand() % n;
    
81.      while(1) {
    
82.         if(gcd(e, phi) == 1) return e;
    
83.          e = (e + 1) % n;
    
84.         if(e <= 2) e = 3;
    
85.      }
    
86. }
    
87. 
    
88. // 用扩展欧几里得法计算n^-1 mod m
    
89. 
    
90. int inverse(int n, int modulus) {
    
91.      int a = n, b = modulus;
    
92.     int x = 0, y = 1, x0 = 1, y0 = 0, q, temp;
    
93.     while(b != 0) {
    
94.         q = a / b;
    
95.          temp = a % b;
    
96.          a = b;
    
97.          b = temp;
    
98.          temp = x; x = x0 - q * x; x0 = temp;
    
99.         temp = y; y = y0 - q * y; y0 = temp;
    
100.      }
     
101.      if(x0 < 0) x0 += modulus;
     
102.      return x0;
     
103. }
     
104. //将文件fd读入准备加密的字节数组，数组将填充零，知道它划分每个块加密的字节数，返回读取的字节数
     
105. int readFile(FILE* fd, char** buffer, int bytes) {
     
106.      int len = 0, cap = BUF_SIZE, r;
     
107.      char buf[BUF_SIZE];
     
108.      *buffer = (char *)malloc(BUF_SIZE * sizeof(char));
     
109.     while((r = fread(buf, sizeof(char), BUF_SIZE, fd)) > 0) {
     
110.         if(len + r >= cap) {
     
111.              cap *= 2;
     
112.            *buffer = (char *)realloc(*buffer, cap);
     
113.         }
     
114.         memcpy(&(*buffer)[len], buf, r);
     
115.          len += r;
     
116.     }
     
117. //将最后一个带有零的块插入密码的信号端。 如果没有多余，则额外增加一个
     
118.      if(len + bytes - len % bytes > cap) *buffer = (char *)realloc(*buffer, len + bytes - len % bytes);
     
119.      do {
     
120.         (*buffer)[len] = '\0';
     
121.          len++;
     
122.      }
     
123.      while(len % bytes != 0);
     
124.      return len;
     
125. }
     
126. //c = m^e mod n使用公共指数和模量对消息m进行编码，c = m^e Mod n
     
127. int encode(int m, int e, int n) {
     
128.     return modpow(m, e, n);
     
129. }
     
130. //m = c^d mod n，用私有指数和公共模量解码密码c，m = c^d Mod
     
131.   int decode(int c, int d, int n) {
     
132.       return modpow(c, d, n);
     
133.   }
     
134.    
     
135. // 使用公钥（指数、模数)对给定长度的消息进行编码），得到的数组将是大小为len/字节，每个索引是由m=(m1m2*128m3*128^2.)给出的“字节”连续字符的加密，编码=m^指数mod模量
     
136. int* encodeMessage(int len, int bytes, char* message, int exponent, int modulus) {
     
137.      int *encoded = (int *)malloc((len/bytes) * sizeof(int));
     
138.     int x, i, j;
     
139.     for(i = 0; i < len; i += bytes) {
     
140.         x = 0;
     
141.         for(j = 0; j < bytes; j++) x += message[i + j] * (1 << (7 * j));
     
142.          encoded[i/bytes] = encode(x, exponent, modulus);
     
143. #ifndef MEASURE
     
144.          printf("%d ", encoded[i/bytes]);
     
145. #endif
     
146.      }
     
147.     return encoded;
     
148. }
     
149. //使用私钥（指数、模数)解码给定长度的密码）， 每个加密的数据包应该按照编码消息表示“字节”字符，返回的消息大小为len*字节。
     
150. 
     
151. int* decodeMessage(int len, int bytes, int* cryptogram, int exponent, int modulus) {
     
152.      int *decoded = (int *)malloc(len * bytes * sizeof(int));
     
153.     int x, i, j;
     
154.     for(i = 0; i < len; i++) {
     
155.         x = decode(cryptogram[i], exponent, modulus);
     
156.         for(j = 0; j < bytes; j++) {
     
157.             decoded[i*bytes + j] = (x >> (7 * j)) % 128;
     
158. #ifndef MEASURE
     
159.             if(decoded[i*bytes + j] != '\0') printf("%c", decoded[i*bytes + j]);
     
160. #endif
     
161.          }
     
162.     }
     
163.     return decoded;
     
164. }
     
165.   //系统降级的主要方法。 设置素数p，q，并开始编码和解码“text.txt”中给出的消息；
     
166. int main(void) {
     
167.      int p, q, n, phi, e, d, bytes, len;
     
168.     int *encoded, *decoded;
     
169.     char *buffer;
     
170.    FILE *f;
     
171.      srand(time(NULL));
     
172.      while(1) {
     
173.         p = randPrime(SINGLE_MAX);
     
174.         printf("生成第一个随机素数, p = %d ", p);
     
175.         getchar();
     
176.         q = randPrime(SINGLE_MAX);
     
177.                 printf("生成第二个随机素数, q = %d  ", q);
     
178.       getchar();
     
179.       n = p*q;
     
180.        printf("计算p和q的乘积n, n = p * q = %d ", n);
     
181.         if(n < 128) {
     
182.             printf("模数小于 128，不能编码单个字节。 再试一次\n");
     
183.             getchar();
     
184.         }
     
185.         else break;
     
186.      }
     
187.    if(n >> 21) bytes = 3;
     
188.     else if(n >> 14) bytes = 2;
     
189.     else bytes = 1;
     
190.      getchar();
     
191.     phi = (p - 1) * (q - 1);
     
192.     printf("计算欧拉函数的值phi, phi = %d ", phi);
     
193.    getchar();
     
194.    e = randExponent(phi, EXPONENT_MAX);
     
195.    printf("选取一个随机素数e, e = %d \n获得公钥 (%d, %d)  ", e, e, n);
     
196.     getchar();
     
197.     d = inverse(e, phi);
     
198.      printf("计算模反元素d, d = %d \n获得密钥 (%d, %d)  ", d, d, n);
     
199.      getchar();
     
200.    printf("打开文件 “text.txt” 用于读取信息");
     
201.     f = fopen("text.txt", "r");
     
202.     if(f == NULL) {
     
203.         printf("无法打开文件 “text.txt” 它存在吗？\n");
     
204.         return EXIT_FAILURE;
     
205.      }
     
206.      len = readFile(f, &buffer, bytes);
     
207.    fclose(f);
     
208.    printf("文件 “text.txt” 读取成功, 读取到%d字节. 以%d字节的字节流编码", len, bytes);
     
209.     getchar();
     
210.     printf("加密得密文为：\n");
     
211.     encoded = encodeMessage(len, bytes, buffer, e, n);
     
212.     printf("编码成功完成 \n");
     
213.     getchar();
     
214.    printf("正在解码编码的信息 .........\n ");
     
215.    getchar();
     
216.     printf("解码得明文为：\n");
     
217.     decoded = decodeMessage(len/bytes, bytes, encoded, d, n);
     
218.         printf("\n");
     
219.     free(encoded);
     
220.     free(decoded);
     
221.     free(buffer);
     
222.     return EXIT_SUCCESS;
     
223. }

复制代码

信计2班蔡冉平

2022年5月3日
4.8—4.11