Научна работа по разкриване на RSA-ключове на сертифицирани смарт-карти

Криптолозите все по-успешно разкриват секретните ключове на смарт-карти, сертифицирани от държавни органи. Този път те са успели да разложат на прости множители 184 различни 1024-битови RSA ключа от тайванската държавна база данни Citizen Digital Certificate, съдържаща над 2 милиона подобни ключа.

Както всички смарт-карти в света, така и тези уязвими сертификати са заверени от американските държавни структури (NIST), от Канада (CSE) и от Германия (Common Criteria на BSI).

103 от изследваните 184 ключа са генерирани чрез еднакви прости множители и са разкрити чрез бързо пресмятане на най-големия общ делител. Останалите ключове са нямали общи делители. За тяхното разкриване специалистите са използвали по-специфични уязвимости на генераторите за случайни числа – използвали са серии общи делители, изчислени по-рано. Така например простият множител, обозначен с p110 е срещан 46 пъти с различни вторични множители.

„Правилно работещият генератор на случайни числа никога не би генерирал еднакви повтарящи се 512-битови прости числа“ – отбелязват авторите на научната работа. В по-долната диаграма са показани повтарящите се прости множители и връзките между тях.

След това върху масива от сертификати са стартирани варианти на атаката на Купърсмит (Coppersmith’s attack). Това е първото в историята на криптоанализа успешно използване на тази атака върху реални криптоключове. Процесът за успешно разлагане на множители за 184 ключа от всичко 2 милиона ключа е отнел няколко часа, а алгоритъмът е изобразен по-долу.

Авторите на изследването са Таня Ланге от Техническия университет в Айндховен, Надя Хенингър от Пенсилванския университет и други, а тяхната научна работа официално ще бъде представена на конференцията Asiacrypt 2013 в Индия.