Cryptography Reference
In-Depth Information
while ((i <= noofprimes) && !EQONE_L (t_l));
}
while (EQONE_L (t_l));
return E_CLINT_OK;
}
As a second example for the application of exponentiation we consider the
encryption procedure of ElGamal, which as an extension of the Diffie-Hellman
procedure also provides security in the matter of the difficulty of computing
discrete logarithms, since breaking the procedure is equivalent to solving the
Diffie-Hellman problem (cf. page 119).
Pretty good privacy
(PGP), the workhorse
known throughout the world for encrypting and signing e-mail and documents
whose development goes back essentially to the work of Phil Zimmermann, uses
the ElGamal procedure for key management (see [Stal], Section 12.1).
A participant
A
selects a public and associated private key as follows.
ElGamal key generation
1.
A
chooses a large prime number
p
such that
p −
1
has a large prime divisor
close to
(
p −
1)
/
2
(cf. page 388) and a primitive root
a
of the multiplicative
group
Z
p
as above (cf. page 120).
2.
A
chooses a random number
x
with
1
≤ x<p−
1
and computes
b
:=
a
x
mod
p
with the aid of Montgomery exponentiation.
3.
As public key
A
uses the triple
p, a, b
A
, and the associated secret key is
p, a, x
A
.
p, a, b
A
a participant
B
can now encrypt a
Using the public key triple
message
M ∈{
1
,...,p−
1
}
and send it to
A
. The procedure is as follows.
Protocol for encryption à la ElGamal
1.
B
chooses a random number
y
with
1
1
.
2.
B
calculates
α
:=
a
y
mod
p
and
β
:=
Mb
y
mod
p
=
M
(
a
x
)
y
mod
p
.
≤
y<p
−
3.
B
sends the cryptogram
C
:= (
α, β
)
to
A
.
4.
A
computes from
C
the plain text using
M
=
β/α
x
modulo
p
.
Since
M
(
a
x
)
y
β
α
x
≡
β
(
a
x
)
y
≡
(
a
x
)
y
≡
M
mod
p,
the procedure works. The calculation of
β/α
x
is carried out by means of a
multiplication
βα
p
−
1
−
x
modulo
p
.
