信息计算2019级1班23号姚俣譞

姚俣譞

一、RSA加解密和签名

1、RSA加密
   RSA的密文是对代表了明文的数字的E次方求mod N的结果。换句话说，就是将明文和自己做E次乘方，然后将其结果除以N求余数，这个余数就是密文。
   即：密文 = 明文E mod N
  只要知道E和N，就可以完成加密， 因此E和N的组合{E，N}，就是「公钥」。
2、RSA解密
  将密文自己做D次乘法，再对其结果除以N求余数，就可以得到明文。（解密的N和加密的N是同一个）
  即：明文 = 密文D mod N
  知道了D和N，就可以完成解密，因此D和N的组合{D，N}，就是私钥。
3.代码和运行        （代码见后面跟的帖子）

二、ECC算法

    ECC是建立在基于椭圆曲线的离散对数问题上的密码体制，给定椭圆曲线上的一个点G，并选取一个整数k，求解K=kG很容易，反过来，在椭圆曲线上给定两个点K和G，若使K=kG，求整数k是一个难题。ECC就是建立在此数学难题之上,这一数学难题称为椭圆曲线离散对数问题。其中椭圆曲线上的点K则为公钥，整数k则为私钥。


代码和运行如下：

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. }

复制代码

姚俣譞

附上第一个报告的代码 不知道为什么编辑直接弄没了

1. package test;
   
2. 
   
3. 
   
4. import javax.crypto.Cipher;
   
5. import java.nio.charset.StandardCharsets;
   
6. import java.security.*;
   
7. import java.security.interfaces.RSAPrivateKey;
   
8. import java.security.interfaces.RSAPublicKey;
   
9. import java.security.spec.PKCS8EncodedKeySpec;
   
10. import java.security.spec.X509EncodedKeySpec;
    
11. import java.util.Base64;
    
12. import java.util.HashMap;
    
13. import java.util.Map;
    
14. 
    
15. 
    
16. public class RsaCoder {
    
17.     private static Map<Integer, String> keyMap = new HashMap<>();  
    
18. 
    
19. 
    
20.     public static void main(String[] args) throws Exception {
    
21.         //生成公钥和私钥
    
22.         genKeyPair();
    
23.         //加密字符串
    
24.         String message = "As broken mirror never put together,see you never again.";
    
25. 
    
26.         String messageEn = encrypt(message, keyMap.get(0));
    
27.         System.out.println(message + "\t加密后的字符串为:" + messageEn);
    
28.         String messageDe = decrypt(messageEn, keyMap.get(1));
    
29.         System.out.println("还原后的字符串为:" + messageDe+"亦如破镜难圆，后会无期");
    
30.     }
    
31. 
    
32. 
    
33. 
    
34.     public static String encrypt(String str, String publicKey) throws Exception {
    
35.         PublicKey pubKey = getPublicKey(publicKey);
    
36.         //RSA加密
    
37.         Cipher cipher = Cipher.getInstance("RSA");//Java 默认的 RSA 实现是 "RSA/None/PKCS1Padding"
    
38.         cipher.init(Cipher.ENCRYPT_MODE, pubKey);
    
39.         String outStr = Base64.getEncoder().encodeToString(cipher.doFinal(str.getBytes(StandardCharsets.UTF_8)));
    
40.         return outStr;
    
41.     }
    
42. 
    
43.    
    
44.     public static String decrypt(String str, String privateKey) throws Exception {
    
45.         //64位解码加密后的字符串
    
46.         byte[] inputByte = Base64.getDecoder().decode(str.getBytes());
    
47.         //得到RSAPrivateKey
    
48.         PrivateKey priKey = getPrivateKey(privateKey);
    
49.         //RSA解密
    
50.         Cipher cipher = Cipher.getInstance("RSA");
    
51.         cipher.init(Cipher.DECRYPT_MODE, priKey);
    
52.         String outStr = new String(cipher.doFinal(inputByte));
    
53.         return outStr;
    
54.     }
    
55. 
    
56.     // 从string转public key
    
57.     public static PublicKey getPublicKey(String key) throws Exception {
    
58.         byte[] keyBytes = Base64.getDecoder().decode(key);
    
59.         X509EncodedKeySpec keySpec = new X509EncodedKeySpec(keyBytes);
    
60.         KeyFactory keyFactory = KeyFactory.getInstance("RSA");
    
61.         PublicKey publicKey = keyFactory.generatePublic(keySpec);
    
62.         return publicKey;
    
63.     }
    
64. 
    
65.     // 从string转private key
    
66.     public static PrivateKey getPrivateKey(String key) throws Exception {
    
67.         byte[] keyBytes;
    
68.         keyBytes = Base64.getDecoder().decode(key);
    
69.         PKCS8EncodedKeySpec keySpec = new PKCS8EncodedKeySpec(keyBytes);
    
70.         KeyFactory keyFactory = KeyFactory.getInstance("RSA");
    
71.         PrivateKey privateKey = keyFactory.generatePrivate(keySpec);
    
72.         return privateKey;
    
73.     }
    
74. 
    
75. 
    
76.     private static void genKeyPair() throws NoSuchAlgorithmException {
    
77. 
    
78.         KeyPairGenerator keyPairGen = KeyPairGenerator.getInstance("RSA");
    
79.       
    
80.         keyPairGen.initialize(1024, new SecureRandom());
    
81.         
    
82.         KeyPair keyPair = keyPairGen.generateKeyPair();
    
83.         RSAPrivateKey privateKey = (RSAPrivateKey) keyPair.getPrivate();   // 得到私钥
    
84.         RSAPublicKey publicKey = (RSAPublicKey) keyPair.getPublic();  // 得到公钥
    
85.         String publicKeyString = Base64.getEncoder().encodeToString(publicKey.getEncoded());
    
86.         // 得到私钥字符串
    
87.         String privateKeyString = Base64.getEncoder().encodeToString(privateKey.getEncoded());
    
88.         // 将公钥和私钥保存到Map
    
89.         keyMap.put(0, publicKeyString);  //0表示公钥
    
90.         keyMap.put(1, privateKeyString);  //1表示私钥

复制代码