已知RSA正确密文c与错误密文c'，如何分解模数n=55？

嘿，这个问题其实可以通过**最大公约数（gcd）**来轻松解决，咱们一步步拆解来看：

已知条件回顾 #

• 正确密文：$c \equiv 4 \mod 55$
• 错误密文：$c' \equiv 37 \mod 55$
• 待分解的模数：$n = 55 = pq$（p、q为未知素因子）

核心步骤：计算差值的最大公约数 #

第一步：计算正确与错误密文的差值 #

先算出两者的绝对差值：

|c - c'| = |4 - 37| = 33

第二步：计算差值与n的最大公约数 #

直接用辗转相除法计算gcd(33, 55)：

1. $55 = 33 \times 1 + 22$
2. $33 = 22 \times 1 + 11$
3. $22 = 11 \times 2 + 0$
   当余数为0时，最后一个非零余数就是gcd，也就是11。

第三步：获取另一个素因子 #

用n除以得到的素因子，就能得到另一个因子：

55 ÷ 11 = 5

所以n的分解结果是 $5 \times 11$。

为什么这个方法有效？ #

咱们从你已有的中国剩余定理推导继续延伸：
你已经得到了 $b \cdot q \cdot (c_1' - c_1) \equiv 33 \mod 55$，本质上：

正确密文c满足：$c \equiv 4 \mod 5$ 且 $c \equiv 4 \mod 11$
错误密文c'满足：$c' \equiv 2 \mod 5$ 且 $c' \equiv 4 \mod 11$

可以看出：

• 密文错误只出现在模5的计算中，因此c和c'在模11下是相等的，差值必然是11的倍数
• 但在模5下两者不相等，所以差值不是5的倍数

因此，差值33是11的倍数但不是5的倍数，它和n=55的最大公约数就是其中一个素因子11，剩下的因子自然就是5了。

内容的提问来源于stack exchange，提问作者L.Z.