信息计算2019级1班10号张夏楠

张夏楠

张夏楠

张夏楠

张夏楠

RSA.java:

1. package club;
   
2. import java.math.BigInteger;
   
3. import java.util.ArrayList;
   
4. import java.util.Scanner;
   
5. 
   
6. public class RSA {
   
7.         static BigInteger x, y;
   
8. 
   
9.         public static boolean fun(BigInteger x, BigInteger y) {
   
10.                 BigInteger t;
    
11.                 while (!(y.equals(new BigInteger("0")))) {
    
12.                         t = x;
    
13.                         x = y;
    
14.                         y = t.mod(y);
    
15.                 }
    
16.                 if (x.equals(new BigInteger("1")))
    
17.                         return false;
    
18.                 else
    
19.                         return true;
    
20.         }
    
21. 
    
22.         public static BigInteger siyue(BigInteger a, BigInteger b) {
    
23.                 BigInteger temp;
    
24.                 if (b.equals(new BigInteger("0"))) {
    
25.                         x = new BigInteger("1");
    
26.                         y = new BigInteger("0");
    
27.                         return x;
    
28.                 }
    
29.                 siyue(b, a.mod(b));
    
30.                 temp = x;
    
31.                 x = y;
    
32.                 y = temp.subtract((a.divide(b).multiply(y)));
    
33.                 return x;
    
34.         }
    
35. 
    
36.         public static double entropy(String mess) {
    
37.                 ArrayList<Node> jieguo = new ArrayList<Node>();
    
38.                 jieguo.clear();
    
39.                 double num = mess.length();
    
40.                 for (int i = 0; i < num; i++) {
    
41.                         boolean flag_exit = true;
    
42.                         for (int j = 0; j < jieguo.size(); j++) {
    
43.                                 if (jieguo.get(j).getalpha() == mess.charAt(i)) {
    
44.                                         flag_exit = false;
    
45.                                         jieguo.get(j).setp(jieguo.get(j).getp() + 1 / num);
    
46.                                 }
    
47.                         }
    
48.                         if (flag_exit)
    
49.                                 jieguo.add(new Node(1 / num, mess.charAt(i)));
    
50.                 }
    
51.                 /** 计算熵 */
    
52.                 double entropy = 0;
    
53.                 for (int i = 0; i < jieguo.size(); i++) {
    
54.                         double p1 = jieguo.get(i).getp();
    
55.                         entropy += (-p1 * (Math.log(p1) / Math.log(2)));
    
56.                 }
    
57.                 return entropy;
    
58.         }
    
59. 
    
60.         public static void main(String[] args) {
    
61.                 BigInteger p = null;
    
62.                 BigInteger e, d, n, t, c;
    
63.                 BigInteger q = null;
    
64.                 for (int i = 0; i < 2; i++) {
    
65.                         int numDigits;
    
66.                         Prime pri = new Prime();
    
67.                         try {
    
68.                                 numDigits = Integer.parseInt("15");
    
69.                         } catch (Exception e1) {
    
70.                                 numDigits = 128;
    
71.                         }
    
72.                         BigInteger start = pri.bigRandom(numDigits);
    
73.                         BigInteger big = pri.nextPrime(start);
    
74.                         if (i == 0)
    
75.                                 p = big;
    
76.                         else
    
77.                                 q = big;
    
78.                 }
    
79.                 Scanner input = new Scanner(System.in);
    
80.                 n = p.multiply(q);
    
81.                 t = p.subtract(new BigInteger("1")).multiply(
    
82.                                 q.subtract(new BigInteger("1")));
    
83.                 int numDigits;
    
84.                 Prime pri = new Prime();
    
85.                 try {
    
86.                         numDigits = Integer.parseInt("15");
    
87.                 } catch (Exception e1) {
    
88.                         numDigits = 128;
    
89.                 }
    
90.                 BigInteger start = pri.bigRandom(numDigits);
    
91.                 BigInteger big = pri.nextPrime(start);
    
92.                 e = big;
    
93.                 while (e.compareTo(t) == 1 || fun(e, t)) {
    
94.                         System.out.println("e不合要求，请重新产生" + (e.compareTo(t) == 1)
    
95.                                         + fun(e, t));
    
96.                         pri = new Prime();
    
97.                         try {
    
98.                                 numDigits = Integer.parseInt("15");
    
99.                         } catch (Exception e1) {
    
100.                                 numDigits = 128;
     
101.                         }
     
102.                         start = pri.bigRandom(numDigits);
     
103.                         big = pri.nextPrime(start);
     
104.                         e = big;
     
105.                 }
     
106.                 // 求出私钥d
     
107.                 d = siyue(e, t);
     
108.                 System.out.println("由计算机随机产生2个素数p,q，分别如下:");
     
109.                 System.out.println(p);
     
110.                 System.out.println(q);
     
111.                 System.out.println("计算得到的n:");
     
112.                 System.out.println(n);
     
113.                 System.out.println("计算得到的t:");
     
114.                 System.out.println(t);
     
115.                 System.out.println("随机产生的公钥：");
     
116.                 System.out.println(e);
     
117.                 System.out.println("由扩展的欧几里德算法求得私钥：");
     
118.                 System.out.println(d);
     
119.                 while (true) {
     
120.                         System.out.println("请输入明文：");
     
121.                         String mess = input.nextLine();
     
122.                         //
     
123.                         BigInteger m = new BigInteger(mess.getBytes());// 把字串转成一个BigInteger对象
     
124.                         System.out.println("明文的大整数表示形式：" + m);
     
125.                         /** 调用函数计算信息，统计信息 */
     
126.                         mess = m.toString();
     
127.                         System.out.println("计算得明文熵：" + entropy(mess));
     
128.                         // 修改第一位，+1
     
129.                         c = m.modPow(e, n);// JAVA中的方法
     
130.                         System.out.println("密文的大整数表示形式：" + c);
     
131.                         System.out.println("计算得密文熵：" + entropy(c.toString()));
     
132.                         m = c.modPow(d, n);
     
133.                         System.out.println("解密得到明文的大整数表示形式：" + c);
     
134.                         String str = new String(m.toByteArray());// 把返回的结果还原成一个字串
     
135.                         System.out.println("解密得到明文为：" + str);
     
136.                 }
     
137.         }
     
138.        
     
139. }
     

复制代码

Node.java:

1. package club;
   
2. 
   
3. public class Node {
   
4.         private double p;// 记录概率
   
5.         private char alpha;// 记录对应的字母
   
6. 
   
7.         public Node(double p, char alpha) {
   
8.                 this.p = p;
   
9.                 this.alpha = alpha;
   
10.         }
    
11. 
    
12.         public void setp(double p) {
    
13.                 this.p = p;
    
14.         }
    
15. 
    
16.         public void setalpha(char a) {
    
17.                 this.alpha = a;
    
18.         }
    
19. 
    
20.         public double getp() {
    
21.                 return p;
    
22.         }
    
23. 
    
24.         public char getalpha() {
    
25.                 return alpha;
    
26.         }
    
27. }

复制代码

Prime.java:

1. package club;
   
2. import java.math.BigInteger;
   
3. 
   
4. public class Prime {
   
5.         public boolean sushu(double n) {
   
6.                 // 判断素数
   
7.                 boolean isPrime = true;
   
8.                 // 如果n大于2 继续判断 否则 isPrime的值不变 2素数
   
9.                 if (n > 2) {
   
10.                         // 如果n是大于2的偶数 认定不是素数 修改变量值为false
    
11.                         if (n % 2 == 0) {
    
12.                                 isPrime = false;
    
13.                         } else {
    
14.                                 // 循环判断如果找到一个可以整除的数 则判定不是素数跳出循环 因为是判断奇数 因此 2 4 6 ...?
    
15.                                 // 不用考虑 循环递增2 即?3 5 7 ...
    
16.                                 for (int i = 3; i <= (int) Math.sqrt(n); i += 2) {
    
17.                                         if (n % i == 0) {
    
18.                                                 isPrime = false;
    
19.                                                 break;
    
20.                                         }
    
21.                                 }
    
22.                         }
    
23. 
    
24.                 }
    
25.                 return isPrime;
    
26.         }
    
27. 
    
28.         private static final BigInteger ZERO = BigInteger.ZERO;
    
29.         private static final BigInteger ONE = BigInteger.ONE;
    
30.         private static final BigInteger TWO = new BigInteger("2");
    
31.         private static final int ERR_VAL = 100;
    
32. 
    
33.         public BigInteger nextPrime(BigInteger start) {
    
34.                 // 产生一个比给定大整数 start 大的素数，错误率低于 1/2 的 ERR_VAL 次方
    
35.                 if (isEven(start))
    
36.                         start = start.add(ONE);
    
37.                 else
    
38.                         start = start.add(TWO);
    
39.                 if (start.isProbablePrime(ERR_VAL))
    
40.                         return (start);
    
41.                 else
    
42.                         // 采用递归方式（递归的层数会是个天文数字吗？）
    
43.                         return (nextPrime(start));
    
44.         }
    
45. 
    
46.         private static boolean isEven(BigInteger n) {
    
47.                 // 测试一个大整数是否为偶数
    
48.                 return (n.mod(TWO).equals(ZERO));
    
49.         }
    
50. 
    
51.         public BigInteger bigRandom(int numDigits) {
    
52.                 // 产生一个随机大整数，各位上的数字都是随机产生的，首位不为 0
    
53.                 StringBuffer s = new StringBuffer("");
    
54.                 for (int i = 0; i < numDigits; i++)
    
55.                         if (i == 0)
    
56.                                 s.append(randomDigit(false));
    
57.                         else
    
58.                                 s.append(randomDigit(true));
    
59.                 return (new BigInteger(s.toString()));
    
60.         }
    
61. 
    
62.         private StringBuffer randomDigit(boolean isZeroOK) {
    
63.                 // 产生一个随机的数字（字符串形式的），isZeroOK 决定这个数字是否可以为 0
    
64.                 int index;
    
65.                 if (isZeroOK)
    
66.                         index = (int) Math.floor(Math.random() * 10);
    
67.                 else
    
68.                         index = 1 + (int) Math.floor(Math.random() * 9);
    
69.                 return (digits[index]);
    
70.         }
    
71. 
    
72.         private static StringBuffer[] digits = { new StringBuffer("0"),
    
73.                         new StringBuffer("1"), new StringBuffer("2"),
    
74.                         new StringBuffer("3"), new StringBuffer("4"),
    
75.                         new StringBuffer("5"), new StringBuffer("6"),
    
76.                         new StringBuffer("7"), new StringBuffer("8"), new StringBuffer("9") };
    
77. 
    
78.         public static void main(String[] args) {
    
79. 
    
80.         }
    
81. }

复制代码

运行截图：

张夏楠

张夏楠

张夏楠

1. #include <iostream>
   
2. #include <cmath>
   
3. #include <cstring>
   
4. #include <ctime>
   
5. #include <cstdlib>
   
6. using namespace std;
   
7. 
   
8. 
   
9. int Plaintext[100];//明文
   
10. long long Ciphertext[100];//密文
    
11. int n, e = 0, d;
    
12. 
    
13. //二进制转换
    
14. int BianaryTransform(int num, int bin_num[])
    
15. {
    
16. 
    
17.     int i = 0, mod = 0;
    
18. 
    
19.     //转换为二进制，逆向暂存temp[]数组中
    
20.     while (num != 0)
    
21.     {
    
22.         mod = num % 2;
    
23.         bin_num[i] = mod;
    
24.         num = num / 2;
    
25.         i++;
    
26.     }
    
27. 
    
28.     //返回二进制数的位数
    
29.     return i;
    
30. }
    
31. 
    
32. //反复平方求幂
    
33. long long Modular_Exonentiation(long long a, int b, int n)
    
34. {
    
35.     int c = 0, bin_num[1000];
    
36.     long long d = 1;
    
37.     int k = BianaryTransform(b, bin_num) - 1;
    
38. 
    
39.     for (int i = k; i >= 0; i--)
    
40.     {
    
41.         c = 2 * c;
    
42.         d = (d * d) % n;
    
43.         if (bin_num[i] == 1)
    
44.         {
    
45.             c = c + 1;
    
46.             d = (d * a) % n;
    
47.         }
    
48.     }
    
49.     return d;
    
50. }
    
51. 
    
52. //生成1000以内素数
    
53. int ProducePrimeNumber(int prime[])
    
54. {
    
55.     int c = 0, vis[1001];
    
56.     memset(vis, 0, sizeof(vis));
    
57.     for (int i = 2; i <= 1000; i++)if (!vis[i])
    
58.     {
    
59.         prime[c++] = i;
    
60.         for (int j = i * i; j <= 1000; j += i)
    
61.             vis[j] = 1;
    
62.     }
    
63. 
    
64.     return c;
    
65. }
    
66. 
    
67. 
    
68. //欧几里得扩展算法
    
69. int Exgcd(int m, int n, int& x)
    
70. {
    
71.     int x1, y1, x0, y0, y;
    
72.     x0 = 1; y0 = 0;
    
73.     x1 = 0; y1 = 1;
    
74.     x = 0; y = 1;
    
75.     int r = m % n;
    
76.     int q = (m - r) / n;
    
77.     while (r)
    
78.     {
    
79.         x = x0 - q * x1; y = y0 - q * y1;
    
80.         x0 = x1; y0 = y1;
    
81.         x1 = x; y1 = y;
    
82.         m = n; n = r; r = m % n;
    
83.         q = (m - r) / n;
    
84.     }
    
85.     return n;
    
86. }
    
87. 
    
88. //RSA初始化
    
89. void RSA_Initialize()
    
90. {
    
91.     //取出1000内素数保存在prime[]数组中
    
92.     int prime[5000];
    
93.     int count_Prime = ProducePrimeNumber(prime);
    
94. 
    
95.     //随机取两个素数p,q
    
96.     srand((unsigned)time(NULL));
    
97.     int ranNum1 = rand() % count_Prime;
    
98.     int ranNum2 = rand() % count_Prime;
    
99.     int p = prime[ranNum1], q = prime[ranNum2];
    
100. 
     
101.     n = p * q;
     
102. 
     
103.     int On = (p - 1) * (q - 1);
     
104. 
     
105. 
     
106.     //用欧几里德扩展算法求e,d
     
107.     for (int j = 3; j < On; j += 1331)
     
108.     {
     
109.         int gcd = Exgcd(j, On, d);
     
110.         if (gcd == 1 && d > 0)
     
111.         {
     
112.             e = j;
     
113.             break;
     
114.         }
     
115. 
     
116.     }
     
117. 
     
118. }
     
119. 
     
120. //RSA加密
     
121. void RSA_Encrypt()
     
122. {
     
123.     cout << "Public Key (e, n) : e = " << e << " n = " << n << '\n';
     
124.     cout << "Private Key (d, n) : d = " << d << " n = " << n << '\n' << '\n';
     
125. 
     
126.     int i = 0;
     
127.     for (i = 0; i < 100; i++)
     
128.         Ciphertext[i] = Modular_Exonentiation(Plaintext[i], e, n);
     
129. 
     
130.     cout << "Use the public key (e, n) to encrypt:" << '\n';
     
131.     for (i = 0; i < 100; i++)
     
132.         cout << Ciphertext[i] << " ";
     
133.     cout << '\n' << '\n';
     
134. }
     
135. 
     
136. //RSA解密
     
137. void RSA_Decrypt()
     
138. {
     
139.     int i = 0;
     
140.     for (i = 0; i < 100; i++)
     
141.         Ciphertext[i] = Modular_Exonentiation(Ciphertext[i], d, n);
     
142. 
     
143.     cout << "Use private key (d, n) to decrypt:" << '\n';
     
144.     for (i = 0; i < 100; i++)
     
145.         cout << Ciphertext[i] << " ";
     
146.     cout << '\n' << '\n';
     
147. }
     
148. 
     
149. 
     
150. //算法初始化
     
151. void Initialize()
     
152. {
     
153.     int i;
     
154.     srand((unsigned)time(NULL));
     
155.     for (i = 0; i < 100; i++)
     
156.         Plaintext[i] = rand() % 1000;
     
157. 
     
158.     cout << "Generate 100 random numbers:" << '\n';
     
159.     for (i = 0; i < 100; i++)
     
160.         cout << Plaintext[i] << " ";
     
161.     cout << '\n' << '\n';
     
162. }
     
163. 
     
164. int main()
     
165. {
     
166.     Initialize();
     
167. 
     
168.     while (!e)
     
169.         RSA_Initialize();
     
170. 
     
171.     RSA_Encrypt();
     
172. 
     
173.     RSA_Decrypt();
     
174. 
     
175.     return 0;
     
176. }

复制代码

运行截图：