RSA算法 - 已知n如何获取p和q

Question

我有一个公钥 (e,n) 和一段加密数据，需要使用C语言通过RSA算法获取明文！

首先，我想知道如何确定我的p和q是什么？我知道它们必须是质数且p ≠ q！

- Last Unicorn

---

据信从n中获得p和q很困难，在一般情况下，没有公开已知的方法可以在可行的计算机时间内为大型n完成。RSA算法的安全性依赖于此。 - undefined

是的，Eric，我知道！但我的e是17，n是3233，所以不算太大！我需要计算私钥d。d = e^(-1) mod (p-1)(q-1) 你有什么办法可以得到d吗？请用C语言编写。 - undefined

Answer 1

首先，分解n。这很简单；因为sqrt(3233)是56.8...，所以你只需要测试小于这个数的质数。这将给出p和q。使用它们来计算(p-1)•(q-1)。

然后使用扩展欧几里得算法找到17模(p-1)•(q-1)的乘法逆元。你不需要C代码来实现；我手算了一下。（该算法会得到一个负数结果。你可以把(p-1)•(q-1)加上去，得到一个正值同样有效。）

- Eric Postpischil