c# - 从私有(private)指数 (d)、公共(public)指数 (e) 和模数 (n) 计算素数 p 和 q

Question

如何根据 e(公钥)、d(私钥)和模数计算 p 和 q 参数？

我手边有 BigInteger 键，我可以将粘贴复制到代码中。一个公钥、一个私钥和一个模数。

我需要据此计算 RSA 参数 p 和 q。但我怀疑有一个我无法用谷歌找到的图书馆。有任何想法吗？谢谢。

这不一定是蛮力，因为我不是在寻找私钥。我只有一个遗留系统，它存储一个公钥、私钥对和一个模数，我需要将它们放入 c# 中以与 RSACryptoServiceProvider 一起使用。

---

所以归结为计算 (p+q)

public BigInteger _pPlusq()
    {
        int k = (this.getExponent() * this.getD() / this.getModulus()).IntValue();

        BigInteger phiN = (this.getExponent() * this.getD() - 1) / k;

        return phiN - this.getModulus() - 1;

    }

但这似乎行不通。你能发现问题吗？

---

5 小时后...:)

好的。如何在 C# 中从 Zn* ( http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n) 中选择一个随机数？

Answer 1

让我们假设 e 很小(这是常见情况；传统公共(public)指数是 65537)。我们还假设 ed = 1 mod phi(n)，其中 phi(n) = (p-1)(q-1) (情况不一定如此；RSA 要求是 ed = 1 mod lcm(p-1,q-1) 和 phi(n) 只是 lcm(p-1,q-1) 的倍数。

现在您有 ed = k*phi(n)+1 一些整数 k。由于 d 小于 phi(n)，您知道 k < e。所以您只有少量的 k 可以尝试。实际上，phi(n) 接近于 n(区别在 sqrt(n) 的数量级上；换句话说，当写成以位为单位，phi(n) 的上半部分与 n 的上半部分相同)，因此您可以使用以下方法计算 k': >k'=round(ed/n)。 k' 非常接近 k(即 |k'-k| <= 1)，只要 e 的大小 不超过 n 大小的一半。

给定 k，您很容易得到 phi(n) = (ed-1)/k。碰巧的是:

phi(n) = (p-1)(q-1) = pq - (p+q) + 1 = n + 1 - (p+q)

因此，您得到 p+q = n + 1 - phi(n)。你也有 pq。是时候记住对于所有实数 a 和 b，a 和 b 是二次方程X²-(a+b)X+ab。所以，给定p+q和pq，通过求解二次方程得到p和q:

p = ((p+q) + sqrt((p+q)² - 4*pq))/2

q = ((p+q) - sqrt((p+q)² - 4*pq))/2

在一般情况下，e 和 d 可能具有任意大小(可能大于 n)，因为 RSA 所需要的只是ed = 1 mod (p-1) 和 ed = 1 mod (q-1)。有一种通用(且快速)的方法看起来有点像 Miller-Rabin 素数测试。在 Handbook of Applied Cryptography 中进行了描述(第 8 章，第 8.2.2 节，第 287 页)。该方法在概念上有点复杂(它涉及模幂)但实现起来可能更简单(因为没有平方根)。