Конечно, мы взламывать ничего не будем, но объясним принцип шифровки RSA (эту хуйню юзают многие банки для транзакций и всякие там гуглы и амазоны для конфиденциальности), как она работает с математической точки зрения и придумаем свой мини-RSA код.

Все мы с вами знаем, что любое число можно разложить на простые числа (которые делятся только на себя и на 1), но также есть числа, которые можно разложить только на 2 простых числа, если не считать умножение самого числа и единицы (например, число 15 = 3 * 5, 3 и 5 – простые числа).

Возьмём, к примеру, RSA Google, который имеет неебически огромный 2048-битовый двоичный код, который, если перевести его в десятичную систему, то получим 617-ти значное число (его очень легко найти в интернете). Так вот, это число – это произведение 2-х простых чисел (для 2048-битного числа могут быть взяты как и 2 1024-битных числа, так и другие соотношения). Это число называется модулем.

Также есть и другие названия, которые нам нахуй не нужны, а лучше рассмотрим, как это работает: мы отправляем число m, которое преобразовали таким образом:
• m^a mod n = c,
А получатель смог декодировать сообщение таким образом:
• с^b mod n = m.
Из этого можно вывести:
• m^(ab) mod n = m.

Теперь я буду объяснять и одновременно создавать с вами RSA-ключ. Для начала нам нужно придумать модуль (n) – число, состоящее из произведения 2-х простых чисел (p*q):
• 15 = 3 * 5.
Дальше нам нужно найти функцию Эйлера:
• ψ(n) = (p-1) * (q-1).
Для нашего числа она выглядит так:
• ψ(15) = (3 - 1) * (5 - 1) = 8.
Теперь мы воспользуемся теоремой Эйлера:
• m^ψ(n) mod n = 1, где m – взаимно простое число с n (у m и n нету общих делителей).
Запишем для наглядности для нашего числа:
• 7^8 mod 15 = 1,
Теперь умножим левую и правую части на 7 и получим:
• 7^9 mod 15 = 7,
Или же
• m^(ψ(n)+1) mod n = m.

Теперь вспомним про загадочные a и b. Из 4 абзаца мы вывели формулу:
• m^(ab) mod n = m, в из предыдущего абзаца мы тоже вывели формулу для m, значит, их можно прировнять:
• m^(ab) mod n = m^(ψ(n)+1) mod n, сократим на mod n:
• m^(ab) = m^(ψ(n)+1),
Но что делать с a и b не стало понятнее.

Мы упрощаем это до вида:
• ab = ψ(n) + 1 (тупо убираем основания),
Дальше придумываем эти 2 числа. Для наших чисел это будет выглядеть так:
• ab = 8 + 1 = 9 = 3 * 3.
В итоге у нас получается произведение 2-х простых чисел (по счастливой случайности это 3 и 3, но на деле они различны и неебически большие). Одно из этих чисел называется шифрованием, а второе расшифровкой.

После этого в свободный доступ выкладывается модуль (n) и шифрование (a), чтобы вы могли отправить ваше сообщение на дешифровку банку, который воспользуется расшифровкой (b), чтобы получить ваше сообщение.

Кароче говоря, одно число шифрует сообщение, а второе расшифровывает, где второе число просто убирает действие первого, а эти числа находятся через функцию Эйлера от придуманного нами числа.



Спасибо за то, что вы с нами.
С любовью, Рителлинг favorite