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