信息计算2019级2班9号范承蝶

范承蝶

2022年4月19日以及4月22日慕课截图：

范承蝶

2022年4月29日慕课截图：

范承蝶

2022年5月3日慕课截图：

范承蝶

1. import java.math.BigInteger;
   
2. import java.util.Random;
   
3. 
   
4. public class rsa {
   
5.     private final static int numLength = 128;//素数长度
   
6.     private final static int accuracy = 100;//素数的准确率为1-(2^(-accuracy))
   
7. 
   
8.     //获取最大公约数
   
9.     private BigInteger getG(BigInteger a, BigInteger b) {
   
10.         if (b.byteValue() == 0)
    
11.                 return a;
    
12.         return getG(b, a.mod(b));
    
13.     }
    
14. 
    
15.     //扩展欧几里得方法,计算 ax + by = 1中的x与y的整数解（a与b互质）
    
16.     private static BigInteger[] extGCD(BigInteger a, BigInteger b) {
    
17.         if (b.signum() == 0) {
    
18.             return new BigInteger[]{a, new BigInteger("1"), new BigInteger("0")};
    
19.         } else {
    
20.             BigInteger[] bigIntegers = extGCD(b, a.mod(b));
    
21.             BigInteger y = bigIntegers[1].subtract(a.divide(b).multiply(bigIntegers[2]));
    
22.             return new BigInteger[]{bigIntegers[0], bigIntegers[2], y};
    
23.         }
    
24.     }
    
25. 
    
26.     //超大整数超大次幂然后对超大的整数取模
    
27.     private static BigInteger expMode(BigInteger base, BigInteger exp, BigInteger mod) {
    
28.         BigInteger res = BigInteger.ONE;
    
29.         BigInteger tempBase = new BigInteger(base.toString());
    
30.         for (int i = 0; i < exp.bitLength(); i++) {
    
31.             if (exp.testBit(i)) {
    
32.                     //判断对应二进制位是否为1
    
33.                 res = (res.multiply(tempBase)).mod(mod);
    
34.             }
    
35.             tempBase = tempBase.multiply(tempBase).mod(mod);
    
36.         }
    
37.         return res;
    
38.     }
    
39. 
    
40.     //产生公钥与私钥
    
41.     public static SecretKey generateKey(BigInteger p, BigInteger q) {
    
42.         //令n = p * q。取 φ(n) = (p-1) * (q-1)。
    
43.         BigInteger n = p.multiply(q);
    
44.         //计算与n互质的整数个数 欧拉函数
    
45.         BigInteger fy = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
    
46.         //取 e ∈ [1 < e < φ(n) ] ，( n , e )作为公钥对，这里取65537
    
47.         BigInteger e = new BigInteger("65537");
    
48.         BigInteger[] bigIntegers = extGCD(e, fy);
    
49.         BigInteger x = bigIntegers[1];
    
50.         if (x.signum() == -1) {
    
51.             x = x.add(fy);
    
52.         }
    
53.         return new SecretKey(n, e, x);
    
54.     }
    
55. 
    
56.     public static SecretKey generateKey() {
    
57.         BigInteger[] pq = getRandomPQ();
    
58.         return generateKey(pq[0], pq[1]);
    
59.     }
    
60. 
    
61.     //加密
    
62.     public static BigInteger encrypt(BigInteger text, SecretKey.PublicKey publicKey) {
    
63.         return expMode(text, publicKey.e, publicKey.n);
    
64.     }
    
65. 
    
66.     //解密
    
67.     public static BigInteger decrypt(BigInteger cipher, SecretKey.PrivateKey privateKey) {
    
68.         return expMode(cipher, privateKey.d, privateKey.n);
    
69.     }
    
70. 
    
71.     //加密
    
72.     public static String encrypt(String text, SecretKey.PublicKey publicKey) {
    
73.         return encrypt(new BigInteger(text.getBytes()), publicKey).toString();
    
74.     }
    
75. 
    
76.     //解密
    
77.     public static String decrypt(String chipper, SecretKey.PrivateKey privateKey) {
    
78.         BigInteger bigInteger = expMode(new BigInteger(chipper), privateKey.d, privateKey.n);
    
79.         byte[] bytes = new byte[bigInteger.bitLength() / 8 + 1];
    
80.         for (int i = 0; i < bytes.length; i++) {
    
81.             for (int j = 0; j < 8; j++) {
    
82.                 if (bigInteger.testBit(j + i * 8)) {
    
83.                     bytes[bytes.length - 1 - i] |= 1 << j;
    
84.                 }
    
85.             }
    
86.         }
    
87.         return new String(bytes);
    
88.     }
    
89. 
    
90.     //产生两个随机128位大质数
    
91.     public static BigInteger[] getRandomPQ() {
    
92.         BigInteger p = BigInteger.probablePrime(numLength, new Random());
    
93.         while (!p.isProbablePrime(accuracy)) {
    
94.             p = BigInteger.probablePrime(numLength, new Random());
    
95.         }
    
96.         BigInteger q = BigInteger.probablePrime(numLength, new Random());
    
97.         while (!q.isProbablePrime(accuracy)) {
    
98.             q = BigInteger.probablePrime(numLength, new Random());
    
99.         }
    
100.         return new BigInteger[]{p, q};
     
101.     }
     
102. 
     
103.     //密匙对
     
104.     static class SecretKey {
     
105.         BigInteger n, e, d;
     
106. 
     
107.         public SecretKey(BigInteger n, BigInteger e, BigInteger d) {
     
108.             this.n = n;
     
109.             this.e = e;
     
110.             this.d = d;
     
111.         }
     
112. 
     
113.         public PublicKey getPublicKey() {
     
114.             return new PublicKey(n, e);
     
115.         }
     
116. 
     
117.         public PrivateKey getPrivateKey() {
     
118.             return new PrivateKey(n, d);
     
119.         }
     
120. 
     
121.         //密钥
     
122.         static class PrivateKey {
     
123.             public BigInteger n, d;
     
124. 
     
125.             public PrivateKey(BigInteger n, BigInteger d) {
     
126.                 this.n = n;
     
127.                 this.d = d;
     
128.             }
     
129.         }
     
130. 
     
131.         //公钥
     
132.         static class PublicKey {
     
133.             public BigInteger n, e;
     
134. 
     
135.             public PublicKey(BigInteger n, BigInteger e) {
     
136.                 this.n = n;
     
137.                 this.e = e;
     
138.             }
     
139.         }
     
140.     }
     
141. 
     
142. 
     
143.     public static void main(String[] args) {
     
144.         SecretKey secretKey = rsa.generateKey();
     
145.         //明文内容不要超过128位,超过后需要分段加密
     
146.         String text = "qwertyuiop";
     
147.         String chipper = rsa.encrypt(text, secretKey.getPublicKey());
     
148. 
     
149.       //密文长度可能会随着随机密钥的改变而改变，最长不超过256位
     
150.         System.out.println("加密后:\n" +
     
151.                 "密文二进制长度:" + new BigInteger(chipper).bitLength()
     
152.                 + "\n"
     
153.                 + chipper);
     
154.         String origin = rsa.decrypt(chipper, secretKey.getPrivateKey());
     
155.         System.out.println("解密后:\n" + origin);
     
156.     }
     
157. }
     
158. 
     

复制代码