Цитата:
Простыми числами называются числа, не имеющие делителей, кроме самих себя и единицы. А вот взаимно простыми числами называются числа, не имеющие общих делителей, кроме 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 можно отнести ту особенность, что одинаковые символы открытого текста будут и в зашифрованном тексте также выглядеть одинаково, что с точки зрения криптографии — неправильно.
|
Всё очень просто - ручками :)
|
