RSA

Постановка задачи:

Алиса и Боб отправляют друг другу сообщения (последовательности из 0 и 1), но есть Ева, которая подсматривает сообщения Алисы и Боба. Алиса и Боб хотят так договориться о способе передачи сообщений (причём считаем, что Ева знает договорённость Алисы и Боба), что Ева не сможет по отправляемым сообщениям понять, что изначально отправлялось, а Алиса и Боб - смогут.

Пару слов вокруг задачи:

Если у Алисы и Боба есть возможность "приватно" друг другу сообщить какую-нибудь информацию, то задача становиться достаточно простой. К примеру, можем договориться, что есть некоторая биекция, которая каждому числу от 0 до 15 будет сопоставлять какое-то число от 0 до 15, и согласно этой биекции заменять блоки из 4 символов. А сама биекция будет передана "тайно". Тогда Ева не сможет понять, какие последовательности из 0 и 1 на самом деле имеются ввиду (разве что если нет каких-то закономерностей в отправляемых данных, например конец сообщения должен обозначаться блоком из 0000. Тогда у Евы есть шансы разгадать биекцию, которая используется при шифровании).

А что есть у Алисы и Боба нет возможности передать информацию приватно? К примеру, если Вы хотите передать данные сайту Информатикс, Вы же не будете лично подходить к офису Информатикса и передавать конверт, на которой записана Ваша таинственная биекция. Но связаться с сайтом Вам нужно, причём так, чтобы никто не украл Ваши личные данные.

Для этого были придуманы способы шифрования с открытым ключом. 
Идея: пусть Боб сообщит Алисе способ зашифровать сообщение (открытый ключ), но способ шифрования будет такой, что по открытому ключу достаточно тяжело расшифровать сообщение обратно, если только не знать закрытый ключ. Стоит оговориться, что под "достаточно тяжело" имеется ввиду практическая сложность в проведении дешифровки. Пример операции, которая легко производится в одну сторону и очень тяжело - в другую, это возведение в степень по модулю. 175 по модулю 53 посчитать очень просто, а вот понять, какое число нужно возвести в 5тую степень, чтобы получить 38, тяжело.

Теорема из ТЧ:
Теорема 1. Пусть N = p * q, где p и q простые. Тогда для любого x верно, что x(p-1)(q-1)+1 ≡ x1. (На самом деле это частный случай обобщённой Малой Теоремы Ферма)
Конкретно этот частный случай можно доказывать применением Малой Теоремы Ферма по модулям p и q, и Китайской Теоремы об Остатках. На самом деле отсюда же следует, что  x(p-1)(q-1)*k+1 ≡ x1.

Алгоритм шифрования RSA:
Пусть Боб выберет 2 случайных простых числа p и q, и какое-нибудь число e, взаимнопростое с (p-1)(q-1). Их произведение равно N. Тогда открытый ключ: пара чисел (e, N). Алиса должна будет свое число M возвести в e-тую степень по модулю N, чтобы получить зашифрованное сообщение С. (Получаем Me≡С). Для того, чтобы Бобу расшифровать сообщение, ему нужно найти такое d, что e*d≡1 по модулю (p-1)(q-1). (Найти такое d можно с помощью алгоритма Эвклида, найдя такие u, v: e*u + (p-1)(q-1)*v = 1. Тогда u будет тем самым d, которое Боб пытается найти.) Тогда для дешифровки ему нужно возвести С в степень d.
Тогда он получит Сd≡Me*d≡M(p-1)(q-1)*k+1≡M.

Задание: реализовать RSA.

Напоминание: не забудьте про быстрое возведение в степень, т.к. e должно быть достаточно большим, чтобы нельзя было декодировать без закрытого ключа (к примеру 65537).