Search Results for “digital signature algorithm”

Source: Digital Signature Algorithm

The Digital Signature Algorithm (DSA) is a public-key cryptosystem and Federal Information Processing Standard for digital signatures, based on the mathematical concept of modular exponentiation and the discrete logarithm problem. In a public-key cryptosystem, two keys are generated: data can only be encrypted with the public key and encrypted data can only be decrypted with the private key. DSA is a variant of the Schnorr and ElGamal signature schemes.: 486
The National Institute of Standards and Technology (NIST) proposed DSA for use in their Digital Signature Standard (DSS) in 1991, and adopted it as FIPS 186 in 1994. Five revisions to the initial specification have been released. The newest specification is: FIPS 186-5 from February 2023. DSA is patented but NIST has made this patent available worldwide royalty-free. Specification FIPS 186-5 indicates DSA will no longer be approved for digital signature generation, but may be used to verify signatures generated prior to the implementation date of that standard.

Overview

algorithm

History

Operation

algorithm

signature

= 1. Key generation

algorithm

and

N
≤

|

H

|

{\displaystyle N\leq |H|}

. FIPS 186-4 specifies

L

{\displaystyle L}

and

N

{\displaystyle N}

to have one of the values: (1024, 160), (2048, 224), (2048, 256), or (3072, 256).
Choose an

N

{\displaystyle N}

-bit prime

q

{\displaystyle q}

.
Choose an

L

{\displaystyle L}

-bit prime

p

{\displaystyle p}

such that

p
−
1

{\displaystyle p-1}

is a multiple of

q

{\displaystyle q}

.
Choose an integer

h

{\displaystyle h}

randomly from

{
2
…
p
−
2
}

{\displaystyle \{2\ldots p-2\}}

.
Compute

g
:=

h

(
p
−
1
)

/

q

mod

p

{\displaystyle g:=h^{(p-1)/q}\mod p}

. In the rare case that

g
=
1

{\displaystyle g=1}

try again with a different

h

{\displaystyle h}

. Commonly

h
=
2

{\displaystyle h=2}

is used. This modular exponentiation can be computed efficiently even if the values are large.
The algorithm parameters are (

p

{\displaystyle p}

,

q

{\displaystyle q}

,

g

{\displaystyle g}

). These may be shared between different users of the system.

Per-user keys

Given a set of parameters, the second phase computes the key pair for a single user:

Choose an integer

x

{\displaystyle x}

randomly from

{
1
…
q
−
1
}

{\displaystyle \{1\ldots q-1\}}

.
Compute

y
:=

g

x

mod

p

{\displaystyle y:=g^{x}\mod p}

.

x

{\displaystyle x}

is the private key and

y

{\displaystyle y}

is the public key.

= 2. Key distribution

=
The signer should publish the public key

y

{\displaystyle y}

. That is, they should send the key to the receiver via a reliable, but not necessarily secret, mechanism. The signer should keep the private key

x

{\displaystyle x}

secret.

= 3. Signing

=
A message

m

{\displaystyle m}

is signed as follows:

Choose an integer

k

{\displaystyle k}

randomly from

{
1
…
q
−
1
}

{\displaystyle \{1\ldots q-1\}}

Compute

r
:=

(

g

k

mod

p

)

mod

q

{\displaystyle r:=\left(g^{k}{\bmod {\,}}p\right){\bmod {\,}}q}

. In the unlikely case that

r
=
0

{\displaystyle r=0}

, start again with a different random

k

{\displaystyle k}

.
Compute

s
:=

(

k

−
1

(

H
(
m
)
+
x
r

)

)

mod

q

{\displaystyle s:=\left(k^{-1}\left(H(m)+xr\right)\right){\bmod {\,}}q}

. In the unlikely case that

s
=
0

{\displaystyle s=0}

, start again with a different random

k

{\displaystyle k}

.
The signature is

(

r
,
s

)

{\displaystyle \left(r,s\right)}

The calculation of

k

{\displaystyle k}

and

r

{\displaystyle r}

amounts to creating a new per-message key. The modular exponentiation in computing

r

{\displaystyle r}

is the most computationally expensive part of the signing operation, but it may be computed before the message is known.
Calculating the modular inverse

k

−
1

mod

q

{\displaystyle k^{-1}{\bmod {\,}}q}

is the second most expensive part, and it may also be computed before the message is known. It may be computed using the extended Euclidean algorithm or using Fermat's little theorem as

k

q
−
2

mod

q

{\displaystyle k^{q-2}{\bmod {\,}}q}

.

= 4. Signature Verification

=
One can verify that a signature

(

r
,
s

)

{\displaystyle \left(r,s\right)}

is a valid signature for a message

m

{\displaystyle m}

as follows:

Verify that

0
<
r
<
q

{\displaystyle 0
and

0
<
s
<
q

{\displaystyle 0
.
Compute

w
:=

s

−
1

mod

q

{\displaystyle w:=s^{-1}{\bmod {\,}}q}

.
Compute

u

1

:=
H
(
m
)
⋅
w

mod

q

{\displaystyle u_{1}:=H(m)\cdot w\,{\bmod {\,}}q}

.
Compute

u

2

:=
r
⋅
w

mod

q

{\displaystyle u_{2}:=r\cdot w\,{\bmod {\,}}q}

.
Compute

v
:=

(

g

u

1

y

u

2

mod

p

)

mod

q

{\displaystyle v:=\left(g^{u_{1}}y^{u_{2}}{\bmod {\,}}p\right){\bmod {\,}}q}

.
The signature is valid if and only if

v
=
r

{\displaystyle v=r}

.

Correctness of the algorithm

The signature scheme is correct in the sense that the verifier will always accept genuine signatures. This can be shown as follows:
First, since

g
=

h

(
p
−
1
)

/

q

mod

p

{\textstyle g=h^{(p-1)/q}~{\text{mod}}~p}

, it follows that

g

q

≡

h

p
−
1

≡
1

mod

p

{\textstyle g^{q}\equiv h^{p-1}\equiv 1\mod p}

by Fermat's little theorem. Since

g
>
0

{\displaystyle g>0}

and

q

{\displaystyle q}

is prime,

g

{\displaystyle g}

must have order

q

{\displaystyle q}

.
The signer computes

s
=

k

−
1

(
H
(
m
)
+
x
r
)

mod

q

{\displaystyle s=k^{-1}(H(m)+xr){\bmod {\,}}q}

Thus

k

≡
H
(
m
)

s

−
1

+
x
r

s

−
1

≡
H
(
m
)
w
+
x
r
w

(
mod

q
)

{\displaystyle {\begin{aligned}k&\equiv H(m)s^{-1}+xrs^{-1}\\&\equiv H(m)w+xrw{\pmod {q}}\end{aligned}}}

Since

g

{\displaystyle g}

has order

q

{\displaystyle q}

we have

g

k

≡

g

H
(
m
)
w

g

x
r
w

≡

g

H
(
m
)
w

y

r
w

≡

g

u

1

y

u

2

(
mod

p
)

{\displaystyle {\begin{aligned}g^{k}&\equiv g^{H(m)w}g^{xrw}\\&\equiv g^{H(m)w}y^{rw}\\&\equiv g^{u_{1}}y^{u_{2}}{\pmod {p}}\end{aligned}}}

Finally, the correctness of DSA follows from

r

=
(

g

k

mod

p
)

mod

q

=
(

g

u

1

y

u

2

mod

p
)

mod

q

=
v

{\displaystyle {\begin{aligned}r&=(g^{k}{\bmod {\,}}p){\bmod {\,}}q\\&=(g^{u_{1}}y^{u_{2}}{\bmod {\,}}p){\bmod {\,}}q\\&=v\end{aligned}}}

Sensitivity

With DSA, the entropy, secrecy, and uniqueness of the random signature value

k

{\displaystyle k}

are critical. It is so critical that violating any one of those three requirements can reveal the entire private key to an attacker. Using the same value twice (even while keeping

k

{\displaystyle k}

secret), using a predictable value, or leaking even a few bits of

k

{\displaystyle k}

in each of several signatures, is enough to reveal the private key

x

{\displaystyle x}

.
This issue affects both DSA and Elliptic Curve Digital Signature Algorithm (ECDSA) – in December 2010, the group fail0verflow announced the recovery of the ECDSA private key used by Sony to sign software for the PlayStation 3 game console. The attack was made possible because Sony failed to generate a new random

k

{\displaystyle k}

for each signature.
This issue can be prevented by deriving

k

{\displaystyle k}

deterministically from the private key and the message hash, as described by RFC 6979. This ensures that

k

{\displaystyle k}

is different for each

H
(
m
)

{\displaystyle H(m)}

and unpredictable for attackers who do not know the private key

x

{\displaystyle x}

.
In addition, malicious implementations of DSA and ECDSA can be created where

k

{\displaystyle k}

is chosen in order to subliminally leak information via signatures. For example, an offline private key could be leaked from a perfect offline device that only released innocent-looking signatures.

Implementations

Below is a list of cryptographic libraries that provide support for DSA:

Botan
Bouncy Castle
cryptlib
Crypto++
libgcrypt
Nettle
OpenSSL
wolfCrypt
GnuTLS

References

External links

FIPS PUB 186-4: Digital Signature Standard (DSS), the fourth (and current) revision of the official DSA specification.
Recommendation for Key Management -- Part 1: general, NIST Special Publication 800-57, p. 62–63