РСА (алгоритам)

Из Википедије, слободне енциклопедије
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 \ne q.
  2. Израчунаћемо следеће производе: n = p q \,.
  3. и ојлерову функцију \phi(n) = (p-1)(q-1) \,.
  4. Одабере се целобројна вредност e при чему 1 < e < \phi(n) \, .
  5. Израчуна се d\, при чему d e \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-так година.

Референце[уреди]