Задачи для самостоятельной работы
1. G – мультипликативная группа поля классов вычетов Z 
, b и y – некоторые элементы группы G . Найти дискретный логарифм элемента y по основанию b , если
а) p =7, b =3, y =3; б) p =7, b = 5, y =5;
в) p =9, b = 3, y =2; г) p =11, b = 2, y =5;
д) p =23, b =5, y =7; е) p =43, b =3 , y =2.
Схема Диффи-Хеллмана
Протокол Ди́ффи – Хе́ллмана (англ. Diffie-Hellman, DH) – криптографический протокол, позволяющий двум и более сторонам получить общий секретный ключ, используя незащищенный от прослушивания канал связи. Полученный ключ используется для шифрования дальнейшего обмена с помощью алгоритмов симметричного шифрования.
Схема открытого распределения ключей, предложенная Диффи и Хеллманом, произвела настоящую революцию в мире шифрования, так как снимала основную проблему классической криптографии – проблему распределения ключей.
Передача ключа по открытым каналам была большой проблемой криптографии 20 века. Но эту проблему удалось решить после появления алгоритма Диффи-Хеллмана. Открытое распространение ключей Диффи – Хеллмана позволяет паре пользователей системы выработать общий секретный ключ, не обмениваясь секретными данными.
Основы криптографии с открытыми ключами были выдвинуты Уитфилдом Диффи (Whitfield Diffie) и Мартином Хеллманом (Martin Hellman), а также независимо от них Ральфом Мерклом (Ralph Merkle). Их вкладом в криптографию было убеждение, что ключи можно использовать парами — ключ шифрования и ключ дешифрирования — и что может быть невозможно получить один ключ из другого. Диффи и Хеллман впервые представили эту идею на Национальной компьютерной конференции 1976 года, а через несколько месяцев была опубликована их основополагающая работа «New Directions in Cryptography» («Новые направления в криптографии»).
|
|
|
Предположим, что обоим абонентам известны некоторые два числа g и p (например, они могут быть «зашиты» в программное обеспечение), которые не являются секретными и могут быть известны также другим заинтересованным лицам. Для того, чтобы создать неизвестный более никому секретный ключ, оба абонента генерируют большие случайные числа: первый абонент – число a, второй абонент – число b. Затем первый абонент вычисляет значение A = ga mod p и пересылает его второму, а второй вычисляет B = g b mod p и передаёт первому. Предполагается, что злоумышленник может получить оба этих значения, но не модифицировать их (то есть у него нет возможности вмешаться в процесс передачи).
На втором этапе, первый абонент на основе имеющегося у него a и полученного по сети B вычисляет значение B a mod p = g ab mod p, а второй абонент на основе имеющегося у него b и полученного по сети A вычисляет значение Ab mod p = g ab mod p. Как нетрудно видеть, у обоих абонентов получилось одно и то же число: K = g ab mod p. Его они и могут использовать в качестве секретного ключа, поскольку здесь злоумышленник встретится с практически неразрешимой (за разумное время) проблемой вычисления g ab mod p по перехваченным ga mod p и g b mod p, если числа p , a , b выбраны достаточно большими.
|
|
|
При работе алгоритма, каждая сторона:
1) генерирует случайное натуральное число a – закрытый ключ;
2) совместно с удалённой стороной устанавливает открытые параметры p и g (обычно значения p и g генерируются на одной стороне и передаются другой), где p является случайным простым числом, g является порождающим элементом в мультипликативной группе конечного поля Z ;
3) вычисляет открытый ключ A, используя преобразование над закрытым ключом: A = ga mod p;
4) обменивается открытыми ключами с удалённой стороной;
5) вычисляет общий секретный ключ К, используя открытый ключ удаленной стороны B и свой закрытый ключ a: К = B a mod p.
К получается равным с обеих сторон, потому что:
Ba mod p = (gb mod p)a mod p = gab mod p =
= (ga mod p)b mod p = Ab mod p.
Пример 1. Ева – криптоаналитик. Она читает пересылку Боба и Алисы, но не изменяет содержимого их сообщений. Рассмотрим следующие конкретные значения для g, p, a, A, b, B:
|
|
|
p = 23 – открытое простое число;
g = 5 – порождающий элемент в мультипликативной группе конечного поля Z 
;
a = 6 – секретный ключ Алисы;
A = g 
mod p = 8 – открытый ключ Алисы;
b = 15 – секретный ключ Боба;
B = g 
mod p = 19 – открытый ключ Боба.
| Алиса | Боб | Ева | |||
| Знает | Не знает | Знает | Не знает | Знает | Не знает |
| p = 23 | b | p = 23 | a | p = 23 | a |
| g = 5 | g = 5 | g = 5 | b | ||
| a = 6 | b = 15 | K | |||
A = 5  mod p= = 8
| B = 5  modp = =19
| A = 5 mod p= = 8
| |||
| B = 19 | A = 8 | B = 5 mod p = = 19
| |||
| K = 19 (mod 23) = 2
| K = 8 (mod 23) = 2
| ||||
Если Ева найдет такие a и b , что5 mod p = 8 и 5 mod p = 19, то она может найти и ключ К. Понятно, что в предложенной задаче a и b легко найти простым перебором вариантов.
На практике для a и b используются числа порядка 10100 и p порядка 10300. Число g не обязано быть большим и обычно имеет значение в пределах первого десятка. В этом случае перебрать все варианты не представляется возможным.
Необходимо отметить, что алгоритм Диффи – Хеллмана работает только на линиях связи, надёжно защищённых от модификации. Если бы он был применим на любых открытых каналах, то давно снял бы проблему распространения ключей и, возможно, заменил собой всю асимметричную криптографию. Однако, в тех случаях, когда в канале возможна модификация данных, появляется возможность атаки человек посередине. Атакующий заменяет сообщения переговоров о ключе на свои собственные и таким образом получает два ключа – свой для каждого из законных участников протокола. Далее он может перешифровывать переписку между участниками, своим ключом для каждого, и таким образом ознакомиться с их сообщениями, оставаясь незамеченным.
|
|
|
Использование алгоритма Диффи – Хеллмана не ограничивается двумя участниками. Он может быть применен на неограниченное количество пользователей. Рассмотрим ситуацию, когда Алиса, Боб и Кэрол вместе генерируют исходный ключ. В данном случае последовательность действий будет следующая:
1. Стороны договариваются о параметрах алгоритма p и g.
2. Стороны генерируют свои ключи – a, b и c.
3. Алиса вычисляет A = ga mod p и посылает его Бобу.
4. Боб вычисляет B = g b mod p и посылает его Дэйву.
5. Боб вычисляет B ’ = Ab mod p = g ab mod p и посылает его Дэйву.
6. Дэйв вычисляет D = B 
mod p = g bc mod p и посылает его Алисе.
7. Алиса вычисляет K = D mod p = g abc mod p и использует его как ключ.
8. Дэйв вычисляет D ’ = g c mod p и посылает его Алисе.
9. Алиса вычисляет A ’ = (D ’) mod p = g ac mod p и посылает его Бобу.
10. Боб вычисляет K = (A ’) mod p = g abc mod p и использует его как ключ.
11. Дэйв вычисляет K = ( B ’) mod p = g abc mod p и использует его как ключ.
В данной ситуации всеми участниками получен один и тот же ключ.
Дата добавления: 2019-02-12; просмотров: 214; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!