Краткий экскурс в криптографию

Посмотрим, как диофантовы уравнения используются в системе шифрования с открытым ключом. Напомним, что для данного натурального числа n группа целых чисел со сложением по модулю n состоит из элементов [0], [1], [2]...[n — 1], а сложение выполняется следующим образом: сначала мы складываем элементы группы как обычные числа, затем вычитаем n из полученного результата до тех пор, пока не получим число, заключенное на интервале от 0 до n — 1. Аналогично можно определить операцию умножения. Допустим, n = 7 и нам нужно вычислить произведение 4*5. Сначала умножим эти два числа так же, как и целые числа. Получим 20.

Теперь нужно вычесть из этого результата 7 нужное число раз: после первого вычитания получим 13, после второго — 6, что меньше 7. Следовательно, произведение 4 и 5 по модулю 7 равно 6.

Теперь перейдем к криптографии.

Допустим, что Боб хочет отправить Алисе секретное сообщение. Так как любую информацию можно представить с помощью чисел, достаточно решить задачу о защищенной передаче числа m. Боб знает открытый ключ Алисы (он доступен всем).

У Алисы также есть закрытый ключ, известный только ей. Следует различать три этапа передачи сообщения: генерация ключей, шифрование сообщения и расшифровка.

Сначала покажем, как генерируются ключи. Выберем два простых числа р и q.

В принципе, достаточно, чтобы произведение р и q (обозначим его через n), было больше числа m, которое нужно передать. Но наш метод шифрования будет обеспечивать достаточный уровень защиты только тогда, когда р и q будут достаточно большими и никакой компьютер не будет способен разложить n на простые множители за разумное время. Выберем два простых числа р и р, состоящие из 300—400 знаков.

Введем величину r = (р — 1)(q — 1) и выберем число е, меньшее r и взаимно простое с ним. Пара (n, е) будет открытым ключом. Чтобы сгенерировать закрытый ключ, нужно решить диофантово уравнение ex + ry = 1. Если мы обозначим через d первое число из пары, которая является решением этого уравнения, то закрытый ключ будет представлять собой пару (n, d).

Теперь, когда открытый и закрытый ключ известны, нужно действовать следующим образом: Боб шифрует сообщение, возведя m в степень е, находит результат возведения в степень по модулю n и отправляет Алисе полученное значение с =m^e (по модулю n).

Для расшифровки сообщения Алиса возводит с в степень d, определяемую закрытым ключом, и находит результат по модулю n. Этой простой операции достаточно для восстановления зашифрованной информации, так как можно доказать, что c^d по модулю n всегда равно m.