Математики, шпионы и хакеры. Кодирование и криптография | страница 52
* * *
АВТОРЫ АЛГОРИТМА
Уитфилд Диффи родился в 1944 г. в Соединенных Штатах. Получив степень бакалавра математики в Массачусетском технологическом институте (МП), он с 2002 по 2009 гг. работал главой службы безопасности и вице-президентом компании Sun Microsystems (в Калифорнии).
Инженер Мартин Хеллман родился в 1945 г. и работал в IBM и Массачусетском технологическом институте, где сотрудничал с Диффи.
Уитфилд Диффи
* * *
1. Джеймс выбирает число, которое он держит в секрете. Мы обозначим это число N>j1
2. Питер выбирает другое случайное число, которое он тоже держит в секрете. Мы обозначим это число N>p1
3. Затем и Джеймс, и Питер применяют к своим числам функцию вида f(x) = а>х (mod р) где р — простое число, известное им обоим.
∙ После этой операции Джеймс получает новое число, N>j2, которое он посылает Питеру.
∙ А Питер посылает Джеймсу свое новое число N>p2
4. Джеймс вычисляет N>Nj1>p2 (mod р) и получает новое число С>j.
5. Питер вычисляет N>Np1>j2 (mod р) и получает новое число С>р.
Хотя это кажется невозможным, но числа С>jи С>р являются одинаковыми. И теперь у нас есть ключ. Заметим, что Джеймс и Питер обменивались информацией только тогда, когда они выбрали функцию f(x) = а>х (mod р) и послали друг другу числа N>j2и N>p2. Ни то, ни другое не является ключом, поэтому перехват этой информации не будет угрожать безопасности системы шифрования. Ключ этой системы имеет следующий вид:
a>Nj1∙Np1 (mod p).
Важно также учесть, что данная функция имеет одну особенность: она необратима, то есть зная саму функцию и результат ее применения к переменной х, невозможно (или, по крайней мере, очень сложно) найти исходное значение х.
Далее, чтобы пояснить идею, мы повторим процесс с конкретными значениями.
Возьмем следующую функцию:
f(x) = 7>х (mod 11).
1. Джеймс выбирает число, N>J1 например, 3, и подставляет в функцию f(3) = 7>3
2. Питер выбирает число, N>p1 например, 6, и подставляет в функцию f(6) = 7>6
3. Джеймс посылает Питеру свой результат, 2, а Питер Джеймсу — свой, 4.
4. Джеймс считает 4>3
5. Питер считает 2>6
Это число, 9, и будет ключом системы.
Джеймс и Питер обменялись функцией f(х) и числами 2 и 4. Будет ли эта информация полезна злоумышленнику? Допустим, злоумышленник знает и функцию, и числа. Тогда он должен найти N>j1 и N>p1 по модулю 11, где N>j1и N>p1 — такие числа, которые и Джеймс, и Питер держат в секрете даже друг от друга. Если шпиону удастся узнать эти числа, он получит ключ, лишь вычислив
