从私有指数(d),公共指数(e)和模数(n)计算素数p和q

Question

如何从e(publickey),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很小(这是常见的情况;传统的公共指数是65537).让我们假设ed = 1 mod phi(n),其中phi(n)=(p-1)(q-1)(不一定是这种情况; RSA要求是ed = 1 mod lcm(p- 1,q-1)和phi(n)仅是1cm(p-1,q-1)的倍数.

现在你有一些整数k的ed = k*phi(n)+1.由于d小于phi(n),你知道k <e.所以你只需要少量的k来试试.实际上,披(n)的靠近Ñ(不同之处的数量级上的sqrt(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素性测试.它在" 应用密码学手册"(第8章,第8.2.2节,第287页)中有所描述.该方法在概念上有点复杂(它涉及模幂运算)但可能更容易实现(因为没有平方根).

Answer 2

在NIST特别出版物800-56B R1 建议书中使用整数因子分解密码对配对密钥建立方案中介绍了一种从n，e和d中恢复p和q的过程，该过程在附录C中提供。

涉及的步骤是：

1. 令k = de – 1。如果k为奇数，请转到步骤4。
2. 将k写为k = 2 ^t r，其中r是除以k的最大奇数整数，而t是？1。或更简单地说，将k重复除以2，直到达到奇数为止。
3. 对于i = 1至100，请执行以下操作：
   1. 生成范围为[0，n？1] 的随机整数g。
   2. 令y = g ^r mod n
   3. 如果y = 1或y = n – 1，则转到步骤3.1（即重复此循环）。
   4. 对于j = 1到t – 1，做：
      1. 令x = y ² mod n
      2. 如果x = 1，请转到（外部）步骤5。
      3. 如果x = n – 1，请转到步骤3.1。
      4. 令y = x。
   5. 令x = y ² mod n
   6. 如果x = 1，请转到（外部）步骤5。
   7. 继续
4. 输出“找不到主要因素”并停止。
5. 令p = GCD（y – 1，n），令q = n / p
6. 输出（p，q）作为主要因子。

我最近用Java编写了一个实现。我意识到对于C＃而言，它并不是直接有用的，但也许可以轻松移植：

// Step 1: Let k = de – 1. If k is odd, then go to Step 4
BigInteger k = d.multiply(e).subtract(ONE);
if (isEven(k)) {

    // Step 2 (express k as (2^t)r, where r is the largest odd integer
    // dividing k and t >= 1)
    BigInteger r = k;
    BigInteger t = ZERO;

    do {
        r = r.divide(TWO);
        t = t.add(ONE);
    } while (isEven(r));

    // Step 3
    Random random = new Random();
    boolean success = false;
    BigInteger y = null;

    step3loop: for (int i = 1; i <= 100; i++) {

        // 3a
        BigInteger g = getRandomBi(n, random);

        // 3b
        y = g.modPow(r, n);

        // 3c
        if (y.equals(ONE) || y.equals(n.subtract(ONE))) {
            // 3g
            continue step3loop;
        }

        // 3d
        for (BigInteger j = ONE; j.compareTo(t) <= 0; j = j.add(ONE)) {
            // 3d1
            BigInteger x = y.modPow(TWO, n);

            // 3d2
            if (x.equals(ONE)) {
                success = true;
                break step3loop;
            }

            // 3d3
            if (x.equals(n.subtract(ONE))) {
                // 3g
                continue step3loop;
            }

            // 3d4
            y = x;
        }

        // 3e
        BigInteger x = y.modPow(TWO, n);
        if (x.equals(ONE)) {

            success = true;
            break step3loop;

        }

        // 3g
        // (loop again)
    }

    if (success) {
        // Step 5
        p = y.subtract(ONE).gcd(n);
        q = n.divide(p);
        return;
    }
}

// Step 4
throw new RuntimeException("Prime factors not found");

这段代码使用了一些帮助程序定义/方法：

private static final BigInteger ONE = BigInteger.ONE;
private static final BigInteger TWO = BigInteger.valueOf(2);
private static final BigInteger ZERO = BigInteger.ZERO;

private static boolean isEven(BigInteger bi) {
    return bi.mod(TWO).equals(ZERO);
}

private static BigInteger getRandomBi(BigInteger n, Random rnd) {
    // From http://stackoverflow.com/a/2290089
    BigInteger r;
    do {
        r = new BigInteger(n.bitLength(), rnd);
    } while (r.compareTo(n) >= 0);
    return r;
}