| 7:04a |
Решил вынести на суд публики метод факторизации произведения двух чисел размером по 64 бита.
Пусть это будет p*q
Известно, что n^((p-1)*(q-1))%(p*q)=1
Можно легко заключить, что (p-1)*(q-1)+p+q=p*q+1
Можно легко заключить, что (p+q)^2>=p*q*4
Из этого вытекает, что перебор формулы n^i%(p*q) начиная с i=p*q-((p*q)^(1/2)*2) должен встретить результат 1.
Трудоемкость перебора не больше чем 2^64
Перебор может быть оптимизирован таблицами. примерно 32G памяти снижают трудоемкоть перебора в 2^30 раз.
Остается построение таблиц трудоемкостью 2^30 и сам перебор трудоемкостью 2^34.
В результате перебора будет найдено число p+q. Имея его и p*q нет проблем восстановить p и q раздельно.
Где я ошибся?
Получается, что RSA-128 ломается на домашнем компе за пару часов? |