给定公共和私有指数，如何分解 RSA 模数？

Question

我有一个带有模数 m、公共指数 e 和私有指数 d 的 RSA 私钥，但我正在使用的程序需要模数的质因数p 和 q。

是否可以使用e和d来获取p和q？

Answer 1

是的——一旦您知道模数 N 以及公共/私有指数 d 和 e，获得 p 和 q 使得 N=pq 并不太困难。

Dan Boneh 的这篇论文描述了一种这样做的算法。它依靠的是
事实上，根据定义，

de = 1 mod phi(N)。

对于任何随机选择的“证人”
在 (2,N) 中，大约有 50% 的机会能够使用它来找到一个非平凡的
1 mod N 的平方根（称为 x）。然后 gcd(x-1,N) 给出因子之一。

Answer 2

您可以使用我在 2009 年开发的开源工具，该工具可以在 SFM 格式 (n,e,d) 和 CRT 格式 (p,q,dp,dq,u) 之间转换 RSA 密钥，反之亦然。它位于 SourceForge 上： http://rsaconverter.sourceforge.net/

我实现的算法基于提出的想法作者：Dan Boneh，如之前的答案所述。

我希望这会有用。

穆尼尔·伊德拉西 - IDRIX

Answer 3

我在加密堆栈交换上发布了一个回复，回答了同样的问题 这里。它使用与 Boneh 论文中概述的相同方法，但对其实际工作原理做了更多解释。我还尝试假设最少的先验知识。

希望这有帮助！

Answer 4

我努力深入研究 Boneh 的论文。从 (n, d) 导出 (p, q) 的“算法”隐藏在第 1.1 节的末尾，用数学术语进行编码，并作为练习留下让读者从他的（相当简洁的）证据中得出这样做是有效的。

令 <N, e> 为 RSA 公钥。给定私钥d，我们可以有效地分解模数N = pq。

证明。 计算 k = de − 1. 根据 d 和 e< 的定义/i> 我们知道k是φ(N)的倍数。由于 φ(N) 是偶数，因此 k = 2^t r 且 r 为奇数且 t ≥ 1。我们有 g^kg ε，sup> = 1 ℤ_N^×，因此 g^{k/2 是单位模 N 的平方根。根据中国余数定理，1 有四个模 N = pq 的平方根。其中两个平方根是±1。另外两个是 ±x，其中 x 满足 x = 1 mod p 和 x > = −1 mod q。使用最后两个平方根之一，通过计算 gcd(x − 1, N) 来揭示 N 的因式分解。一个简单的论证表明，如果从 ℤ_N× 中随机选择 g ，那么概率至少为 1/ 2（通过选择g）序列gk/2中的元素之一， gk/4，…，gk/2< support>t} mod N 是单位平方根，它揭示了 N 的因式分解。序列中的所有元素都可以在 O(n³) 时间内高效计算，其中 n = log₂(N)。

显然，对于不知道什么的人来说，这几乎毫无意义 $Z_N^\ast $ 是，并且具有相当非线性的结构，需要大量时间才能转变为线性算法。

所以这是有效的解决方案：

from random import randrange
from math import gcd


def ned_to_pqe(secret_key):
    """
    https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf#:~:text=Given%20d%2C,reveals%20the%20factorization%20of%20N%2E
    """
    n, e, d = secret_key
    k = d * e - 1
    t = bit_scan1(k)
    trivial_sqrt1 = {1, n - 1}
    while True:
        g = randrange(2, n - 1)
        for j in range(1, t + 1):
            x = pow(g, k >> j, n)
            if pow(x, 2, n) == 1:
                if x in trivial_sqrt1: continue
                p = gcd(x - 1, n)
                q = n // p
                if q > p: p, q = q, p
                return p, q, e


def pqe_to_ned(secret_key):
    p, q, e = secret_key
    n = p * q
    l = (p - 1) * (q - 1)
    d = pow(e, -1, l)
    return n, e, d


def bit_scan1(i):
    """
    https://gmpy2.readthedocs.io/en/latest/mpz.html#mpz.bit_scan1
    """
    # https://stackoverflow.com/a/63552117/1874170
    return (i & -i).bit_length() - 1


def test():
    secret_key = (
        # https://en.wikipedia.org/wiki/RSA_numbers#RSA-100
        # Should take upwards of an hour to factor on a consumer desktop ca. 2022
        1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139,
        65537,
        1435319569480661473883310243084583371347212233430112391255270984679722445287591616684593449660400673
    )
    if secret_key != pqe_to_ned(ned_to_pqe(secret_key)):
        raise ValueError


if __name__ == '__main__':
    test()
    print("Self-test OK")

现场演示（JS）：

function ned_to_pqe({n, e, d}) {
  // https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf#:~:text=Given%20d%2C,reveals%20the%20factorization%20of%20N%2E
  let k = d * e - 1n;
  let t = scan1(k);
  let trivial_sqrt1 = new Set([1n, n - 1n]);
  while (true) {
    let g = insecure_randrange(2n, n - 1n);
    for ( let j = t ; j > 0 ; --j ) {
      let x = bn_powMod(g, k >> j, n);
      if (bn_powMod(x, 2n, n) === 1n) {
        if (trivial_sqrt1.has(x)) continue;
        let p = gcd(x - 1n, n), q = n/p;
        if (q > p) [p, q] = [q, p];
        return {p, q, e};
      }
    }
  }
}


function pqe_to_ned({p, q, e}) {
  let n = p * q;
  let l = (p - 1n) * (q - 1n);
  let d = bn_modInv(e, l);
  return {n, e, d};
}


function bn_powMod(x, e, m) {
  // h/t https://umaranis.com/2018/07/12/calculate-modular-exponentiation-powermod-in-javascript-ap-n/
  if (m === 1n) return 0n;
  let y = 1n;
  x = x % m;
  while (e > 0n) {
    if (e % 2n === 1n)  //odd number
      y = (y * x) % m;
    e = e >> 1n;  //divide by 2
    x = (x * x) % m;
  }
  return y;
}


function bn_modInv(x, m) {
  // TOY IMPLEMENTATION
  // DO NOT USE IN GENERAL-PURPOSE CODE
  // h/t https://rosettacode.org/wiki/Modular_inverse#C
  let m0 = m, t, q;
  let x0 = 0n, y = 1n;
  if (m === 1n) return 1n;
  while (x > 1n) {
    q = x / m;
    t = m;
    m = x % m;
    x = t;
    t = x0;
    x0 = y - q * x0;
    y = t;
  }
  if (y < 0n) y += m0;
  return y;
}


function gcd(a, b) {
  // h/t https://stackoverflow.com/a/17445304/1874170
  while (b) {
    [a, b] = [b, a % b];
  }
  return a;
}


function scan1(i) {
  // https://gmplib.org/manual/Integer-Logic-and-Bit-Fiddling#mpz_scan1
  let k = 0n;
  if ( i !== 0n ) {
    while( (i & 1n) === 0n ) {
      i >>= 1n;
      k += 1n;
    }
  }
  return k;
}


function insecure_randrange(a, b) {
  // h/t https://arxiv.org/abs/1304.1916
  let numerator = 0n;
  let denominator = 1n;
  let n = (b - a);
  while (true) {
    numerator <<= 1n;
    denominator <<= 1n;
    numerator |= BigInt(Math.random()>1/2);
    if (denominator >= n) {
      if (numerator < n)
        return a + numerator;
      numerator -= n;
      denominator -= n;
    }
  }
}

<form action="javascript:" onsubmit="(({target:form,submitter:{value:action}})=>{eval(action)(form)})(event)">
<p>
<label for="p">p=</label><input name="p" value="37975227936943673922808872755445627854565536638199" /><br />
<label for="q">q=</label><input name="q" value="40094690950920881030683735292761468389214899724061" /><br />
<label for="n">n=</label><input name="n" /><br />
<label for="e">e=</label><input name="e" placeholder="65537" /><br />
<label for="d">d=</label><input name="d" /><br />
</p>
<p>
<button type="submit" value="pqe2nd">Get (n,d) from (p,q,e)</button><br />
<button type="submit" value="delpq">Forget (p,q)</button><br />
<button type="submit" value="ned2pq">Get (p,q) from (n,e,d)</button>
</form>

<script>
function pqe2nd({elements}) {
  if (!elements['e'].value) elements['e'].value = elements['e'].placeholder;
  let p = BigInt(elements['p'].value||undefined);
  let q = BigInt(elements['q'].value||undefined);
  let e = BigInt(elements['e'].value||undefined);
  let {n, d} = pqe_to_ned({p,q,e});
  elements['n'].value = n.toString();
  elements['d'].value = d.toString();
}
function ned2pq({elements}) {
  if (!elements['e'].value) elements['e'].value = elements['e'].placeholder;
  let n = BigInt(elements['n'].value||undefined);
  let e = BigInt(elements['e'].value||undefined);
  let d = BigInt(elements['d'].value||undefined);
  let {p, q} = ned_to_pqe({n,e,d});
  elements['p'].value = p.toString();
  elements['q'].value = q.toString();
}
function delpq({elements}) {
  elements['p'].value = null;
  elements['q'].value = null;
}
</script>

---

要回答标题中所述的问题：因式分解 N 需要求 N。但是在一般情况下，你不能从(e, d)<导出N /代码>。因此，在一般情况下，您无法从 (e, d) 导出 N 的因子；量子电子器件。

对于小<，从（e，d）中找到n在计算上是可行的，具有相当的概率，甚至是确定性/strong> 但可观察到的 RSA 密钥中具有实际意义的部分

如果您想尝试这样做，您将需要能够分解 e * d - 1 （如果我正确理解上面链接的答案）：

from itertools import permutations


def ed_to_pq(e, d):
    # NOT ALWAYS POSSIBLE -- the number e*d-1 must be small enough to factorize
    # h/t https://crypto.stackexchange.com/a/81620/8287
    factors = factorize(e * d - 1)
    factors.sort()
    # Unimplemented optimization:
    #   if two factors are larger than (p * q).bit_length()//4
    #   and the greater of (p, q) is not many times bigger than the lesser,
    #   then you can safely assume that the large factors belong to (p-1) and (q-1)
    #   and thereby reduce the number of iterations in the following loops
    # Unimplemented optimization:
    #   permutations are overkill for this partitioning scheme;
    #   a clever mathematician could come up with something more efficient
    # Unimplemented optimization:
    #   prune permutations based on "sanity" factor of logarithm knapsacking
    l = len(factors)
    for arrangement in permutations(factors):
        for l_pm1 in range(1, l - 1):
            for l_qm1 in range(1, l_pm1):
                pm1 = prod(arrangement[:l_pm1])
                qm1 = prod(arrangement[l_pm1:l_pm1+l_qm1])
                try:
                    if pow(e, -1, pm1 * qm1) == d:
                        return (pm1 + 1, qm1 + 1)
                except Exception:
                    pass


from functools import reduce
from operator import mul


def prod(l):
    return reduce(mul, l)