RSA

Из пројекта Википедија

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

Садржај 1 Историјат 2 Опис алгоритма 3 Поступак генерисања кључа за RSA алгоритма 4 Шифровање поруке 4.1 Генерисање кључева 4.2 Шифровање поруке 4.3 Дешифровање поруке 5 Недостаци алгоритма 6 Референце

[уреди] Историјат

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

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

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

[уреди] Опис алгоритма

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

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

1. Генерисаћемо случајно два велика (различита) проста броја and при чему .
2. Израчунаћемо следеће производе:.
3. и ојлерову функцију .
4. Одабере се целобројна вредност e при чему .
5. Израчуна се при чему .
6. Јавни кључ је пар , Приватни кључ је пар .

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

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

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

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

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

1. изабрала је просте бројеве ,
2. израчунала је број
3. израчунала је број .
4. бира случајно број (део јавног кључа),
5. одговарајућим (проширени Еуклидов) алгоритмом рачуна . тј. тајни кључ

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

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

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

1. рачуна .
2. Тај број c = 3650502 (шифрат оригиналне поруке m) особа Б, шаље особи А, која приступа дешифровању. односно користећи број d - тајни кључ рачуна:

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

Користећи број d - тајни кључ особа А рачуна:

а тај број је и оригинална порука 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 0262032937. Section 31.7: The RSA public-key cryptosystem, pp.881–887.