-1

我正在编写一个程序来计算弱 RSA 公钥的私钥。我想知道我将如何确定 value 的值p和q来自 value 的值n。到目前为止，这是 Python 代码：

from Crypto.PublicKey import RSA #PyCryptoDome
import .math as cm # My own module

with open(public_keyfile, 'rb') as key: # Public Keyfile Is in PEM format
    public_key = RSA.import_key(key)

n = public_key.n # N value of the public_key

e = public_key.e # E value of the public_key

p, q = get_factors_of(n) # This I don't know how to do, though there is a question that might help [see bottom]

t = cm.lcm(p-1, q-1) # Get the lowest common multiple of q and q

d = cm.mod_inverse(e, t) # Get d, the modular inverse of e % t

private_key = RSA.construct((n, e, d, p, q) # Construct the RSA private_key

上面引用的.math模块：

from math import gcd


def mod_inverse(a, b):
    a = a % b
    for x in range(1, b):
        if (a * x) % b == 1:
            return x
    return 1


def lcm(x, y):
    return x * y // gcd(x, y)

我需要做的似乎在 这里被引用，但这段代码是用 Java 编写的。

如果有人知道如何使用 python 获取p和q获取n，将不胜感激。

非常感谢，Legorooj。

4

2 回答 2

2

强制警告：如果你追求性能，你需要自己调查算法的细节。即使是“弱”的公钥也需要很长时间才能用简单的算法（例如 Erathostene 的筛子）破解。

话虽这么说，sympy.ntheory.factorint()可能是你需要的：

from sympy.ntheory import factorint

print(factorint(54))  # {2: 1, 3: 3} i.e. 54 == 2**1 * 3**3
于 2019-06-06T10:17:15.777 回答
1

经过大量的谷歌搜索和 pdf 阅读后，我找到了一个可行的算法。这是一个python实现：

import math
def get_factors_of(num):
    poss_p = math.floor(math.sqrt(num)) 

    if poss_p % 2 == 0: # Only checks odd numbers, it reduces time by orders of magnitude
        poss_p += 1
    while poss_p < num:
        if num % poss_p == 0:
            return poss_p
        poss_p += 2

该算法有效地找到了一个小的 RSA 密钥的 P/Q 因子。（我已经针对 64 位 PEM 公钥对其进行了测试）

于 2019-06-09T17:29:51.340 回答