信息计算2019级2班25号裴焕权

裴焕权

RSA

RSA算法产生密钥的过程： 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. p1.x = P0.x; p2.x = P0.x;
   
2.         p1.y = P0.y; p2.y = P0.y;
   
3.         while (true)
   
4.         {
   
5.                 p2 = add(p1, p2, a, p);
   
6.                 if (p2.x == -1 && p2.y == -1)
   
7.                 {
   
8.                         break;
   
9.                 }
   
10.                 number++;
    
11.                 if (p2.x == p1.x)
    
12.                 {
    
13.                         break;
    
14.                 }
    
15.         }
    
16.         pp.x = p1.x;
    
17.         pp.y = p1.y;
    
18.         int n = ++number;
    
19.         return n;
    
20. }
    
21. 
    
22. //素数判断
    
23. bool judge(int num)
    
24. {
    
25.         bool ret = true;
    
26.         int ubound = sqrt(num) + 1;
    
27.         for (int i = 2; i < ubound; i++)
    
28.         {
    
29.                 if (num % i == 0)
    
30.                 {
    
31.                         ret = false;
    
32.                         break;
    
33.                 }
    
34.         }
    
35.         return ret;
    
36. }
    
37. 
    
38. //计算kG
    
39. point cal(point G, int k, int a, int p)
    
40. {
    
41.         point temp = G;
    
42.         for (int i = 0; i < k - 1; i++)
    
43.         {
    
44.                 temp = add(temp, G, a, p);
    
45.         }
    
46.         return temp;
    
47. }
    
48. 
    
49. int main()
    
50. {
    
51.         srand(time(NULL));
    
52.         int a, b, p;
    
53.         point generator; int n;
    
54.         char SE[10];
    
55.         char CR[10];
    
56. 
    
57.         cout << "请输入椭圆曲线群（a,b,p）：";
    
58.         cin >> a >> b >> p;
    
59.         cout << "请输入明文：";
    
60.         cin >> SE;
    
61.         cout << "请输入密钥：";
    
62.         cin >> CR;
    
63. 
    
64.         //计算所有点
    
65.         all_points(a, b, p);
    
66.         //选取生成元，直到阶为素数
    
67.         do
    
68.         {
    
69.                 n = jie(generator, a, p);
    
70.         } while (judge(n) == false);
    
71.         cout << endl << "选取生成元（" << generator.x << "," << generator.y << "）,阶为：" << n << endl;
    
72.         //选取私钥
    
73.         int ka = int(CR[0]) % (n - 1) + 1;//选取使用的密钥
    
74.         point pa = cal(generator, ka, a, p);//计算公钥
    
75.         cout << "私钥：" << ka << endl;
    
76.         cout << "公钥：（" << pa.x << "," << pa.y << "）" << endl;
    
77. 
    
78.         //加密
    
79.         int k = 0;//随机数k
    
80.         k = rand() % (n - 2) + 1;
    
81.         point C1 = cal(generator, k, a, p);//计算C1
    
82. 
    
83.         //m嵌入到椭圆曲线
    
84.         int t = rand() % num; //选择映射点
    
85.         point Pt = P[t];
    
86.         point P2 = cal(pa, k, a, p);
    
87.         point Pm = add(Pt, P2, a, p);
    
88.         cout << endl << "要发送的密文：" << endl;
    
89.         cout << "kG=(" << C1.x << "," << C1.y << "),pt+kPa=(" << Pm.x << "," << Pm.y << ")";
    
90.         int C[100];
    
91.         cout << ",C = { ";
    
92.         for (int i = 0; i < strlen(SE); i++)
    
93.         {
    
94.                 C[i] = int(SE[i]) * Pt.x + Pt.y;//选取要加密的明文
    
95.                 cout << C[i] << " ";
    
96.         }
    
97.         cout << "}" << endl;
    
98. 
    
99. 
    
100.         //解密
     
101.         point temp, temp1;
     
102.         int m;
     
103.         temp = cal(C1, ka, a, p);
     
104.         temp.y = 0 - temp.y;
     
105.         temp1 = add(Pm, temp, a, p);//求解Pt
     
106.         printf("\n解密结果：\n");
     
107.         for (int i = 0; i < strlen(SE); i++)
     
108.         {
     
109.                 m = (C[i] - temp1.y) / temp1.x;
     
110.                 printf("%c", char(m));//输出密文
     
111.         }
     
112.         printf("\n");
     
113. 
     
114.         return 0;
     
115. }

复制代码

裴焕权

1. //RSA解密。
   
2.     private String decryption(BigInteger[] c, BigInteger d, BigInteger n) {
   
3.         String cPadding = "";
   
4.         String mToString = "";
   
5.         int mToStringLengthMod = 0;
   
6.         BigInteger m = BigInteger.ZERO;
   
7.         for (int i = 0; i < c.length; i++) {// 逐组解密
   
8.             m = RSA4.expMod(c[i], d, n);
   
9.             mToString = m.toString();
   
10.             mToStringLengthMod = m.toString().length() % 3;
    
11.             if (mToStringLengthMod != 0) {// 由于加密时String转BigInter时前者前面的0并不会计入，所以需要确认并补全
    
12.                 for (int j = 0; j < 3 - mToStringLengthMod; j++) {
    
13.                     mToString = "0" + mToString;
    
14.                 }
    
15.             }
    
16.             cPadding += mToString;
    
17.         }
    
18. 
    
19.         int byteNum = cPadding.length() / 3;// 明文总字节数
    
20.         byte[] result = new byte[byteNum];
    
21.         for (int i = 0; i < byteNum; i++) {// 每三位数转化为byte型并返回该byte数组所表达的字符串
    
22.             result[i] = (byte) (Integer.parseInt(cPadding.substring(i * 3, i * 3 + 3)));
    
23.         }
    
24.         return new String(result);
    
25.     }
    
26. 
    
27. 
    
28.     //利用扩展欧几里得算法求出私钥d，使得de = kφ(n)+1，k为整数。
    
29.     private static BigInteger[] extdGcd(BigInteger e, BigInteger φn) {
    
30.         BigInteger[] gdk = new BigInteger[3];
    
31. 
    
32.         if (φn.compareTo(BigInteger.ZERO) == 0) {
    
33.             gdk[0] = e;
    
34.             gdk[1] = BigInteger.ONE;
    
35.             gdk[2] = BigInteger.ZERO;
    
36.             return gdk;
    
37.         } else {
    
38.             gdk = extdGcd(φn, e.remainder(φn));
    
39.             BigInteger tmp_k = gdk[2];
    
40.             gdk[2] = gdk[1].subtract(e.divide(φn).multiply(gdk[2]));
    
41.             gdk[1] = tmp_k;
    
42.             return gdk;
    
43.         }
    
44.     }
    
45. 
    
46.     // 利用米勒·罗宾算法判断一个数是否是质数。
    
47.     private static boolean isPrime(BigInteger p) {
    
48.         if (p.compareTo(BigInteger.TWO) == -1) {// 小于2直接返回false
    
49.             return false;
    
50.         }
    
51.         if ((p.compareTo(BigInteger.TWO) != 0) && (p.remainder(BigInteger.TWO).compareTo(BigInteger.ZERO) == 0)) {// 不等于2且是偶数直接返回false
    
52.             return false;
    
53.         }
    
54. 
    
55.         BigInteger p_1 = p.subtract(BigInteger.ONE);
    
56.         BigInteger m = p_1;// 找到q和m使得p = 1 + 2^q * m
    
57.         int q = m.getLowestSetBit();// 二进制下从右往左返回第一次出现1的索引
    
58.         m = m.shiftRight(q);
    
59. 
    
60.         for (int i = 0; i < 5; i++) {// 判断的轮数，精度、轮数和时间三者之间成正比关系
    
61.             BigInteger b;
    
62.             do {// 在区间1~p上生成均匀随机数
    
63.                 b = new BigInteger(String.valueOf(p.bitLength()));
    
64.             } while (b.compareTo(BigInteger.ONE) <= 0 || b.compareTo(p) >= 0);
    
65. 
    
66.             int j = 0;
    
67.             BigInteger z = RSA4.expMod(b, m, p);
    
68.             while (!((j == 0 && z.equals(BigInteger.ONE)) || z.equals(p_1))) {
    
69.                 if ((j > 0 && z.equals(BigInteger.ONE)) || ++j == q) {
    
70.                     return false;
    
71.                 }
    
72.                 z = RSA4.expMod(z, BigInteger.TWO, p);
    
73.             }
    
74.         }
    
75. 
    
76.         return true;
    
77.     }
    
78. 
    
79.     private static BigInteger generateNBitRandomPrime(int n) {
    
80.         BigInteger tmp = new BigInteger("2").pow(n - 1);// 最高位肯定是1
    
81.         BigInteger result = new BigInteger("2").pow(n - 1);
    
82.         Random random = new Random();
    
83.         int r1 = random.nextInt(101);// 产生0-100的整数，用于确定0和1的比例
    
84.         int r2;
    
85. 
    
86.         while (true) {// 循环产生数，直到该数为素数
    
87.             for (int i = n - 2; i >= 0; i--) {// 逐位产生表示数的0和1，并根据所在位计算结果相加起来
    
88.                 r2 = random.nextInt(101);
    
89.                 if (0 < r2 && r2 < r1) {// 产生的数为1
    
90.                     result = result.add(BigInteger.TWO.pow(i));
    
91.                 }
    
92.                 continue;
    
93.             }
    
94. 
    
95.             if (RSA4.isPrime(result)) {// 素数判断
    
96.                 return result;
    
97.             }
    
98. 
    
99.             result = tmp;// 重新计算
    
100.         }
     
101.     }
     
102. 
     
103.     //蒙哥马利快速幂模运算，返回base^exponent mod module的结果。
     
104.     private static BigInteger expMod(BigInteger base, BigInteger exponent, BigInteger module) {
     
105.         BigInteger result = BigInteger.ONE;
     
106.         BigInteger tmp = base.mod(module);
     
107. 
     
108.         while (exponent.compareTo(BigInteger.ZERO) != 0) {
     
109.             if ((exponent.and(BigInteger.ONE).compareTo(BigInteger.ZERO)) != 0) {
     
110.                 result = result.multiply(tmp).mod(module);
     
111.             }
     
112.             tmp = tmp.multiply(tmp).mod(module);
     
113.             exponent = exponent.shiftRight(1);
     
114.         }
     
115.         return result;
     
116.     }
     
117. 
     
118.     //判断是否互素
     
119.     public static boolean fun(BigInteger x, BigInteger y) {
     
120.         BigInteger t;
     
121.         while (!(y.equals(new BigInteger("0")))) {
     
122.             t = x;
     
123.             x = y;
     
124.             y = t.mod(y);
     
125.         }
     
126.         if (x.equals(new BigInteger("1")))
     
127.             return false;
     
128.         else
     
129.             return true;
     
130.     }
     
131. 
     
132.     public BigInteger bigRandom(int numDigits) {
     
133.         // 产生一个随机大整数，各位上的数字都是随机产生的，首位不为 0
     
134.         StringBuffer s = new StringBuffer("");
     
135.         for (int i = 0; i < numDigits; i++)
     
136.             if (i == 0)
     
137.                 s.append(randomDigit(false));
     
138.             else
     
139.                 s.append(randomDigit(true));
     
140.         return (new BigInteger(s.toString()));
     
141.     }
     
142. 
     
143.     private StringBuffer randomDigit(boolean isZeroOK) {
     
144.         // 产生一个随机的数字（字符串形式的），isZeroOK 决定这个数字是否可以为 0
     
145.         int index;
     
146.         if (isZeroOK)
     
147.             index = (int) Math.floor(Math.random() * 10);
     
148.         else
     
149.             index = 1 + (int) Math.floor(Math.random() * 9);
     
150.         return (digits[index]);
     
151.     }
     
152. 
     
153.     private static StringBuffer[] digits = {
     
154.             new StringBuffer("0"),
     
155.             new StringBuffer("1"), new StringBuffer("2"),
     
156.             new StringBuffer("3"), new StringBuffer("4"),
     
157.             new StringBuffer("5"), new StringBuffer("6"),
     
158.             new StringBuffer("7"), new StringBuffer("8"), new StringBuffer("9")};
     
159. 
     
160.     public BigInteger nextPrime(BigInteger start) {
     
161.         if (isEven(start))
     
162.             start = start.add(ONE);
     
163.         else
     
164.             start = start.add(TWO);
     
165.         if (start.isProbablePrime(ERR_VAL))
     
166.             return (start);
     
167.         else
     
168.             return (nextPrime(start));
     
169.     }
     
170. 
     
171.     private static boolean isEven(BigInteger n) {
     
172.         // 测试一个大整数是否为偶数
     
173.         return (n.mod(TWO).equals(ZERO));
     
174.     }
     
175. }

复制代码

裴焕权

ECC
原理
1、用户A选定一条椭圆曲线Ep(a,b)，并取椭圆曲线上一点，作为基点G；
2、用户A选择一个私有密钥k，并生成公开密钥K=kG；
3、用户A将Ep(a,b)和点K，G传给用户B；
4、用户B接到信息后 ，将待传输的明文编码到Ep(a,b)上一点M，并产生一个随机整数r；
5、用户B计算点C1=M+rK，C2=rG；
6、用户B将C1、C2传给用户A；
7、用户A接到信息后，计算C1-kC2，结果就是点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. }

复制代码