Последние дни RSA

Евгений Firstborn Рогов

Спецвыпуск: Хакер, номер #055, стр. 055-016-2

А может быть, есть другой подход? Есть, и даже несколько, но все они, к сожалению взломщика, основаны на недоработках в реализации алгоритма, то есть являются не фундаментальными трудностями, а просто легко устранимыми человеческими ошибками. В качестве примера такой недоработки можно привести механизмы генерации случайных чисел, используемые для выбора простых чисел P и Q, на которых основывается вычисление ключей. Действительно ли случайны генерируемые стандартными библиотечными функциями числа? В действительности эти числа не случайны: тут применяются так называемые генераторы псевдослучайных чисел - некоторый алгоритм, который использует в качестве входных данных системное время и на выходе выдает числа, по виду похожие на случайные. Если алгоритм известен (а это именно так), то, узнав его входные данные (время!), можно однозначно реконструировать эти самые "случайные" числа, а затем и получить ключи! Впрочем, стоит тут же охладить твой пыл криптовзломщика: в серьезных системах используются специальные методы, позволяющие генерить действительно случайные числа, основанные на таких явлениях, как различные термодинамические эффекты и даже радиоактивный распад.

Настоящий подвох

Почему бы не обратить внимание на другой аспект проблемы: когда речь шла о невозможности эффективно вычислить решение математических задач вроде разложения чисел на простые сомножители, всегда имелись в виду классические вычислительные машины. А что если мы попробуем применить к этим проблемам что-нибудь совсем не классическое? Например, квантовый компьютер. Оп-па, попались! Оказывается, квантовый компьютер - то, что нам нужно! Уже в 1991 году некто Шор взял и предложил эффективный алгоритм разложения чисел на простые множители, но только для квантового компьютера. Если у тебя возникнет желание погрузиться в технические детали этого во всех отношениях весьма интересного алгоритма, то ты сможешь найти все подробности, например, тут: www.rec.vsu.ru/rus/ecourse/quantcomp/sem9.pdf.