Взламывание длинных ключей RSA только от ключа publi c - PullRequest
Новая
       50

Взламывание длинных ключей RSA только от ключа publi c

2 голосов
/ 27 апреля 2020

Для конкурса я пытаюсь научиться ломать ключ RSA, используя только ключ c:

  • e = 65537
  • n = 632459103267572196107100983820469021721602147490918660274601

Итак, я следил за этой веб-страницей и за этим ответом . И попробовал: 

    >>> n = 632459103267572196107100983820469021721602147490918660274601
    >>> import math
    >>> math.floor(math.sqrt(n))
    795272974058324394239265341440
    >>> c = math.floor(math.sqrt(n))
    >>> for i in range(c-1,c-41,-2):
    ...     if c%i ==0:
    ...         print(i, c%i)
    ...

Но это мне ничего не дает. Я начал использовать метод грубой силы: 

>>> print(repr(math.sqrt(n)))
7.952729740583244e+29
>>> c = math.sqrt(n)
>>> int(c)
795272974058324394239265341440
>>> for i in range(c-1, 2, -2):
...     if n%i == 0:
...         print(i, n%i)
...

Но он длился полдня. Я знаю, что это глупо, потому что я проверяю даже не простые числа. Есть ли более мудрый путь?

В самом начале я начал с c, который является четным числом. Я думаю, что глупо уменьшать с шагом 2 от четного числа, так как это только приводит меня к тестированию без факторизации?

Обновление

После прочтения комментария Дэна я сейчас пытаюсь искать маленький фактор, а не начинать с большого. 

>>> for i in range(1,c-1,2):
...     if c%i ==0 and i%2 != 0 and i%5 !=0:
...         print(i, c%i)
...
1 0

1 Ответ

1 голос
/ 28 апреля 2020

TL; DR: взлом длинных ключей RSA сложен в вычислительном отношении (т. Е. Нет известного решения, работающего за полиномиальное время), и хотя ваш алгоритм может быть не самым эффективным, никто не нашел такого, который может взломать длинные ключи RSA ( с классическим компьютером - алгоритм Шора для квантового компьютера может взломать длинные ключи RSA за полиномиальное время).

Более длинный ответ:

Чтобы оценить, как долго ваш Чтобы выполнить программу, я написал следующее python: 

import time

n = 632459103267572196107100983820469021721602147490918660274601
c = 795272974058324394239265341440

test_size = 100000

start_time = time.time()

for i in range(c-1, c-test_size, -2):
    if n%i == 0:
        print(i, n%i)

time_elapsed = (time.time() - start_time)

print("Elapsed Time for %i iterations: %f seconds" % (test_size, time_elapsed))
seconds_in_a_year = 31557600
projected_time = time_elapsed * (c / 2 / test_size) / seconds_in_a_year
print("Projected Time for %i iterations: %i years" % (c, projected_time))

Когда я запустил это на моем компьютере, результат был: 

Elapsed Time for 100000 iterations: 0.024008 seconds
Projected Time for 795272974058324394239265341440 iterations: 3025094101018381 years

Это слишком много лет!

Одна вещь, на которую следует обратить внимание в связи со статьей и ответом, на который вы ссылаетесь, - это примеры с короткими клавишами. Причина, по которой криптосистема RSA используется и работает, заключается в том, что когда генерируются достаточно большие ключи, вычислительно трудно (то есть потребуется много жизней, даже если все вычислительные ресурсы на земле работают вместе), чтобы использовать любую известную процедуру для определения закрытого ключа учитывая ключ publi c. Поскольку компьютеры работают быстрее, то, что считается достаточно большим ключом, может немного измениться, и другие криптосистемы с открытым ключом c, которые еще сложнее взломать, также могут быть использованы для большей безопасности, но в настоящий момент от 1024 до 4096 битных RSA широко используется в производственных условиях. n, который вы указали, составляет 199 бит (math.log(n,2)), поэтому я полагаю, что он может быть подвергнут грубому принуждению за разумное время ... просто не используя ноутбук и не используя python (если вы попробуете тот же самый грубый метод) При наступлении силы в C он все равно не будет запущен в разумные сроки, но будет быстрее, чем python). Если вам интересны другие алгоритмы для решения задачи дискретного логарифмирования или целочисленной факторизации, я не знаю много об этом, но могу вам сказать, что не существует известных эффективных алгоритмов для неквантовых компьютеров .

Если у меня будет время, я вернусь и дополню этот ответ кодом C для сравнения. Я просто хотел отметить, что вы не делаете ничего плохого, вы пытаетесь решить неразрешимая проблема.

...