Peržiūrėti šaltinį RSA

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

== Raktų parinkimo algoritmas ==
Pasirenkame du pirminius skaičius <math>p \,</math> ir <math>q \,</math> (jie turi būti pakankamai ilgi), <math>p \ne q</math>; sudauginame juos: <math>n = p q \,</math>. Pasirenkame natūralųjį skaičių <math>e = e_A \,</math> taip, kad jis būtų santykinai pirminis su
<math>\phi(n)=(p-1)(q-1) \,</math>, t. y. <math>(e,\phi(n))=1 \,</math>.

Naudojantis [[Euklidas Aleksandrietis|Euklido]] algoritmu surandame skaičių <math>d=d_A \,</math>, kad būtų <math>d e \equiv 1 \pmod{\phi(n)}</math>.

Sudarome raktus: viešąjį <math>K_v=(e,n) \,</math> ir privatųjį <math>K_p=(d) \,</math>.

=== Šifravimas/Dešifravimas ===
Pranešimai, kuriuos norime siųsti yra [[Aibė|aibės]] <math>\hat{M}=\{1,2,...,n\} \,</math> skaičiai. [[Šifravimas]] apibrėžiamas lygybe:
: <math>C = e(M, e_A) =M^{e_A} \pmod{n}</math>,
<math> C \,</math> – pranešimo <math>M \,</math> [[šifras]] <math>C \,</math> (<math>M \,</math> yra skaičius iš [[Aibė|aibės]] <math>\hat{M} \,</math>, tad <math> M < n \,</math>)

[[Dešifravimo]] [[algoritmas]] visiškai toks pat, kaip ir [[Šifravimas|šifravimo]]:
: <math>M=d(C, d_A) = C^{d_A} \pmod{n}</math>

== RSA Iššūkis ==

Duotajam <math>n \,</math> surasti pirminius <math>p \,</math> ir <math>q \,</math>, kad <math>n = p q \,</math>, laikoma labai sunkia matematine užduotimi. Visas RSA kriptosistemos saugumas remiasi šiuo faktu. RSA Laboratories paskelbė konkursą, kurio esmė yra surasti <math>p \,</math> ir <math>q \,</math> duotajam <math>n \,</math>. Pavyzdžiui, surasti <math>p \,</math> ir <math>q \,</math> skaičiui
: <math>n=13506641086599522334960321627880596993888147560566702752448514385152 \,</math>
: <math>651060485953383394028715057190944179820728216447155137368041970396419174 \,</math>
: <math>304649658927425623934102086438320211037295872576235850964311056407350150 \,</math>
: <math>818751067659462920556368552947521350085287941637732853390610975054433499 \,</math>
: <math>9811150056977236890927563 \,</math>.
Nuo 2007 m. RSA Laboratories šių konkursų neberengia.

== Nuorodos ==
* RSA Laboratories http://www.rsasecurity.com {{Webarchive|url=https://web.archive.org/web/20090106053636/http://www.rsasecurity.com/ |date=2009-01-06 }}

[[Kategorija:Kriptografija]]