第 7 章：RSA的指数选择与解密正确性

7.1 公钥、私钥和模数各自做什么

取两个不同的奇质数 $p,q$ ，令 $n=pq$ 。消息 $m$ 用模 $n$ 的一个剩余类表示。公钥是 $(n,e)$ ，加密把 $m$ 变为 $c\equiv m^e\pmod n$ ；私钥指数 $d$ 用于计算 $c^d\pmod n$ 。

要让解密回到 $m$ ，需要安排 $(m^e)^d=m^{ed}$ 与 $m$ 同余。做法是选择 $e,d$ 满足

$ed\equiv1\pmod{\varphi(n)},\qquad \varphi(n)=(p-1)(q-1).$

于是存在非负整数 $h$ 使 $ed=1+h\varphi(n)$ 。两个指数相乘后的“多余部分”是欧拉指数的倍数，这是它与欧拉定理连接的地方。

7.2 这些指数为什么一定可以选出来

先计算 $\varphi(n)$ ，再选择与它互质的正整数 $e$ 。由第1章的逆元条件， $e$ 模 $\varphi(n)$ 有逆元 $d$ ，可以用扩展欧几里得算法算出，并取一个正整数代表。

因此 $e,d$ 并非任意设定后再假定它们满足关系；先选择互质的 $e$ ，逆元定理保证 $d$ 存在。这里逆元的模数是 $\varphi(n)$ ，加密时的模数是 $n$ ，两者用途不同。

对于与 $n$ 互质的消息，欧拉定理直接给出

$m^{ed}=m^{1+h\varphi(n)} =m\,(m^{\varphi(n)})^h\equiv m\pmod n.$

但这只处理了互质消息。若消息含有 $p$ 或 $q$ 这个因子，不能继续套用模 $n$ 的欧拉定理；需要下面的逐质数证明。

7.3 不互质的消息为什么也能还原

先对 $p$ 证明 $m^{ed}\equiv m$ ，分成两个互补的情况。

若 $p\mid m$ ，因为 $ed\ge1$ ， $m^{ed}$ 和 $m$ 模 $p$ 都为0。若 $p\nmid m$ ，可以用费马小定理 $m^{p-1}\equiv1\pmod p$ 。而 $p-1$ 整除 $\varphi(n)$ ，故也整除 $ed-1$ ，于是

$m^{ed}=m\,(m^{p-1})^{(ed-1)/(p-1)}\equiv m\pmod p.$

无论 $p$ 是否整除消息，模 $p$ 的结论都成立。对 $q$ 完全同理，得到 $m^{ed}\equiv m\pmod q$ 。CRT再把两个结论合起来，得到 $m^{ed}\equiv m\pmod n$ 。

这份证明没有假设消息与 $n$ 互质。它利用的是：在每个质数坐标上，消息要么为0，要么可用费马小定理；两种情况覆盖了全部消息。

7.4 这与分解有什么关系

若能分解 $n$ 得到 $p,q$ ，就能计算 $\varphi(n)$ ，再由公开的 $e$ 计算逆元 $d$ ，从而解密。这证明了

$\text{分解 }n\ \Longrightarrow\ \text{恢复私钥指数并解密}.$

还可以追问：已知 $d$ ，能不能反过来分解 $n$ ？答案是可以使用随机算法；下一章从 $ed-1$ 出发说明为什么。这里的计算关系不直接证明完整签名方案安全；RSA反演与签名伪造的区别在第13章继续说明。

这里讨论RSA的数学幂运算。实际RSA参数可采用更弱的 $ed\equiv1\pmod{\lambda(n)}$ 条件，其中 $\lambda(n)=\operatorname{lcm}(p-1,q-1)$ ；它仍足以完成上面的逐质数证明。统一指数与具体规范的关系放在第17章。标准依据见RFC 8017第3.2节。

第 7 章：RSA的指数选择与解密正确性 ​

7.1 公钥、私钥和模数各自做什么 ​

7.2 这些指数为什么一定可以选出来 ​

7.3 不互质的消息为什么也能还原 ​

7.4 这与分解有什么关系 ​

第 7 章：RSA的指数选择与解密正确性

7.1 公钥、私钥和模数各自做什么

7.2 这些指数为什么一定可以选出来

7.3 不互质的消息为什么也能还原

7.4 这与分解有什么关系