Самостоятельно расшифровать.

Защита информации

уровень высшего образования - бакалавриат

_{(образовательно-квалификационный уровень)}

Расчетно-графическая работа по теме Алгоритм Уильямса

	Выполнила: студентка IV курса
	группы: СА-бо-161
	направление подготовки (специальность):
	27.03.03 – системный анализ и управление
	^{(шифр и название направления подготовки, специальности)}
	Костенкова Ульяна Сергеевна
	^{(Фамилия Имя Отчество)}
	Руководитель	Родзевич Н.А.
		^{(Фамилия, Имя, Отчество)}
	Оценка:

Симферополь 2020 г.

История

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

Стойкость алгоритма

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

Описание алгоритма

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

Математический аппарат

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

(1)

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

(2)

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

(3)

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

(4)

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

(5)

(6)

Последнее выражение предназначено только для упрощения понимания. Так как функции определены для пар (a,b), то не содержат .

(7)

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

Создание ключа

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

(8)

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

(9)

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

(10)

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

Зашифрование

Все вычисления здесь ведутся по модулю . Запись здесь означает:

(11)

Представим открытый текст в виде числа Определим равен +1, то иначе определим через произведение s . Тогда легко убедится, что символ Якоби , что проверяется прямым вычислением. Далее находим число

. (12)

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

(13)

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

(14)

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

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

Расшифрование

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

(15)

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

(16)

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