DSA (Digital Signature Algorithm ), skaitmeninio parašo algoritmas yra Jungtinių Valstijų federalinės valdžios (angl. United States Federal Government ) standartinis skaitmeninis parašas. Jis buvo patvirtintas Nacionalinės standartų ir technologijų instituto (NIST, National Institute of Standards and Technology ) 1991 metais.
Pasirenkamas 160-bitų pirminis skaičius
q
{\displaystyle q}
Pasirenkamas
L
{\displaystyle L}
p
{\displaystyle p}
p
=
q
z
+
1
{\displaystyle p=qz+1}
z
{\displaystyle z}
L
{\displaystyle L}
512
<=
L
<=
1024
{\displaystyle 512<=L<=1024}
L
{\displaystyle L}
Pasirenkamas
h
{\displaystyle h}
1
<
h
<
p
−
1
{\displaystyle 1<h<p-1}
g
=
h
∗
z
m
o
d
p
>
1
{\displaystyle g\ =\ h*z\ mod\ p>1}
Pasirenkamas atsitiktinai sugeneruota skaičių x kuris tenkintu sąlyga
0
<
x
<
q
{\displaystyle 0<x<q}
Suskaičiuojamas
y
=
g
∗
x
m
o
d
p
{\displaystyle y=\ g*x\ mod\ p}
Viešas raktas yra
(
p
,
q
,
g
,
y
)
{\displaystyle (p,q,g,y)}
x
{\displaystyle x}
Generuojama atsitiktinė žinutė, kurios reikšmė k būtų
0
<
k
<
q
{\displaystyle 0<k<q}
Suskaičiuojama
r
=
(
g
k
m
o
d
p
)
m
o
d
q
{\displaystyle r\ =\ (g^{k}\ mod\ p)\ mod\ q}
Suskaičiuojama
s
=
(
k
−
1
(
S
H
A
−
1
(
m
)
+
x
∗
r
)
)
m
o
d
q
{\displaystyle s\ =\ (k^{-1}\ (SHA-1(m)\ +\ x*r))\ mod\ q}
S
H
A
−
1
(
m
)
{\displaystyle SHA-1(m)}
santraukos funkcija taikoma žinutei
m
{\displaystyle m}
Perskaičiuojam parašą mažai tikėtinu atveju kai
r
=
0
{\displaystyle r=0}
s
=
0
{\displaystyle s=0}
Parašas yra
(
r
,
s
)
{\displaystyle (r,s)}
Atmesti parašą jei netenkinama bent viena iš sąlygų
0
<
r
<
q
{\displaystyle 0<r<q}
0
<
s
<
q
{\displaystyle 0<s<q}
Suskaičiuojama
w
=
s
−
1
m
o
d
q
{\displaystyle w\ =s^{-1}\ mod\ q}
Suskaičiuojama
u
1
=
(
S
H
A
−
1
(
m
)
∗
w
)
m
o
d
q
{\displaystyle u_{1}\ =\ (SHA-1(m)*w)\ mod\ q}
Suskaičiuojama
u
2
=
(
r
∗
w
)
m
o
d
q
{\displaystyle u_{2}\ =\ (r*w)\ mod\ q}
Suskaičiuojama
v
=
(
(
g
u
1
∗
y
u
2
)
m
o
d
p
)
m
o
d
q
{\displaystyle v\ =\ ((g^{u_{1}}*y^{u_{2}})\ mod\ p)\ modq}
Parašas galioja jeigu tenkinama lygybe
v
=
r
{\displaystyle v=r}
