RSA解密密钥d求解及密文c=5解密技术咨询

没问题，我来一步步帮你完成RSA解密密钥d的求解，以及密文c=5的解密过程：

已知信息 #

• n = 221，p = 17，q = 13，e = 11
• 欧拉函数 $\phi(n) = (p-1)(q-1) = 16 \times 12 = 192$

核心求解方程 #

要找到解密密钥d，需满足同余方程：

$ed \equiv 1 \mod \phi(n)$

代入已知值后，我们需要解的具体方程为：
$11d \equiv 1 \mod 192$

这里用扩展欧几里得算法来求解最直接，步骤如下：

第一步：辗转相除法求最大公约数

通过反复做除法取余数，直到余数为0，最后一个非零余数就是两数的最大公约数：

• $192 = 17 \times 11 + 5$
• $11 = 2 \times 5 + 1$
• $5 = 5 \times 1 + 0$

到这里余数为0，说明11和192互质，方程有解，上一步的余数1就是最大公约数。

第二步：反向推导还原1的表达式

从最后一个非零余数开始，把每一步的余数用被除数和除数表示，逐步回代：

• $1 = 11 - 2 \times 5$
• 把第一步得到的$5 = 192 - 17 \times 11$代入上式：
  $1 = 11 - 2 \times (192 - 17 \times 11)$
• 展开并整理同类项：
  $1 = 11 - 2 \times 192 + 34 \times 11$
  $1 = 35 \times 11 - 2 \times 192$

这个式子说明：$11 \times 35$除以192的余数是1，所以解密密钥d ≡ 35 \mod 192，也就是d=35。

密文c=5的解密 #

RSA的解密公式为：$m = c^d \mod n$

代入数值后，我们需要计算$5^{35} \mod 221$，用快速幂法简化计算：

• $5^2 = 25 \mod 221$
• $5^4 = (25)^2 = 625 \mod 221 = 625 - 2 \times 221 = 183$
• $5^8 = (183)^2 = 33489 \mod 221$，计算得$33489 - 151 \times 221 = 118$，即$5^8 ≡ 118$
• $5^{16} = (118)^2 = 13924 \mod 221$，计算得$13924 - 63 \times 221 = 1$，即$5^{16} ≡ 1$
• $5^{32} = (5^{16})2 ≡ 1^2 = 1 \mod 221$

把35拆分为32+2+1，组合计算：
$5^{35} = 5^{32} \times 5^2 \times 5^1 ≡ 1 \times 25 \times 5 = 125 \mod 221$

所以解密后的明文m=125。

备注：内容来源于stack exchange，提问作者Alix Blaine