使用欧几里得算法求解RSA解密密钥d的操作疏漏排查

先来看咱们要解决的问题：

已知RSA公钥相关参数：n=119，p=17，q=7，e=13，求解密密钥d并解密密文c=8。已知φ(n)=(p-1)(q-1)=16×6=96，求解d的核心方程为：ed ≡ 1 mod φ(n)

咱们先看尝试的推导过程，正向欧几里得算法的前两步是对的：

• 96 = 7 × 13 + 5
• 13 = 2 × 5 + 3

但第三步明显出问题了！正确的第三步应该是 5 = 1 × 3 + 2，而不是你写的5 = 2 × 2 + 1——这里把上一步得到的余数3给漏掉了，直接用2来计算，这是关键疏漏，导致后续反向推导全错了。

咱们重新走一遍正确的正向欧几里得步骤：

1. 96 = 7 × 13 + 5
2. 13 = 2 × 5 + 3
3. 5 = 1 × 3 + 2
4. 3 = 1 × 2 + 1
5. 2 = 2 × 1 + 0 （到余数为0时停止，最后一个非零余数是1，说明13和96互质，存在有效解密密钥d）

接下来做反向推导，把1用前面的式子逐步回代：

• 1 = 3 - 1 × 2
• 把2替换成5 - 1 × 3，代入得：1 = 3 - 1 × (5 - 1 × 3) = 2 × 3 - 1 × 5
• 再把3替换成13 - 2 × 5，代入得：1 = 2 × (13 - 2 × 5) - 1 × 5 = 2 × 13 - 5 × 5
• 最后把5替换成96 - 7 × 13，代入得：1 = 2 × 13 - 5 × (96 - 7 × 13) = 37 × 13 - 5 × 96

现在看这个式子，37 × 13 ≡ 1 mod 96，所以d=37就是咱们要找的解密密钥。

最后解密密文c=8，计算m = c^d mod n，也就是8^37 mod 119，咱们可以用快速幂简化计算：

• 先算8^2=64 mod 119
• 8^4=(64)^2=4096 mod 119：119×34=4046，4096-4046=50，所以8^4=50
• 8^8=(50)^2=2500 mod 119：119×21=2499，2500-2499=1，所以8^8=1
• 37=32+4+1=2^5 + 2^2 + 2^0，所以8^37=8^32 ×8^4 ×8^1
• 8^32=(8^8)^4=1^4=1，所以8^37=1×50×8=400 mod 119：119×3=357，400-357=43，最终明文m=43。

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