Криптосистема Уильямса

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Криптосистема Уильямса (Williams System) — система шифрования с открытым ключом, созданная Хью Коуи Уильямсом (Hugh Cowie Williams) в 1984 году.

История[править | править код]

Алгоритм был разработан в 1984 году как альтернатива более известному RSA. Целью разработки было избавиться от уязвимостей криптосистемы.

Об алгоритме[править | править код]

Для любой криптосистемы желательно, чтобы было доказано, что её взлом имеет вычислительную сложность аналогичную вычислительной сложности задачи, которую на данный момент невозможно решить за обозримое время. Как и RSA, криптосистема Уильямса опирается на предположение о сложности факторизации больших чисел, и было доказано, что для любого взлома шифротекста с помощью предварительного криптоанализа (имея лишь открытый ключ) необходимо провести факторизацию[1], то есть решить уравнение относительно и . Это утверждение не было доказано для системы RSA. Вычислительная сложность задачи факторизации неизвестна, но считается, что она достаточно высока. Но, как и RSA, криптосистема Уильямса уязвима к атаке на основе подобранного шифротекста.


Описание алгоритма[править | править код]

Алгоритм системы Уильямса, не являясь вычислительно более сложным, чем RSA, намного более громоздкий в описании. Для него существует лемма[2], которая будет описана в разделе о математическом аппарате — она играет ключевую роль в этой криптосистеме.

Математический аппарат[править | править код]

Для начала следует определить терминологию — она заимствована из теории квадратичных полей, но для криптосистемы требуются лишь самые начальные знания. Рассмотрим элемент

где  — целые числа, а  — условный элемент, квадрат которого равен . Тогда будут справедливы следующие формулы:

Сопряжённым к числом называется

Определим также функции, которые помогут нам выразить степень этого числа. Пусть

тогда и можно выразить через следующим образом:

Последнее выражение предназначено только для упрощения понимания. Так как функции определены для пар , то не содержат . Если предположить теперь, что , то можно записать следующие рекуррентные соотношения:

Эти формулы предназначены для быстрого вычисления и . Так как и , то также не зависит от .

Создание ключа[править | править код]

Сначала выбираются два простых числа и , вычисляется их произведение . С помощью перебора выбирается число так, чтобы символы Лежандра и удовлетворяли условиям, наложенным в лемме. Затем (также подбором) определяется число такое, что символ Якоби

и Число выбирается так же, как и в лемме:

Затем выбираются числа , удовлетворяющие условиям, наложенным в лемме. Выберем случайное, например, , а вычислим по формуле

Тогда  — открытый ключ, а  — секретный ключ.

Зашифрование[править | править код]

Все вычисления здесь ведутся по модулю . Запись здесь означает Представим открытый текст в виде числа . Определим и : если символ Якоби равен , то

и

иначе определим через произведение

и

Тогда легко убедиться, что символ Якоби

что проверяется прямым вычислением (во втором случае с учётом выбора и мультипликативности символа Якоби). Далее находим число

Представим в виде удовлетворяет условиям, накладываемым в лемме. Действительно, удовлетворяют условиям по построению, и

Из последней формулы следует, что

Получив следует его зашифровать возведением в степень  — результат может быть представлен через и которые могут быть[3] быстро (за количество операций порядка ) найдены с помощью рекуррентных формул. Введём обозначение

Тогда криптотекстом будет являться тройка чисел где

Расшифрование[править | править код]

Расшифрование проводится проще. Сначала вычисляется

что может сделать и злоумышленник. Но для окончательного расшифрования необходимо вычислить, как показано в лемме,  — при том, что держится в секрете.

Число передаваемое в сообщении, укажет, какой из знаков верен — тот, что даёт чётный результат или тот, что даёт нечётный. Число покажет, следует ли умножить результат на . В результате мы получим число

И с лёгкостью найдём исходный текст, что и завершит процесс расшифрования.

Безопасность[править | править код]

Как и на RSA, на криптосистему может быть проведена атака на основе подобранного шифротекста. Предположим, что криптоаналитик нашёл некоторый алгоритм, позволяющий с вероятностью расшифровать криптотекст. Тогда он может поступить следующим образом:

1. Выбрать число такое, что символ Якоби ;
2. Зашифровать , но таким образом, как будто упомянутый символ Якоби равен и , получив на выходе криптотекст ;
3. Расшифровать полученный криптотекст, получив некоторый .

Тогда с вероятностью криптоаналитик может получить

или

Что позволяет произвести факторизацию и взломать криптосистему.

Быстродействие[править | править код]

После генерации ключа основные вычисления происходят при возведении числа в степень, а это может быть произведено за умножений по модулю, каждое из которых происходит за операций сложения, в свою очередь выполняющихся за элементарных операций сложения неизменной скорости — то есть за , с той же скоростью, что и возведение в степень целого числа по модулю, которое требуется для использования RSA.

Пример[править | править код]

Генерация ключа[править | править код]

Выберем, например, и , произведением которых является . Так как

и

Можно выбрать . Также, если выбрать , получим

Что удовлетворяет условию теоремы. Далее получим

И, наконец, выберем экспоненты шифрования и расшифрования: так как

Можно выбрать

Зашифрование[править | править код]

Пусть исходный текст будет . Так как

Имеем , и

Так как нечётно, получаем . После вычисления и получаем

Таким образом, шифротекстом является тройка .

Расшифрование[править | править код]

Теперь следует вычислить :

Так как , вычисляем также

Так как , то должно быть нечётным и

Учитывая, что вторая компонента шифротекста , заключаем, что . В таком случае

.

Таким образом, мы получили , который и являлся первоначальным открытым текстом.

Примечания[править | править код]

  1. Kim, 1992.
  2. Williams, 1985.
  3. Арто Саломаа — Криптография с открытым ключом, изд. Мир, 1995, ISBN 5-03-001991-X

Литература[править | править код]

  • Hugh C. Williams. Some Public-Key Crypto-Functions as Intractable as Factorization. — 1985.
  • Kwangio Kim (Ed.). Public Key Criptography. — 1992. — С. 1—17.