P4358

WeLikeStudying · 2021-11-17 19:15:01 · 题解

背景

• RSA加密算法。
• 似乎是因为它数论才备受重视。
• 本题题面。
• 为什么我们不可以用这种方式破译呢？
• 给出一组数据：到 2009 年，常用的大质数乘积 N 一般在 768 到 2048 个（二进制）位之间，这显然远远超出我们的处理范围。
• 另外为了下面的方便，我们重新给出了 \text{RSA} 的定义方式。
• 给出质数 p,q（应该满足 p\ne q），取 N=p\times q，r=(p-1)\times(q-1)，取 e\perp r，取其模 r 下的逆元 d。
• 当 a\perp p 时，a^{p-1}=a\pmod p，否则 p|a，a^{p-1}=0=a\pmod p。
• 故容易得到 (a^e)^d=a^{e\times d}=a\pmod N，但给出 e,N，要求 d 是困难的，所以每个人都可以利用公钥 N,e 对文章加密，但持有私钥 N,d 才能解密。

题意

• 给出 e,N,c，求 d,n 其中 c=n^e\pmod N，它代表着密文。
• 题面中给出的数据保证不大于 2^{62}。

思路

• 如果能得到 N 的质因数分解 p\times q，即可得到 r=(p-1)\times(q-1)，接着求 e 模 r 下的逆元即可得到 d，最后计算 c^d\bmod N 即可得到 n。
• 后面我们会说明没有比分解 N 更简单的方法。
• 但这里 N 的规模达到了 2^{62}，普通的试除法行不通。
• 可以观看质因数分解模板题的题解了解如何分解这个规模的大数。
• 不过由于这题的特殊性质，我们并不需要 Miller-Rabin 来判断是不是质数这不更好不用担心自己 RP。
• 另外由于模数并不是质数，需要用拓展欧几里得求解逆元。
• 代码实现。
• 下面是关于这道题目的一些拓展，引自《算法导论》。

一些有趣的性质

• 设 P(n)=n^e\bmod N 函数用来表示加密过程。
• 显然 P(a)\times P(b)\equiv P(a\times b)\pmod N，同样的性质对解密也成立。
• 下面我们来证明：如果你有一种算法能较好地破译模 N 意义下 1\% 的 P(a)，那么你可以运行一种概率性算法以破译每一个 P(a)。
• 方法：随机一个 b，利用公钥计算 P(b) 和 P(a)\times P(b)=P(a\times b)，如果能破译出（以 1\% 的概率） a\times b，那么我们即可破译出 a。