Шифрование информации методом RSA (система с открытым ключом)

Шифрование информации методом RSA (система с
открытым ключом)

 

    Суть их со­сто­ит в том, что ка­ж­дым ад­ре­са­том
ИС ге­не­ри­ру­ют­ся два клю­ча, свя­зан­ные ме­ж­ду со­бой по оп­ре­де­лен­но­му
пра­ви­лу. Один ключ объ­яв­ля­ет­ся от­кры­тым,
а дру­гой за­кры­тым. От­кры­тый ключ
пуб­ли­ку­ет­ся и дос­ту­пен лю­бо­му, кто же­ла­ет по­слать со­об­ще­ние ад­ре­са­ту.
Секретный ключ сохраняется в тайне.

    Ис­ход­ный текст шиф­ру­ет­ся от­кры­тым клю­чом
адресата и пе­ре­да­ет­ся ему. За­шиф­ро­ван­ный текст в прин­ци­пе не мо­жет
быть рас­шиф­ро­ван тем же от­кры­тым клю­чом. Де­шиф­ро­ва­ние со­об­ще­ние
воз­мож­но толь­ко с ис­поль­зо­ва­ни­ем за­кры­то­го клю­ча, ко­то­рый из­вес­тен
толь­ко са­мо­му ад­ре­са­ту.











    Крип­то­гра­фи­че­ские сис­те­мы с от­кры­тым клю­чом
ис­поль­зу­ют так называемые  не­об­ра­ти­мые  или од­но­сто­рон­ние функ­ции, ко­то­рые
об­ла­да­ют сле­дую­щим свой­ст­вом: при за­дан­ном зна­че­нии x от­но­си­тель­но про­сто вы­чис­лить
зна­че­ние f(x), од­на­ко ес­ли y=f(x),
то нет про­сто­го пу­ти для вы­чис­ле­ния зна­че­ния x.

 

Алгоритм метода RSA.

 

Выбрать два больших простых числа P и Q (необходимо
составить подпрограмму генерации простых чисел)

Простым называется целое
число, большее единицы, единственными множителями которого является 1 и оно
само: оно не делится ни на одно другое число. Два - это простое число. Простыми
являются и 73, 2521, 2365347734339 и 2 756839
–1

 

Вычислить общий ключ N=P*Q.Вычислить функцию Эйлера F(N)=(P-1)*(Q-1).

Функцией
Эйлера F(N) называется число положительных целых, меньших N и
простых относительно N.

 

Выбрать секретный ключ D – взаимно простое с
F(N).

Два числа называются взаимно простыми, если у них нет общих множителей кроме 1. Иными словами, если наибольший общий делитель a и n равен 1. Это
записывается как:НОД(a,n)=1.

Взаимно просты числа 15 и 28.
15 и 27 не являются взаимно простыми, а 13 и 500 - являются. Простое число

взаимно просто со всеми
другими числами, кроме чисел, кратных данному простому числу.

 

Выбрать открытый ключ E. В качестве такого
числа может быть взято любое число, для которого удовлетворяется
соотношение (E*D) = 1 (mod F(N)) т.е. (E*D) mod F(N) = 1.

Или (E*D) = F(N)*k + 1 для некоторого k.

Для шифровки сообщения
воспользоваться формулой:

M = (C^E) mod F(N), где С – исходный текст, M – зашифрованный текст.

Для расшифровки сообщения воспользуемся
формулой:

C = (M^D) mod
F(N).

 

Предусмотреть рекурсивное
упрощение, при возведении в большие степени.

Можно воспользоваться
формулой: (a * b) mod n == ((a mod n) *
(b mod n)) mod n

 

 

 

Пример Зашифруем сообщение «САВ».
Для простоты будем использовать маленькие числа (на практике применяются
гораздо большие).

1.   
Выберем p=3 и q=11.

2.   
Определим n=3*11=33.

3.   
Найдем (p-1)(q-1)=20.
Следовательно, в качестве d, взаимно
простое  с 20, например, d=3.

4.   
Выберем число
е. В качестве такого числа может быть взято любое число, для которого
удовлетворяется соотношение (е*3) (mod 20) = 1, например 7.

5.   
Представим
шифруемое сообщение как последовательность целых чисел с помощью отображения: АSYMBOL
174 \f "Symbol" \s 14®1, ВSYMBOL
174 \f "Symbol" \s 14®2, СSYMBOL
174 \f "Symbol" \s 14®3. Тогда сообщение принимает вид (3,1,2).
Зашифруем сообщение с помощью ключа {7,33}.

ШТ1 = (37)
(mod 33) = 2187 (mod 33) = 9,

ШТ2 = (17)
(mod 33) = 1 (mod 33) = 1,

ШТ3 = (27)
(mod 33) = 128 (mod 33) = 29.

6.   
Расшифруем
полученное зашифрованное сообщение (9,1,29) на основе закрытого ключа {3,33}:

ИТ1 = (93)
(mod 33) = 729 (mod 33) = 3,

ИТ2= (13)
(mod 33) = 1 (mod 33) = 1,

ИТ3 = (293)
(mod 33) = 24389 (mod 33) = 2.

 

More abstracts about the Шифрование информации методом RSA (система с открытым ключом)