C, PHP, VB, .NET

RSA е алгоритъм за асиметрично криптиране на данни. Използват се два ключа, с които се криптира и съответно декриптира информацията. Измислен е през 1983 г. от Роналд Ривест, Ади Шамир и Леонард Адлеман. Използва се и до днес като един от основните алгоритми за пренос на криптирана информация в интернет с протокола TLS, както и при електронни подписи. Основната идея е имайки единия ключ да е математически много трудно да бъде изчислен какъв е другия. По този начин става възможно да даваме свободно единия от ключовете като "публичен" (приема се, че всички го знаят), а другия да остане "таен" (само собственика го притежава и никой друг не може в разумно време да го намери).

Алгоритъмът се основава на т.нар. "модулно експоненциране" и генерирането на двойката ключове включва серия от операции с цели числа. В тази статия няма да разисквам математическата основа на алгоритъма, а ще се фокусирам основно върху даване на практически пример за това как се генерират ключовете и впоследствие как се шифрира и дешифрира съобщение с тях.

Генериране на ключ за криптиране

В началото на алгоритъма се генерират две различни произволни прости числа. За текущия пример ще използваме две малки стойности, но на практика обикновено се избират много големи:

[math]p=11, q=5[/math]

След това се изчислява тяхното произведение:

[math]n = p\times q = 11\times5 = 55[/math]

Числото [mathi]n[/mathi] ще се използва като част от ключовете за криптиране и декриптиране. От тук нататък търсим [mathi]\rho{(n)}[/mathi], което е броят на естествените числа, ненадминаващи [mathi]n[/mathi] и взаимно прости с него. Понеже [mathi]n[/mathi] е съставено като произведение на две прости числа, то ако запишем всички числа от 2 до 55, можем да задраскаме тези, които се делят на [mathi]p[/mathi] и [mathi]q[/mathi], след което да преброим незадрасканите:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55

Вижда се, че незадрасканите в списъка са 40 на брой. Този метод разбира се не е ефективен, а за намирането на въпросното число има готова формула - функция на Ойлер:

[math]\rho{(n)} = \rho{(55)} = (p-1)\times (q-1) = 10 \times 4 = 40[/math]

От тук нататък търсим число [mathi]e[/mathi], което е в интервала [mathi](1,\rho{(n)})[/mathi] и такова, че [mathi]e[/mathi] и [mathi]\rho{(n)}[/mathi] са взаимно прости (нямат общи делители). В случая делителите на 40 са 2 и 5, т.е. ако запишем числата от 2 до 39 и задраскаме тези от тях, които се делят на 2 и 5, ще остане списък с потенциалните стойности на [mathi]e[/mathi]:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39

Числото [mathi]e[/mathi] може да е което и да е от незадрасканите числа. Например избираме:

[math]e = 7[/math]

От тук нататък ключът за криптиране е комбинацията от числата [mathi]\textbf{(e, n) = (7, 55)}[/mathi]

Генериране на ключ за декриптиране

Търсим такова число [mathi]d[/mathi], което да удовлетворява равенството:

[math]e \times d\mod{\rho{(n)}} = 1[/math]

Като заместим вече намерените числа виждаме, че търсим:

[math]7 \times d\mod{40} = 1[/math]

Ще използваме разширен алгоритъм на Евклид. Първо търсим най-големия общ делител на 7 и 40. Може би най-лесно (решавайки задачата на хартия) се намира в табличен вид:

Делимо	Делител	Частно	Остатък
40	7	5	5
7	5	1	2
5	2	2	1
2	1	2	0

В първия ред поставяме числата 40 и 7 като делимо и делител (винаги по-голямото го взимаме първо). Понеже [mathi]40 = 7 \times 5 + 5[/mathi], записахме като частно 5 и остатък 5. На втори ред показахме, че сме пренесли делителя (оцветен в синьо) и остатъка (оцветен в червено) съответно като нови делимо и делител. Процедурата се повтаря до тогава, докато се стигне до остатък 0. НОД на двете числа ще бъде остатъка на реда над този, на който се е получила 0. В случая НОД(40,7) = 1. Това беше напълно очаквано, защото изначало ги търсихме взаимно прости. Направихме го, защото ще използваме тази таблица за последващи изчисления.

Нека разширим таблицата, като на всеки нейн ред дадем еквивалентно негово уравнение (пропускаме реда с остатък 0, защото той не ни е нужен):

Делимо	Делител	Частно	Остатък	№	Уравнение
40	7	5	5	В	[mathi]40 - 7 \times 5 = (5)[/mathi]
7	5	1	2	Б	[mathi]7 - 5 \times 1 = (2)[/mathi]
5	2	2	1	А	[mathi](5) - (2) \times 2 = 1[/mathi]

Нарочно ги номерирах в обратен ред (В, Б, А), защото ще започнем да правим замествания отдолу-нагоре. Нарочно и едни от числата са оградени в скоби - тях впоследствие ще приемем за нещо като променливи и ще ги заместваме от едни уравнения в други.

Нека за удобство обърнем реда на уравненията отгоре-надолу:

№	Уравнение
А	[mathi](5) - {\color{blue} (2)} \times 2 = 1[/mathi]
Б	[mathi]7 - 5 \times 1 = {\color{blue} (2)}[/mathi]
В	[mathi]40 - 7 \times 5 = (5)[/mathi]

И да започнем с първото заместване. Взимаме стойността на оцветеното в синьо от уравнение Б и го поставяме на на мястото на оцветеното в синьо на уравнение А:

№	Уравнение
А	[mathi](5) - {\color{blue} (7 - 5 \times 1)} \times 2 = 1[/mathi]
Б	[mathi]7 - 5 \times 1 = {\color{blue} 2}[/mathi]
В	[mathi]40 - 7 \times 5 = 5[/mathi]

Опростяваме уравнение А като разкриваме големите скоби (и заменяме [mathi](5 \times 1)[/mathi] с [mathi](5)[/mathi]):

№	Уравнение
А	[mathi](5) - 2 \times (7) + 2 \times (5) = 1[/mathi]
Б	[mathi]7 - 5 \times 1 = 2[/mathi]
В	[mathi]40 - 7 \times 5 = 5[/mathi]

с което финално в уравнение А получаваме:

№	Уравнение
А	[mathi]-2 \times (7) + 3 \times {\color{blue} (5)} = 1[/mathi]
Б	[mathi]7 - 5 \times 1 = 2[/mathi]
В	[mathi]40 - 7 \times 5 = {\color{blue} 5}[/mathi]

Сега взимаме оцветеното в синьо от уравнение В и го заместваме на мястото на оцветеното в синьо от новото уравнение А:

№	Уравнение
А	[mathi]-2 \times (7) + 3 \times {\color{blue} (40 - 7 \times 5)} = 1[/mathi]
Б	[mathi]7 - 5 \times 1 = 2[/mathi]
В	[mathi]40 - 7 \times 5 = {\color{blue} 5}[/mathi]

Отново разкриваме скобите и в увравнение А се получава:

№	Уравнение
А	[mathi]-2 \times (7) + 3 \times (40) - 3 \times (7) \times 5 = 1[/mathi]
Б	[mathi]7 - 5 \times 1 = 2[/mathi]
В	[mathi]40 - 7 \times 5 = 5[/mathi]

Така получаваме финално уравнение А:

[math]A: 3 \times (40) {\color{red} -17} \times (7) = 1[/math]

От интерес за нас остана числото, което е оцветено в червено. Ако то беше положително, това щеше да е търсеното [mathi]d[/mathi]. То обаче е отрицателно, затова:

[math]d = 40 {\color{red} -17} = 23[/math]

От тук нататък ключът за декриптиране е комбинацията от числата [mathi]\textbf{(d, n) = (23, 55)}[/mathi]

Как се криптира и декриптира?

Нека имаме съобщение [mathi]M=15[/mathi] (трябва да е число, което е по-малко от [mathi]n[/mathi]). За да го криптираме използваме формулата:

[math]c = M^{e} \mod n [/math]

тоест в нашия пример получаваме криптирано съобщение:

[math]c = 15^{7}\mod 55 = 5[/math]

За да го декриптираме използваме формулата:

[math]M = c^{d}\mod n[/math]

тоест в нашия пример получаваме съобщението:

[math]M = 5^{23} \mod 55 = 15[/math]

Както виждате оригиналното съобщение се декриптира успешно и се възстанови в оригиналния си вид. Това беше и целта ни.

Сигурност на алгоритъма

Трябва да сме сигурни, че при дадено [mathi](е, n)[/mathi] не може да се намери [mathi](d, n)[/mathi] и обратно. От представения алгоритъм става ясно, че ако знаем [mathi]p[/mathi] и [mathi]q[/mathi], то лесно може да се намерят [mathi]e[/mathi] и [mathi]d[/mathi]. Тоест сигурността на алгоритъма се корени в това, че няма известен лесен алгоритъм, с който при дадено [mathi]n[/mathi] да бъдат намерени прости числа [mathi]p[/mathi] и [mathi]q[/mathi] такива, че [mathi]n= p \times q[/mathi]. Ясно е, че ако имаме малка стойност на [mathi]n[/mathi] ще ни бъде сравнително лесно да намерим такива дори на принципа "проба-грешка". При много голямо [mathi]n[/mathi] обаче това ще отнеме изключително много изчисления дори при най-добрите познати алгоритми. Например при протокола TLS произволните числа се подбират такива, че [mathi]n[/mathi] да бъде с дължина от 2048 или 4096 бита (в десетичен вид това са 617 или съответно 1234 цифрени числа [mathi]n[/mathi]).

Казано по-стегнато: сигурността на алгоритъма RSA се дължи на това, че няма известен бърз алгоритъм за разделяне на едно число на прости множители.

Известен е т.нар. "алгоритъм на Шор" (1994 г.), с който задачата може да бъде решена за полиномно време, но на квантов компютър. Засега човечеството е много далеч от създаването на достатъчно мощен квантов компютър, който да може да извършва разлагане на прости множители на достатъчно големи числа - най-голямото "разбито" досега число от квантов компютър е едва шестцифреното десетично число 291311 (2017 г.). Колкото до обикновените компютри, със съществуващите алгоритми се счита за невъзможно. През 2009 г. беше изчислено, че RSA с 768 битов ключ може да бъде разбит от едноядрен 2.2Ghz процесор AMD Opteron за около 2000 години. Предполага се, че с 1024 битов ключ изчисленията на същия процесор биха отнели около 2 милиона години. Понеже изчисленията растат експоненциално с големината на ключа, разбиването на RSA-2048 или RSA-4096 на този етап се счита за напълно невъзможно за наличната компютърна техника.