2020-04-12
190
И вот однажды Хеллмана осенило и он смог разработать рабочий алгоритм обмена ключами. Для работы по этому алгоритму нужно выполнять шаги на обоих сторонах, поэтому я зарисую это в таблице:
| Алиса | Боб | |||
| Этап 1 | Оба участника договариваются о значениях Y и P для общей односторонней функции. Эта информация не является секретной. Допустим были выбраны значения 7 и 11. Общая функция будет выглядеть следующим образом: 7x (mod 11) | |||
| Этап 2 | Алиса выбирает случайное число, например 3, хранит его в секрете, обозначим его как число A | Боб выбирает случайное число, например 6, хранит его в секрете, обозначим его как число B | ||
| Этап 3 | Алиса подставляет число A в общую функцию и вычисляет результат 73 (mod 11) = 343 (mod 11) = 2, обозначает результат этого вычисления как число a | Боб подставляет число B в общую функцию и вычисляет результат 76 (mod 11) = 117649 (mod 11) = 4, обозначает результат этого вычисления как число b | ||
| Этап 4 | Алиса передает число a Бобу | Боб передает число b Алисе | ||
| Этап 5 | Алиса получает b от Боба, и вычисляет значение bA (mod 11) = 43 (mod 11) = 64 (mod 11) = 9 | Боб получает a от Алисы, и вычисляет значение aB (mod 11) = 26 (mod 11) = 64 (mod 11) = 9 | ||
| Этап 6 | Оба участника в итоге получили число 9. Это и будет являться ключом.
| |||
Магия? Не спорю, с первого взгляда непонятно. Но после вчитывания и вдумывания в эту таблицу становится понятно как это работает. Впрочем если понятно не стало, то пролистайте до конца главы, там я выложил поясняющее видео.
Причем обратите внимание, что для получения ключа в конечной формуле, любому человеку нужно иметь три значения:
· Значения a и P, и секретное число Боба B
· или значения b и P, и секретное число Алисы A
Но секретные числа по каналу не передаются! Еве не получится восстановить ключ, не имея чьего-нибудь секретного числа. Почему — я писал выше, данная функция является односторонней. Попробуйте решите уравнение 4x (mod 11) = 2y (mod 11) найдя x и y.
Чтобы было понятнее, как работает схема Хеллмана, представьте шифр, в котором в качестве ключа каким-то образом используется цвет:
Допустим вначале, что у всех, включая Алису, Боба и Еву, имеется трехлитровая банка, в которую налит один литр желтой краски. Если Алиса и Боб хотят договориться о секретном ключе, они добавляют в свои банки по одному литру своей собственной секретной краски.
Алиса может добавить краску фиолетового оттенка, а Боб — малинового. После этого каждый из них посылает свою банку с перемешанным содержимым другому.
И наконец, Алиса берет смесь Боба и подливает в нее один литр своей секретной краски, а Боб берет смесь Алисы и добавляет в нее один литр своей секретной краски. Краска в обеих банках теперь станет одного цвета, поскольку в каждой находится по одному литру желтой, фиолетовой и малиновой краски.
|
|
|
Именно этот цвет, полученный при добавлении дважды в банки красок, и будет использоваться как ключ. Алиса понятия не имеет, какую краску добавил Боб, а Боб также не представляет, какую краску налила Алиса, но оба они достигли одного и того же результата.
Между тем Ева в ярости. Даже если она и сумеет перехватить банки с промежуточным продуктом, ей не удастся определить конечный цвет, который и будет согласованным ключом. Ева может видеть цвет краски, полученной при перемешивании желтой краски и секретной краски Алисы в банке, отправленной Бобу, и она может видеть цвет краски, полученной при перемешивании желтой краски и секретной краски Боба в банке, отправленной Алисе, но чтобы найти ключ, ей, на самом деле, необходимо знать цвета исходных секретных красок Алисы и Боба. Однако, рассматривая банки с перемешанными красками, Ева не сможет определить секретные краски Алисы и Боба. Даже если она возьмет образец одной из смешанных красок, ей не удастся разделить ее на исходные краски, чтобы найти секретную, поскольку смешивание краски является односторонней функцией.
Иллюстрация работы RSA на примере
Вокруг алгоритмов шифрования с отрытым и закрытым ключом существует множество недопониманий и мистификаций. Здесь я хотел бы предельно коротко и наглядно, с конкретными числами и минимумом формул, показать, как это работает.
Итак. Допустим, я хочу получить от вас некие данные. Мы с вам не хотим, чтобы эти данные узнал кто-то, кроме нас. И у нас нет никакой уверенности в надёжности канала передачи данных. Приступим.
Шаг первый. Подготовка ключей
Я должен проделать предварительные действия: сгенерировать публичный и приватный ключ.
· Выбираю два простых числа. Пусть это будет p=3 и q=7.
· Вычисляем модуль — произведение наших p и q: n=p×q=3×7=21.
· Вычисляем функцию Эйлера: φ=(p-1)×(q-1)=2×6=12.
· Выбираем число e, отвечающее следующим критериям: (i) оно должно быть простое, (ii) оно должно быть меньше φ — остаются варианты: 3, 5, 7, 11, (iii) оно должно быть взаимно простое с φ; остаются варианты 5, 7, 11. Выберем e=5. Это, так называемая, открытая экспонента.
Теперь пара чисел {e, n} — это мой открытый ключ. Я отправляю его вам, чтобы вы зашифровали своё сообщение. Но для меня это ещё не всё. Я должен получить закрытый ключ.
Мне нужно вычислить число d, обратное е по модулю φ. То есть остаток от деления по модулю φ произведения d×e должен быть равен 1. Запишем это в обозначениях, принятых во многих языках программирования: (d×е)%φ=1. Или (d×5)%12=1. d может быть равно 5 ((5×5)%12=25%12=1), но чтобы оно не путалось с e в дальнейшем повествовании, давайте возьмём его равным 17. Можете проверить сами, что (17×5)%12 действительно равно 1 (17×5-12×7=1). Итак d=17. Пара {d, n} — это секретный ключ, его я оставляю у себя. Его нельзя сообщать никому. Только обладатель секретного ключа может расшифровать то, что было зашифровано открытым ключом.
