Как найти главные факторы числа с питоном - PullRequest
Новая
       57

Как найти главные факторы числа с питоном

0 голосов
/ 06 июня 2019

Я пишу программу, которая будет вычислять закрытый ключ для слабого открытого ключа RSA.Мне интересно, как бы я мог определить значения для p и q из значения 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.

Если кто-нибудь знает, как получить p и q из n с помощью python, мы будем благодарны за помощь.

Большое спасибо, Легорой.

Ответы [ 2 ]

2 голосов
/ 06 июня 2019

Обязательное предупреждение: если вы после исполнения, вам нужно будет изучить детали алгоритмов самостоятельно.Даже «слабые» открытые ключи будут взламываться с помощью упрощенного алгоритма (например, сито Эратостена).

При этом sympy.ntheory.factorint() может быть тем, что вам нужно: 

from sympy.ntheory import factorint

print(factorint(54))  # {2: 1, 3: 3} i.e. 54 == 2**1 * 3**3
0 голосов
/ 09 июня 2019

После большого количества поисков в Google и чтения 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

Этот алгоритм эффективно находит P / Q-факторы небольшого ключа RSA.(Я проверил это с 64-битным открытым ключом PEM)

...