Cryptography Reference
In-Depth Information
the RSA signature scheme with appendix.
We close this section with a description and discussion of the first DSS rec-
ognized by any government. In August of 1991, NIST proposed the
Digital
Signature Standard
(DSS) and in May of 1994, it became FIPS 186, (see [91]).
Although this evolved into a new standard in the twenty-first century, for sim-
plicity, we present the original standard here, (see [92] for the current DSS,
which uses key sizes of 1024 bits or
more
).
Digital Signature Algorithm (DSA — the DSS)
Setup Stage
:
1. Alice selects a prime
q
with 160 bits. Then she selects a prime
p
with
bitlength a multiple of 64 between 512 and 1024, satisfying the property
that
q
divides
p
−
1.
∈
F
p
of order
q
modulo
p
. This can be done, for instance,
by selecting a primitive root
a
modulo
p
and setting
α
2. She chooses an
α
a
(
p
−
1)
/q
(mod
p
).
≡
F
q
→
B
160
(bitstrings of length 160) is
selected. She chooses a private key
e
3. A cryptographic hash function
h
:
∈
N
such that
e<q
and computes
α
e
(mod
p
).
β
≡
4. She publishes (
p, q, α, β
) and keeps private her key
e
.
Signing Stage
: Alice performs the following in order to sign a message
∈
F
q
. In what follows, we will assume that any powers of
α
or
β
have been
reduced modulo
p
before being used in any congruence modulo
q
:
m
1. Select a random
r
∈
N
such that
r
≤
q
−
1.
α
r
(mod
q
).
2. Compute
γ
≡
r
−
1
(
h
(
m
)+
eγ
) (mod
q
).
3. Compute
σ
≡
4. Alice sends
m
and sig
k
(
m, r
)=(
γ,σ
) to Bob.
Verification Stage
: Bob executes the following steps:
1. Obtain Alice's public data (
p, q, α, β
).
σ
−
1
h
(
m
) (mod
q
) and
δ
2
≡
σ
−
1
γ
(mod
q
).
2. Compute
δ
1
≡
α
δ
1
β
δ
2
(mod
q
).
3. Compute
δ
≡
4. ver
k
(
m,
(
γ,σ
)) = 1 if and only if
δ
≡
γ
(mod
q
), in which case Bob accepts,
and rejects otherwise.
a given transmission medium. In other words, it is the speed of data on a given transmission
path, usually measured in Mbps (see Footnote 3.11, page 160).
Search WWH ::
Custom Search