Алгоритм шифрования данных с открытым ключом RSA

Алгоритм шифрования данных с открытым ключом является наиболее переспективным в настоящий момент (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/ Данные, приведенные выше, не должны быть использованы в незаконных целях!