В настоящее время особенно популярны так называемые схемы шифрования с открытым ключом. Мы расскажем о схеме Диффи – Хеллмана, которая датируется 1970-ми годами и активно используется на практике. Эта схема основана на глубокой математике, но саму идею понять совсем несложно.

Возьмем простое число р. В реальности оно должно быть огромным, но для примера выберем маленькое простое число 19. Теперь выберем еще одно число g, тоже целое, но необязательно простое и меньше р. Например, g = 2.

Числа р и g знают все: и Алиса, и Боб, и даже Ева. Теперь Алиса выбирает число х, например x = 6, и хранит его в тайне. Боб выбирает число у, скажем y = 8, и тоже никому его не сообщает.

Дальше начинается шифрование. Алиса находит остаток от деления на р числа g^х:

Боб делает то же самое со своим задуманным числом:

Итак, наше преобразование выглядит следующим образом: возвести 2 в степень х и взять остаток от деления на 19. Мы изобразили это преобразование в общем виде на рис. 6.3. Напомним, что числа g и р известны, а число х выбрала Алиса.

Рис. 6.3. Преобразование по схеме Диффи – Хеллмана x → f (x). Числа g и р известны, а число х выбрала Алиса

Здесь принципиально важно, что р простое число, а g меньше р, потому что в этом случае g^х на р не делится, то есть остаток от деления не может быть нулем. Есть и более глубокие причины, почему р должно быть простым. Кроме того, для заданного р есть набор «подходящих» g.

Получив остаток от Боба, Алиса возводит его в степень х и снова берет остаток от деления на р. В нашем маленьком примере Алиса получила от Боба число 9, а Боб от Алисы число 7. Тогда у Алисы получается:

Боб действует аналогично. Он получил остаток от Алисы, и у него есть известный ему одному у (даже Алиса его не знает!). Он возводит полученный от Алисы остаток в степень у и снова берет остаток от деления на р:

Это то же самое число 11, что и у Алисы!

Естественно, это неслучайно. Математически нетрудно показать, что Алиса и Боб получат одинаковое число при любых р, g, x, и у.