Атака на RSA при малом размере открытого текста

CreatorCray
я с тобой, в обшем, согласен, что боятся волков - в лес не ходить) а пока активную защиту рса я встречал от самого рса - что ни говори, а задача реально интересная)) куда ни плюнь - везде возникает потребность в больших ресурсах.

 

А что все на парня то набросились ? - задача ведь совершенно нетиповая.
Если он знает 40 бит из 64 бит исходного сообщения, то полным перебором 2^24, зная (e,N), будет подбирать оставшиеся запросто.

Вот он и спрашивает дело - как узнать (e,N) - ведь в самом RSA нет никаких требований к их закрытости.

 

(e, N) - это открытый ключ. N - модуль, по которому вполняется приведение, e - публичная экспонента (с большой долей вероятности e = 3, 17 или 0x10001).

 

OLS
Дык в том то и дело, что если он пишет изначально что нет открытого ключа то все, приехали.

 

Тут для перебора нужно 2^24^(груперовка 2х из 190 000 000 простых чисел)^3 (я согласен с flankerx насчет e)

 

Какой ещё взлом RSA, речь совершенно о другом, о том что алгоритм используют глупым образом. Я не собираюсь задевать интересы мировых корпораций и сверх держав. И уж тем более разводить кучу глупого трепа.

SWR
Я тоже склонялся примерно к этому же варианту, надо только ускорить перебор. Имея большое кол-во зашифрованных сообщений, за меньшее кол-во операций оценить, что (N,e) нам не подходят. Но сейчас упираюсь в недостаточные знания математики, поэтому решили отложить задачу, возможно вернусь к ней через пол года, когда восполню пробелы в знаниях.
Спасибо всем кто ответил по делу

 

bsnake
ради чистого любопытства: зачем пытаться выщимить открытый ключ - смысл?

 

bsnake

Для восполнения пробелов в знаниях проштудируй книжечку.

 

из тай формы что привел выше надо выкинуть 2^24^
Так как достаточно полностью расшифровать сообжения (перебор недостающей части ненужен)

Можно тупо снгенерить все простый числа до 32 и загнать через CUDA в GPU для перебора
За пол дня должно управиться (или раньше)

 

Известный специалист по IT-безопасности и выдающийся криптолог Брюс Шнайер высказался по поводу недавней инициативы лаборатории Касперского по взлому 1024 бит ключа, который используется во вредоносной программе Virus.Win32.Gpcode.ak - последней версии опасного вируса-шантажиста Gpcode. Для факторизации ключа, по мнению специалистов Лаборатории Касперского, потребуется совместная работа 15 миллионов современных компьютеров в течение года.

В настоящее время еще никто не смог факторизовать 1024-бит ключ, кроме разве что секретных государственных служб, а инициатива Лаборатории Касперского является не более чем саморекламой. В настоящее время рекордом по факторизации является 1023 битный ключ определенного вида 2^1039 – 1, на взлом которого потребовалось около 11 месяцев. Взлом Gpcode, по мнению Шнайера, потребует гораздо больше вычислительных ресурсов, чем можно привлечь призывом на интернет-форуме.

По мнению Лаборатории Касперского, компания лишь пытается обнаружить недостаток в текущем криптографическом алгоритме GPCode, что позволяло восстановить закрытый ключ в более ранних версиях вируса. Если такой недостаток не будет обнаружен то, по мнению Роэля Шовенберга, главного инженера лаборатории Касперского, декодировать ключ простым перебором будет невозможно.

4 июня 2008 года специалистами ЛК был обнаружен новый вариант опасной вредоносной программы — шифровальщика «Gpcode».

Для шифрования файлов новый вариант Gpcode использует встроенные в операционную систему Windows криптоалгоритмы (Microsoft Enhanced Cryptographic Provider v1.0). Файлы шифруются при помощи алгоритма RC4. Ключ шифрования затем шифруется открытым ключом RSA длиной 1024 бит, содержащимся в теле вируса.

До сих пор все попытки факторизации ключей RSA останавливались на отметке 663 бит, решение этой задачи потребовало трехмесячной работы кластера из 80-ти компьютеров.

Задача «взлома» ключа RSA-1024, стоящая сейчас перед всеми антивирусными компаниями мира, является сложнейшей и фундаментальной криптографической проблемой.

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

Мы не обладаем подобными вычислительными мощностями.

«Лаборатория Касперского» приглашает всех специалистов в области криптографии, правительственные и научные институты, другие антивирусные компании и независимых исследователей присоединиться к решению проблемы.

Мы считаем задачу «взлома» ключа RSA-1024, который использовал злоумышленник, первым в истории случаем, который требует объединения накопленных знаний и существующих вычислительных ресурсов для достижения практической и благородной цели, а не только для академических исследований или хакерства.

Мы публикуем открытые ключи, использованные автором Gpcode.

Один ключ используется для шифрования в операционных системах Windows XP и выше.

Key type: RSA KeyExchange
bitlength: 1024
RSA exponent: 00010001
RSA modulus:
c0c21d693223d68fb573c5318982595799d2d295ed37da38be41ac8486ef900a
ee78b4729668fc920ee15fe0b587d1b61894d1ee15f5793c18e2d2c8cc64b053
9e01d088e41e0eafd85055b6f55d232749ef48cfe6fe905011c197e4ac6498c0
e60567819eab1471cfa4f2f4a27e3275b62d4d1bf0c79c66546782b81e93f85d

Второй – в Windows ранних версий (до Windows XP).

Key type: RSA KeyExchange
bitlength: 1024
RSA exponent: 00010001
RSA modulus:
d6046ad6f2773df8dc98b4033a3205f21c44703da73d91631c6523fe73560724
7cc9a5e0f936ed75c75ac7ce5c6ef32fff996e94c01ed301289479d8d7d708b2
c030fb79d225a7e0be2a64e5e46e8336e03e0f6ced482939fc571514b8d7280a
b5f4045106b7a4b7fa6bd586c8d26dafb14b3de71ca521432d6538526f308afb

Экспонента для обоих ключей: 0x10001 (65537).

Этой информации достаточно для того, чтобы специалисты смогли приступить к факторизации ключа.

Значительную помощь в решении задачи может оказать создание специальной утилиты для проведения факторизации.

«Лаборатория Касперского» готова предоставить любую дополнительную информацию и открыта для диалога с участниками проекта. Для координации действий между участниками создан специальный форум «Stop Gpcode».

 

Мне не понятно зачем весь этот сыр бор? Ну сделает вирусописатель в следующий раз 2048 бит и что они будут делать?

 

halyavin
это просто маркетинговое дерьмо
нет ни одного авера без баек.
макафе к примеру любит всё увеличивать в 10 раз и все к этому привыкли.
надо же как-то юзеров завоёвывать?
вреда от этих баек Вам ни кокого не причиняют - прочитали, посмеялись и забыли

 

оффтоп. GPCode вообще как-то странно возродился. Особенно учитывая историю с рустоком.ц и тем, что вперёд вышли вебовцы... Подозрительно всё слишком, имхо.