Прикладная криптология

 

Государственный университет телекоммуникаций

Учебно-научный  институт защиты информации

Кафедра безопасности информационных технологий

 

 

Прикладная криптология

 

 

 

 

 

 

 

 

 

 

 

 

 

 

О Т Ч Ё  Т

 

по лабораторной работе № 10

 

 

ПРОТОКОЛ СОГЛАСОВАНИЯ КЛЮЧЕЙ ДИФФИ-ХЕЛЛМАНА

И КРИПТОСИСТЕМА  ЭЛЬ-ГАМАЛЯ

 

Вариант № 0

 

 

Выполнил(ла): студент(ка) БСД – 4іБ, і=1,2

 

 

Фамилия И.О.________________________

 

 

Дата сдачи/защиты____________________

 

 

Проверил___________________________

 

 

Оценка_____________________________

 

 

 

 

 

20__

 

Выполнение работы

 

1. Краткие теоретические сведения.

 

1. Протокол согласования  ключей Диффи-Хеллмана.

 

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

У.Диффи и М.Хеллман предложили для создания криптографических систем с открытым ключом использовать однонаправленную показательную функцию в мультипликативной группе конечного поля (функцию дискретного возведения в степень).

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

Протокол Диффи-Хеллмана осуществляет так называемый экспоненциальный  ключевой обмен, с использованием функции , при заранее выбранных несекретных параметрах . Эти параметры зависимы, в том смысле, что выбирается так, чтобы последовательность степеней совпадала с точностью до перестановки с последовательностью .

Наименьшее натуральное число  называется порядком числа по модулю , если имеет место сравнение ; и НОД . Число называется примитивным элементом или первообразным корнем по модулю , если . В этом случае все числа класса вычетов – также первообразные корни по этому модулю.

Если модуль – простое число, то и по теореме Ферма . Следовательно, первообразные корни следует искать среди решений сравнения . Для практического нахождения первообразных корней по простому модулю удобно пользоваться следующим критерием поиска первообразных корней: если – каноническое разложение числа и , , …, , то целое число будет первообразным корнем по модулю сравнения .

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

Первообразные корни по простому модулю всегда существуют и их число равно (теорема Гаусса).

 

Первообразные корни простому модулю всегда существуют и их число равно (теорема Гаусса).

Протокол обмена ключами Диффи–Хеллмана:

Открытые параметры, известные  участникам ключевого обмена и – и – заранее выбранные числа, – некоторый первообразный элемент поля Галуа , – простое.

1. Абоненты и независимо и случайно выбирают по одному числу – случайному вычету по модулю , соответственно и , сохраняя их в тайне. Абоненты и независимо вычисляют и .
2. Абоненты и обмениваются значениями и .
3. Абонент , получив значение , вычисляет .

Абонент , получив значение , вычисляет .

4. Каждый из абонентов имеет значение общего секретного ключа .

 

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

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

 

2. Криптосистема  Эль-Гамаля

 

Криптосистема Эль-Гамаля является одним из вариантов протокол обмена ключами Диффи–Хеллмана.

Организация шифрованного обмена сообщениями с помощью криптосистемы Эль-Гамаля между абонентами , когда абонент хочет получать зашифрованные сообщения от абонентов :

1. Создание открытого и закрытого ключей. Абонент генерирует открытый ключ и закрытый ключ . Для этого:

1. выбирается большое простое число и вычисляется первообразный корень по модулю ;
2. наугад выбирается целое число из интервала , которое является закрытым ключом ;
3. вычисляется значение .
4. открытый ключ – тройку чисел – абонент пересылает всем абонентам .

2. Шифрование. Каждым из абонентов

1. выбирается произвольное число из отрезка (рандомизатор, разовый ключ) с условием НОД . Рандомизаторы не должны повторяться и должны содержаться в секрете.
2. открытое сообщение разбивается на блоки . Каждый блок – элемент мультипликативной группы вычетов по модулю ;
3. блоки открытых сообщений шифруются по формулам: (лазейка), (шифртекст);
4. криптограммой является пара блоков данных , которая и отсылается абоненту .

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

.

(

).

 

 

2. Сгенерируем общий ключ, пользуясь протоколом обмена ключей Диффи-Хеллмана.

 

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

Открытые параметры и .

1. Абонент генерирует псевдослучайное число, например,

Абонент генерирует псевдослучайное число, например, .

2. Абонент вычисляет .

Абонент вычисляет .

3. Абоненты и обмениваются значениями и .
4. Абонент вычисляет общий ключ

Абонент вычисляет общий ключ

.

Значение общего секретного ключа .

 

 

3. Сгенерируем ключи и зашифруем открытое сообщение , пользуясь криптосистемой Эль-Гамаля.

1. Сгенерируем открытый ключ и закрытый ключ . Для этого
1. Выберем простое число и первообразный корень по модулю .
2. Выберем целое число из интервала , например, .
3. Вычислим значение .

Таким образом, открытый ключ и закрытый ключ сформированы.

2. Зашифруем открытое сообщение , для чего выберем рандомизатор и вычислим

,

.

Криптограмма  имеет вид  .

3. Рассмотрим процесс дешифрования полученной криптограммы:

Найдём число, обратное к 16 по модулю 43. С помощью расширенного алгоритма Евклида найдем линейное представление наибольшего общего делителя , то есть найдем целые числа и такие, что .

Протокол работы расширенного алгоритма Евклида оформим в виде таблицы:

 

Остатки	43	16	11	5	1	0
Частные			2	1	2	5
	1	0	1	–1	3	–16
	0	1	–2	3	–8	43

 

Имеем , откуда . Следовательно, , поэтому .

 

Таким образом, .