Взламывание коротких ключей RSA

Question

Учитывая следующие ключи RSA, как можно определить, какие значения p и q ?

Public Key: (10142789312725007, 5)
Private Key: (10142789312725007, 8114231289041741)

Answer 1

Существует много плохих предположений о факторизации больших полупростых чисел, которые переходят в грубую силу или просеивание, ни одно из которых не требуется для факторизации полупростого числа.На моем компьютере 64 бит занимает 1 - 2 секунды, а 256 бит обычно менее 2 дней

Answer 2

Вам нужно факторизовать модуль, это первый параметр открытого ключа, 10142789312725007. Подойдет грубая сила (проверяет каждое нечетное число от 3 до sqrt (n), если это фактор), хотя существуют более сложные / быстрые алгоритмы .

Поскольку число слишком велико, чтобы вписаться в обычное целое число (даже 64-разрядное), вам может потребоваться числовая библиотека, которая поддерживает произвольные целые числа. Для C есть GMP и MPIR (более дружественный к Windows). Для PHP есть Bignum. Python поставляется со встроенным - встроенный целочисленный тип данных уже произвольной длины.