信息计算2019级2班2号胡莘梅

信计19-2胡莘梅

信计19-2胡莘梅

大数版本RSA

一、RSA介绍
  RSA是被研究得最广泛的公钥算法，也是第一个能同时用于加密和数字签名的算法。
  RSA算法是一种非对称密码算法，所谓非对称，就是指该算法需要一对密钥，使用其中一个加密，则需要用另一个才能解密。
  RSA的算法涉及三个参数，n、e1、 e2。

  其中，n是两个大质数p、q的积，n的二进制表示时所占用的位数，就是所谓的密钥长度。
  e1和e2是一对相关的值，e1可以任意取，但要求el与(p-1)*(q-1)互质;
  再选择e2，要求(e2*e 1)mod((p-1)*(q-1))=1。满足上述条件后，(n及e1),(n及e2)就是密钥对。

二、RSA算法实现步骤
产生非对称密钥的算法流程

加解密算法过程

三、运行截图

信计19-2胡莘梅

四、源代码
(1)Node.java

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

复制代码

(2)Prime.java

1. package rsa;
   
2. 
   
3. import java.math.BigInteger;
   
4. 
   
5. public class Prime {
   
6. public boolean sushu(double n) {
   
7. boolean isPrime = true;
   
8. if (n > 2) {
   
9. if (n % 2 == 0) {
   
10. isPrime = false;
    
11. } else {
    
12. for (int i = 3; i <= (int) Math.sqrt(n); i += 2) {
    
13. if (n % i == 0) {
    
14. isPrime = false;
    
15. break;
    
16. }
    
17. }
    
18. }
    
19. 
    
20. }
    
21. return isPrime;
    
22. }
    
23. 
    
24. private static final BigInteger ZERO = BigInteger.ZERO;
    
25. private static final BigInteger ONE = BigInteger.ONE;
    
26. private static final BigInteger TWO = new BigInteger("2");
    
27. private static final int ERR_VAL = 100;
    
28. 
    
29. public BigInteger nextPrime(BigInteger start) {
    
30. if (isEven(start))
    
31. start = start.add(ONE);
    
32. else
    
33. start = start.add(TWO);
    
34. if (start.isProbablePrime(ERR_VAL))
    
35. return (start);
    
36. else
    
37. return (nextPrime(start));
    
38. }
    
39. 
    
40. private static boolean isEven(BigInteger n) {
    
41. return (n.mod(TWO).equals(ZERO));
    
42. }
    
43. 
    
44. public BigInteger bigRandom(int numDigits) {
    
45. StringBuffer s = new StringBuffer("");
    
46. for (int i = 0; i < numDigits; i++)
    
47. if (i == 0)
    
48. s.append(randomDigit(false));
    
49. else
    
50. s.append(randomDigit(true));
    
51. return (new BigInteger(s.toString()));
    
52. }
    
53. 
    
54. private StringBuffer randomDigit(boolean isZeroOK) {
    
55. int index;
    
56. if (isZeroOK)
    
57. index = (int) Math.floor(Math.random() * 10);
    
58. else
    
59. index = 1 + (int) Math.floor(Math.random() * 9);
    
60. return (digits[index]);
    
61. }
    
62. 
    
63. private static StringBuffer[] digits = { new StringBuffer("0"),
    
64. new StringBuffer("1"), new StringBuffer("2"),
    
65. new StringBuffer("3"), new StringBuffer("4"),
    
66. new StringBuffer("5"), new StringBuffer("6"),
    
67. new StringBuffer("7"), new StringBuffer("8"), new StringBuffer("9") };
    
68. 
    
69. public static void main(String[] args) {
    
70. 
    
71. }
    
72. }
    
73. 
    

复制代码

(3)RSA.java

1. package rsa;
   
2. 
   
3. import java.math.BigInteger;
   
4. import java.util.ArrayList;
   
5. import java.util.Scanner;
   
6. 
   
7. public class RSA {
   
8. static BigInteger x, y;
   
9. 
   
10. public static boolean fun(BigInteger x, BigInteger y) {
    
11. BigInteger t;
    
12. while (!(y.equals(new BigInteger("0")))) {
    
13. t = x;
    
14. x = y;
    
15. y = t.mod(y);
    
16. }
    
17. if (x.equals(new BigInteger("1")))
    
18. return false;
    
19. else
    
20. return true;
    
21. }
    
22. 
    
23. public static BigInteger siyue(BigInteger a, BigInteger b) {
    
24. BigInteger temp;
    
25. if (b.equals(new BigInteger("0"))) {
    
26. x = new BigInteger("1");
    
27. y = new BigInteger("0");
    
28. return x;
    
29. }
    
30. siyue(b, a.mod(b));
    
31. temp = x;
    
32. x = y;
    
33. y = temp.subtract((a.divide(b).multiply(y)));
    
34. return x;
    
35. }
    
36. 
    
37. public static double entropy(String mess) {
    
38. ArrayList<Node> jieguo = new ArrayList<Node>();
    
39. jieguo.clear();
    
40. double num = mess.length();
    
41. for (int i = 0; i < num; i++) {
    
42. boolean flag_exit = true;
    
43. for (int j = 0; j < jieguo.size(); j++) {
    
44. if (jieguo.get(j).getalpha() == mess.charAt(i)) {
    
45. flag_exit = false;
    
46. jieguo.get(j).setp(jieguo.get(j).getp() + 1 / num);
    
47. }
    
48. }
    
49. if (flag_exit)
    
50. jieguo.add(new Node(1 / num, mess.charAt(i)));
    
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 = siyue(e, t);
     
107. System.out.println("随机生成素数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. BigInteger m = new BigInteger(mess.getBytes());
     
122. System.out.println("明文的大整数表示形式：" + m);
     
123. mess = m.toString();
     
124. System.out.println("计算得明文熵：" + entropy(mess));
     
125. c = m.modPow(e, n);
     
126. System.out.println("密文的大整数表示形式：" + c);
     
127. System.out.println("计算得密文熵：" + entropy(c.toString()));
     
128. System.out.println("密文的字符串表示形式：" + new String(c.toByteArray()));
     
129. m = c.modPow(d, n);
     
130. System.out.println("解密得到明文的大整数表示形式：" + c);
     
131. String str = new String(m.toByteArray());
     
132. System.out.println("解密得到明文为：" + str);
     
133. }
     
134. }
     
135. }

复制代码