信息计算2019级2班17号戴隆俊

戴隆俊

1. package kl;

复制代码

1. package kl;
   
2. 
   
3. import java.math.BigInteger;
   
4. 
   
5. public class Prime {
   
6.         public boolean sushu(double n) {
   
7.                 // 判断素数
   
8.                 boolean isPrime = true;
   
9.                 // 如果n大于2 继续判断 否则 isPrime的值不变 2素数
   
10.                 if (n > 2) {
    
11.                         // 如果n是大于2的偶数 认定不是素数 修改变量值为false
    
12.                         if (n % 2 == 0) {
    
13. 
    
14.                                 isPrime = false;
    
15.                         } else {
    
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. 
    
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. 
    
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. 
    
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. }
    
82. package kl;
    
83. 
    
84. import java.math.BigInteger;
    
85. import java.util.ArrayList;
    
86. import java.util.Scanner;
    
87. 
    
88. public class RSA {
    
89.         static BigInteger x, y;
    
90. 
    
91.         public static boolean fun(BigInteger x, BigInteger y) {
    
92.                 BigInteger t;
    
93.                 while (!(y.equals(new BigInteger("0")))) {
    
94.                         t = x;
    
95.                         x = y;
    
96.                         y = t.mod(y);
    
97.                 }
    
98.                 if (x.equals(new BigInteger("1")))
    
99.                         return false;
    
100.                 else
     
101.                         return true;
     
102.         }
     
103. 
     
104.         public static BigInteger siyue(BigInteger a, BigInteger b) {
     
105.                 BigInteger temp;
     
106.                 if (b.equals(new BigInteger("0"))) {
     
107.                         x = new BigInteger("1");
     
108.                         y = new BigInteger("0");
     
109.                         return x;
     
110.                 }
     
111.                 siyue(b, a.mod(b));
     
112.                 temp = x;
     
113.                 x = y;
     
114.                 y = temp.subtract((a.divide(b).multiply(y)));
     
115.                 return x;
     
116.         }
     
117. 
     
118.         public static double entropy(String mess) {
     
119.                 ArrayList<Node> jieguo = new ArrayList<Node>();
     
120.                 jieguo.clear();
     
121.                 double num = mess.length();
     
122.                 for (int i = 0; i < num; i++) {
     
123.                         boolean flag_exit = true;
     
124.                         for (int j = 0; j < jieguo.size(); j++) {
     
125.                                 if (jieguo.get(j).getalpha() == mess.charAt(i)) {
     
126.                                         flag_exit = false;
     
127.                                         jieguo.get(j).setp(jieguo.get(j).getp() + 1 / num);
     
128.                                 }
     
129.                         }
     
130.                         if (flag_exit)
     
131.                                 jieguo.add(new Node(1 / num, mess.charAt(i)));
     
132.                 }
     
133.                 /** 计算熵 */
     
134.                 double entropy = 0;
     
135.                 for (int i = 0; i < jieguo.size(); i++) {
     
136.                         double p1 = jieguo.get(i).getp();
     
137.                         entropy += (-p1 * (Math.log(p1) / Math.log(2)));
     
138.                 }
     
139.                 return entropy;
     
140.         }
     
141. 
     
142.         public static void main(String[] args) {
     
143.                 BigInteger p = null;
     
144.                 BigInteger e, d, n, t, c;
     
145.                 BigInteger q = null;
     
146.                 for (int i = 0; i < 2; i++) {
     
147.                         int numDigits;
     
148.                         Prime pri = new Prime();
     
149.                         try {
     
150.                                 numDigits = Integer.parseInt("15");
     
151.                         } catch (Exception e1) {
     
152.                                 numDigits = 128;
     
153.                         }
     
154.                         BigInteger start = pri.bigRandom(numDigits);
     
155.                         BigInteger big = pri.nextPrime(start);
     
156.                         if (i == 0)
     
157.                                 p = big;
     
158.                         else
     
159.                                 q = big;
     
160.                 }
     
161.                 Scanner input = new Scanner(System.in);
     
162.                 n = p.multiply(q);
     
163.                 t = p.subtract(new BigInteger("1")).multiply(
     
164.                                 q.subtract(new BigInteger("1")));
     
165.                 int numDigits;
     
166.                 Prime pri = new Prime();
     
167.                 try {
     
168.                         numDigits = Integer.parseInt("15");
     
169.                 } catch (Exception e1) {
     
170.                         numDigits = 128;
     
171.                 }
     
172.                 BigInteger start = pri.bigRandom(numDigits);
     
173.                 BigInteger big = pri.nextPrime(start);
     
174.                 e = big;
     
175.                 while (e.compareTo(t) == 1 || fun(e, t)) {
     
176.                         System.out.println("e不合要求，请重新产生" + (e.compareTo(t) == 1)
     
177.                                         + fun(e, t));
     
178.                         pri = new Prime();
     
179.                         try {
     
180.                                 numDigits = Integer.parseInt("15");
     
181.                         } catch (Exception e1) {
     
182.                                 numDigits = 128;
     
183.                         }
     
184.                         start = pri.bigRandom(numDigits);
     
185.                         big = pri.nextPrime(start);
     
186.                         e = big;
     
187.                 }
     
188.                 // 求出私钥d
     
189.                 d = siyue(e, t);
     
190.                 System.out.println("由计算机随机产生2个素数p,q，分别如下:");
     
191.                 System.out.println(p);
     
192.                 System.out.println(q);
     
193.                 System.out.println("计算得到的n:");
     
194.                 System.out.println(n);
     
195.                 System.out.println("计算得到的t:");
     
196.                 System.out.println(t);
     
197.                 System.out.println("随机产生的公钥：");
     
198.                 System.out.println(e);
     
199.                 System.out.println("由扩展的欧几里德算法求得私钥：");
     
200.                 System.out.println(d);
     
201.                 while (true) {
     
202.                         System.out.println("请输入明文：");
     
203.                         String mess = input.nextLine();
     
204.                         //
     
205.                         BigInteger m = new BigInteger(mess.getBytes());// 把字串转成一个BigInteger对象
     
206.                         System.out.println("明文的大整数表示形式：" + m);
     
207.                         /** 调用函数计算信息，统计信息 */
     
208.                         mess = m.toString();
     
209.                         System.out.println("计算得明文熵：" + entropy(mess));
     
210.                         // 修改第一位，+1
     
211.                         c = m.modPow(e, n);// JAVA中的方法
     
212.                         System.out.println("密文的大整数表示形式：" + c);
     
213.                         System.out.println("计算得密文熵：" + entropy(c.toString()));
     
214.                         System.out.println("密文的字符串表示形式：" + new String(c.toByteArray()));
     
215.                         m = c.modPow(d, n);
     
216.                         System.out.println("解密得到明文的大整数表示形式：" + c);
     
217.                         String str = new String(m.toByteArray());// 把返回的结果还原成一个字串
     
218.                         System.out.println("解密得到明文为：" + str);
     
219.                 }
     
220.         }
     
221. }

复制代码

RSA公开密钥密码体制是一种使用不同的加密秘钥与解密密钥，“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体质。它通常是先生成一对RSA密钥，其中之一是保密密钥，有用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册。

戴隆俊

mooc学习

戴隆俊

  大数RSA算法的实现
一.原理：
1. 随意选择两个大的质数p和q，p不等于q，计算N = pq.
2. 根据欧拉函数，求得r=φ(N)=φ(p)φ(q)=(p-1)(q-1)。
3. 选择一个小于r的整数e,是e与r互质。并求得e关于r的模反元素，命名为d。(求d令ed≡1(mod r))。(模反元素存在，当且仅当e与r互质）
4. 将p和q的记录销毁。

戴隆俊

1. package kl;
   
2. 
   
3. import java.math.BigInteger;
   
4. 
   
5. public class Prime {
   
6.         public boolean sushu(double n) {
   
7.                 // 判断素数
   
8.                 boolean isPrime = true;
   
9.                 // 如果n大于2 继续判断 否则 isPrime的值不变 2素数
   
10.                 if (n > 2) {
    
11.                         // 如果n是大于2的偶数 认定不是素数 修改变量值为false
    
12.                         if (n % 2 == 0) {
    
13. 
    
14.                                 isPrime = false;
    
15.                         } else {
    
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. 
    
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. 
    
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. 
    
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. }
    
82. package kl;
    
83. 
    
84. import java.math.BigInteger;
    
85. import java.util.ArrayList;
    
86. import java.util.Scanner;
    
87. 
    
88. public class RSA {
    
89.         static BigInteger x, y;
    
90. 
    
91.         public static boolean fun(BigInteger x, BigInteger y) {
    
92.                 BigInteger t;
    
93.                 while (!(y.equals(new BigInteger("0")))) {
    
94.                         t = x;
    
95.                         x = y;
    
96.                         y = t.mod(y);
    
97.                 }
    
98.                 if (x.equals(new BigInteger("1")))
    
99.                         return false;
    
100.                 else
     
101.                         return true;
     
102.         }
     
103. 
     
104.         public static BigInteger siyue(BigInteger a, BigInteger b) {
     
105.                 BigInteger temp;
     
106.                 if (b.equals(new BigInteger("0"))) {
     
107.                         x = new BigInteger("1");
     
108.                         y = new BigInteger("0");
     
109.                         return x;
     
110.                 }
     
111.                 siyue(b, a.mod(b));
     
112.                 temp = x;
     
113.                 x = y;
     
114.                 y = temp.subtract((a.divide(b).multiply(y)));
     
115.                 return x;
     
116.         }
     
117. 
     
118.         public static double entropy(String mess) {
     
119.                 ArrayList<Node> jieguo = new ArrayList<Node>();
     
120.                 jieguo.clear();
     
121.                 double num = mess.length();
     
122.                 for (int i = 0; i < num; i++) {
     
123.                         boolean flag_exit = true;
     
124.                         for (int j = 0; j < jieguo.size(); j++) {
     
125.                                 if (jieguo.get(j).getalpha() == mess.charAt(i)) {
     
126.                                         flag_exit = false;
     
127.                                         jieguo.get(j).setp(jieguo.get(j).getp() + 1 / num);
     
128.                                 }
     
129.                         }
     
130.                         if (flag_exit)
     
131.                                 jieguo.add(new Node(1 / num, mess.charAt(i)));
     
132.                 }
     
133.                 /** 计算熵 */
     
134.                 double entropy = 0;
     
135.                 for (int i = 0; i < jieguo.size(); i++) {
     
136.                         double p1 = jieguo.get(i).getp();
     
137.                         entropy += (-p1 * (Math.log(p1) / Math.log(2)));
     
138.                 }
     
139.                 return entropy;
     
140.         }
     
141. 
     
142.         public static void main(String[] args) {
     
143.                 BigInteger p = null;
     
144.                 BigInteger e, d, n, t, c;
     
145.                 BigInteger q = null;
     
146.                 for (int i = 0; i < 2; i++) {
     
147.                         int numDigits;
     
148.                         Prime pri = new Prime();
     
149.                         try {
     
150.                                 numDigits = Integer.parseInt("15");
     
151.                         } catch (Exception e1) {
     
152.                                 numDigits = 128;
     
153.                         }
     
154.                         BigInteger start = pri.bigRandom(numDigits);
     
155.                         BigInteger big = pri.nextPrime(start);
     
156.                         if (i == 0)
     
157.                                 p = big;
     
158.                         else
     
159.                                 q = big;
     
160.                 }
     
161.                 Scanner input = new Scanner(System.in);
     
162.                 n = p.multiply(q);
     
163.                 t = p.subtract(new BigInteger("1")).multiply(
     
164.                                 q.subtract(new BigInteger("1")));
     
165.                 int numDigits;
     
166.                 Prime pri = new Prime();
     
167.                 try {
     
168.                         numDigits = Integer.parseInt("15");
     
169.                 } catch (Exception e1) {
     
170.                         numDigits = 128;
     
171.                 }
     
172.                 BigInteger start = pri.bigRandom(numDigits);
     
173.                 BigInteger big = pri.nextPrime(start);
     
174.                 e = big;
     
175.                 while (e.compareTo(t) == 1 || fun(e, t)) {
     
176.                         System.out.println("e不合要求，请重新产生" + (e.compareTo(t) == 1)
     
177.                                         + fun(e, t));
     
178.                         pri = new Prime();
     
179.                         try {
     
180.                                 numDigits = Integer.parseInt("15");
     
181.                         } catch (Exception e1) {
     
182.                                 numDigits = 128;
     
183.                         }
     
184.                         start = pri.bigRandom(numDigits);
     
185.                         big = pri.nextPrime(start);
     
186.                         e = big;
     
187.                 }
     
188.                 // 求出私钥d
     
189.                 d = siyue(e, t);
     
190.                 System.out.println("由计算机随机产生2个素数p,q，分别如下:");
     
191.                 System.out.println(p);
     
192.                 System.out.println(q);
     
193.                 System.out.println("计算得到的n:");
     
194.                 System.out.println(n);
     
195.                 System.out.println("计算得到的t:");
     
196.                 System.out.println(t);
     
197.                 System.out.println("随机产生的公钥：");
     
198.                 System.out.println(e);
     
199.                 System.out.println("由扩展的欧几里德算法求得私钥：");
     
200.                 System.out.println(d);
     
201.                 while (true) {
     
202.                         System.out.println("请输入明文：");
     
203.                         String mess = input.nextLine();
     
204.                         //
     
205.                         BigInteger m = new BigInteger(mess.getBytes());// 把字串转成一个BigInteger对象
     
206.                         System.out.println("明文的大整数表示形式：" + m);
     
207.                         /** 调用函数计算信息，统计信息 */
     
208.                         mess = m.toString();
     
209.                         System.out.println("计算得明文熵：" + entropy(mess));
     
210.                         // 修改第一位，+1
     
211.                         c = m.modPow(e, n);// JAVA中的方法
     
212.                         System.out.println("密文的大整数表示形式：" + c);
     
213.                         System.out.println("计算得密文熵：" + entropy(c.toString()));
     
214.                         System.out.println("密文的字符串表示形式：" + new String(c.toByteArray()));
     
215.                         m = c.modPow(d, n);
     
216.                         System.out.println("解密得到明文的大整数表示形式：" + c);
     
217.                         String str = new String(m.toByteArray());// 把返回的结果还原成一个字串
     
218.                         System.out.println("解密得到明文为：" + str);
     
219.                 }
     
220.         }
     
221. }

复制代码