Cryptography Reference
In-Depth Information
Alice
Bob
1. choose
p
= 29
2. choose α = 2
3. choose
d
= 12
4.
d
β
=
α
≡
7 mod 29
)=(29
,
2
,
7)
←−−−−−−−−−−−−
(
p
,
α
,
β
compute
signature
for
message
x
= 26:
choose
k
E
= 5,
note
that
gcd(5
,
28)=1
r
=
k
E
2
5
α
≡
≡
3 mod 29
dr
)
k
−
1
E
s
=(
x
−
≡
(
−
10)
·
17
≡
26 mod 28
(
x
,
(
r
,
s
))=(26
,
(3
,
26))
←−−−−−−−−−−−−
verify:
t
=
r
r
s
7
3
3
26
β
·
≡
·
≡
22 mod 29
x
≡
2
26
≡
22 mod 29
α
x
t
≡
α
⇒
mod 29 =
valid signature
10.3.2 Computational Aspects
The key generation phase is identical to the set-up phase of Elgamal encryption,
which we introduced in Sect. 8.5.2. Because the security of the signature scheme
relies on the discrete logarithm problem,
p
needs to have the properties discussed
in Sect. 8.3.3. In particular, it should have a length of at least 1024 bits. The prime
can be generated using the prime-finding algorithms introduced in Sect 7.6. The
private key should be generated by a true random number generator. The public key
requires one exponentiation using the square-and-multiply algorithm.
The signature consists of the pair (
r
,
s
). Both have roughly the same bit length
as
p
, so that the total length of the package (
x
,
(
r
,
s
)) is about three times as long
as only the message
x
. Computing
r
requires an exponentiation modulo
p
, which
can be achieved with the square-and-multiply algorithm. The main operation when
computing
s
is the inversion of
k
E
. This can be done using the extended Euclidean
algorithm. A speed-up is possible through precomputing. The signer can generate
the ephemeral key
k
E
and
r
in advance and store both values. When a message is to
be signed, they can be retrieved and used to compute
s
. The verifier performs two
exponentiations that are again computed with the square-and-multiply algorithm,
and one multiplication.
