信息计算2019级1班4号吴春滟

吴春滟

吴春滟

吴春滟

1. <b style="font-size: x-large; background-color: rgb(255, 255, 255);">大数RSA算法的实现</b>

复制代码

1. package aa;
   
2. 
   
3. public class Node {
   
4. 
   
5. 
   
6. private double p;
   
7. private char alpha;
   
8. 
   
9. public Node(double p, char alpha) {
   
10. this.p = p;
    
11. this.alpha =alpha;
    
12. }
    
13. 
    
14. public void setp(double p) {
    
15. this.p = p;
    
16. }
    
17. 
    
18. public void setalpha(char a) {
    
19. this.alpha =a;
    
20. }
    
21. 
    
22. public double getp() {
    
23. return p;
    
24. }
    
25. 
    
26. public char getalpha() {
    
27. return alpha;
    
28. }
    
29. }

复制代码

1. package aa;
   
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. }

复制代码

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

复制代码

吴春滟

吴春滟

大数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.公开整数n和e，秘密保存d；
5.将明文m（m<n，是一个整数）加密成密文c，加密算法为c=E(m)=memodn；
6.将密文c解密为明文m，解密算法为m=D(c)=cdmodn。

1. package mm;
   
2. import java.util.Random;
   
3. import java.util.Scanner;
   
4. import java.math.BigInteger;
   
5. import java.security.SecureRandom;
   
6. 
   
7. public class Rsa1 {
   
8.         private static final int ORDER = 100000;// 随机数的数量级
   
9.         private static final int MIN = 10000; // 选择的随机数的最小值
   
10. 
    
11.         public static long getPrime() { // 获取一个随机数，判断是否为素数，并用MillerRabin方法检验
    
12.                 long x = 0;
    
13.                 while (x % 2 == 0 || !MillerRabin(x, 5)) {
    
14.                         x = getRandom();
    
15.                 }
    
16.                 return x;
    
17.         }
    
18. 
    
19.         public static long getRandom() {// 随机生成一个奇数
    
20.                 long x = 3;
    
21.                 Random rd = new Random();
    
22.                 do {
    
23.                         x = rd.nextInt(ORDER);
    
24.                 } while (x < MIN || x % 2 == 0);
    
25.                 return x;
    
26.         }
    
27. 
    
28.         public static boolean MillerRabin(long n, int t) {
    
29.                 for (int i = 0; i < t; i++)
    
30.                         if (!isPrime(n))
    
31.                                 return false;
    
32.                 return true;
    
33.         }
    
34. 
    
35.         public static boolean isPrime(long n) {
    
36.                 long k, q;
    
37.                 SecureRandom random = new SecureRandom();
    
38.                 for (k = 0; (((n - 1) >> k) & 1) == 0; k++)
    
39.                         ;
    
40.                 q = (n - 1) >> k;
    
41.                 long a = random.nextLong(n);
    
42.                 if (squareMultiply(a, q, n) == 1)
    
43.                         return true;
    
44.                 for (int j = 0; j < k; j++)
    
45.                         if (squareMultiply(a, (int) Math.pow(2, j) * q, n) == n - 1)
    
46.                                 return true;
    
47.                 return false;
    
48.         }
    
49. 
    
50.         public static long squareMultiply(long a, long b, long p) {
    
51.                 long x = 1, y = a;
    
52.                 long len = (long) Math.ceil((Math.log(b) / Math.log(2)));
    
53.                 for (int i = 0; i < len; i++) {
    
54.                         if (((b >> i) & 1) == 1) {
    
55.                                 x = (x * y) % p;
    
56.                         }
    
57.                         y = (y * y) % p;
    
58.                 }
    
59.                 return x;
    
60.         }
    
61. 
    
62.         public static long powMod(long x, long y, long z) {//模幂运算
    
63. 
    
64.                 if (y == 0)
    
65.                         return 1 % z;
    
66. 
    
67.                 long half = powMod(x, y >> 1, z);
    
68. 
    
69.                 half = (half * half) % z;
    
70. 
    
71.                 if ((y & 1) == 0) { // y是偶数
    
72. 
    
73.                         return half;
    
74. 
    
75.                 } else { // y是奇数
    
76. 
    
77.                         return (half * (x % z)) % z;
    
78. 
    
79.                 }
    
80. 
    
81.         }
    
82. 
    
83.         public static long Inverse(long a, long b) { // 模逆运算
    
84.                 long[] m = { 1, 0, a };
    
85.                 long[] n = { 0, 1, b };
    
86.                 long[] temp = new long[3];
    
87.                 long q = 0; // 初始化
    
88.                 boolean flag = true;
    
89.                 while (flag) {
    
90.                         q = m[2] / n[2];
    
91.                         for (int i = 0; i < 3; i++) {
    
92.                                 temp[i] = m[i] - q * n[i];
    
93.                                 m[i] = n[i];
    
94.                                 n[i] = temp[i];
    
95.                         }
    
96.                         if (n[2] == 1) {
    
97.                                 if (n[1] < 0) {
    
98.                                         n[1] = n[1] + a;
    
99.                                 }
    
100.                                 return n[1];
     
101.                         }
     
102.                         if (n[2] == 0) {
     
103.                                 flag = false;
     
104.                         }
     
105.                 }
     
106.                 return 0;
     
107.         }
     
108. 
     
109.         public static void main(String[] args) {
     
110.                 long p = getPrime(); // 生成两个素数
     
111.                 long q = getPrime();
     
112.                 while (p == q) {
     
113.                         q = getPrime();
     
114.                 }
     
115.                 long n = p * q;
     
116.                 long φ = (p - 1) * (q - 1);
     
117.                 long e = getPrime();
     
118.                 long d = Inverse(φ, e);
     
119.                 System.out.println("p:"+p);
     
120.                 System.out.println("q:"+q);
     
121.                 System.out.println("n:"+n);
     
122.                 System.out.println("φ:"+φ);
     
123.                 System.out.println("e:"+e);
     
124.                 System.out.println("d:"+d);
     
125. 
     
126.                 System.out.print("请输入明文：");
     
127.                 Scanner sc = new Scanner(System.in);
     
128.                 long m=sc.nextLong();
     
129.                 long c=powMod(m, e, n);
     
130.                 System.out.println("密文：" + c);
     
131.                 m = powMod(c, d, n);
     
132.                 System.out.println("解密得到明文：" + m);
     
133.                 sc.close();
     
134.         }
     
135. }

复制代码