信息计算2019级1班13号郝怀宇

郝怀宇

慕课截图

郝怀宇

慕课截图

郝怀宇

慕课截图

郝怀宇

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. 
   
4. int long_n(int n);
   
5. int shuru(char* arr, int k, char* wei, int is_first);
   
6. void jiami(char* arr, int k, int e, int n);
   
7. 
   
8. int shuru(char* arr, int k, char* wei, int is_first)
   
9. {
   
10.         int i;
    
11.         char ch;
    
12.      
    
13.         if (is_first == 1)
    
14.                 ch = getchar();
    
15.         else
    
16.                 ch = *wei;
    
17.         for (i = 0; (i < k) && (ch != '\n'); i++)
    
18.         {
    
19.                 arr[i] = ch;
    
20.                 ch = getchar();
    
21.         }
    
22.         *wei = ch;
    
23.         for (i = i; i < k; i++)
    
24.                 arr[i] = 'a';  
    
25.         if (ch == '\n')  
    
26.                 return 0;
    
27.         else
    
28.                 return 1;
    
29. }
    
30. 
    
31. 
    
32. void jiami(char* arr, int k, int e, int n)
    
33. {
    
34.         int m = 0, c = 1, i, j, t = 0, shu, temp, num = 0;
    
35.         int* array;
    
36.       
    
37.         for (i = 0; i < k; i++)
    
38.         {
    
39.                 temp = 1;
    
40.                 for (j = 0; j < (k - i - 1) * 2; j++)
    
41.                         temp = temp * 10;
    
42.                 shu = (int)arr[i] - 97;
    
43.                 m = m + temp * shu;
    
44.         }
    
45.         temp = e;
    
46.      
    
47.         do {
    
48.                 temp = temp / 2;
    
49.                 num++;
    
50.         } while (temp != 0);
    
51.         array = (int*)malloc(sizeof(int) * k);
    
52.         temp = e;
    
53.       
    
54.         for (i = 0; i < num; i++)
    
55.         {
    
56.                 array[i] = temp % 2;
    
57.                 temp = temp / 2;
    
58.         }
    
59.       
    
60.         for (i = num - 1; i >= 0; i--)
    
61.         {
    
62.                 t = t * 2;
    
63.                 temp = c * c;
    
64.                 if (temp > n)
    
65.                 {
    
66.                         for (j = 0; temp - n * j >= 0; j++);
    
67.                         j--;
    
68.                         c = temp - n * j;
    
69.                 }
    
70.                 else
    
71.                         c = temp;
    
72.                 if (array[i] == 1)
    
73.                 {
    
74.                         t = t + 1;
    
75.                         temp = c * m;
    
76.                         if (temp > n)
    
77.                         {
    
78.                                 for (j = 0; temp - n * j >= 0; j++);
    
79.                                 j--;
    
80.                                 c = temp - n * j;
    
81.                         }
    
82.                         else
    
83.                                 c = temp;
    
84.                 }
    
85. 
    
86.                 e = e / 2;
    
87.         }
    
88.         temp = c;
    
89.         i = 0;
    
90.       
    
91.         do {
    
92.                 temp = temp / 10;
    
93.                 i++;
    
94.         } while (temp != 0);
    
95.         for (i; i < num; i++)
    
96.                 printf("0");
    
97.         printf("%d", c);
    
98. }
    
99. 
    
100. int long_n(int n)
     
101. {
     
102.         int temp, i, j, k, shi, comp = 0;
     
103.         temp = n;
     
104. 
     
105.         for (i = 1; temp / 10 != 0; i++)
     
106.         {
     
107.                 temp = temp / 10;
     
108.         }
     
109.         temp = i;
     
110.    
     
111.         if (i % 2 != 0)
     
112.         {
     
113.                 i = i - 1;
     
114.                 return i;
     
115.         }
     
116.    
     
117.         else
     
118.         {
     
119.                 for (j = 0; j < i / 2; j++)
     
120.                 {
     
121.                         shi = 1;
     
122.                         for (k = 0; k < temp - 2; k++)
     
123.                                 shi = shi * 10;
     
124.                         comp = comp + shi * 25;
     
125.                         temp = temp - 2;
     
126.                 }
     
127.                 if (comp <= n)
     
128.                         return i;
     
129.                 else
     
130.                 {
     
131.                         i = i - 2;
     
132.                         return i;
     
133.                 }
     
134.         }
     
135. }
     
136. 
     
137. 
     
138. int main()
     
139. {
     
140.         int p, q, e, d, n, fai_n, k, i, is_first = 1;
     
141.         char ch, * arr, wei = 'a';
     
142.         printf("请输入p、q、e值，用空格间隔开\n");
     
143.         scanf_s("%d%d%d", &p, &q, &e);
     
144.         n = p * q;
     
145.         fai_n = (p - 1) * (q - 1);   //Φ(n)
     
146.         for (k = 0; (k * n + 1) % e != 0; k++);
     
147.         if ((k * n + 1) % e == 0)
     
148.                 d = (k * n + 1) / e;  //d * e ≡ 1 (mod Φ(n))
     
149.         k = long_n(n);
     
150.         k = k / 2;  
     
151.         ch = getchar();
     
152.         arr = (char*)malloc(sizeof(char) * k);  
     
153.         printf("请输入明文\n");
     
154.         while (1)
     
155.         {
     
156.                 i = shuru(arr, k, &wei, is_first);  
     
157.                 is_first = 0;  
     
158.                 jiami(arr, k, e, n);  
     
159.                 if (i == 0)  
     
160.                         break;
     
161.         }
     
162.         printf("\n");
     
163.         return 0;
     
164. }

复制代码

郝怀宇

大数改进

1. import java.math.BigInteger;
   
2. import java.util.Random;
   
3. import java.util.Scanner;
   
4. 
   
5. public class RSA大数版本 {
   
6. 
   
7.         public static BigInteger Mod_ni(BigInteger a, BigInteger b) {
   
8.                 BigInteger zero = new BigInteger("0");
   
9.                 a = a.subtract(b.multiply(a.divide(b))); // a = a - b * (a / b)
   
10.                 int i = 0;
    
11.                 BigInteger bb = b;
    
12.                 BigInteger s[] = new BigInteger[1024];
    
13.                 while (a.compareTo(zero) != 0) { // a != 0
    
14.                         s[i] = b.divide(a); // s[i] = b / a
    
15.                         BigInteger t = b;
    
16.                         b = a;
    
17.                         a = t.mod(a); // t % a
    
18.                         i++;
    
19.                 }
    
20.                 BigInteger y[] = new BigInteger[i];
    
21.                 y[0] = new BigInteger("1");
    
22.                 y[1] = s[0];
    
23.                 for (int j = 2; j < i; j++)
    
24.                         y[j] = (y[j - 1].multiply(s[j - 1])).add(y[j - 2]); // y[j] = y[j - 1] * s[j - 1] + y[j - 2]
    
25.                 if ((i - 1) % 2 == 1)
    
26.                         y[i - 1] = bb.subtract(y[i - 1]); // y[i - 1] = bb - y[i - 1]
    
27.                 return y[i - 1];
    
28.         }
    
29. 
    
30.         public static void main(String args[]) {
    
31.                 BigInteger one = new BigInteger("1");
    
32.                 Random rnd = new Random();
    
33.                 BigInteger p = new BigInteger("1");
    
34.                 BigInteger q = new BigInteger("1");
    
35.                 p = BigInteger.probablePrime(1024, rnd);
    
36.                 q = BigInteger.probablePrime(1024, rnd);
    
37.                 BigInteger n = p.multiply(q); // n = p * q
    
38.                 BigInteger f = (p.subtract(one).multiply(q.subtract(one))); // f = (p - 1) * (q - 1)
    
39.                 BigInteger e = new BigInteger("65537");
    
40.                 while (true) {
    
41.                         e = BigInteger.probablePrime(1024, rnd);
    
42.                         if (e.compareTo(f) <= 1)
    
43.                                 break;
    
44.                 }
    
45.                 BigInteger d = Mod_ni(e, f);
    
46.                 System.out.println("n = " + n);
    
47.                 System.out.println("公钥：" + e);
    
48.                 System.out.println("私钥：" + d);
    
49. 
    
50.                 BigInteger xx, yy;
    
51.                 while (true) {
    
52.                         System.out.println("请选择功能： \n0.退出 \n1.加密\n2.解密");
    
53.                         Scanner scan1 = new Scanner(System.in);
    
54.                         int ch = scan1.nextInt();
    
55.                         if (ch == 1) {
    
56.                                 System.out.println("请输入明文：");
    
57.                                 String mingwen = new String();
    
58.                                 Scanner scan2 = new Scanner(System.in);
    
59.                                 mingwen = scan2.nextLine();
    
60.                                 byte x[] = new byte[mingwen.length()];
    
61.                                 for (int i = 0; i < mingwen.length(); i++)
    
62.                                         x[i] = Byte.valueOf((byte) mingwen.charAt(i));                        
    
63.                                 xx = new BigInteger(x);  // 字节数组转大整型
    
64.                                 xx = xx.modPow(e, n);  // xx^e mod n
    
65.                                 System.out.println("密文为：" + xx);
    
66.                         } else if (ch == 2) {
    
67.                                 System.out.println("请输入密文：");
    
68.                                 String miwen = new String();
    
69.                                 Scanner scan3 = new Scanner(System.in);
    
70.                                 miwen = scan3.nextLine();
    
71.                                 yy = new BigInteger(miwen);
    
72.                                 yy = yy.modPow(d, n);   // yy^d mod n
    
73.                                 byte[] y = yy.toByteArray(); // 大整型转字节数组
    
74.                                 System.out.print("明文为:");
    
75.                                 for (int i = 0; i < y.length; ++i)
    
76.                                         System.out.print((char) y[i]);
    
77.                                 System.out.print('\n');
    
78.                         } else
    
79.                                 break;
    
80.                 }
    
81. 
    
82.         }
    
83. }
    

复制代码