Генерация ключа. 
Криптографические методы защиты информации

Первым этапом любого асимметричного алгоритма является создание пары ключей: открытого и закрытого и распространение открытого ключа «по всему миру». Для алгоритма RSA этап создания ключей состоит из следующих операций :

Выбираются два простых (!) числа p и q.

Вычисляется их произведение n (=p*q).

Выбирается произвольное число e (e.

Методом Евклида решается в целых числах (!) уравнение e*d+(p-1)(q-1)*y=1. Здесь неизвестными являются переменные d и y — метод Евклида как раз и находит множество пар (d, y), каждая из которых является решением уравнения в целых числах. Два числа (e, n) — публикуются как открытый ключ.

Число d хранится в строжайшем секрете — это и есть закрытый ключ, который позволит читать все послания, зашифрованные с помощью пары чисел (e, n).

Шифрование/расшифровывание

Отправитель разбивает свое сообщение на блоки, равные k=[log2(n)] бит, где квадратные скобки обозначают взятие целой части от дробного числа.

Подобный блок, как Вы знаете, может быть интерпретирован как число из диапазона (0;2k-1). Для каждого такого числа (mi) вычисляется выражение ci=((mi)e)mod n. Блоки ci и есть зашифрованное сообщение, и их можно спокойно передавать по открытому каналу, поскольку операция возведения в степень по модулю простого числа, является необратимой математической задачей. Обратная ей задача носит название «логарифмирование в конечном поле» и является на несколько порядков более сложной задачей. То есть даже если злоумышленник знает числа e и n, то по ci прочесть исходные сообщения mi он не может никак, кроме как полным перебором mi.

А вот на приемной стороне процесс дешифрования все же возможен, и поможет нам в этом хранимое в секрете число d. Достаточно давно была доказана теорема Эйлера, частный случай которой утверждает, что если число n представимо в виде двух простых чисел p и q, то для любого x имеет место равенство (x (p-1)(q-1))mod n = 1. Для дешифрования RSA-сообщений воспользуемся этой формулой.

Возведем обе ее части в степень.

(-y): (x (-y)(p-1)(q-1))mod n = 1(-y) = 1.

Теперь умножим обе ее части на x:

(x (-y)(p-1)(q-1)+1)mod n = 1*x = x.

А теперь вспомним как создавались открытый и закрытый ключи. с помощью алгоритма Евклида подбиралось такое d, что e*d+(p-1)(q-1)*y=1, то есть e*d=(-y)(p-1)(q-1)+1. А следовательно в последнем выражении предыдущего абзаца можем заменить показатель степени на число (e*d). Получаем (xe*d)mod n = x. То есть для того чтобы прочесть сообщение ci=((mi)e)mod n достаточно возвести его в степень d по модулю m:

((ci)d)mod n = ((mi)e*d)mod n = mi.

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