RSA

RSA (Rivest–Shamir–Adleman abreviatūra) – viešojo rakto kriptosistema, kurios algoritmą 1977 metais sukūrė Ronald Rivest, Adi Shamir ir Leonard Adleman.

Raktų parinkimo algoritmas

Pasirenkame du pirminius skaičius $p\,$ ir $q\,$ (jie turi būti pakankamai ilgi), $p\neq q$; sudauginame juos: $n=pq\,$. Pasirenkame natūralųjį skaičių $e=e_{A}\,$ taip, kad jis būtų santykinai pirminis su $\phi (n)=(p-1)(q-1)\,$, t. y. $(e,\phi (n))=1\,$.

Naudojantis Euklido algoritmu surandame skaičių $d=d_{A}\,$, kad būtų $de\equiv 1{\pmod {\phi (n)}}$.

Sudarome raktus: viešąjį $K_{v}=(e,n)\,$ ir privatųjį $K_{p}=(d)\,$.

Šifravimas/Dešifravimas

Pranešimai, kuriuos norime siųsti yra aibės ${\hat {M}}=\{1,2,...,n\}\,$ skaičiai. Šifravimas apibrėžiamas lygybe:

$C=e(M,e_{A})=M^{e_{A}}{\pmod {n}}$,

$C\,$ – pranešimo $M\,$ šifras $C\,$ ($M\,$ yra skaičius iš aibės ${\hat {M}}\,$, tad $M<n\,$)

Dešifravimo algoritmas visiškai toks pat, kaip ir šifravimo:

$M=d(C,d_{A})=C^{d_{A}}{\pmod {n}}$

RSA Iššūkis

Duotajam $n\,$ surasti pirminius $p\,$ ir $q\,$, kad $n=pq\,$, laikoma labai sunkia matematine užduotimi. Visas RSA kriptosistemos saugumas remiasi šiuo faktu. RSA Laboratories paskelbė konkursą, kurio esmė yra surasti $p\,$ ir $q\,$ duotajam $n\,$. Pavyzdžiui, surasti $p\,$ ir $q\,$ skaičiui

$n=13506641086599522334960321627880596993888147560566702752448514385152\,$

$651060485953383394028715057190944179820728216447155137368041970396419174\,$

$304649658927425623934102086438320211037295872576235850964311056407350150\,$

$818751067659462920556368552947521350085287941637732853390610975054433499\,$

$9811150056977236890927563\,$.

Nuo 2007 m. RSA Laboratories šių konkursų neberengia.

Nuorodos

• RSA Laboratories http://www.rsasecurity.com Archyvuota kopija 2009-01-06 iš Wayback Machine projekto.