信息计算2019级1班20号李善安

李善安

RSA加密算法是一种非对称加密算法，所谓非对称，就是指该算法需要一对密钥，使用其中一个加密，则需要用另一个才能解密。这样就可以在不直接传递密钥的情况下，完成解密。这能够确保信息的安全性，避免了直接传递密钥所造成的被破解的风险。是由一对密钥来进行加解密的过程，分别称为公钥和私钥。两者之间有数学相关，该加密算法的原理就是对一极大整数做因数分解的困难性来保证安全性。通常个人保存私钥,公钥是公开的(可能同时多人持有)。
RSA签名的过程如下：
(1)A生成一对密钥（公钥和私钥)，私钥不公开，A自己保留。公钥为公开的，任何人可以获取。
(2)A用自己的私钥对消息加签，形成签名，并将加签的消息和消息本身一起传递给B。
(3)B收到消息后，在获取A的公钥进行验签，如果验签出来的内容与消息本身一致，证明消息是A回复的。
在这个过程中，只有2次传递过程，第一次是A传递加签的消息和消息本身给B，第二次是B获取A的公钥，即使都被敌方截获，也没有危险性，因为只有A的私钥才能对消息进行签名，即使知道了消息内容，也无法伪造带签名的回复给B，防止了消息内容的篡改。
总结:公钥加密、私钥解密、私钥签名、公钥验签。

1. Package basictraing
   
2. 
   
3. import org.apache.commons.codec.binary.Base64;
   
4. import javax.crypto.Cipher;
   
5. import java.io.ByteArrayOutputStream;
   
6. import java.security.*;
   
7. import java.security.spec.PKCS8EncodedKeySpec;
   
8. import java.security.spec.X509EncodedKeySpec;
   
9. 
   
10. public class RsaUtil {
    
11. //RSA最⼤加密明⽂⼤⼩
    
12.         private static final int MAX_ENCRYPT_BLOCK = 117;
    
13. //RSA最⼤解密密⽂⼤⼩
    
14.         private static final int MAX_DECRYPT_BLOCK = 128;
    
15.         public static final String privateKeyA = "privateKeyA";
    
16.         public static final String publicKeyA = "publicKeyA";
    
17.         public static final String publicKeyB = "publicKeyB";
    
18.         public static final String privateKeyB = "privateKeyB";
    
19. 
    
20.         public static PrivateKey getPrivateKey(String privateKey) throws Exception {
    
21.                 KeyFactory keyFactory = KeyFactory.getInstance("RSA");
    
22.                 byte[] decodedKey = Base64.decodeBase64(privateKey.getBytes());
    
23.                 PKCS8EncodedKeySpec keySpec = new PKCS8EncodedKeySpec(decodedKey);
    
24.                 return keyFactory.generatePrivate(keySpec);
    
25.         }
    
26. 
    
27.         public static PublicKey getPublicKey(String publicKey) throws Exception {
    
28.                 KeyFactory keyFactory = KeyFactory.getInstance("RSA");
    
29.                 byte[] decodedKey = Base64.decodeBase64(publicKey.getBytes());
    
30.                 X509EncodedKeySpec keySpec = new X509EncodedKeySpec(decodedKey);
    
31.                 return keyFactory.generatePublic(keySpec);
    
32.         }
    
33. 
    
34.         public static Map<Integer, String> genKeyPair() throws NoSuchAlgorithmException {
    
35.                 // KeyPairGenerator类⽤于⽣成公钥和私钥对，基于RSA算法⽣成对象
    
36.                 KeyPairGenerator keyPairGen = KeyPairGenerator.getInstance("RSA");
    
37.                 // 初始化密钥对⽣成器，密钥⼤⼩为96-1024位
    
38.                 keyPairGen.initialize(1024, new SecureRandom());
    
39.                 // ⽣成⼀个密钥对，保存在keyPair中
    
40.                 KeyPair keyPair = keyPairGen.generateKeyPair();
    
41.                 RSAPrivateKey privateKey = (RSAPrivateKey) keyPair.getPrivate(); // 得到私钥
    
42.                 RSAPublicKey publicKey = (RSAPublicKey) keyPair.getPublic(); // 得到公钥
    
43.                 String publicKeyString = new String(Base64.encodeBase64(publicKey.getEncoded()));
    
44.                 // 得到私钥字符串
    
45.                 String privateKeyString = new String(Base64.encodeBase64((privateKey.getEncoded())));
    
46.                 // 将公钥和私钥保存到Map
    
47.                 Map<Integer, String> keyMap = new HashMap();
    
48.                 keyMap.put(0, publicKeyString); // 0表⽰公钥
    
49.                 keyMap.put(1, privateKeyString); // 1表⽰私钥
    
50.                 return keyMap;
    
51.         }
    
52. 
    
53.        
    
54.         public static String encrypt(String str, String publicKey) throws Exception {
    
55.                 // base64编码的公钥
    
56.                 byte[] decoded = Base64.decodeBase64(publicKey);
    
57.                 RSAPublicKey pubKey = (RSAPublicKey) KeyFactory.getInstance("RSA")
    
58.                                 .generatePublic(new X509EncodedKeySpec(decoded));
    
59.                 // RSA加密
    
60.                 Cipher cipher = Cipher.getInstance("RSA");
    
61.                 cipher.init(Cipher.ENCRYPT_MODE, pubKey);
    
62.                 byte[] data = str.getBytes("UTF-8");
    
63.                 int inputLen = data.length;
    
64.                 ByteArrayOutputStream out = new ByteArrayOutputStream();
    
65.                 int offSet = 0;
    
66.                 byte[] cache;
    
67.                 int i = 0;
    
68.                 // 对数据分段加密
    
69.                 while (inputLen - offSet > 0) {
    
70.                         if (inputLen - offSet > MAX_ENCRYPT_BLOCK) {
    
71.                                 cache = cipher.doFinal(data, offSet, MAX_ENCRYPT_BLOCK);
    
72.                         } else {
    
73.                                 cache = cipher.doFinal(data, offSet, inputLen - offSet);
    
74.                         }
    
75.                         out.write(cache, 0, cache.length);
    
76.                         i++;
    
77.                         offSet = i * MAX_ENCRYPT_BLOCK;
    
78.                 }
    
79.                 byte[] encryptedData = out.toByteArray();
    
80.                 out.close();
    
81.                 String outStr = Base64.encodeBase64String(encryptedData);
    
82.                 return outStr;
    
83.         }
    
84. 
    
85.         public static String decrypt(String str, String privateKey) throws Exception {
    
86.                 // 64位解码加密后的字符串
    
87.                 byte[] data = Base64.decodeBase64(str.getBytes("UTF-8"));
    
88.                 // base64编码的私钥
    
89.                 byte[] decoded = Base64.decodeBase64(privateKey);
    
90.                 RSAPrivateKey priKey = (RSAPrivateKey) KeyFactory.getInstance("RSA")
    
91.                                 .generatePrivate(new PKCS8EncodedKeySpec(decoded));
    
92.                 // RSA解密
    
93.                 Cipher cipher = Cipher.getInstance("RSA");
    
94.                 cipher.init(Cipher.DECRYPT_MODE, priKey);
    
95.                 int inputLen = data.length;
    
96.                 ByteArrayOutputStream out = new ByteArrayOutputStream();
    
97.                 int offSet = 0;
    
98.                 byte[] cache;
    
99.                 int i = 0;
    
100.                 // 对数据分段解密
     
101.                 while (inputLen - offSet > 0) {
     
102.                         if (inputLen - offSet > MAX_DECRYPT_BLOCK) {
     
103.                                 cache = cipher.doFinal(data, offSet, MAX_DECRYPT_BLOCK);
     
104.                         } else {
     
105.                                 cache = cipher.doFinal(data, offSet, inputLen - offSet);
     
106.                         }
     
107.                         out.write(cache, 0, cache.length);
     
108.                         i++;
     
109.                         offSet = i * MAX_DECRYPT_BLOCK;
     
110.                 }
     
111.                 byte[] decryptedData = out.toByteArray();
     
112.                 out.close();
     
113.                 String outStr = new String(decryptedData);
     
114.                 return outStr;
     
115.         }
     
116. 
     
117.         public static String sign(String data, PrivateKey privateKey) throws Exception {
     
118.                 byte[] keyBytes = privateKey.getEncoded();
     
119.                 PKCS8EncodedKeySpec keySpec = new PKCS8EncodedKeySpec(keyBytes);
     
120.                 KeyFactory keyFactory = KeyFactory.getInstance("RSA");
     
121.                 PrivateKey key = keyFactory.generatePrivate(keySpec);
     
122.                 Signature signature = Signature.getInstance("MD5withRSA");
     
123.                 signature.initSign(key);
     
124.                 signature.update(data.getBytes());
     
125.                 return new String(Base64.encodeBase64(signature.sign()));
     
126.         }
     
127. 
     
128.         public static boolean verify(String srcData, PublicKey publicKey, String sign) throws Exception {
     
129.                 byte[] keyBytes = publicKey.getEncoded();
     
130.                 X509EncodedKeySpec keySpec = new X509EncodedKeySpec(keyBytes);
     
131.                 KeyFactory keyFactory = KeyFactory.getInstance("RSA");
     
132.                 PublicKey key = keyFactory.generatePublic(keySpec);
     
133.                 Signature signature = Signature.getInstance("MD5withRSA");
     
134.                 signature.initVerify(key);
     
135.                 signature.update(srcData.getBytes());
     
136.                 return signature.verify(Base64.decodeBase64(sign.getBytes()));
     
137.         }
     
138. }

复制代码

李善安

ECC使用的椭圆曲线定义在有限域p上，p是素数，p>3
2m 域大小为 p = 2m 为一方阵（the field is a square matrix of size p x p）
曲线上的点不连续，限定为离散的整数。域内的点加、点乘结果还在曲线上。
有限域p上的椭圆曲线等式：
y^2 ≡ x ^ 3 + ax + b (mod p)
RSA的密钥空间为域ℤp上的整数 [0…p-1] 。
ECC的密钥用点{x,y},在Galois field ????p 上，x和y都是 [0…p-1]的整数。

椭圆曲线加密算法的过程
公私钥生成：

Alice首先构造一条椭圆曲线E EE，在曲线上选择一点G GG作为生成元，并求G GG的阶为n nn，要求n nn必须为质数；
Alice选择一个私钥k ( k < n ) k (k < n)k(k<n)，生成公钥Q = k G Q = kGQ=kG；
Alice将公钥组E 、 Q 、 G E、Q、GE、Q、G发送给Bob。

加密过程：
Bob收到信息后，将明文编码为M MM，M MM为曲线上一点，并选择一个随机数r rr（r < n , n r < n, nr<n,n为G GG的阶）；
Bob计算点Cipher1与Cipher2即两段密文，计算方法如下
Cipher1= M + r Q Cipher1 = M + rQCipher1=M+rQ
Cipher2 = r G Cipher2 = rGCipher2=rG
Bob把Cipher1和Cipher2发给Alice。

解密过程：
Alice收到密文后，为了获得M MM，只需要Cipher1 − k ⋅ Cipher2Cipher1 - k · Cipher2Cipher1−k⋅Cipher2，因为
Cipher1 − k ∗ Cipher2 = M + r Q − k r G = M + r k G − k r G = M Cipher1 - k*Cipher2 = M + rQ - krG = M + rkG - krG = MCipher1−k∗Cipher2=M+rQ−krG=M+rkG−krG=M
将M解码即可。

1. #include<iostream>
   
2. #include<math.h>
   
3. #include<time.h>
   
4. using namespace std;
   
5. 
   
6. class point
   
7. {
   
8. public:
   
9.         int x;
   
10.         int y;
    
11. };
    
12. point P[100];
    
13. int num = 0;
    
14. 
    
15. //取模
    
16. int my_mod(int a, int p)
    
17. {
    
18.         int i;
    
19.         i = a / p;
    
20.         int re = a - i * p;
    
21.         if (re >= 0)
    
22.         {
    
23.                 return re;
    
24.         }
    
25.         else
    
26.         {
    
27.                 return re + p;
    
28.         }
    
29. }
    
30. 
    
31. int my_pow(int a, int m, int p)
    
32. {
    
33.         int result = 1;
    
34.         for (int i = 0; i < m; i++)
    
35.         {
    
36.                 result = (result * a) % p;
    
37.         }
    
38.         return result;
    
39. }
    
40. 
    
41. int my_sqrt(int s)
    
42. {
    
43.         int t;
    
44.         t = (int)sqrt(s);
    
45.         if (t * t == s)
    
46.         {
    
47.                 return t;
    
48.         }
    
49.         else {
    
50.                 return -1;
    
51.         }
    
52. }
    
53. 
    
54. void all_points(int a, int b, int p)
    
55. {
    
56.         for (int i = 0; i < p; i++)
    
57.         {
    
58.                 int s = i * i * i + a * i + b;
    
59.                 while (s < 0)
    
60.                 {
    
61.                         s += p;
    
62.                 }
    
63.                 s = my_mod(s, p);
    
64. 
    
65.                 int re = my_pow(s, (p - 1) / 2, p);
    
66.                 if (re == 1)
    
67.                 {
    
68.                         //求y
    
69.                         int n = 1, y;
    
70.                         int f = my_sqrt(s);
    
71.                         if (f != -1)
    
72.                         {
    
73.                                 y = f;
    
74.                         }
    
75.                         else
    
76.                         {
    
77.                                 for (; n <= p - 1;)
    
78.                                 {
    
79.                                         s = s + n * p;
    
80.                                         f = my_sqrt(s);
    
81.                                         if (f != -1)
    
82.                                         {
    
83.                                                 y = f;
    
84.                                                 break;
    
85.                                         }
    
86.                                         n++;
    
87.                                 }
    
88.                         }
    
89.                         y = my_mod(y, p);
    
90.                         P[num].x = i;
    
91.                         P[num].y = y;
    
92.                         num++;
    
93.                         if (y != 0)
    
94.                         {
    
95.                                 P[num].x = i;
    
96.                                 P[num].y = (p - y) % p;
    
97.                                 num++;
    
98.                         }
    
99.                 }
    
100.         }
     
101. }
     
102. 
     
103. void show()
     
104. {
     
105.         for (int i = 0; i < num; i++)
     
106.         {
     
107.                 cout << P[i].x << " " << P[i].y << endl;
     
108.         }
     
109. }
     
110. 
     
111. 
     
112. int extend(int a, int b, int& x, int& y)
     
113. {
     
114.         if (b == 0)
     
115.         {
     
116.                 x = 1;
     
117.                 y = 0;
     
118.                 return a;
     
119.         }
     
120.         int r = extend(b, a % b, x, y);
     
121.         int t = x;
     
122.         x = y;
     
123.         y = t - a / b * y;
     
124.         return r;
     
125. }
     
126. 
     
127. //递归扩展欧几里得求逆
     
128. int inv(int a, int b)
     
129. {
     
130.         int x, y;
     
131.         int r = extend(a, b, x, y);
     
132.         if (r != 1)
     
133.         {
     
134.                 return 0;
     
135.         }
     
136.         x = x % b;
     
137.         if (x < 0)
     
138.         {
     
139.                 x = x + b;
     
140.         }
     
141.         return x;
     
142. }
     
143. 
     
144. 
     
145. //加法运算
     
146. point add(point p1, point p2, int a, int p)
     
147. {
     
148.         long t; int flag = 0;
     
149.         int x1 = p1.x; int y1 = p1.y;
     
150.         int x2 = p2.x; int y2 = p2.y;
     
151.         int tx, ty; int x3, y3;
     
152. 
     
153.         if ((x2 == x1) && (y2 == y1))
     
154.         {
     
155.                 //相同点
     
156.                 if (y1 == 0)
     
157.                 {
     
158.                         flag = 1;
     
159.                 }
     
160.                 else
     
161.                 {
     
162.                         t = (3 * x1 * x1 + a) * inv(2 * y1, p) % p;
     
163.                 }
     
164.         }
     
165.         else
     
166.         {
     
167.                 //不同点
     
168.                 ty = y2 - y1;
     
169.                 tx = x2 - x1;
     
170.                 while (tx < 0)
     
171.                 {
     
172.                         tx = tx + p;
     
173.                 }
     
174.                 while (ty < 0)
     
175.                 {
     
176.                         ty = ty + p;
     
177.                 }
     
178. 
     
179.                 if (tx == 0 && ty != 0)
     
180.                 {
     
181.                         flag = 1;
     
182.                 }
     
183.                 else
     
184.                 {
     
185.                         //点不相等
     
186.                         t = ty * inv(tx, p) % p;
     
187.                 }
     
188.         }
     
189. 
     
190.         if (flag == 1)
     
191.         {
     
192.                 //无限点
     
193.                 p2.x = -1;
     
194.                 p2.y = -1;
     
195.         }
     
196.         else
     
197.         {
     
198.                 x3 = (t * t - x1 - x2) % p;
     
199.                 y3 = (t * (x1 - x3) - y1) % p;
     
200.                 while (x3 < 0)
     
201.                 {
     
202.                         x3 += p;
     
203.                 }
     
204.                 while (y3 < 0)
     
205.                 {
     
206.                         y3 += p;
     
207.                 }
     
208.                 p2.x = x3;
     
209.                 p2.y = y3;
     
210.         }
     
211.         return p2;
     
212. }
     
213. 
     
214. //随机选取一个生成元并计算阶
     
215. int jie(point& pp, int a, int p)
     
216. {
     
217.         int ii = rand() % num;
     
218.         point P0 = P[ii];
     
219.         point p1, p2;
     
220.         int number = 1;
     
221.         p1.x = P0.x; p2.x = P0.x;
     
222.         p1.y = P0.y; p2.y = P0.y;
     
223.         while (true)
     
224.         {
     
225.                 p2 = add(p1, p2, a, p);
     
226.                 if (p2.x == -1 && p2.y == -1)
     
227.                 {
     
228.                         break;
     
229.                 }
     
230.                 number++;
     
231.                 if (p2.x == p1.x)
     
232.                 {
     
233.                         break;
     
234.                 }
     
235.         }
     
236.         pp.x = p1.x;
     
237.         pp.y = p1.y;
     
238.         int n = ++number;
     
239.         return n;
     
240. }
     
241. 
     
242. //素数判断
     
243. bool judge(int num)
     
244. {
     
245.         bool ret = true;
     
246.         int ubound = sqrt(num) + 1;
     
247.         for (int i = 2; i < ubound; i++)
     
248.         {
     
249.                 if (num % i == 0)
     
250.                 {
     
251.                         ret = false;
     
252.                         break;
     
253.                 }
     
254.         }
     
255.         return ret;
     
256. }
     
257. 
     
258. //计算kG
     
259. point cal(point G, int k, int a, int p)
     
260. {
     
261.         point temp = G;
     
262.         for (int i = 0; i < k - 1; i++)
     
263.         {
     
264.                 temp = add(temp, G, a, p);
     
265.         }
     
266.         return temp;
     
267. }
     
268. 
     
269. int main()
     
270. {
     
271.         srand(time(NULL));
     
272.         int a, b, p;
     
273.         point generator; int n;
     
274.         char SE[10];
     
275.         char CR[10];
     
276. 
     
277.         cout << "请输入椭圆曲线群（a,b,p）：";
     
278.         cin >> a >> b >> p;
     
279.         cout << "请输入明文：";
     
280.         cin >> SE;
     
281.         cout << "请输入密钥：";
     
282.         cin >> CR;
     
283. 
     
284.         //计算所有点
     
285.         all_points(a, b, p);
     
286.         //选取生成元，直到阶为素数
     
287.         do
     
288.         {
     
289.                 n = jie(generator, a, p);
     
290.         } while (judge(n) == false);
     
291.         cout << endl << "选取生成元（" << generator.x << "," << generator.y << "）,阶为：" << n << endl;
     
292.         //选取私钥
     
293.         int ka = int(CR[0]) % (n - 1) + 1;//选取使用的密钥
     
294.         point pa = cal(generator, ka, a, p);//计算公钥
     
295.         cout << "私钥：" << ka << endl;
     
296.         cout << "公钥：（" << pa.x << "," << pa.y << "）" << endl;
     
297. 
     
298.         //加密
     
299.         int k = 0;//随机数k
     
300.         k = rand() % (n - 2) + 1;
     
301.         point C1 = cal(generator, k, a, p);//计算C1
     
302. 
     
303.         //m嵌入到椭圆曲线
     
304.         int t = rand() % num; //选择映射点
     
305.         point Pt = P[t];
     
306.         point P2 = cal(pa, k, a, p);
     
307.         point Pm = add(Pt, P2, a, p);
     
308.         cout << endl << "要发送的密文：" << endl;
     
309.         cout << "kG=(" << C1.x << "," << C1.y << "),pt+kPa=(" << Pm.x << "," << Pm.y << ")";
     
310.         int C[100];
     
311.         cout << ",C = { ";
     
312.         for (int i = 0; i < strlen(SE); i++)
     
313.         {
     
314.                 C[i] = int(SE[i]) * Pt.x + Pt.y;//选取要加密的明文
     
315.                 cout << C[i] << " ";
     
316.         }
     
317.         cout << "}" << endl;
     
318. 
     
319. 
     
320.         //解密
     
321.         point temp, temp1;
     
322.         int m;
     
323.         temp = cal(C1, ka, a, p);
     
324.         temp.y = 0 - temp.y;
     
325.         temp1 = add(Pm, temp, a, p);//求解Pt
     
326.         printf("\n解密结果：\n");
     
327.         for (int i = 0; i < strlen(SE); i++)
     
328.         {
     
329.                 m = (C[i] - temp1.y) / temp1.x;
     
330.                 printf("%c", char(m));//输出密文
     
331.         }
     
332.         printf("\n");
     
333. 
     
334.         return 0;
     
335. }

复制代码