Можно ли перебрать 10 ^ 8 вариантов, чтобы определить правильный ответ?
У меня есть номер длиной 615 цифр. В нем есть 8 мест, где пропущены цифры. Я должен узнать, что это за цифры. Есть 10^8 возможностей.
Это для проблемы с RSA. Рассматриваемый номер является закрытым ключом, и я пытаюсь выяснить, что это такое. Чтобы помочь мне, у меня есть пара открытых ключей (n, e), оба из которых также имеют длину 615 цифр, а также открытый текст и соответствующий зашифрованный текст.
Таким образом, единственный способ вычислить d — это перебрать его. Я пытаюсь использовать gmpy2 в python, чтобы понять это. Мне пришлось пройти через множество обручей, чтобы заставить его работать. Я даже не знаю, правильно ли я это сделал. Мне пришлось загрузить Python2.7, чтобы я мог запустить программу установки gmpy2, чтобы не получить сообщение об ошибке. Но я думаю, что теперь это работает, так как я могу печатать
>>>import gmpy2
в терминале, и он не дает мне ошибку.
Прежде чем я попытаюсь перебрать 10 ^ 8 возможностей, я хочу знать, возможно ли это сделать за относительно короткий промежуток времени, учитывая мою ситуацию. Я не хочу поджарить свой компьютер или заморозить его, пытаясь вычислить это. Я также хочу знать, использую ли я для этого правильные инструменты, или gmpy2 не правильная версия, или Python 2.7 недостаточно хорош/быстр. Я запускаю gmpy2 на Python2.7 на ноутбуке.
В конце концов, я полагаю, я хочу взять все 10 ^ 8 ответов и поднять так, чтобы C ^ d = M mod n. Итак, это (уже) большое число в степени числа 615 цифр, 10 ^ 8 раз. Это возможно? Если это так, как я могу сделать это с помощью gmpy2? Есть ли более эффективный способ вычислить это?
Я искренне извиняюсь, если это не то место, где можно задать этот вопрос. Спасибо за любую помощь.
Такой длинный цикл никогда не бывает хорошей идеей, вы пробовали рекурсию?
Ответы 2
Вы не собираетесь жарить свой компьютер.
Это может занять много времени, но похоже, что это прямая задача O(n), поэтому она не разрастется до бесконечности. Пока проверка того, является ли один хэш действительным или нет, не занимает слишком много времени, это может занять даже меньше минуты. Современные машины измеряют тактовые циклы в ГГц. Это 10^9 циклов в секунду. И кроме того, поскольку вы говорите, что не можете сделать никаких выводов о правильном ответе из неверных предположений, грубая сила кажется единственным решением.
Я gmpy2 сопровождающий.
Чтобы вычислить C**d mod n, вы должны использовать встроенный pow() и указать все три значения. pow(C,d,n) будет намного быстрее, чем C**d % n.
Использование gmpy2 должно быть легким для этого. Вместо того, чтобы использовать int() для преобразования строки в целое число Python, вам просто нужно использовать gmpy2.mpz(). Вы можете использовать pow() с экземплярами mpz. (И если хотя бы одно из трех значений pow() является mpz, gmpy2 будет использоваться для расчета.)
Я оцениваю время работы с gmpy2 в диапазоне от менее часа до нескольких часов. Собственные целые числа Python могут быть в 10 раз медленнее.
то, что вы сказали, звучит разумно, и это должно завершиться в разумные сроки. обратите внимание, что целые значения в python уже имеют «произвольную точность» (поэтому я могу сделать
10**615 % 7727) и получить правильный ответ. Я бы расширил ваш вопрос, включив в него некоторый код, реализующий ваш алгоритм, если вы хотите, чтобы люди здесь могли комментировать более полезно.