Cryptography Reference
In-Depth Information
Diffie - Hellman or ElGamal method (see next section), which have not been
covered by patents since 1997.
Fortunately, this is all history now; the only thing you should be aware of
when using public-key algorithms in data communication with the USA are
continually relaxing export regulations.
The ElGamal Method
While the RSA algorithm can presumably be cracked by factoring large num-
bers, the ElGamal method is based on the difficulty of computing discrete
logarithms, i.e., determining the value of
x
from
y=a
x
mod n
with known base
a
and module
n
. This method has two distinct benefits versus
RSA:
1. People who can compute discrete logarithms have also won an algorithm
for factoring large numbers. Theoretically, it is not more insecure than
RSA.
2. In contrast to RSA, ElGamal is not patented, but the PKP patent man-
agement thinks it is covered by the Diffie - Hellman patent in the USA.
This patent expired on April 29, 1997. By the time you read these lines,
ElGamal will presumably be the first non-patented asymmetric algorithm.
After the number-theory preparations above, it is no longer difficult to explain
the algorithm.
We choose a prime number,
p
, as our module, and a base,
g
. Both are part of
the public key. (
p
−
1
)/
2 should also be a prime number. The private key is a
secret exponent,
x<p
. We also publish remainder
y
with
y=g
x
mod p.
So, the
public key
consists of three numbers: prime number
p
, base
g
, and
remainder
y
. The
secret key
,
x
, is the discrete logarithm of
y
to base
g
with
