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\,}
q
{\displaystyle q\,}
p
≠
q
{\displaystyle p\neq q}
n
=
p
q
{\displaystyle n=pq\,}
e
=
e
A
{\displaystyle e=e_{A}\,}
ϕ
(
n
)
=
(
p
−
1
)
(
q
−
1
)
{\displaystyle \phi (n)=(p-1)(q-1)\,}
(
e
,
ϕ
(
n
)
)
=
1
{\displaystyle (e,\phi (n))=1\,}
Naudojantis Euklido algoritmu surandame skaičių
d
=
d
A
{\displaystyle d=d_{A}\,}
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)\,}
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\}\,}
Š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\,}
M
{\displaystyle M\,}
šifras
C
{\displaystyle C\,}
M
{\displaystyle M\,}
aibės
M
^
{\displaystyle {\hat {M}}\,}
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\,}
p
{\displaystyle p\,}
q
{\displaystyle q\,}
n
=
p
q
{\displaystyle n=pq\,}
p
{\displaystyle p\,}
q
{\displaystyle q\,}
n
{\displaystyle n\,}
p
{\displaystyle p\,}
q
{\displaystyle q\,}
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.
