Roman Lonely
Алгоритм шифрования данных с открытым ключом является
наиболее переспективным в настоящий момент (RSA - Rivest, Shamir and Aldeman -
его изобретатели).
Понятия:
Простое число - делится только на 1 и на само себя;
Взаимно простым- не имеют ни одного общего делителя, кроме
1;
Результат операции i mod j - остаток от целочисленного деления
i на j.
Чтобы использовать алгоритм RSA, надо сначала сгенерировать
открытый и секретные ключи выполнив следующие шаги:
1) Выберем два очень больших простых числа p and q.
2) Определим n, как результат умножения p on q (n= p*q).
3) Выберем большое случайное число, которое назовем d. Это
число должно быть взаимно простым с результатом умножения (p-1)*(q-1).
4) Определим такое число е, для которого является истинным
следующее соотношение (e*d) mod ((p-1)*(q-1))=1.
5) Hазовем открытым ключем числа e и n, а секретным ключом -
чмсла d и n.
=================================
Теперь, чтобы зашифровать данные по известному ключу {e,n},
необходимо сделать следующее:
- разбить шифруемый текст на блоки, каждый из которых может
быть представлен в виде числа M(i)=0,1,2..., n-1( т.е. только до n-1).
- зашифровать текст, рассматриваемый как последовательность
чисел M(i) по формуле C(i)=(M(I)^e)mod n.
Чтобы расшифровать эти данные, используя секретный ключ {d,n},
необходимо выполнить следующие вычисления: M(i) = (C(i)^d) mod n. В результате
будет получено множество чисел M(i), которые представляют собой исходный
текст.
==========================
Hу, чтобы более наглядно представить алгоритм RSA, приведу
следующий пример:
Зашифруем и расшифруем сообщение "САВ" по алгоритму
RSA. Для простоты буду использовать маленькие числа(на практике - нужно брать
намного большие).
1) Выберем p=3 and q=11.
2)Определим n= 3*11=33.
3) Hайдем (p-1)*(q-1)=20. Следовательно, d будет равно,
например, 3: (d=3).
4) Выберем число е по следующей формуле: (e*3) mod 20=1. Значит
е будет равно, например, 7: (e=7).
5) Представим шифруемое сообщение как последовательность чисел
в диапозоне от 0 до 32 (незабывайте, что кончается на n-1). Буква А =1, В=2,
С=3.
Теперь зашифруем сообщение, используя открытый ключ {7,33}
C1 = (3^7) mod 33 = 2187 mod 33 = 9;
C2 = (1^7) mod 33 = 1 mod 33 = 1;
C3 = (2^7) mod 33 = 128 mod 33 = 29;
Теперь расшифруем эти данные, используя закрытый ключ
{3,33}.
M1=(9^3) mod 33 =729 mod 33 = 3(С);
M2=(1^3) mod 33 =1 mod 33 = 1(А);
M3=(29^3) mod 33 = 24389 mod 33 = 2(В);
Все, данные расшифрованы.
================================
Криптостойкость алгоритма RSA основывается на предположении,
что исключительно трудно определить секретный ключь по известному, поскольку для
этого необходимо решить задачу о существовании делителей целого числа. Данная
задача является NP-полной, и, как следствие этого факта, не допускает cейчас
эффективного (полиноминального) решения. Более того, сам вопрос существования
эффективных алгоритмов решения NP-полных задач является до настоящего времени
открытым. Если Вы используете числа, состоящие из 200 цифр(такие и надо
использовать при шифровании данных), для несанкционированной расшифровки
придется генерировать огромное число операций (около 10^23).
P.S/ Данные, приведенные выше, не должны быть использованы
в незаконных целях!
Литература по компьютерной безопасности
|