信息计算2019级2班16号吴盛盛

吴盛盛

4月22日

吴盛盛

4月29日

吴盛盛

RSA算法的具体描述如下：
（1）任意选取两个不同的大素数p和q计算乘积n=pq，φ(n)=(p-1)(q-1)；
（2）任意选取一个大整数e，满足gcd(e, φ(n))=1且1<e<φ(n)，e用做加密钥；
（3）确定的解密钥d，满足(de)modφ(n)=1，即de=kφ(n)+1，k>=1且为整数；
（4）公开整数n和e，秘密保存d；
（5）将明文m（m<n，是一个整数）加密成密文c，加密算法为c=E(m)=memodn；
（6）将密文c解密为明文m，解密算法为m=D(c)=cdmodn。 根据如上所示的RSA算法的基本流程，结合本实例来说明一下程序结构。公钥e直接使用通用的65537，在generateKey函数中可使用文件读入或随机的方式产生p、q，随机产生的方式会利用到函数generateNBitRandomPrime和isPrime产生指定位的素数，然后利用extdGcd函数计算出私钥d。接着在encryption加密函数中会根据m<n的原则进行分组逐组加密，利用expMod进行快速幂模运算，解密函数decryption中同样逐组利用expMod函数进行幂模运算。

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

复制代码

吴盛盛