Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 20 декабря 2014 года; проверки требуют 11 правок.
Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 20 декабря 2014 года; проверки требуют 11 правок.
Для любой криптосистемы желательно, чтобы было доказано, что её взлом имеет вычислительную сложность аналогичную вычислительной сложности задачи, которую на данный момент невозможно решить за обозримое время. Как и RSA, криптосистема Уильямса опирается на предположение о сложности факторизации больших чисел, и было доказано, что для любого взлома шифротекста с помощью предварительного криптоанализа (имея лишь открытый ключ) необходимо провести факторизацию[1], то есть решить уравнение относительно и . Это утверждение не было доказано для системы RSA. Вычислительная сложность задачи факторизации неизвестна, но считается, что она достаточно высока.
Но, как и RSA, криптосистема Уильямса уязвима для атаки на основе подобранного шифротекста.
Алгоритм системы Уильямса, не являясь вычислительно более сложным, чем RSA, намного более громоздкий в описании.
Для него существует лемма[2], которая будет описана в разделе о математическом аппарате — она играет ключевую роль в этой криптосистеме.
Для начала следует определить терминологию — она заимствована из теории квадратичных полей, но для криптосистемы требуются лишь самые начальные знания. Рассмотрим элемент
где — целые числа, а — условный элемент, квадрат которого равен . Тогда будут справедливы следующие формулы:
Сопряжённым к числом называется
Определим также функции, которые помогут нам выразить степень этого числа. Пусть
тогда и можно выразить через следующим образом:
Последнее выражение предназначено только для упрощения понимания. Так как функции определены для пар , то не содержат .
Если предположить теперь, что , то можно записать следующие рекуррентные соотношения:
Эти формулы предназначены для быстрого вычисления и . Так как и , то также не зависит от .
Лемма
Пусть является произведением двух нечётных простых чисел и ; - целые числа, удовлетворяющие уравнению
.
Пусть символы Лежандра и удовлетворяют сравнениям
Сначала выбираются два простых числа и , вычисляется их произведение . С помощью перебора выбирается число так, чтобы символы Лежандра и удовлетворяли условиям, наложенным в лемме. Затем (также подбором) определяется число такое, что символ Якоби
и
Число выбирается так же, как и в лемме:
Затем выбираются числа , удовлетворяющие условиям, наложенным в лемме. Выберем случайное, например, , а вычислим по формуле
Все вычисления здесь ведутся по модулю . Запись здесь означает
Представим открытый текст в виде числа . Определим и : если символ Якоби равен , то
и
иначе определим через произведение
и
Тогда легко убедиться, что символ Якоби
что проверяется прямым вычислением (во втором случае с учётом выбора и мультипликативности символа Якоби).
Далее находим число
Представим в виде удовлетворяет условиям, накладываемым в лемме. Действительно, удовлетворяют условиям по построению, и
Из последней формулы следует, что
Получив следует его зашифровать возведением в степень — результат может быть представлен через и которые могут быть[3] быстро (за количество операций порядка ) найдены с помощью рекуррентных формул.
Введём обозначение
Тогда криптотекстом будет являться тройка чисел где
Расшифрование проводится проще. Сначала вычисляется
что может сделать и злоумышленник. Но для окончательного расшифрования необходимо вычислить, как показано в лемме, — при том, что держится в секрете.
Число передаваемое в сообщении, укажет, какой из знаков верен — тот, что даёт чётный результат или тот, что даёт нечётный. Число покажет, следует ли умножить результат на . В результате мы получим число
И с лёгкостью найдём исходный текст, что и завершит процесс расшифрования.
Как и на RSA, на криптосистему может быть проведена атака на основе подобранного шифротекста. Предположим, что криптоаналитик нашёл некоторый алгоритм, позволяющий с вероятностью расшифровать криптотекст. Тогда он может поступить следующим образом:
1. Выбрать число такое, что символ Якоби ;
2. Зашифровать , но таким образом, как будто упомянутый символ Якоби равен и , получив на выходе криптотекст ;
3. Расшифровать полученный криптотекст, получив некоторый .
Тогда с вероятностью криптоаналитик может получить
или
Что позволяет произвести факторизацию и взломать криптосистему.
После генерации ключа основные вычисления происходят при возведении числа в степень, а это может быть произведено за умножений по модулю, каждое из которых происходит за операций сложения, в свою очередь выполняющихся за элементарных операций сложения неизменной скорости — то есть за , с той же скоростью, что и возведение в степень целого числа по модулю, которое требуется для использования RSA.