стойкость алгоритма RSA
В RSA стойкость определяется как сложность обращения односторонней функции F(x) = xy (mod N), которая зависит от сложности разложения на множители модуля N (факторизация). При этом следует иметь в виду, что это утверждение является всего лишь предположением, поскольку строгих математических доказательств данного факта не существует. Стойкость алгоритма может быть существенно снижена за счёт некорректного выбора параметров алгоритма. Недавние работы по разложению больших чисел на сомножители показали, что для этого могут быть использованы разные и даже совершенно неожиданные средства. Сначала авторы RSA предлагали выбрать простые числа Р и Q случайно, по 50 десятичных знаков каждое. Считалось, что такие большие числа очень трудно разложить на простые сомножители при криптоанализе. Ривест полагал, что разложение на простые множители числа из почти что 130 десятичных цифр, приведенного в их публикации, потребует более 40 квадриллионов лет машинного времени. Но математики Ленстра из фирмы Bellcore и Манасси из фирмы DEC разложили число из 155 десятичных цифр на простые сомножители всего за 6 недель, соединив для этого 1000 ЭВМ, находящихся в разных странах мира. Выбранное число, называемое девятым числом Ферма, с 1983 года находилось в списке чисел, разложение которых считалось наиболее желательным. Это число взято потому, что оно считалось неразложимым при существующей вычислительной технике и достаточно большим для того, чтобы его можно считать безопасным для формирования N в RSA. Как заявил Ленстра, ведущий в Bellcore исследования по электронной защите информации и разложению больших чисел, их целью было показать разработчикам и пользователям криптографических систем, с какими угрозами они могут встретиться и насколько осторожными должны быть при выборе параметров алгоритмов шифрования.
Следует учесть, что работа по совершенствованию методов и техники разложения больших чисел только началась и будет продолжена. Те же Ленстра и Манасси в 1991 году нашли делитель тринадцатого числа Ферма, которое состоит примерно из 2500 десятичных разрядов. Теперь разработчикам криптографических алгоритмов с открытым ключом на базе RSA приходится избегать применения разложимых чисел длиной менее 200 десятичных разрядов. А так как для шифрования каждого блока информации приходится соответствующее число возводить в колоссально большую степень по модулю N, то для современных компьютеров это задача на грани возможного. Поэтому для практической реализации шифрования RSA начали разрабатывать специальные процессоры, которые позволили бы выполнять операции RSA достаточно быстро. Лучшими из серийно выпускаемых кристаллов являются процессоры фирмы CYLINK, которые позволяют выполнять возведение в степень целого числа из 307 десятичных знаков за доли секунды. Отметим, что чрезвычайно слабое быстродействие криптографических систем на основе RSA лишь ограничивает область их применения, но вовсе не перечеркивает их ценность.
предыдущая тема следующая