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\ne q$; sudauginame juos: $n=pq$. Pasirenkame natūralųjį skaičių $e=e_A$ taip, kad jis būtų santykinai pirminis su $\varphi (n)=(p-1)(q-1)$, t. y. $(e,\varphi (n))=1$.

Naudojantis Euklido algoritmu surandame skaičių $d=d_A$, kad būtų $de\equiv 1(\mathrm{mod}\varphi (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}(\mathrm{mod}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}(\mathrm{mod}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 Šablonas:Webarchive