Я упоминала исключительно сложную задачу разложения числа на простые множители. Основная теорема арифметики утверждает, что такое разложение единственно, с точностью до перестановки множителей. То есть какое бы число не взяли для него точно найдется простой делитель. В некоторых случаях этим делителем будет само число. Тогда оно простое.
Но знать, что у задачи есть решение, не значит решить. Попробуйте, например, разложить на простые множители следующие числа: 6, 42, 161, 1643, 567 109.
Это задача для шестого класса. Разложение первых двух чисел сразу приходит на ум.
6 = 2 · 3;
42 = 2 · 3 · 7.
Со следующими скорее всего возникнут трудности:
161 = 7 · 23;
1643 = 31 · 53.
А оставшееся заставит попотеть:
567 109 = 701 · 809.
Даже с использованием калькулятора разложение последнего числа занимает много времени. Конечно, компьютер может это сделать за секунды. Но даже его возможности ограничены.
Первое упоминание алгоритма RSA
В 1977 году Мартин Гарднер в колонке «Математические игры» опубликовал задачу. Он предложил читателям расшифровать послание. Кроме самого текста в статье упоминался алгоритм шифрования и давался открытый ключ N. Число содержащее 129 знаков. Вторая часть ключа число e = 9007. За решение задачи обещали вознаграждение в размере ста долларов.
Создатель алгоритма шифрования утверждал, что это невозможно сделать и за 40 квадриллионов лет. Но не учел развитие технологий и жажду человека разгадать тайну. В 1993 году с использованием распределенных вычислений головоломку решили. Было задействовано 1600 вычислительных машин, в том числе три факса.
Идея алгоритма RSA
В обычных системах шифрования используется ключ, который знают получатель и отправитель. Это не удобно, если отправителю необходимо общаться с большим количеством агентов. Для каждого из них придётся хранить свой ключ.
В 1976 году Уитфилд Диффи и Мартин Хеллман опубликовали концепцию асиметричного шифрования с открытым и закрытым ключом. Первый направляется получателю сообщения, второй хранится только у отправителя.
Спустя год Рон Ривест, Ади Шамир и Леонард Адлеман придумали, как осуществить такую систему. Алгоритм получил имя по первым буквам их фамилий RSA.
Как работает алгоритм RSA
Рассмотрим на примере, как шифруются данные.
Для начала нужно выбрать два простых числа и найти их произведение. В настоящих системах используются очень большие числа. Например, так выглядит открытый ключ Дзена:
Для примера возьмем числа поменьше.
- Пусть, N = 11 · 13 = 143.
- Вычислим функцию Эйлера для полученного числа.
φ(143) = (11 — 1)(13 — 1) =120. - Выберем любое число взаимно простое с 120. Например, e = 7. Это открытая экспонента.
- Найдем число d, такое чтобы выполнялось равенство: d · 7 ≡1 (mod 120). Немного решения сравнения первой степени и получим d = 103.
- Получаем N = 143 (открытый ключ), е = 7 (открытая экспонента), d = 103 (закрытый ключ).
Открытый ключ и значение экспоненты передаём получателю. С их помощью шифруются сообщения.
Зашифруем слово «Дзен». Представим каждую букву в виде числа. Д — 5, З — 9, E – 6, Н — 15.
Можно шифровать числа не превосходящие N – 1. В нашем случае 142. Поэтому разобьем текст следующим образом и зашифруем каждое число:
Дз — 59: 59^7 mod(143) = 71
е — 6: 6^7 mod(143) = 85
н — 15: 15^7 mod(143) = 115
Возводим числа в степень равную открытой экспоненте и находим остаток от деления на значение ключа.
Зашифрованное сообщение: 7185115
Чтобы его расшифровать, потребуется закрытый ключ:
71: 71^103 mod (143) = 59
85: 85^103 mod (143) = 6
115: 115^103 mod (143) = 15
Очень похожая операция, но теперь возводим число в степень равную закрытому ключу. Дальше находится остаток от деления на N.
Этот алгоритм используется в огромном количестве сетевых протоколов. И при этом дети изучают эту тему в шестом классе. Кроме решения сравнения. Но эту задачу можно переформулировать и тогда не останется ничего выходящего за пределы школьной математики.