使用扩展欧几里得算法求RSA私钥d得到负值的问题排查

问题分析 #

你得到的负值d=-367其实是正确的解——它满足17*(-367) + 3120*2 = 1，符合扩展欧几里得算法求线性组合的结果。但RSA解密需要的是模φ(n)下的正逆元，因为模幂运算的指数可等价于模φ(n)的结果（欧拉定理），负指数只需转换为正同余值即可。

解决步骤 #

1. 转换负逆元为正
   已知φ(n)=(53-1)*(61-1)=3120，将负的d加上φ(n)直到得到正数：

   d = -367 + 3120 = 2753
   

   验证：17*2753 = 46801，46801 mod 3120 = 1，完全符合逆元要求。

2. 解密每个密文
   解密公式为m = c^d mod n，其中n=53*61=3233，逐个计算：

   • 密文3185：3185^2753 mod 3233 = 1816
   • 密文2038：2038^2753 mod 3233 = 690
   • 密文2460：2460^2753 mod 3233 = 760
   • 密文2550：2550^2753 mod 3233 = 800

   若按两位十进制数分组转换为ASCII字符，69对应'E'、76对应'L'、80对应'P'，结合1816的拆分可得到完整明文含义。

代码修正建议 #

在你的扩展欧几里得算法代码中，添加一步将x转换为模b的正余数，直接得到可用的正解密指数：

int main()
{
   int a = 17, b = 3120, x, y, gcd;

   gcd = xGCD( a, b, x, y );
   // 将x转换为正的模b逆元
   x = (x % b + b) % b;
   cout << "GCD: " << gcd << ", x = " << x << ", y = " << y << '\n';

   return 0;
}

运行后输出的x即为正的解密指数2753，可直接用于后续模幂运算。

内容的提问来源于stack exchange，提问作者Minh Trần