RSA

RSA (Rivest–Shamir–Adleman abreviatūra) – , kurios algoritmą 1977 metais sukūrė , ir .

Raktų parinkimo algoritmas

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

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

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

Šifravimas/Dešifravimas

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

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

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

algoritmas visiškai toks pat, kaip ir :

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

RSA Iššūkis

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

${\displaystyle n=13506641086599522334960321627880596993888147560566702752448514385152\,}$

${\displaystyle 651060485953383394028715057190944179820728216447155137368041970396419174\,}$

${\displaystyle 304649658927425623934102086438320211037295872576235850964311056407350150\,}$

${\displaystyle 818751067659462920556368552947521350085287941637732853390610975054433499\,}$

${\displaystyle 9811150056977236890927563\,}$.

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

Nuorodos

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