§ Предисловие

Это алгоритм для шифрования сообщений. Он сложный, трудоемкий и напрямую не используется из-за своей очень невысокой скорости работы. А скорость работы у него невероятно медленная по той причине, что такой алгоритм оперирует гигантскими числами.

§ Открытый и закрытый ключи

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

• Алиса спрашивает у Боба открытый ключ, он ей говорит его по телефону. Ключ становится известен всем, в том числе не только Алисе, но и еще тому, кто сидит и слушает их
• Алиса берет это число (открытый ключ), производит определенные действия над тем числом, что хочет закодировать и отсылает Бобу. Человек посередине эту информацию тоже перехватил.
• Боб же берет закрытый ключ, который он создал вместе с открытым и производя математические действия, расшифровывает число Алисы
• Человек посередине не знает закрытого ключа Боба, а по открытому ключу он не может ничего сделать, потому что расшифровать сообщение можно только с помощью закрытого. Человек с досады кусает свои локти.

Вкратце:

• Боб создает открытый и закрытый ключи (они взаимосвязаны, как Том и Джерри)
• Алиса получает открытый ключ Боба
• Кодирует с его помощью свое число
• Отсылает число по небезопасному каналу связи
• Боб расшифровывает число с помощью закрытого ключа

Более абстрактно:

• Создать открытый и закрытый ключи
• Передать открытый ключ тому, кто будет шифровать
• Зашифровать сообщение с помощью открытого ключа
• Передать зашифрованное сообщение по каналу связи
• Расшифровать сообщение с помощью закрытого ключа

§ Открытый ключ

Задача создать открытый и закрытый ключи - очень сложна, если речь заходит о колоссальных цифрах. Сложность именно в том, как их быстро вычислить. Дело в том, что если взять два гигантских простых числа, и умножить, обратно потом найти эти простые числа уже весьма проблематично. Алгоритм RSA устройчив к взлому исключительно потому, что:

Невозможно быстро и эффективно разложить на множители огромные числа

Вот так вот. Если бы это было реально, то алгоритм RSA утратил бы свою криптостойкость и пришлось бы искать еще какой-нибудь метод. Сейчас рулят эллиптические кривые, но я без понятия как они работают, поэтому расскажу только про RSA.
Шаг 1. Взять два простых числа p и q
Кстати говоря, это далеко не так просто, как кажется. Если речь идет о небольших простых числах, не превышающих к примеру миллиарда, то их нахождение для взломщика не составляет вообще никакого труда. На любом процессоре разложить подобные числа можно за несколько миллисекунд. Однако, как только речь заходит о числах порядка аж 800-1000 десятичных знаков, то тогда никакой сверхмощной видеокарты, да и вообще вычислительной мощности всей планеты не хватит, чтобы даже за 1 год взломать такой код. Единственный, кто может справиться с этой задачей - это алгоритм Шора для квантовых компьютеров, которые сейчас находятся пока что в довольно неразвитой стадии на 2020 год.
Да, простые то числа взять можно, только вот надо чтобы они реально простые были, потому что составные числа работать не будут в RSA вообще. Они будут просто ломать всё. Это значит, что надо бы еще найти простые числа, а это сложная задача. Существуют разные тесты простоты, но в этой статье я их рассматривать не буду.
Получив простые числа p, q, надо их перемножить:
И получим n, который будет играть важную роль дальше.
Шаг 2. Вычислить открытую экспоненту e
Перед тем, как вычислить открытую экспоненту, надо рассчитать функцию Эйлера, которая считается для двух простых чисел невероятно простым способом:
То есть нужно лишь просто вычесть из p и q по единице и умножить их. Для чего это все? Здесь есть строгое математическое доказательство, приводить которое я тут не буду, потому что сложно и много. Просто надо поверить на слово. А если хочется проверить, то надо смотреть специальную литературу.
Теперь самый ответственный момент. Надо взять наобум число такое, которое бы попало в следующий диапазон:
И при этом его наибольший общий делитель (НОД) был равен 1, или, другими словами, чтобы ни одно целое число, кроме 1, не смогло поделить и , то есть, чтобы у этих двух чисел не было наибольшего общего делителя, больше чем 1.
Примеры:

• Числа 5 и 15 имеют НОД(5,15) = 5 — число 15 делится на 5, и 5 делится на 5 без остатка
• НОД(7, 14) = 7 — число 7 делится на 7, и 14 делится на 7 тоже
• НОД(12, 15) = 3 — число 12 делится на 3, число 15 делится на 3
• НОД(9, 11) = 1 — вот это в самый раз, ни одно число не делится, кроме как на 1

Шаг 3. Открытый ключ
Теперь появились все данные, чтобы найти открытый ключ, который представлен как пара {e, n}. Теперь перейду к практической части вычисления открытого ключа.

• Берется (для примера) p=47, q=31, оба числа простые
• Получается n = pq = 47*31 = 1457 — это число часть как открытого, так и закрытого ключа
• Вычисляем = (47-1)(31-1) = 1380
• Теперь, надо взять такое , чтобы НОД(, ) = 1, берем число e=257 (для примера), проверятся НОД(257, 1380) = 1, все верно

Открытый ключ {e, n} равен {257, 1457}.

§ Закрытый ключ

Теперь задача в том, чтобы сформировать закрытый ключ на числах p, q. Как я и говорил ранее, закрытый ключ нужен, чтобы расшифровать то сообщение, которое было зашифровано с помощью открытого ключа. Закрытый ключ базируется на тех же самых p,q, и потому у него будет точно та же компонента n, что и у открытого ключа. Закрытый же ключ будет представлен как пара {d, n}, где d - закрытая компонента, n = pq.
Существует формула для поиска закрытого ключа:
Но, ее понять сложно без подготовки. Лучше ее переписать в следующем виде:
И что это значит? Это значит, что надо найти такое, что при умножении на и потом после деления на получился остаток 1.
Вот возьмем простой пример, допустим = 7, = 60:
Теперь надо подобрать такое d, при котором остаток от деления на 60 был бы 1. Пробуем:

• d = 1 — 7*1 mod 60 = 7, не подходит
• d = 9 — 7*9 mod 60 = 63 mod 60 = 3, не подходит
• d = 23 — 23*7 mod 60 = 161 mod 60 = 41, не подходит
• d = 43 — 43*7 mod 60 = 301 mod 60 = 1, подошло

Получается, что для числа = 7 число = 43. Таким образом, мы смогли найти закрытый ключ {43, 77}, при этом открытый ключ был {7, 77}.
Поиск закрытого ключа происходит с помощью расширенного алгоритма Евклида, объяснение которого здесь тоже не приводится.

§ Пример шифрования и дешифрования

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

• Возьмем p=11, q=23, n = pq = 253
• Число Эйлера
• Выберем открытую экспоненту = 17, ибо НОД(17, 220) = 1

Итак, открытый ключ будет равен {17, 253}. Теперь надо найти закрытый ключ, используя вот это уравнение:
Пока что находим перебором, но можно искать с помощью расширенного алгоритма НОД. Но в данном случае просто перебором, про НОД позже расскажу.
Путем подбора (я просто программой перебрал числа d=1..253), оказалось равным 134. Проверим, 134*17 mod 253 = 1, все подошло. Закрытый ключ равен {134, 253}.
Теперь надо попробовать что-нибудь зашифровать и расшифровать. Поскольку число n у нас 253, то зашифровать можно сообщение только от 0 до 252 включительно, ибо если попытаться использовать 253, то такое сообщение просто превратится в 0 при расшифровке. Это не проблема, но надо учитывать, что шифровать число более чем n нельзя.
Выбираем a=110, теперь шифруем с помощью открытого ключа.
У нас получился b=77. Даже зная n=253, нельзя получить обратно 110, потому что нужен для этого закрытый ключ. Однако, если разложить 253 на простые множители p, q, то тогда можно найти и закрытый ключ d. Однако, при большом значении n это сделать невозможно. Расшифровка с помощью закрытого ключа делается так:
Что и требовалось сделать. Все работает корректно. Процедура для быстрого возведения в степень приведена в этой статье.

§ Нахождение закрытого ключа с помощью расширенного НОД

Существуют способы, при которых можно найти d, зная e, не используя при этом перебор, и этот способ - расширенный алгоритм Евклида, о котором я уже писал ранее в другой статье. То есть как находить коэффициенты к расширенному алгоритму, об этом здесь я говорить не стану, а только опишу самую суть того, почему надо использовать именно этот НОД.
Поскольку числа и взаимно простые, но их НОД будет равен 1:
НОД(, ) = = 1
Здесь значения x, y получаются из решения расширенного алгоритма НОД. Теперь применим модуль к левой и правой части:
Поскольку любой модуль от 1 будет 1, а модуль самого от себя, будет равняться 0, то уравнение сокращается:
Тут сразу же видно, что x - это как раз тот самый искомый d. В общем-то и всё.

§ Программный код

Получение значений расширенного НОД:

1int NOD(int a, int b, int & x, int & y) {
2
3    int x1, y1, d;
4    if (a == 0) { x = 0; y = 1; return b; }
5    d = NOD(b % a, a, x1, y1);
6    x = y1 - (int)(b / a) * x1;
7    y = x1;
8    return d;
9}

Быстрое возведение в степень:

1unsigned long fpow(unsigned long a, unsigned long b, unsigned long m) {
2
3    int id;
4    unsigned long r = 1;
5    for (id = 31; id >= 0; id--) {
6        if (b & (1 << id)) r = (r * a) % m;
7        if (id) r = (r * r) % m;
8    }
9    return r;
10}