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

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

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

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

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

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

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

Правильный ответ был получен лишь через 17 лет. Он стал результатом сотрудничества более чем 600 человек. Ключами оказались р = 32769132993266 709549961988190834461413177642967992942539798288533 и q = 3490529510847650949147849619903898133417764638493387843990820577, а зашифрованная фраза звучала так: «Волшебные слова — это брезгливый ягнятник».

Алгоритм, представленный Гарднером, известен как RSA — буквенная аббревиатура от фамилий Rivest (Ривест), Shamir (Шамир) и Adleman (Адлеман). Это первое практическое применение придуманной Диффи системы шифрования с открытым ключом, которая повсеместно используется и по сей день. Надежность ее практически гарантирована, потому что процесс расшифровки является невероятно сложным, почти невозможным делом. Далее мы рассмотрим основы этой системы в упрощенной форме.

Подробнее об алгоритме RSA

Алгоритм RSA основан на некоторых свойствах простых чисел, о которых заинтересованный читатель может подробнее прочитать в Приложении. Мы ограничимся здесь изложением простых фактов, лежащих в основе алгоритма.

• Количество натуральных чисел, меньших n и взаимно простых с n, называется функцией Эйлера и обозначается как ф(n).

• Если n = p∙q, где р и q — простые числа, то ф(n) = (р — 1)(q — 1).

• Из малой теоремы Ферма мы знаем, что если а — целое число, большее нуля, и р — простое число, то а^р-1

 1 (mod р).

• Согласно теореме Эйлера, если НОД (n, а) = 1, то а^ф(n)

 1 (mod n).

Как уже упоминалось, система шифрования называется «с открытым ключом», потому что ключ шифрования доступен любому отправителю, желающему передавать сообщения. Каждый получатель имеет свой открытый ключ. Сообщения всегда передаются в виде цифр, будь то ASCII-коды или какая-либо другая система.

Сначала Джеймс вычисляет значение n путем умножения двух простых чисел р и q (n = pq) и выбирает значение е так, чтобы НОД (ф(n), е) = 1. Напомним, что ф(n) = (р — 1)(q — 1). Данные, которые являются открытыми, — это значение n и значение е (ни при каких обстоятельствах нельзя выдавать значения р и q). Пара (n, е) является открытым ключом системы, а значения р и q называются RSА-числами. Затем Джеймс вычисляет единственное значение d по модулю ф(n), которое удовлетворяет условию d∙е = 1, то естьd является обратным элементом к числу е по модулю ф(n). Мы знаем, что обратный элемент существует, потому что НОД (ф(n), е) = 1. Это число d является закрытым ключом системы. Со своей стороны, Питер использует открытый ключ (n, е) для шифрования сообщения М с помощью функции М = m^e (mod n). Получив сообщение, Джеймс вычисляет M^d = (m^e)^d (mod n), а это выражение эквивалентно M^d = (m^e)^d = m (mod n), что свидетельствует о возможности расшифровать сообщение.

Теперь мы применим эту процедуру к конкретным числовым значениям.

Если р = 3 и q = 11, получим n = 33. Тогда ф(33) = (3–1)∙(11—1) = 20.

Джеймс выбирает е, не имеющее общего делителя с 20, например, е = 7. Открытый ключ Джеймса (33,7).

• Джеймс также вычислил закрытый ключ d, который является обратным элементом к числу 7 по модулю 20, а именно число d = 3, так как 7∙3 

1 (mod 20).

• Питер, имея открытый ключ, хочет отправить нам сообщение «9». Чтобы зашифровать это сообщение, он использует открытый ключ Джеймса и вычисляет:

9⁷  = 4 782969 

15 (mod 33).

Зашифрованное сообщение имеет вид «15». Питер посылает его нам.

Джеймс получает сообщение «15» и расшифровывает его следующим образом:

15³  = 3375 

9 (mod 33).

Сообщение расшифровано правильно.

Если мы выбираем большие простые числа р, q, то вычисления в алгоритме RSA становятся такими сложными, что нам придется использовать компьютер. Например, если р = 23 и q = 17, то n = 391. Открытым ключом при выбранном е = 3 будет пара (391,3). Тогда d = 235. Для простого сообщения «34» операция расшифровки будет выглядеть так:

204²³⁵ 

34 (mod 391).

Обратите внимание на степень числа и представьте себе гигантское количество расчетов, необходимых для нахождения этого решения.

Почему мы можем доверять алгоритму RSA

Потенциальный шпион располагает значениями n и е, потому что они являются открытыми. Чтобы расшифровать сообщение, ему нужно также значение d, т. е. закрытый ключ. Как мы показали в предыдущем примере, значение d получается из n и е. Чем же обусловлена безопасность? Напомним, что для построениям/ необходимо знать ф(n) = (р — 1)(q — 1), в частности, р и q. Для этого «достаточно» разложить n на простые множители р и q. Проблема для шпиона заключается в том, что разложение большого числа на простые множители является медленным и трудоемким процессом. Если n достаточно большое (состоящее более чем из 100 цифр), не существует известных способов нахождения р и q за разумное количество времени. В настоящее время простые числа, используемые для шифрования чрезвычайно конфиденциальных сообщений, состоят более чем из 200 цифр.