RSA (алгоритам)

RSA

Опште
Пројектант(и)	Роналд Ривест, Ади Шамир, Леонард Ејдлман
Датум објаве	1977.
Сертификација	PKCS#1, ANSI X9.31, IEEE 1363
Детаљи
Величина сажимања	1.024 - 4.096
Рунде	1
Најбоља јавна криптоанализа
768-битни RSA кључ је пробијен.

RSA је алгоритам за асиметричну криптографију, првенствено намењен шифровању података али се данас користи и у системима електронског потписа. RSA данас представља индустријски стандард у области асиметричне криптографије и заштити података, тако да је широко примењен у многим сигурносним протоколима и системи електронског пословања.

Историјат

RSA је алгоритам за асиметричну криптографију настао 1977. на МИТ универзитету. Творци овог алгоритма су Роналд Ривест, Леонард Ејдлман и Ади Шамир, где RSA представља акроним њихових презимена.

Клифорд Кокс, британски математичар који је радећи за једну владину агенцију за комуникације, још је 1973. године објавио у интерним документима потпуно еквивалентни систем за асиметричну криптографију, али због поверљивости тих докумената, то је тек објављено 1997.

Алгоритам је патентиран од стране МИТ-а 1983. у САД , под шифром U.S. Patent 4,405,829. Патентна права су истекла 21. септембра 2000.

Опис алгоритма

У RSA алгоритму кључну улогу имају велики прости бројеви. Сигурност RSA заснива се на сложености факторизације великих бројева. Сматра се да је одређивање оригиналне поруке на основу шифрата и кључа за шифровање еквивалентно факторизацији производа два велика проста броја.

Поступак генерисања кључа за RSA алгоритма

1. Генерисаћемо случајно два велика проста броја $p\,$ и $q\,$ при чему $p\neq q$.
2. Израчунаћемо следеће производе: $n=pq\,$.
3. и ојлерову функцију $\phi (n)=(p-1)(q-1)\,$.
4. Одабере се целобројна вредност $e$ при чему $1<e<\phi (n)\,$ .
5. Израчуна се $d\,$ при чему $de\equiv 1{\pmod {\phi (n)}}$.
6. Јавни кључ је пар $(n,e)\,$. Приватни кључ је пар $(n,d)\,$.

Власник приватног (неко каже и тајног кључа) d, слободно може да објави бројеве n и e, тако да свако ко жели да му упути тајну поруку може то и учинити, а њен садржај може читати само власник приватног кључа, док остали добијају бесмислен текст.

Шифровање поруке

Илустративан је бројни пример (додуше са малим бројевима али је јаснији)

Генерисање кључева

Особа А формира јавни и тајни кључ:

1. изабарала је просте бројеве $p=2357,q=2551\,$,
2. израчунала је број $n=p*q=6012707\,$
3. израчунала је број $t=(p-1)*(q-1)=6007800\,$.
4. бира случајно број $e=3674911\,$ (део јавног кључа),
5. одговарајућим (проширени Еуклидов) алгоритмом рачуна $d=422191\,$. тј. тајни кључ

Дакле јавни кључ је пар $(n=6012707,e=3674911)$.

Шифровање поруке

Да би особа Б која поседује тај јавни кључ, шифровала поруку $m=5234673$ , особи А мора да:

1. рачуна $c=m^{e}\mod n=5234673^{3674911}\mod 6012707=3650502$.
2. Тај број c = 3650502 (шифрат оригиналне поруке m) особа Б, шаље особи А, која приступа дешифровању. односно користећи број d - тајни кључ рачуна:

Дешифровање поруке

Користећи број d - тајни кључ особа А рачуна: $c^{d}\mod n=3650502^{422191}\mod 6012707=5234673$

а тај број је и оригинална порука m).

Недостаци алгоритма

Прости бројеви који се користе у овом алгоритму углавном садрже неколико стотина цифара и због тога се овде јављају више проблема практичне природе. Да би се помножили толико велики бројеви, морају се користити посебни алгоритми за множење. Сем тога лако се да приметити да је за такве операције потребно више времена, па су тако ови алгоритми шифровања много спорији у односу на симетричне алгоритме. DES алгоритам шифровања је око 100 до 1000 пута бржи у односу на RSA алгоритам. Сем овога алгоритми за факторизацију бројева постају сваким даном све бољи, као и неумољив развој компјутера учинили су да данас 512 битни RSA алгоритам не буде довољан за безбедно шифровање порука, за 1024 битне алгоритме претпоставља се да ће бити безбедни барем још 15-так година.

Референце

• mr Драган Видаковић, Мала Школа Криптографије
• R. Rivest, A. Shamir, L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, Vol. 21 (2), pp.120-126. 1978. Previously released as an MIT "Technical Memo" in April 1977. Initial publication of the RSA scheme.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.7: The RSA public-key cryptosystem, pp.881-887.