Криптологи продолжают успешно факторизовать секретные ключи из смарт-карт, сертифицированных государственными стандартизующими органами. На этот раз они разложили на множители 184 разных 1024-битных ключа RSA из тайваньской государственной базы данных Citizen Digital Certificate, содержащей более 2 млн ключей.
Как и многие другие смарт-карты в разных странах мира, уязвимые сертификаты имеют официальный статус, заверенный государственными структурами США (NIST), Канады (CSE) и Германии (сертификация Common Criteria от BSI).
103 из 184 ключей сгенерированы с одинаковым простым множителем, они факторизованы путем вычисления наибольшего общего делителя. Остальные ключи не имели общих делителей. Для их факторизации пришлось использовать более тонкие уязвимости генераторов случайных чисел. На них указывал набор общих делителей, найденный ранее. Например, простой множитель p110 встречался 46 раз с разными вторыми множителями. Шестнадцатеричное представление множителя (это следующее простое число после 2511+2510) выглядит следующим образом.
0xc00000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000002f9
Еще семь раз встречался следующий простой множитель.
0xc92424922492924992494924492424922492924992494924492424922492924 992494924492424922492924992494924492424922492924992494924492424e5
В бинарном представлении это постоянное повторение последовательности 001.
«Правильно работающий ГСЧ никогда не сгенерирует одинаковые 512-битные простые числа», — отмечают авторы научной работы. На диаграмме ниже показаны повторяющиеся простые множители и их взаимосвязи.
Затем на массиве сертификатов были запущены варианты атаки Копперсмита с частичным восстановлением ключа. Это первое в истории криптоанализа успешное применение атаки Копперсмита на реальных ключах. Процесс разложения на множители 184 ключей из более 2 млн занял несколько часов, алгоритм изображен на схеме.
Авторы исследования — Надя Хенингер из университета Пенсильвании, Таня Ланге из Технического университета Эйндховена и др. Это те же самые криптологи, которые в прошлом году использовали аналогичный метод для факторизации тысяч криптографических ключей в интернете, тот доклад был представлен на конференции USENIX Security 2012.
Научная работа с описанием факторизации ключей RSA заявлена для конференции Asiacrypt 2013 в Бангалоре (Индия).
