RSA (Rivest–Shamir–Adleman abreviatūra) – viešojo rakto kriptosistema, kurios algoritmą 1977 metais sukūrė Ronald Rivest, Adi Shamir ir Leonard Adleman.
Pasirenkame du pirminius skaičius
ir
(jie turi būti pakankamai ilgi),
; sudauginame juos:
. Pasirenkame natūralųjį skaičių
taip, kad jis būtų santykinai pirminis su
, t. y.
.
Naudojantis Euklido algoritmu surandame skaičių
, kad būtų
.
Sudarome raktus: viešąjį
ir privatųjį
.
Pranešimai, kuriuos norime siųsti yra aibės
skaičiai. Šifravimas apibrėžiamas lygybe:
,
– pranešimo
šifras
(
yra skaičius iš aibės
, tad
)
Dešifravimo algoritmas visiškai toks pat, kaip ir šifravimo:
![{\displaystyle M=d(C,d_{A})=C^{d_{A}}{\pmod {n}}}](http://178.128.105.246/content-https-wikimedia.org/api/rest_v1/media/math/render/svg/c292f5b1fe99d5bad999ee59a74e88e0cce2f195)
Duotajam
surasti pirminius
ir
, kad
, laikoma labai sunkia matematine užduotimi. Visas RSA kriptosistemos saugumas remiasi šiuo faktu. RSA Laboratories paskelbė konkursą, kurio esmė yra surasti
ir
duotajam
. Pavyzdžiui, surasti
ir
skaičiui
![{\displaystyle n=13506641086599522334960321627880596993888147560566702752448514385152\,}](http://178.128.105.246/content-https-wikimedia.org/api/rest_v1/media/math/render/svg/ab7fa7dba2349ed412ef72313113d80712b9dbf3)
![{\displaystyle 651060485953383394028715057190944179820728216447155137368041970396419174\,}](http://178.128.105.246/content-https-wikimedia.org/api/rest_v1/media/math/render/svg/fe0e4e967cac298832ff700ce92ea98ce495fa44)
![{\displaystyle 304649658927425623934102086438320211037295872576235850964311056407350150\,}](http://178.128.105.246/content-https-wikimedia.org/api/rest_v1/media/math/render/svg/36dd77886442bf0780324dfa15923a553a338c5a)
![{\displaystyle 818751067659462920556368552947521350085287941637732853390610975054433499\,}](http://178.128.105.246/content-https-wikimedia.org/api/rest_v1/media/math/render/svg/0197422926fdc9fe3644d5cc19f82d6c966c1aa9)
.
Nuo 2007 m. RSA Laboratories šių konkursų neberengia.