信息计算2019级2班14号张柯冕

张柯冕

RSA算法

RSA加密算法是一种非对称加密算法，所谓非对称，就是指该算法加密和解密使用不同的密钥，即使用加密密钥进行加密、解密密钥进行解密。在RAS算法中，加密密钥（即公开密钥）PK是公开信息，而解密密钥（即秘密密钥）SK是需要保密的。优点是不需要进行密钥传递，提高了安全性，可以进行数字签名认证。

原理： 1.系统产生两个大素数p, q（保密）
2.计算n=pq（公开），欧拉函数Φ(n)=(p-1)(q-1)(保密)
3.随机选择满足gcd(e,Φ(n))=1的e作为公钥(公开)，加密密钥就是(e,n)
4.计算满足ed=1(mod Φ(n))的d作为私钥(保密)，解密密钥即为(d,n)

RSA的加解密过程： 首先将明文分组并数字化，每个数字化分组明文的长度不大于log n，然后对每个明文分组m依次进行加解密运算。
1.加密运算：使用公钥e和要加密的明文m进行c=me(mod n)运算即得密文
2.解密运算：使用私钥d和要加密的明文m进行c=md(mod n)运算即得明文。

1. package RSA;
   
2. 
   
3. import java.awt.desktop.SystemEventListener;
   
4. import java.util.Scanner;
   
5. 
   
6. public class Demo {
   
7.     //判断是否是素数
   
8.     public static boolean isPrime(long n) {
   
9.         boolean b = true;
   
10.         for (long i = 2; i <= Math.sqrt(n); i++) {
    
11.             if (n % i == 0) {
    
12.                 b = false;
    
13.                 break;
    
14.             } else
    
15.                 b = true;
    
16.         }
    
17.         return b;
    
18.     }
    
19. 
    
20.     //计算欧拉数
    
21.     public static long Euler(long p, long q) {
    
22.         return (p - 1) * (q - 1);
    
23.     }
    
24. 
    
25.     //欧几里得算法求两数的最大公因数---a>b
    
26.     static long gcd(long a, long b) {
    
27.         if (a < b) {
    
28.             long t = a;
    
29.             a = b;
    
30.             b = t;
    
31.         }
    
32.         if (a % b == 0) return b;
    
33.         else return gcd(b, a % b);
    
34.     }
    
35. 
    
36.     //求模反元素d（私钥）
    
37.     public static long Key(long e, long euler) {
    
38.         long key = 1;
    
39.         while ((key * e) % euler != 1) {
    
40.             key++;
    
41.         }
    
42.         return key;
    
43.     }
    
44. 
    
45.     //递归求n次方
    
46.     public static long power(long a, long n) {
    
47.         long r = 1;
    
48.         if (n == 0) r = 1;
    
49.         else {
    
50.             r = a * power(a, n - 1);
    
51.         }
    
52.         return r;
    
53.     }
    
54. 
    
55.     //加密
    
56.     public static long encryption(long msg, long e, long n) {
    
57.         System.out.println("加密中.......");
    
58.         return power(msg, e) % n;
    
59.     }
    
60. 
    
61.     //解密
    
62.     public static long decryption(long c, long key, long n) {
    
63.         System.out.println("解密中.......");
    
64.         return power(c, key) % n;
    
65.     }
    
66. 
    
67.     public static void main(String[] args) {
    
68.         System.out.println("--------RSA--------");
    
69.         //两个大素数
    
70.         long p;
    
71.         long q;
    
72.         System.out.print("输入两个大素数p、q：");
    
73.         Scanner sc = new Scanner(System.in);
    
74.         p = sc.nextLong();
    
75.         q = sc.nextLong();
    
76.         // System.out.println("p = " + p + ",q = " + q);
    
77.         //判断输入的是否是素数
    
78.         boolean b;   //flag
    
79.         //判断p
    
80.         b = isPrime(p);
    
81.         if (b == false) {
    
82.             System.out.println("p = " + p + "不是素数。重新输入p！");
    
83.             p = sc.nextLong();
    
84.             b = isPrime(p);
    
85.             while (b = false) {
    
86.                 System.out.println("p = " + p + "不是素数。重新输入p！");
    
87.                 p = sc.nextLong();
    
88.                 b = isPrime(p);
    
89.             }
    
90.         }
    
91.         System.out.println(" p = " + p + "是素数。");
    
92. 
    
93.         //判断q
    
94.         b = isPrime(q);
    
95.         if (b == false) {
    
96.             System.out.println("q = " + q + "不是素数。重新输入q！");
    
97.             q = sc.nextLong();
    
98.             b = isPrime(q);
    
99.             while (b = false) {
    
100.                 System.out.println("q = " + q + "不是素数。重新输入q！");
     
101.                 q = sc.nextLong();
     
102.                 b = isPrime(q);
     
103.             }
     
104.         }
     
105.         System.out.println(" q = " + q + "是素数。");
     
106.         //打印最终的p、q
     
107.         System.out.println("p = " + p + ",q = " + q);
     
108. 
     
109.         //计算p、q的欧拉数
     
110.         long euler = Euler(p, q);
     
111.         System.out.println("Euler(p,q) = " + euler);
     
112. 
     
113.         //选取最小的公钥e，1<e<euler，且与euler互质
     
114.         long e = 2;
     
115.         while (gcd(e, euler) != 1 || e > euler || e < 1) {
     
116.             e++;
     
117.         }
     
118.         System.out.println("e = " + e);
     
119. 
     
120.         //求出模反元素（私钥）
     
121.         long key = Key(e, euler);
     
122.         System.out.println("key = " + key);
     
123. 
     
124.         //System.out.println(power(2, 2));
     
125.         //加密过程
     
126.         System.out.println("输入明文：");
     
127.         long msg = sc.nextLong();
     
128.         System.out.println("明文：" + msg);
     
129.         long c = encryption(msg, e, p * q);//密文
     
130.         System.out.println("加密后的密文：" + c);
     
131.         //解密过程
     
132.         msg = decryption(c, key, p * q);
     
133.         System.out.println("解密后的明文：" + msg);
     
134. 
     
135.     }
     
136. }

复制代码

张柯冕

ECC算法

ECC是Elliptic Curve Cryptography（椭圆曲线密码学）的缩写，是一种基于椭圆曲线数学的公开密钥加密算法，其本质是利用离散对数问题实现加密。
ECC的主要优势，是在使用更小的密钥的同时，提供更快的性能和更高等级的安全。


ECC算法原理：
描述一条Fp上的椭圆曲线，常用到六个参量：T=(p,a,b,n,x,y)。
（p 、a 、b） 用来确定一条椭圆曲线，p为素数域内点的个数，a和b是其内的两个大数；
x,y为G基点的坐标，也是两个大数；
n为点G基点的阶；
以上六个量就可以描述一条椭圆曲线，有时候我们还会用到h(椭圆曲线上所有点的个数p与n相除的整数部分)。
现在我们描述一个利用椭圆曲线进行加密通信的过程：
1、选定一条椭圆曲线 Ep(a,b) 并取椭圆曲线上一点，作为基点P。
2、选择一个大数k作为私钥，并生成公钥 Q=kP。
3、将 Ep(a,b) 和点Q、P传给用户。
4、用户接到信息后 ，将待传输的明文编码到Ep(a,b)上的一点M，并产生一个随机整数r。
5、公钥加密（密文C是一个点对）：
C={rP, M+rQ}
6、私钥解密（M + rQ - k(rP) ，解密结果就是点M），公式如下：

        M + rQ - k(rP) = M + r(kP) - k(rP) = M
7、对点M进行解码就可以得到明文
假设在加密过程中，有一个第三者H，H只能知道椭圆曲线 Ep(a,b)、公钥Q、基点P、密文点C，而通过公钥Q、基点P求私钥k或者通过密文点C、基点P求随机数r都是非常困难的，因此得以保证数据传输的安全。
代码：

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

复制代码