Лабораторная работа 7 Обмен ключами по схеме Диффи-Хеллмана

Цель работы

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

Указание к работе

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

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

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

Рис. Обмен ключами по схеме Диффи - Хеллмана.

Алгоритм заключается в следующем:

1. Глобальные открытые элементы: q - простое число a - первообразный корень q

2. Вычисление ключа абонентом A:

• выбирается секретное число X_A (X_A< q)

• вычисление открытого значения Y_A:

3. Вычисление ключа абонентом B:

• выбирается секретное число X_B (X_B< q)

• вычисление открытого значения Y_B:

4. Вычисление секретного ключа абонентом A:

5. Вычисление секретного ключа абонентом B:

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

Пример:

Пусть q = 97 и a = 5

Абонент A: Сгенерировал случайное число X_A = 36

Абонент B: Сгенерировал случайное число X_B = 58

Эти элементы они держат в секрете. Далее каждый из них вычисляет новый элемент: ,

Потом они обмениваются этими элементами по каналу связи. Теперь абонент A, получив Y_B и зная свой секретный элемент X_A, вычисляет общий ключ: .

Аналогично поступает абонент B:

Задание

Реализовать программу, генерирующую алгоритм обмена ключей по схеме Диффи-Хеллмана. Лабораторная работа 8 Шифр rsa

Цель работы

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

Указание к работе

Алгоритм RSA был разработан в 1977 году Роном Ривестом, Ади Шамиром и Леном Адлеманом и опубликованный в 1978 году. С тех пор алгоритм Rivest-Shamir-Adleman (RSA) широко применяется практически во всех приложениях, использующих криптографию с открытым ключом.

Алгоритм RSA состоит из трех этапов:

I. Вычисление ключей

Важным моментом в этом криптоалгоритме является создание пары ключей: открытого и закрытого. Для алгоритма RSA этап создания ключей состоит из следующих операций:

1. Выбираются два простых РАЗЛИЧНЫХ числа p и q. Вычисляется их произведение n=p*q, называемое модулем.

2. Вычисляется функция Эйлера Ф(n)=(p - 1)*(q - 1).

3. Выбирается произвольное число e (e <n), такое, что 1< e <Ф(n) и не имеет общих делителей кроме 1 (взаимно простое) с числом (p - 1)*(q - 1).

4. Вычисляется d методом Евклида таким образом, что (e*d - 1) делится на (p - 1)*(q - 1).

5. Два числа (е, n) - публикуются как открытый ключ.

6. Число d хранится в секрете - закрытый ключ есть пара (d, n), который позволит читать все послания, зашифрованные с помощью пары чисел (е, n).

II. Шифрование

Шифрование с помощью этих чисел производится так:

• Отправитель разбивает свое сообщение на блоки . Значение , поэтому длина блока в битах не больше k=[log₂(n)] бит, где квадратные скобки обозначают, взятие целой части от дробного числа.

Например, если n=21, то максимальная длина блока k=[log₂(21)]=[4.39…]=4 бита.

• Подобный блок может быть интерпретирован как число из диапазона (0;2^k-1). Для каждого такого числа m_i вычисляется выражение (c_i – зашифрованное сообщение): .

Необходимо добавлять нулевые биты слева в двоичное представление блока до размера k=[log₂(n)] бит.

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

Чтобы получить открытый текст надо каждый блок расшифровать отдельно:

Пример:

Выбрать два простых числа: р = 7, q = 17. Вычислить n = p·q = 7 · 17 = 119. Вычислить Ф(n) = (p - 1)·(q - 1) = 96. Выбрать е так, чтобы е было взаимнопростым с Ф(n) = 96 и меньше, чем Ф(n): е = 5. Определить d так, чтобы d·e ≡ 1 mod 96 и d < 96. d = 77, так как 77 · 5 = 385 = 4 · 96 + 1. Результирующие ключи открытый {5, 119} и закрытый ключ {77, 119}. Например, требуется зашифровать сообщение М = 19. 19⁵ = 66 (mod 119); С = 66. Для расшифрования вычисляется 66⁷⁷ (mod 119) = 19.

Задание