* * *
АВТОРЫ АЛГОРИТМА
Уитфилд Диффи родился в 1944 г. в Соединенных Штатах. Получив степень бакалавра математики в Массачусетском технологическом институте (МП), он с 2002 по 2009 гг. работал главой службы безопасности и вице-президентом компании Sun Microsystems (в Калифорнии).
Инженер Мартин Хеллман родился в 1945 г. и работал в IBM и Массачусетском технологическом институте, где сотрудничал с Диффи.
Уитфилд Диффи
* * *
1. Джеймс выбирает число, которое он держит в секрете. Мы обозначим это число Nj1
2. Питер выбирает другое случайное число, которое он тоже держит в секрете. Мы обозначим это число Np1
3. Затем и Джеймс, и Питер применяют к своим числам функцию вида f(x) = ах (mod р) где р — простое число, известное им обоим.
∙ После этой операции Джеймс получает новое число, Nj2, которое он посылает Питеру.
∙ А Питер посылает Джеймсу свое новое число Np2
4. Джеймс вычисляет NNj1p2 (mod р) и получает новое число Сj.
5. Питер вычисляет NNp1j2 (mod р) и получает новое число Ср.
Хотя это кажется невозможным, но числа Сj и Ср являются одинаковыми. И теперь у нас есть ключ. Заметим, что Джеймс и Питер обменивались информацией только тогда, когда они выбрали функцию f(x) = ах (mod р) и послали друг другу числа Nj2 и Np2. Ни то, ни другое не является ключом, поэтому перехват этой информации не будет угрожать безопасности системы шифрования. Ключ этой системы имеет следующий вид:
aNj1∙Np1 (mod p).
Важно также учесть, что данная функция имеет одну особенность: она необратима, то есть зная саму функцию и результат ее применения к переменной х, невозможно (или, по крайней мере, очень сложно) найти исходное значение х.
Далее, чтобы пояснить идею, мы повторим процесс с конкретными значениями.
Возьмем следующую функцию:
f(x) = 7х (mod 11).
1. Джеймс выбирает число, NJ1 например, 3, и подставляет в функцию f(3) = 73 
2 (mod 11).
2. Питер выбирает число, Np1 например, 6, и подставляет в функцию f(6) = 76 4 (mod 11).
3. Джеймс посылает Питеру свой результат, 2, а Питер Джеймсу — свой, 4.
4. Джеймс считает 43 9 (mod 11).
5. Питер считает 26 9 (mod 11).
Это число, 9, и будет ключом системы.
Джеймс и Питер обменялись функцией f(х) и числами 2 и 4. Будет ли эта информация полезна злоумышленнику? Допустим, злоумышленник знает и функцию, и числа. Тогда он должен найти Nj1 и Np1 по модулю 11, где Nj1 и Np1 — такие числа, которые и Джеймс, и Питер держат в секрете даже друг от друга. Если шпиону удастся узнать эти числа, он получит ключ, лишь вычислив aNj1∙Np1 по модулю р. Решение уравнения вида у = ах, кстати, в математике называется дискретным логарифмом.
Например, в случае:
f(х) = 3х (mod 17),
зная, что 3х = 15 (mod 17), и пробуя различные значения х, мы получим, что х = 6.
Алгоритмы этого типа и задачи с дискретным логарифмом не получали должного внимания вплоть до начала 1990 гг., и лишь в последнее время эти методы начали разрабатываться. В приведенном выше примере число 6 является дискретным логарифмом числа 15 с основанием 3 по модулю 17.
Особенностью этого типа уравнений, как мы уже говорили, является сложность обратного процесса — они асимметричны. Если р больше 300, а число а больше 100, решение — и, следовательно, взлом ключа — становится крайне сложной задачей.
* * *
ВИРУСЫ И БЭКДОРЫ