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