Жуан Гомес - Мир математики. т.2. Математики, шпионы и хакеры. Кодирование и криптография

* * *

АВТОРЫ АЛГОРИТМА

Уитфилд Диффиродился в 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 (mod 11).

2. Питер выбирает число, N p1например, 6, и подставляет в функцию f(6) = 7 6 4 (mod 11).

3. Джеймс посылает Питеру свой результат, 2, а Питер Джеймсу — свой, 4.

4. Джеймс считает 4 3 9 (mod 11).

5. Питер считает 2 6 9 (mod 11).

Это число, 9, и будет ключом системы.

Джеймс и Питер обменялись функцией f(х)и числами 2 и 4. Будет ли эта информация полезна злоумышленнику? Допустим, злоумышленник знает и функцию, и числа. Тогда он должен найти N j1и N p1по модулю 11, где N j1 и N p1— такие числа, которые и Джеймс, и Питер держат в секрете даже друг от друга. Если шпиону удастся узнать эти числа, он получит ключ, лишь вычислив a Nj1∙Np1 по модулю р. Решение уравнения вида у = а х, кстати, в математике называется дискретным логарифмом.

Например, в случае:

f(х) = 3 х(mod 17),

зная, что 3 х= 15 (mod 17), и пробуя различные значения х, мы получим, что х= 6.

Алгоритмы этого типа и задачи с дискретным логарифмом не получали должного внимания вплоть до начала 1990 гг., и лишь в последнее время эти методы начали разрабатываться. В приведенном выше примере число 6 является дискретным логарифмом числа 15 с основанием 3 по модулю 17.

Особенностью этого типа уравнений, как мы уже говорили, является сложность обратного процесса — они асимметричны . Если рбольше 300, а число абольше 100, решение — и, следовательно, взлом ключа — становится крайне сложной задачей.

* * *

ВИРУСЫ И БЭКДОРЫ

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

* * *

Этот алгоритм является основой современной криптографии. Диффи и Хеллман представили свою идею на Национальной компьютерной конференции, на семинаре, который можно назвать поворотным. В полном объеме их работу можно почитать на www.cs.berkeley.edu/~christos/classics/diffiehellman.pdf, статья с названием «Новые направления в криптографии».

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

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

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

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

Простые числа спешат на помощь: алгоритм шифрования RSA

В августе 1977 г. знаменитый американский писатель и популяризатор науки Мартин Гарднер озаглавил свою колонку по занимательной математике в журнале Scientific American так: «Новый вид шифра, на расшифровку которого потребуются миллионы лет». После объяснения принципа системы шифрования с открытым ключом он показал само зашифрованное сообщение и открытый ключ N, используемый в этом шифре:

Гарднер призвал читателей попробовать расшифровать сообщение, используя предоставленную информацию, и даже дал подсказку: для решения необходимо разложить число Nна простые множители ри q. Более того, Гарднер назначил приз в размере $100 (приличная сумма на тот момент) тому, кто первым получит правильный ответ. Каждый, кто захочет побольше узнать о шифре, писал Гарднер, может обратиться к создателям шифра — Рону Ривесту, Ади Шамиру и Лену Адлеману из Лаборатории информации Массачусетского технологического института.