Сегодня я увидел на доске crypto в форуме сайта BugTraq.ru сообщение от Komlin-а "Ошибка в RSA?" и решил, что пришла пора вспомнить и написать о моих изысканиях в области криптографии и стойкости алгоритма RSA.

Волей Случая, с 1994 года я занимался вопросами организации безопасной работы с информацией с ограниченным доступом в компьютерных сетях. Область для меня была достаточно новая, поэтому надо было составить свое представление о решаемых задачах, провести свое собственное изучение объекта приложения своих сил. Сначала надо было определиться с безопасностью оборудования, операционных систем, сетей и сетевых протоколов. Затем надо было определиться со способами и методами ограничения или полного пресечения несанкционированного доступа к информации ограниченного доступа. Итак, в 1996 году я приступил к исследованию роли, определению места и выработке стратегии применения криптографии в защите информации с ограниченным доступом от несанкционированного доступа.

Для исследования вопроса я придумал математическую модель в виде антагонистической игры двух лиц, одно из которых - "банкир" - желает получить максимальный выигрыш от применения алгоритмов шифрования для защиты информации при передаче ее по открытым каналам связи, а другое - "кракер" - желает увеличить свой выигрыш своевременным прочтением перехваченных зашифрованных сообщений "банкира". В качестве стратегий были выбраны непрерывные на некотором интервале функции: "банкир" - доверие к методу шифрования в интервале от полного отказа до безоговорочного доверия, "кракер" - затраты на "взлом" зашифрованных сообщений в интервале от полной бездеятельности до привлечения всех доступных ему ресурсов. В случае прочтения сообщения в течении заранее заданного времени (время, в течении которого возможно нанесение ущерба злоумышленником в результате расшифровки перехваченного сообщения), "кракер" получал выигрыш в десятки, сотни и/или тысячи раз больший, нежели банкир. В остальных случаях выигрыш "кракера" был равен нулю. Суммарный выигрыш игроков всегда равен нулю (условие антагонизма). Дополнительным условием игры был закон Мура, когда вычислительная мощность усредненного компьютера "кракера" увеличивалась вдвое каждые два года. Необходимо было найти оптимальные стратегии поведения игроков. Решение осуществлялось интегрированием полученной системы дифференциальных уравнений модифицированным методом РК-4 с учетом теоремы о минимаксе. Подбор и уточнение параметров системы уравнений и целевой функции осуществлялось моделированием известных ситуаций для некоторых алгоритмов шифрования.

В результате решения этой игры было выяснено, что для алгоритма DES его применение должно закончиться где-то в 2000-2001 году, для алгоритма ГОСТ в районе 2100-2150 года, а для RSA с ключом 1024 бит где-то в районе 3000-3300 года. В одном из номеров ТИИЭР за 1990-1992 годы я прочел обзор по криптографии, где приводился пример с "взломом" алгоритма "укладка ранца". Я ввел в систему уравнений игры условие существования НП-полной задачи, от решения которой существенно зависит стойкость метода шифрования и добавил "кракеру" вторую стратегию - затраты на решение НП-полной задачи. Суммарные затраты ресурсов "кракера" не должны были превышать его ресурсы, растущие по закону Мура. Результаты просчета стратегий для разных алгоритмов кардинально изменились только для алгоритмов класса RSA, стойкость которых зависит от разрешимости некоей математической проблемы. Время применения RSA по результатам уточненной игры заканчивалось примерно к 2025 году. После введения в игру дополнительного условия о том, что "кракер" мог найти решение математической проблемы и не поставить об этом в известность "банкира" и "банкир" узнавал об этом только в результате резкого уменьшения выигрыша, время применения RSA уменьшилось до 2000 года. Выигрыш "банкира" при применении RSA на первом этапе был существенно больше, чем при применении DES из-за значительно меньшей начальной вероятности простого подбора секретного ключа. По прошествии же некоторого времени (порядка 10-12 лет) после начала применения алгоритма происходил резкий спад выигрыша из-за роста вероятности разрешения математической проблемы и к 2000 году должен был наступить полный отказ от применения этого метода шифрования.

Анализируя результаты игры, я пришел к выводу, что все существующие методы шифрования следует разделять на две группы по функциональному признаку: безусловностойкие алгоритмы, стойкость которых определяется только затратами ресурсов на подбор ключей, и условностойкие алгоритмы, стойкость которых зависит еще и от разрешения некой математической проблемы. Безусловностойкие алгоритмы можно назвать обыкновенными алгоритмами, а условностойкие - феноменальными алгоритмами, поскольку их стойкость основана на некоем математическом феномене. Такая классификация алгоритмов обусловлена возлагаемыми на шифрование функциями и подтверждается качественно различными стратегиями поведения игроков при использовании различных классов алгоритмов в рассмотренной игре "Применение алгоритмов шифрования".

Потом мне стало интересно, а может быть я сам смогу найти слабые места в алгоритме RSA или даже алгоритм вычисления секретных ключей. В том же обзоре ТИИЭР приводился пример простой расшифровки сообщений для алгоритма, похожего на алгоритм Эль Гамаля, но использующего побитную операцию "ИСКЛЮЧАЮЩЕЕ-ИЛИ" между данными и ключом вместо возведения в степень по модулю. Я начал обдумывать проблему и искать подходы к решению задачи "взлома" алгоритма RSA. Первоначально я ошибочно предположил, что резкое уменьшение выигрыша "банкира" указывает на время, когда будет найден приемлемый по затратам ресурсов алгоритм факторизации. Но потом понял, что возможно к этому времени будет найдено слабое место в алгоритме или даже какой-то алгоритм вычисления секретных ключей, не обязательно базирующийся на факторизации.

Теорема Геделя подсказывает: чтобы решить НП-полную задачу, необходимо расширить окружающее задачу пространство так, чтобы эта задача стала разрешимой либо тривиальной. Иными словами, решение математической проблемы может быть найдено в смежной области. Наиболее вероятным расширением виделось привлечение теории вероятностей и выявление каких-то нерегулярных (не тождественных) закономерностей. Тем более, что для анализа стойкости алгоритмов шифрования широко используются статистическо-вероятностные модели. Например, теорема Шеннона или Марковские цепочки. Оставалось найти такие закономерности и придумать, как их использовать.

Я предположил, что поскольку RSA базируется на малой теореме Ферма, то закономерности надо искать среди объектов и высказываний этой теоремы. Кроме того, известно, что для алгоритма DES существует четыре тривиальных ключа. Для алгоритма RSA мне такие ключи неизвестны. 0 и 1 - не могут быть ключами из-за свойств алгоритма по определению, однако эти два числа уже являются тривиальными сообщениями. Возможно, что некоторая дополнительная тривиальность, если она существует, должна проявляться именно в области шифруемых данных, а не ключей. Как следствие этих рассуждений была написана программа, текст которой приводится в конце статьи. И сразу же попадание в десятку. В этой программе используются два числа P и P-1 из малой теоремы Ферма и производится перебор данных, для выявления закономерностей. В качестве исходных чисел p, q, e, d были взяты числа из иллюстративного примера работы алгоритма RSA, где в сообщении S=1650 зашифровано слово "RSA".

Из следующей за текстом программы распечатки результата ее работы видно, что равенство между любыми двумя из пяти выражений:

S, S^e|_{mod m}, S^d|_{mod m}, S^ed|_{mod m}, S^ed|_{mod n}

бывает справедливо в среднем где-то в 50% случаев. На основе этих выражений можно составить 12 равенств (уравнений), 11 из которых могут выполняться или не выполняться для сообщения S, а равенство S = S^ed|_{mod n}, выполняется всегда, поскольку является самим алгоритмом RSA. Итак, мы получили 11 систем из двух уравнений с двумя неизвестными m и e (или d). Теперь, если предположить, что выполнение одного равенства - это независимое событие, то вероятность справедливости хотя бы одного равенства значительно возрастает. Предположим, что для шифрования сообщения S используется 700 битное основание модуля. Вероятность подбора ключа будет 2*2^-700 = 2^-699. Если же вместо ключа подбирать такое сообщение, для которого будет выполнено хотя бы одно равенство из 11, то вероятность этого события будет равна

2*2^-700/11 = 2*2^-64 = 2^-63,

в предположении, что выполнение всех равенств одновременно обязательно происходит хотя бы один раз на всем множестве сообщений меньших 700 разрядного основания модуля. 2^-63 - это уже что-то. Число хотя и большое, но уже не запредельное. Я специально оговорился, что рассматриваю справедливость каждого из 11 равенств как независимые события. Вероятность наступления всех 11 событий одновременно я принимаю равной 2^-700 (произведение вероятностей). Следовательно, вероятность наступления одного события будет 2^-64 (корень 11 степени из вероятности наступления всех событий одновременно). Учитывая, что вероятность успешного попадания в середину интервала при любом переборе всегда равна 1/2, окончательная вероятность получается 2^-63. Остается только научиться решать системы таких уравнений.

Я не специалист в области теории чисел и поэтому я не знаю, как решать системы этих уравнений в целых числах. Я - Российский Инженер. Для меня в моей профессиональной деятельности главным Законом является поразившая меня в молодости выдержка из устава морского технического комитета N15 от апреля 1915 года: "Никакая должностная инструкция не может предусмотреть все отдельные случаи и дать вперед соответствующие указания, а поэтому господа Инженеры должны применять знания своей специальности и руководствуясь пользой дела прилагать все усилия для оправдания своего назначения". Я - конструктор, и значит практик, а не теоретик. Я не занимаюсь "добыванием" кирпичиков, из которых потом строю свои конструкции, а использую уже готовые, кем-то ранее "добытые". Мне крайне важно знать свойства базовых элементов конструкции, в том числе их надежность, ибо я терпеть ненавижу делать свою работу плохо. Поэтому я часто использую довольно грубые оценочные методы "прикидки". В данном случае, если к найденным мной 11 свойствам будет добавлено еще 10 других независимых свойств, то вероятность вычисления секретного ключа для рассматриваемого 700 битного модуля будет уже 2*2^-700/21 = 2*2^-33 = 2^-32. А это уже будет означать возможность вычисления секретного ключа в течении обозримого времени - нескольких месяцев или даже дней и даст возможность всерьез задуматься о создании специализированной микросхемы для "взлома" алгоритма RSA, что позволит уменьшить стойкость метода до часов или даже минут. Для меня было важно придумать, как выявленную закономерность использовать для вычисления секретного ключа, чтобы подтвердить результат решения игры "Применение алгоритмов шифрования" для алгоритма RSA. Решение получившихся систем на основе найденных свойств у меня вышло корявое и я опущу его описание. Скажу только, что была намеренно снижена вероятность вычисления секретного ключа для решаемости системы уравнений, что было много ручной работы, процесс решения далеко не всегда сходился. В конечном итоге я все же прочитал зашифрованное сообщение "RSA" на процессоре P5/100 с помощью интерпретатора bc в среде ОС FreeBSD за 25-30 минут. Я так же попытался вычислить секретный ключ e для расшифровки фразы "ALL GREEK TO ME" из примера в первой публикации алгоритма RSA. Но, в это время на Сахалине происходили "веерные" отключения электричества, из-за чего чуть было не "погибла" файловая система на моем компьютере и я едва не потерял все свои наработки. Эксперимент пришлось прекратить.

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

Возможно, что я где-то ошибаюсь. ERRARE HUMANUM EST. Скорее всего, я ошибаюсь, предполагая полную независимость событий. Тогда вероятность в моем случае будет не 2^-63, а 2^-70 или даже 2^-100. Но вряд ли я ошибаюсь в том, что реальная стойкость алгоритма RSA существенно ниже заявленной и что не обязательно искать оптимальный алгоритм факторизации для вычисления секретного ключа. И вряд ли я ошибаюсь, описывая придуманный мной метод оценки нижней границы стойкости феноменальных алгоритмов шифрования.

Программа вычисления секретного ключа была мной написана в декабре 1999 года. Несколько раньше, когда я еще только обдумывал эту программу, я написал статью-предупреждение "Гипотеза о стойкости RSA", в которой попытался обратить внимание всех на "развесистую клюкву", которая начала свое хождение от одного автора к другому и уже стала даже как бы Истиной. "Развесистая клюква", в отличии от "Ньютоновых яблок", опасна для здоровья, ибо она не вызывает к жизни Мысль, а наоборот, убивает последнюю. Поэтому необходимо крайне осторожно использовать RSA и лучше вообще отказаться от его применения из-за возможного существования слабых мест или даже ошибок в рассуждениях. Видимо, я был недостаточно убедителен. Что же касается самой "развесистой клюквы", то некоторые авторы совершают логическую ошибку, утверждая, что стойкость RSA определяется сложностью решения задачи факторизации. На самом деле, факторизация используется в одном УЖЕ ИЗВЕСТНОМ алгоритме вычисления секретных ключей. А поскольку для алгоритма RSA из-за его НП-полноты невозможно ни доказать, ни опровергнуть существование более оптимального алгоритма вычисления секретных ключей, то это ВЕРХНЯЯ ГРАНИЦА затрат. И если более оптимальный алгоритм пока не известен, то это не означает, что его вовсе нет в Природе. Просто, ТАКОЙ АЛГОРИТМ ПОКА ЕЩЕ НЕ НАЙДЕН. И существующая в настоящее время система электронной подписи будет сразу дискредитирована, как только будет "взломан" RSA. И последствия этого будут глобальными и катастрофическими, поскольку из-за "развесистой клюквы" алгоритм RSA получил очень широкое распространение, особенно в банковской сфере. И необходимо СРОЧНО ОТКАЗЫВАТЬСЯ ОТ ПРИМЕНЕИЯ АЛГОРИТМА RSA, пока ЕЩЕ ЕСТЬ НЕМНОГО ВРЕМЕНИ для поиска эквивалентной замены. И электронная подпись так и будет оставаться "голубой мечтой" до тех пор, пока не БУДУТ НАЙДЕНЫ БЕЗУСЛОВНОСТОЙКИЕ АЛГОРИТМЫ ШИФРОВАНИЯ С АСИММЕТРИЧНЫМИ КЛЮЧАМИ. Возможность (невозможность) существования таких алгоритмов и являлась той гипотезой, которую я высказывал ранее в статье "Гипотеза о стойкости RSA".

Системы шифрования, основанные на условностойких (феноменальных) алгоритмах, необходимо законодательно КАТЕГОРИЧЕСКИ ЗАПРЕТИТЬ К ПРИМЕНЕНИЮ для защиты информации, ущерб от несанкционированного доступа к которой сколько-нибудь значителен. Надеюсь, что на своем примере молчания в течении нескольких лет я это продемонстрировал. Хорошо, что я законопослушный гражданин и не пытался тайно использовать в своих интересах известное мне Знание!!! А если бы я был злоумышленником?

Моя мама не раз повторяла мне слова своего Учителя Андрея Алексеевича Трескова - "если ты не можешь объяснить старшекласснику теорию относительности Энштейна без сложных математических выкладок, то ты не понимаешь суть предмета". Надеюсь, что теперь я изложил все понятно.

15-21 ноября 2002 года
Urix

P.S. К сожалению, при переезде с Сахалина в Москву часть архивов была утеряна. В том числе исходные тексты окончательных версий программ решения игры "Применение алгоритмов шифрования" и вычисления секретного ключа алгоритма RSA. Удалось восстановить только кое-какие "огрызки" и полный текст приведенной в приложении программы. Восстанавливать же все нет ни времени, ибо Komlin уже наступает на пятки, ни желания, поскольку я сейчас занят другими задачами, над решением которых работаю уже более 15 лет, ни необходимости, из-за теперь уже известной нижней границы стойкости феноменальных алгоритмов шифрования. Статья об общих принципах криптографии, поэтому формулировки, доказательства и следствия теоремы Геделя, малой теоремы Ферма, теоремы Шеннона и теоремы о МиниМаксе смотрите самостоятельно. Желающие могут попробовать написать на основе изложения идей, лежащих в основе проделанной когда-то мной работы, свои программы вычисления секретного ключа алгоритма RSA. Лучше поискать решение системы уравнений в виде прямого алгоритма на основе теории чисел. Огромное спасибо Дмитрию Леонову и Komlin'у за помощь, которую они мне оказали в вспоминании и дополнительном осмыслении идей когда-то давно проделанной и уже почти забытой работы.

P.P.S. Вчера меня опять мучила бессоница. Так бывает, когда какое-то важное решение лежит на поверхности, а я прошел мимо него. Это работает подсознание. Посмотрел еще раз теорию RSA, все еще раз хорошенько обдумал и понял, какого "слона" то я и не приметил. Но сначала одно пояснение к условиям игры "Применение алгоритмов шифрования". Я использовал вероятность наступления неблагоприятного события (нахождение условия слабости алгоритма) в качестве условия существования НП-полной задачи и работы над ее разрешением. В течении определенного времени (1 год) добавлялось одно, ставшее известным за этот период и независимое от уже известных, свойство слабости алгоритма. Совокупность таких свойств в конечном итоге приводит к уменьшению стойкости феноменального алгоритма быстрее, нежели для обыкновенного алгоритма. Сокрытие слабого свойства я рассматривал, как удвоение числа слабых свойств, известных "кракеру". Сразу оговорюсь, что я не хочу уподобляться собирателям "развесистой клюквы", поэтому я исправляю ошибку, допущенную в тексте статьи. Поскольку сам алгоритм RSA (S=S^e*d|_mod(n)) является тождеством, то системы уравнений формируются из оставшихся 11 уравнений. Получается 10*9/2 = 45 систем 2-х уравнений с двумя неизвестными e и m. Усредненные затраты на раскрытие 700 битного ключа должны составлять 45*2^700*2/45/2 = 45*2³¹/2 = 45*2³⁰ = 4.5*10¹⁰ решений систем. Множитель, равный числу составленных систем, появился в выражениях из-за необходимости искать решения всех составленных систем уравнений для одного S. Из теории следует, что с равным успехом можно составить уравнения из S плюс 12 выражений, полученных комбинацией показателей степени (e,d,e*d) и множителей модуля (p-1,p) и (q-1,q). Отсюда получаем 12*11/2-1 = 65 уравнений, из которых можно составить 63*62*61/6=39710 систем 3-х уравнений с тремя неизвестными p, q и e. Средние затраты в этом случае уже должны составлять 39710*2^700*3/39710/2 = 39710*2^0.05/2 = 19980 = 2*10⁴ решений систем уравнений. Если предположить, что решение одной системы уравнений может быть найдено в течении одной секунды, то стойкость алгоритма RSA с 700 битным ключом будет чуть меньше шести часов. В общем виде необходимо в среднем решить 2*k*e^m*n/k систем уравнений, где k - количество уравнений, составленных на основе известных слабых свойств алгоритма, m - разрядность модуля, n - число уравнений составляющих систему. Для рассматриваемого случая минимальные затраты находятся из уравнения ^d/_dk(2*k*2^m*n/k) = 2*2^m*n/k*(1-m*n*ln(2)/k) = 0. Отсюда получаем k = m*n*ln(2) = 700*3*0.7 = 1456 систем уравнений для рассматриваемого случая 700 битного ключа. Затраты составят 1456*2^700*3/1456/2 = 1456*2^1.44/2 = 1975 = 2*10³ решений систем уравнений. Конечно, приведенный расчет справедлив только в том случае, ЕСЛИ ВЫПОЛНЕНИЕ КАЖДОГО РАВЕНСТВА ЯВЛЯЕТСЯ АБСОЛЮТНО НЕЗАВИСИМЫМ СЛУЧАЙНЫМ СОБЫТИЕМ. Я предполагаю, что выполнения лишь небольшой части составленных для одного S равенств являются независимыми и почти случайными событиями. Это же, кстати, следует из распечатки протокола работы программы. Следовательно, нижняя граница стойкости RSA находится существенно выше. Возможно, что зависимость уравнений является следствием периодичности результатов возведения в степень по модулю, когда для каждого сообщения S существует такое число t < n, для которого будет выполняться равенство S=S^t|_mod(n). Для взаимно простых S периоды повторения t(S,n) возведения в степень по модулю n независимы друг от друга и их значения являются лишь следствием общего (совместного) свойства пары чисел S и n. Отсюда следует, что для успешного вычисления секретного ключа для модуля n необходимо использовать различные и специально подобранные значения S. Например, предположим, что найдено такое (p-1)*(q-1) < S < p*q, что только для модулей p*q и (p-1)*(q-1) и/или комбинаций их сомножителей некое свойство будет одновременно выполняться не смотря на то, что S'=S|_{mod((p-1)*(q-1))} и S совсем разные числа. Тогда методом "ловли льва в пустыне" можно очень быстро найти произведение (p-1)*(q-1), что эквивалентно "взлому" алгоритма RSA. Для 700 битного ключа это будет 700 проверок выполнения условия. И, как я понимаю, теперь для теоретиков изменилась цель их поисков. Им теперь надо не опускать верхнюю границу стойкости, а необходимо доказательно поднимать нижнюю, чтобы хоть как-то реабилитировать дискредитированный пока еще только общими рассуждениями алгоритм RSA. Что же касается самой программы "взлома" алгоритма RSA, то на вопрос, как разделить дробь 7/8 на 6/11, можно ответить либо 77/48, либо рассказать, как это сделать. Оба ответа будут правильными. С моей точки зрения, решение игры "Применение алгоритмов шифрования" имеет гораздо более глобальное значение для криптографии, как прикладной науки, нежели один ее частный случай - алгоритм RSA.

23-25 ноября 2002 года
Юрий Аверьянов

Приложение N1
Программа RSA.bc, демонстрирующая обнаруженное свойство.

#!/usr/bin/bc -q

define pow (dig,exp,mod) {
    auto ret;
    ret = 1;
    while (exp > 0) {
	if ((exp % 2) == 1) {
	    ret = (ret * dig) % mod;
	    exp = exp - 1;
	}
	dig = (dig * dig) % mod;
	exp = exp / 2;
    }
    return (ret);
}

p = 211
q = 223
n = p * q
m = (p - 1) * (q - 1)
e = 16813
d = 19837
print "n = p*q = ", n, ",  m = (p-1)*(q-1) =", m, "\n";
print "s\tsdm\tsdn\tsdem\tsden\n";
print "e = ", e, ", d = ", d, "\n";
for (s = 1000; s < 1033; ++s) {
    sdm = pow(s,d,m);
    sdn = pow(s,d,n);
    sdem = pow(sdm,e,m);
    sden = pow(sdn,e,n);
    print s, "\t", sdm, "\t", sdn, "\t", sdem, "\t", sden, "\n";
}

n = p*q =47053, m = (p-1)*(q-1) = 46620
e = 16813, d = 19837
s	sdm	sdn	sdem	sden
1000	1000	36221	1000	1000
1001	1001	22819	1001	1001
1002	39852	1140	39852	1002
1003	1003	32551	1003	1003
1004	1004	34349	1004	1004
1005	32085	25843	32085	1005
1006	24316	32485	24316	1006
1007	1007	5703	1007	1007
1008	1008	17324	1008	1008
1009	1009	27226	1009	1009
1010	24320	7122	24320	1010
1011	16551	2650	16551	1011
1012	1012	5241	1012	1012
1013	1013	45218	1013	1013
1014	8784	39428	8784	1014
1015	1015	20314	1015	1015
1016	1016	45871	1016	1016
1017	1017	25226	1017	1017
1018	24328	45789	24328	1018
1019	1019	30093	1019	1019
1020	16560	56	16560	1020
1021	1021	22112	1021	1021
1022	24332	44917	24332	1022
1023	32103	27925	32103	1023
1024	1024	5962	1024	1024
1025	1025	38332	1025	1025
1026	24336	39978	24336	1026
1027	1027	14564	1027	1027
1028	1028	44392	1028	1028
1029	16569	2499	16569	1029
1030	24340	7271	24340	1030
1031	1031	24417	1031	1031
1032	32112	17831	32112	1032