Пловдивски

62 който притежава публичния ключ на изпращача за неговото разшифриране
(фигура 34). Подходът се използва за потвърждаване на автентичността на съобщенията.
фигура 34 Цифров подпис
5.2.1. Алгоритъм RSA
RSA е един от първите шифриращи алгоритми, отговарящи на изискванията за асиметрично криптиране. Разработен е от Ron Rivest, Adi
Shamir и Len Adelman (през 1977 г.), които получават за него награда
Тюринг през 2003 г. Той е блоков алгоритъм с дължина на ключовете 1024 и 2048 бита. Първоначалното съобщение се разделя на k бита, където
2
k
k+1
. Шифрирането и дешифрирането могат да се изразят по следния начин: C=M
e mod n, M=C
d mod n, където M е блок от първичния текст, а C е блок от шифрирания текст. Двата обособени блока са числа принадлежащи на интервала [0,n-1].Наредената двойка (e,n) сформира публичния ключ на получателя, а (d,n) е частният ключ на получателя.
Числата e, d, n се получават по следния начин:
1. Генерират се две големи прости числа p и q (по-големи от 10 100
);
2. Образува се произведението n=p.q, което е част от генерираните ключове;
3. Изчислява се

(n)=(p-1)(q-1), показващо броя на числата 4. Пресмята се e, за което 1<е<

(n) и gcd(

(n),e)=1 (gcd – взаимно прости). То е част от публичния ключ;
5. Изчислява се d=e
-1
mod

(n) и d<

(n), което е част от частния ключ;
RSA използва факта, че произведението n (от т.2) е почти невъзможно да се разложи на множители. обикновен текст
(plaintext) шифриращ алгоритъм частен ключ на изпращач дешифриращ алгоритъм обикновен текст
(plaintext)
шифриран текст
(ciphertext)
публичен ключ на изпращач

63
Функционирането на алгоритъма може да се демонстрира със следния пример: Да се изпрати съобщение М=88 като се използва RSA алгоритъм
(фигура 35).
1. Нека p=17 и q=11;
2. n=p.q=17.11=187;
3.

(n)=(p-1)(q-1)=16.10=160;
4. Избира се e=7, така че да удовлетворява условията 1<е<160
(1<е<

(n)) и gcd(160,7)=1 (gcd(

(n),e)=1);
5. Изчислява се d=e
-1
mod

(n) и d<

(n) т.е. d.e=1 mod 160. За d=23

23.7-160=1.160+1 и 23<160;
6. За шифриране на съобщението М=88 се използва публичният ключ
(e,n)

(7,187) и формулата C=M
e mod n

C=88 7
mod 187=11 т.е. шифрираното съобщение ще е 11;
7.
За дешифриране на съобщението се използва частният ключ (d,n)

(23,187) и формулата M=C
d mod n

M=11 23
mod 187=88 т.е. дешифрираното съобщение ще е 88;
Забележка: В примера, за блока M, се използва директно цифровата стойност на съобщението в десетичен вид 88
(10)
. При по-подробно разписване това означава да се определи стойността на k (дължината на съобщението в битове), за която 2
k
k+1
. В случая при n=187

k=7
(2 7
=128<187<2 7+1
=256). Тогава блокът M ще е съставен от 7 бита

88
(10)
=1011000
(2)
т.е. на входа на шифраторът ще е постъпила двоичната комбинация 1011000.

Изтегляне 7.37 Mb.

Сподели с приятели: