The El-Gamal Cryptosystem and Discrete Logarithms

1.  The discrete logarithm problem:  where p is a prime, g is a primitive
element mod p, and a is any residue mod p, find i such that g^i mod p = a.
i is the "discrete logarithm" of a to the base g mod p.

The idea is that exponentiations g^i are easy to compute (square and
multiply, as before) but the inverse operation of finding logarithms
is difficult.

2.  To thwart known attacks, p should have at least 150 digits and 
p-1 should have at least one large prime factor.

3.  El Gamal cryptosystem:

Let p be a suitable prime and let g be a primitive element mod p.  (Query:
how can we reliably identify primitive elements mod p?  The factorization
of p-1 seems to be necessary to do this efficiently).

The key takes the form (p,alpha, a, beta), where beta = alpha^a mod p.
The values p, alpha and beta are public, while the value a is secret.

Given this key, a secret random number k < p-1, encrypt a message x
as the pair (y1,y2) where

y1 = alpha^k mod p, 

y2 = x(beta^k) mod p

Decrypt a ciphertext (y1,y2) by computing y2/(y1^a) mod p.

x(beta^k)/alpha^(ka) = x(alpha^ak)/(alpha^ak) = x.

4.  To build an El Gamal key we need a suitable prime p, a primitive element
alpha mod p, and a power beta of alpha by an exponent we keep secret.

To find a primitive element, it is useful to have a factorization of
p-1 (small, so that we only need to test a few powers of g to see if
it is primitive).  Besides, our security requirements tell us that p-1
should have at least one large prime factor.

We will have some discussion later of methods of finding discrete logarithms.

The file elgamaltext.mws in the public directory demonstrates how this
is done.

Class Exercise:  Construct a public El Gamal key and mail it to me.


Signature Schemes:

In this world of untrusted communications, how do we make sure that
a message comes from the person we think it comes from?

Exercise in thought for the class:  using my public RSA key, is there
a way that I can produce a message which only I could in fact produce?

Class Exercise:  write a plaintext message and "sign" it using your RSA
public key, and send it to someone else in the class.  Recipients must
verify the authenticity of the message they receive.  Copy worksheets to me --
as always, do not include your decryption exponent in mail you send to me!

Another Class Exercise:  See if you can break anyone's key using the
   p-1 factoring algorithm.  Credit is available to anyone who succeeds.
   I have not so far, but I haven't run it for very long, either.

   Anyone may submit a new public key at any time.

The El Gamal Signature Scheme: