信息计算2019级1班17号刘帆杰

刘帆杰

1. package com.密码算法;
   
2. 
   
3. import java.io.UnsupportedEncodingException;
   
4. import java.math.BigInteger;
   
5. import java.util.Random;
   
6. import java.util.Scanner;
   
7. 
   
8. public class RSA {
   
9.     private BigInteger n;// = p * q，两个大质数的乘积
   
10.     private BigInteger e;// 公钥指数
    
11.     private BigInteger d;// 私钥指数
    
12.     private final int PQMINLENGTH = 1024;// p、q最小的长度（比特数）
    
13. 
    
14.     public static void main(String[] args) throws RSA.pqException, UnsupportedEncodingException {
    
15.         Scanner input = new Scanner(System.in);
    
16.         int pqLength = 1024;// p、q长度（比特数）
    
17.         String e = "65537";// 公钥指数
    
18.         System.out.println("请输入要加密的内容：");
    
19.         String originalText=input.nextLine();
    
20.         RSA rsa = new RSA(new BigInteger(e), pqLength);
    
21.         System.out.println("加密前：" + originalText);
    
22.         BigInteger[] c = rsa.encryption(originalText);// 加密
    
23.         System.out.print("加密后：");
    
24.         for (int i = 0; i < c.length; i++) {
    
25.             System.out.println(c[i]);
    
26.         }
    
27.         System.out.println("解密后：" + rsa.decryption(c));// 解密
    
28.     }
    
29. 
    
30.     private class pqException extends Exception {
    
31.         private static final long serialVersionUID = -7777566816579144864L;
    
32. 
    
33.         public pqException(String message) {
    
34.             super(message);
    
35.         }
    
36.     }
    
37. 
    
38.     public RSA(BigInteger e, int pqLength) throws RSA.pqException {
    
39.         this.e = e;
    
40.         generateKey(pqLength);// 产生密钥
    
41.     }
    
42.    
    
43. 
    
44.     private void generateKey(int pqLength) throws RSA.pqException {
    
45.         BigInteger p = BigInteger.ZERO;// 两个大素数
    
46.         BigInteger q = BigInteger.ZERO;
    
47.         BigInteger φn;// = (p-1)(q-1)
    
48. 
    
49.         if (pqLength < PQMINLENGTH) {
    
50.                 throw new pqException("p、q长度小于" + PQMINLENGTH + "，请重新选择更大的比特数！");
    
51.             }
    
52.             p = RSA.generateNBitRandomPrime(pqLength);
    
53.             q = RSA.generateNBitRandomPrime(pqLength);
    
54. 
    
55.         n = p.multiply(q);
    
56.         System.out.println("随机产生两个素数p、q");
    
57.         System.out.println("p:"+p);
    
58.         System.out.println("q:"+q);
    
59.         System.out.println("p、q乘积为n:"+n);
    
60.         φn = (p.subtract(BigInteger.ONE)).multiply(q.subtract(BigInteger.ONE));
    
61.         d = RSA.extdGcd(e, φn)[1];// 利用扩展欧几里得算法求私钥d
    
62.         if (d.compareTo(BigInteger.ZERO) != 1) {// 私钥不可以小于0
    
63.             d = d.add(φn);
    
64.         }
    
65.         System.out.println("公钥为:"+e);
    
66.         System.out.println("私钥为:"+d);
    
67.     }
    
68. 
    
69. 
    
70.     private BigInteger[] encryption(String plainText) throws UnsupportedEncodingException {
    
71.         String textNum = "";// 明文数字字符串表示形式
    
72.         BigInteger m = BigInteger.ZERO;// 明文数字表示形式
    
73.         byte[] textByte = plainText.getBytes("UTF-8");
    
74.         for (int i = 0; i < textByte.length; i++) {// 每个字节用3位数的整数表示，不够则在前面补0
    
75.             int bn = textByte[i] & 0xff;
    
76.             if (bn < 10) {
    
77.                 textNum += "00" + bn;
    
78.             } else if (bn < 100) {
    
79.                 textNum += "0" + bn;
    
80.             } else {
    
81.                 textNum += bn;
    
82.             }
    
83.         }
    
84.         m = new BigInteger(textNum);
    
85. 
    
86.         BigInteger[] mArray = null;// 明文分组结果
    
87.         if (m.compareTo(n) == -1) {// m < n，可直接加密
    
88.             mArray = new BigInteger[1];
    
89.             mArray[0] = m;
    
90.         } else {
    
91.             int groupLength = n.toString().length() - 1;// 每组明文长度
    
92.             int mStringLength = m.toString().length();// 明文转化为字符串的长度
    
93.             while (groupLength % 3 != 0) {// 由于前面每个字节用3位整数表示，因此每组的长度必须为3的整数，避免恢复时错误
    
94.                 groupLength--;
    
95.             }
    
96.             if (mStringLength % groupLength != 0) {// 如果最后一组的长度不足
    
97.                 mArray = new BigInteger[mStringLength / groupLength + 1];
    
98.             } else {
    
99.                 mArray = new BigInteger[mStringLength / groupLength];
    
100.             }
     
101. 
     
102.             String tmp;
     
103.             for (int i = 0; i < mArray.length; i++) {
     
104.                 tmp = "";
     
105.                 if (i != mArray.length - 1) {// 根据每组长度进行分割分组保存
     
106.                     tmp = textNum.substring(groupLength * i, groupLength * i + groupLength);
     
107.                 } else {
     
108.                     tmp = textNum.substring(groupLength * i);
     
109.                 }
     
110.                 mArray[i] = new BigInteger(tmp);
     
111.             }
     
112.         }
     
113. 
     
114.         for (int i = 0; i < mArray.length; i++) {// 逐组加密并返回
     
115.             mArray[i] = expMod(mArray[i], e, n);
     
116.         }
     
117.         return mArray;
     
118.     }
     
119. 
     
120. 
     
121.     private String decryption(BigInteger[] c) {
     
122.         String cPadding = "";
     
123.         String mToString = "";
     
124.         int mToStringLengthMod = 0;
     
125.         BigInteger m = BigInteger.ZERO;
     
126.         for (int i = 0; i < c.length; i++) {// 逐组解密
     
127.             m = RSA.expMod(c[i], d, n);
     
128.             mToString = m.toString();
     
129.             mToStringLengthMod = m.toString().length() % 3;
     
130.             if (mToStringLengthMod != 0) {// 由于加密时String转BigInter时前者前面的0并不会计入，所以需要确认并补全
     
131.                 for (int j = 0; j < 3 - mToStringLengthMod; j++) {
     
132.                     mToString = "0" + mToString;
     
133.                 }
     
134.             }
     
135.             cPadding += mToString;
     
136.         }
     
137. 
     
138.         int byteNum = cPadding.length() / 3;// 明文总字节数
     
139.         byte[] result = new byte[byteNum];
     
140.         for (int i = 0; i < byteNum; i++) {// 每三位数转化为byte型并返回该byte数组所表达的字符串
     
141.             result[i] = (byte) (Integer.parseInt(cPadding.substring(i * 3, i * 3 + 3)));
     
142.         }
     
143.         return new String(result);
     
144.     }
     
145. 
     
146. 
     
147.     private static BigInteger[] extdGcd(BigInteger e, BigInteger φn) {
     
148.         BigInteger[] gdk = new BigInteger[3];
     
149. 
     
150.         if (φn.compareTo(BigInteger.ZERO) == 0) {
     
151.             gdk[0] = e;
     
152.             gdk[1] = BigInteger.ONE;
     
153.             gdk[2] = BigInteger.ZERO;
     
154.             return gdk;
     
155.         } else {
     
156.             gdk = extdGcd(φn, e.remainder(φn));
     
157.             BigInteger tmp_k = gdk[2];
     
158.             gdk[2] = gdk[1].subtract(e.divide(φn).multiply(gdk[2]));
     
159.             gdk[1] = tmp_k;
     
160.             return gdk;
     
161.         }
     
162.     }
     
163. 
     
164. 
     
165.     private static boolean isPrime(BigInteger p) {
     
166.         if (p.compareTo(BigInteger.TWO) == -1) {// 小于2直接返回false
     
167.             return false;
     
168.         }
     
169.         if ((p.compareTo(BigInteger.TWO) != 0) && (p.remainder(BigInteger.TWO).compareTo(BigInteger.ZERO) == 0)) {// 不等于2且是偶数直接返回false
     
170.             return false;
     
171.         }
     
172. 
     
173.         BigInteger p_1 = p.subtract(BigInteger.ONE);
     
174.         BigInteger m = p_1;// 找到q和m使得p = 1 + 2^q * m
     
175.         int q = m.getLowestSetBit();// 二进制下从右往左返回第一次出现1的索引
     
176.         m = m.shiftRight(q);
     
177. 
     
178.         for (int i = 0; i < 5; i++) {// 判断的轮数，精度、轮数和时间三者之间成正比关系
     
179.             BigInteger b;
     
180.             do {// 在区间1~p上生成均匀随机数
     
181.                 b = new BigInteger(String.valueOf(p.bitLength()));
     
182.             } while (b.compareTo(BigInteger.ONE) <= 0 || b.compareTo(p) >= 0);
     
183. 
     
184.             int j = 0;
     
185.             BigInteger z = RSA.expMod(b, m, p);
     
186.             while (!((j == 0 && z.equals(BigInteger.ONE)) || z.equals(p_1))) {
     
187.                 if ((j > 0 && z.equals(BigInteger.ONE)) || ++j == q) {
     
188.                     return false;
     
189.                 }
     
190.                 z = RSA.expMod(z, BigInteger.TWO, p);
     
191.             }
     
192.         }
     
193. 
     
194.         return true;
     
195.     }
     
196. 
     
197. 
     
198.     private static BigInteger generateNBitRandomPrime(int n) {
     
199.         BigInteger tmp = new BigInteger("2").pow(n - 1);// 最高位肯定是1
     
200.         BigInteger result = new BigInteger("2").pow(n - 1);
     
201.         Random random = new Random();
     
202.         int r1 = random.nextInt(101);// 产生0-100的整数，用于确定0和1的比例
     
203.         int r2;
     
204. 
     
205.         while (true) {// 循环产生数，直到该数为素数
     
206.             for (int i = n - 2; i >= 0; i--) {// 逐位产生表示数的0和1，并根据所在位计算结果相加起来
     
207.                 r2 = random.nextInt(101);
     
208.                 if (0 < r2 && r2 < r1) {// 产生的数为1
     
209.                     result = result.add(BigInteger.TWO.pow(i));
     
210.                 }
     
211.                 continue;
     
212.             }
     
213. 
     
214.             if (RSA.isPrime(result)) {// 素数判断
     
215.                 return result;
     
216.             }
     
217. 
     
218.             result = tmp;// 重新计算
     
219.         }
     
220.     }
     
221. 
     
222. 
     
223.     private static BigInteger expMod(BigInteger base, BigInteger exponent, BigInteger module) {
     
224.         BigInteger result = BigInteger.ONE;
     
225.         BigInteger tmp = base.mod(module);
     
226. 
     
227.         while (exponent.compareTo(BigInteger.ZERO) != 0) {
     
228.             if ((exponent.and(BigInteger.ONE).compareTo(BigInteger.ZERO)) != 0) {
     
229.                 result = result.multiply(tmp).mod(module);
     
230.             }
     
231.             tmp = tmp.multiply(tmp).mod(module);
     
232.             exponent = exponent.shiftRight(1);
     
233.         }
     
234. 
     
235.         return result;
     
236.     }
     
237. 
     
238. }
     
239. 
     

复制代码

刘帆杰