[Dindin]

Простыми числами называются числа, не имеющие делителей, кроме самих себя и единицы. А вот взаимно простыми числами называются числа, не имеющие общих делителей, кроме 1. Под большими и очень большими :-) числами будем понимать числа с разрядностью не менее 200 бит. Итак.

Определим открытый и секретный ключи.

1) Выберем два очень больших числа p и q.

2) Определим n как результат перемножения p и q (n=p*q)

3) Выберем большое случайное число, которое назовем d, причем это число должно быть взаимно простым с результатом умножения (p-1)*(q-1).

4) Отыщем такое число e, для которого верно соотношение (e*d) mod ((p-1)*(q-1)) = 1.

5) Открытым ключом является пара чисел e и n, секретным — пара чисел d и n.

Зашифровываем информацию по открытому ключу e, n. Разбиваем зашифровываемый текст на символы, каждый из которых может быть представлен в виде числа M(i)=0,1,..,n-1. Собственно зашифровываем данные (текст, письмо, дневник, файл), рассматриваемые как числовой ряд M(i), используя формулу C(i)= (M(i)^e) mod n.

Расшифровывание информации также достаточно просто реализуется. Имея секретный ключ d, n и числовую последовательность C(i), выполняем M(i)= (C(i)^d) mod n. Рассмотрим простейший пример применения алгоритма RSA. Чтобы не утруждать себя громоздкими вычислениями, возьмем очень маленькие исходные числа p и q.
1) p=3, q=7.

2) n=p*q=21.

3) Выбираем d как 5.

4) (e*5) mod 12=1, e=17.

5) Открытый ключ 17, 21, закрытый (секретный) — 5, 21.

Пусть нам нужно зашифровать слово «USD». Чтобы не загромождать большими числами текст статьи, присвоим каждой букве просто порядковый номер из ряда натуральных чисел. То есть:

USD = 1 2 3.

Зашифровываем:

C(1)= 1^17 mod 21= 1; C(2)= 2^17 mod 21 =11; C(3)= 3^17 mod 21= 12.

Получился код:

1 11 12

Расшифровываем.

(1)= 1^5 mod 21= 1; M(2)= 11^5 mod 21= 2; M(3)= 12^5 mod 21= 3.

Имеем:

1 2 3

Тождественно слову «USD».

Как видим, алгоритм достаточно прозрачен и прост в воплощении — реализующую его программу предлагаю составить читателю самостоятельно (это как бы домашнее задание :-)).

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

Всё очень просто - ручками