Как найти простые множители числа с помощью python
Я пишу программу, которая будет вычислять закрытый ключ для слабого открытого ключа 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, помощь будет оценена по достоинству.
Большое спасибо, Легорой.
Я знаю. Я вообще не понимаю Java, я надеялся, что SO сможет помочь с тем, как получить p и q из n с помощью python.
Вы понимаете, как это сделать вручную? Если нет, то у вас действительно вопрос по математике, а не по программированию (и уж тем более не по Python). Если вы это сделаете, начните с этого и задайте более конкретный вопрос, если вы не можете заставить реализацию работать.
Я не думаю, что вы понимаете сложность факторизации больших целых чисел, которые являются произведениями двух приблизительно равных простых чисел, то есть модулей RSA. Без большого количества оборудования и/или времени вы не сможете это сделать.
К счастью, у меня есть оба. @KarlKnechtel, я понимаю, как это сделать вручную, и нашел способ реализовать это - пока только в виде псевдокода. Если это сработает, я отвечу на свой вопрос. Если нет, я задам новый вопрос о том, почему внедрение не работает.
Ответы 2
Обязательное предупреждение: если вам нужна производительность, вам нужно будет самостоятельно изучить детали алгоритмов. Даже «слабые» открытые ключи будут взламываться вечно с помощью упрощенного алгоритма (например, решета Эратостена).
При этом sympy.ntheory.factorint() может быть тем, что вам нужно:
from sympy.ntheory import factorint
print(factorint(54)) # {2: 1, 3: 3} i.e. 54 == 2**1 * 3**3
Спасибо за этот ответ, но smpy.ntheory.factorint() занимает слишком много времени с этим тестовым числом: 9236378997685682877721661094972497924039685752827371833327322710323377895840902638303442492100881746878186386244383135186587004052271180780932725919664899
math.log(your number, 2) возвращает ~ 512. Опять же, даже «слабый» открытый ключ будет взломан целую вечность. Страница Википедии en.wikipedia.org/wiki/… заставляет меня думать, что RSA-512 по-прежнему является крепким орешком для одного случайного парня, использующего Python, даже если его использование небезопасно (потому что злоумышленники — теоретики чисел с доступом к приличному оборудованию).
Также возникает вопрос о том, для чего вы используете свою программу, так как я уверен, что есть некоторые компании, которые все еще используют RSA-512...
Я собираюсь использовать свою программу для атаки на рецепт шифра, который я придумал - тот, который не отличается от pgp.
После долгих поисков в Google и чтения PDF-файлов я нашел алгоритм, который работает. Вот реализация на питоне:
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)
SO не является бесплатной службой преобразования кода. Сделайте преобразование в Python, затем опубликуйте свой код с вопросами.