Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
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
p
{\displaystyle p\,}
ir
q
{\displaystyle q\,}
(jie turi būti pakankamai ilgi),
p
≠
q
{\displaystyle p\neq q}
; sudauginame juos:
n
=
p
q
{\displaystyle n=pq\,}
. Pasirenkame natūralųjį skaičių
e
=
e
A
{\displaystyle e=e_{A}\,}
taip, kad jis būtų santykinai pirminis su
ϕ
(
n
)
=
(
p
−
1
)
(
q
−
1
)
{\displaystyle \phi (n)=(p-1)(q-1)\,}
, t. y.
(
e
,
ϕ
(
n
)
)
=
1
{\displaystyle (e,\phi (n))=1\,}
.
Naudojantis Euklido algoritmu surandame skaičių
d
=
d
A
{\displaystyle d=d_{A}\,}
, kad būtų
d
e
≡
1
(
mod
ϕ
(
n
)
)
{\displaystyle de\equiv 1{\pmod {\phi (n)}}}
.
Sudarome raktus: viešąjį
K
v
=
(
e
,
n
)
{\displaystyle K_{v}=(e,n)\,}
ir privatųjį
K
p
=
(
d
)
{\displaystyle K_{p}=(d)\,}
.
Pranešimai, kuriuos norime siųsti yra aibės
M
^
=
{
1
,
2
,
.
.
.
,
n
}
{\displaystyle {\hat {M}}=\{1,2,...,n\}\,}
skaičiai. Šifravimas apibrėžiamas lygybe:
C
=
e
(
M
,
e
A
)
=
M
e
A
(
mod
n
)
{\displaystyle C=e(M,e_{A})=M^{e_{A}}{\pmod {n}}}
,
C
{\displaystyle C\,}
– pranešimo
M
{\displaystyle M\,}
šifras
C
{\displaystyle C\,}
(
M
{\displaystyle M\,}
yra skaičius iš aibės
M
^
{\displaystyle {\hat {M}}\,}
, tad
M
<
n
{\displaystyle M<n\,}
)
Dešifravimo algoritmas visiškai toks pat, kaip ir šifravimo :
M
=
d
(
C
,
d
A
)
=
C
d
A
(
mod
n
)
{\displaystyle M=d(C,d_{A})=C^{d_{A}}{\pmod {n}}}
Duotajam
n
{\displaystyle n\,}
surasti pirminius
p
{\displaystyle p\,}
ir
q
{\displaystyle q\,}
, kad
n
=
p
q
{\displaystyle n=pq\,}
, laikoma labai sunkia matematine užduotimi. Visas RSA kriptosistemos saugumas remiasi šiuo faktu. RSA Laboratories paskelbė konkursą, kurio esmė yra surasti
p
{\displaystyle p\,}
ir
q
{\displaystyle q\,}
duotajam
n
{\displaystyle n\,}
. Pavyzdžiui, surasti
p
{\displaystyle p\,}
ir
q
{\displaystyle q\,}
skaičiui
n
=
13506641086599522334960321627880596993888147560566702752448514385152
{\displaystyle n=13506641086599522334960321627880596993888147560566702752448514385152\,}
651060485953383394028715057190944179820728216447155137368041970396419174
{\displaystyle 651060485953383394028715057190944179820728216447155137368041970396419174\,}
304649658927425623934102086438320211037295872576235850964311056407350150
{\displaystyle 304649658927425623934102086438320211037295872576235850964311056407350150\,}
818751067659462920556368552947521350085287941637732853390610975054433499
{\displaystyle 818751067659462920556368552947521350085287941637732853390610975054433499\,}
9811150056977236890927563
{\displaystyle 9811150056977236890927563\,}
.
Nuo 2007 m. RSA Laboratories šių konkursų neberengia.