2019年第十届蓝桥杯JAVA G组——试题 E: RSA 解密

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了2019年第十届蓝桥杯JAVA G组——试题 E: RSA 解密，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4093字，纯文字阅读大概需要6分钟。

内容图文

【问题描述】

本题总分：15 分

RSA 是一种经典的加密算法。它的基本加密过程如下。

首先生成两个质数 p, q，令 n = p · q，设 d 与 (p ? 1) · (q ? 1) 互质，则可

找到 e 使得 d · e 除 (p ? 1) · (q ? 1) 的余数为 1。n, d, e 组成了私钥，n, d

组成了公钥。当使用公钥加密一个整数 X 时（小于 n），计算 C = X^d mod n，

则 C 是加密后的密文。当收到密文 C 时，可使用私钥解开，计算公式为 X = C^e mod n。

例如，当 p = 5, q = 11, d = 3 时，n = 55, e = 27。若加密数字 24，得 243 mod 55 = 19。解密数字 19，得 1927 mod 55 = 24。

现在你知道公钥中 n = 1001733993063167141, d = 212353，同时你截获了别人发送的密文 C = 20190324，请问，原文是多少？

【答案提交】这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

 分析

这题一开始想通过暴力搜索将p和q算出来，再去。。。等，后来发现自己的思路已经错了，然后去看了一位大神的博客，他里面是先求e，然后利用公式 X = C^e mod n求出原来加密之前的整数。 因为经过发现我们可以知道这里其实是要用一个叫作拓展欧几里得原理的，拓展欧几里得原理也是基于两个数求最大公约数而来的。

拓展欧几里得原理可以用来解这样的不定方程：
aX + bY = c(求X,Y)
若c不是gcd(a,b)的倍数，则该不定方程一定无解
则问题可以转化为求不定方程的一组解{x,y}：
aX + by = gcd(a,b)

这个求解过程用到了扩展欧几里得原理、快速幂和快速乘。要是不用后面的两个快速算法，那么时间会很长，因为题目所给的数字毕竟很大。

AC代码

 1 public class RSA {
 2     public static long p, q, m, x, y, n = 1001733993063167141L;
 3 
 4     public static void main(String[] args) {
 5 
 6         long d = 212353L;
 7         long c = 20190324L;
 8         p = 2;
 9         // 先求p、q
10         while (true) {
11             if ((n / p) * p == n) {
12                 q = n / p;
13                 break;
14             }
15             p++;
16         }
17         // 再求e
18         m = (p - 1) * (q - 1);
19         // ans[1] == x ans[2] = y
20         long[] ans = exgcd(d, m);
21         // 这里是因为e可能为负数，这里的m是个很大的数，跟n差不多一个数量级
22         ans[1] = (ans[1] + m) % m; // 579706994112328949
23         // X = C^e % n
24         System.out.println(qpow(c, ans[1]));
25     }
26 
27     /**
28      * 扩展欧几里得算法：
29      * 我们知道，欧几里得公式可以由这个式子表示：
30      * gcd(a,b) = gcd(b, a%b)
31      * 不断往下连等，直到b = 0，此时a即为最大公约数
32      * @param a
33      * @param b
34      * @return
35      */
36     public static long[] exgcd(long a, long b) {
37         long ans;
38         long[] result = new long[3];
39         if (b == 0) {
40             result[0] = a;
41             // 这里的result[1]、result[2]分别相当于一个解中的x、y
42             result[1] = 1;
43             result[2] = 0;
44             return result;
45         }
46         // temp数组中存储的是上一组的解，temp[1]相当于X2，temp[2]相当于Y2
47         long[] temp = exgcd(b, a % b);
48         // result[0]存储的就是两个数的最大公约数
49         ans = temp[0];
50         result[0] = ans;
51         // 这里result[1]相当于X1，result[2]相当于Y1
52         result[1] = temp[2];
53         result[2] = temp[1] - (a / b) * temp[2];
54         return result;
55     }
56 
57     /**
58      * 快速幂
59      * @param a
60      * @param b
61      * @return
62      */
63     public static long qpow(long a, long b) {
64         // 累乘就初始为1
65         long ans = 1;
66         while (b > 0) {
67             if (b % 2 == 1)
68                 ans = qmul(ans, a);
69             a = qmul(a, a);
70             b /= 2;
71         }
72         return ans;
73     }
74 
75     /**
76      * 快速乘，将b不断的缩小，a不断的扩大，这样也能像快速幂缩指数一样提高程序的运行效率
77      * 如果是原始的两数相乘，在底层时要做b次的加法，现在只需要b / 2次的加法
78      * @param a
79      * @param b
80      * @return
81      */
82     public static long qmul(long a, long b) {
83         // 累加就初始为0
84         long ans = 0;
85         while (b > 0) {
86             if (b % 2 == 1) {
87                 ans += a;
88                 ans %= n;
89             }
90             a *= 2;
91             a %= n;
92             b /= 2;
93         }
94         return ans;
95     }
96 }

内容总结

以上是互联网集市为您收集整理的2019年第十届蓝桥杯JAVA G组——试题 E: RSA 解密全部内容，希望文章能够帮你解决2019年第十届蓝桥杯JAVA G组——试题 E: RSA 解密所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端