Cryptography Reference
In-Depth Information
The ElGamal Method
Creating keys
:
•
Choose a large prime number,
p
(e.g., 512 or 1024 bits long), for which
(
p
−
1
)/
2 is also a prime number. Let
p
be
N
bits long.
•
Choose a base,
g<p
.
•
Choose a secret exponent,
x<p
.
g
x
•
Compute
y
=
mod
p
.
•
p
,
g
, and
y
form the public key,
x
forms the private key.
Encryption
:
•
Decompose the plaintext into blocks of
N
−
1 bits each (the last block may
have to be padded).
•
Choose a
k<p
that is relatively prime to
p
1.
k
must remain secret. It can
be created by a program and discarded after use.
−
•
For each block,
m
, compute two numbers,
a
and
b
, as follows:
a=g
k
b = y
k
m mod p
mod p
and
The two numbers,
a
and
b
, form two ciphertext blocks of length
N
.
Decryption
:
•
Decompose the ciphertext into
N
-bit blocks.
•
For two consecutive
a
-and-
b
blocks, solve the equation
a
x
m = b mod p
toward
m
(using the generalized Euclidean algorithm).
m
is the plaintext
looked for.
Figure 4.18:
Asymmetric encryption by the ElGamal method.
