RSA (algoritm)

RSA (Rivest-Shamir-Adleman) on avaliku võtmesüsteemiga krüpteerimise algoritm andmeedastuses.

Aastal 1977, natuke aega pärast seda, kui oli esitatud avaliku võtmesüsteemi idee, koostasid kolm matemaatikut Ron Rivest, Adi Shamir ja Len Adleman näite sellest, kuidas sellist meetodit saaks kasutada. Nende auks nimetati meetod RSA skeemiks. See süsteem kasutab salajast ja avalikku võtit. RSA oli kõige populaarsem meetod avaliku võtme krüpteerimiseks ja digitaalseks allkirjastamiseks, Eesti kasutab nüüd elliptilist krüptograafiat.

Võtmete loomine

1. Alustuseks valitakse kaks erinevat algarvu p ja q.
2. Algarvud korrutatakse omavahel; n = pq.
3. Arvutatakse φ(n) = φ(pq) = φ(p)φ(q) = (p − 1)(q − 1).
4. Valitakse eksponent e nii, et SÜT(e, φ(n)) = 1. Teisisõnu peavad e ja φ(n) olema kaasalgarvud.
5. Arvutatakse e pöördarv moodulis φ(n); d ≡ e⁻¹ (mod φ(n)). Selleks saab kasutata laiendatud Eukleidese algoritmi.

Täisarvupaar (e, n) on avalik võti ja (d, n) privaatne võti.

Krüptimine ja dekrüptimine

Sõnumi M saab krüptida valemiga

${\displaystyle C\equiv M^{e}{\pmod {n}}}$ ehk ${\displaystyle M^{e}=qn+C}$, kus ${\displaystyle 0<=C<n}$.

Dekrüptimine toimub vastupidi:

${\displaystyle M\equiv C^{d}{\pmod {n}}}$.

Vaata ka

• Avaliku võtme krüptograafia

Välislingid

• Heikki Vallaste "RSA (Rivest-Shamir-Adleman)" e-Teatmik: IT ja sidetehnika seletav sõnaraamat