🚀 go-pugleaf

rcain@netcom.com (Robert Cain) asks:

>>Is there a good description of ElGamal available by ftp from anywhere?

Don't know an FTP source, but it's not all that difficult:

Let p be a large prime (say 512 to 1024 bits), and g a generator of the
multiplicative group of units in the finite field Zp (the integers mod
p).  In other words g is an element of order p-1:  g^(p-1) = 1 mod p,
but no smaller exponent satisfies this congruence.

(Actually, we could choose any element g of sufficiently large order,
rather than a generator; this is useful in improving the efficiency of
signature schemes without significantly comproming security.  See the
NIST DSA explained below, for example.  But lets stick with a true
generator of the full group for the moment; they're no harder to find.
BTW, all this can just as easily be done over any finite field, but I'll
stick to the prime ones for simplicity.)

Now Alice chooses a private key a in the range 1 < a < p, computes her
public key g^a, and sends it to Bob.  If Bob has a message M in the
range 1 < M < p, he can encrypt it for Alice by choosing a (secret)
random k and computing:

    c = g^k mod p
    d = (g^(ak) * M) mod p

He discards k and sends the pair [c,d] to Alice as the ciphertext.
(Note the doubling of message size!)  Now Alice, knowing a may compute:

    c^(-a) * d = M mod p

There's actually more than one way to do this, but the point is that no
one can strip the g^(ak) factor from d to recover M without knowing
either Alice's secret key a or Bob's random number k.

Several digital signature schemes have been based on this variation of
the Diffie-Hellman key exchange protocol.  ElGamal's original suggestion
was to sign M, 1 < M < p, as folows:

    1. choose a secret random k relatively prime to p-1
    2. compute r = g^k mod p
    3. compute s = (M - ar) * k^-1 mod p-1

Alice sends [M,r,s] to Bob.  Bob takes Alice's public key y = g^a and
checks that

    y^r * r^s = g^M mod p

If this equation holds, [r,s] is indeed Alice's signature on M (since
step 3 required knowledge of the secret key a, only Alice could have
sent it).

See:  A public key cryptosystem and a signature scheme based on discrete
logarithms, IEEE Trans.  Info.  Theory, July 1985.

In 1989, Schnorr proposed a more efficient scheme based on taking g to
be an element of large, but not maximal, order in Zp.  The Digital
Signature Standard proposed by NIST (Federal Register, Aug.  30, 1991)
is a variation on this idea:

Let p be a large prime with 2^511 < p < 2^512, q a large prime factor of
p-1 with 2^159 < q < 2^160, and g and element of Zp* of order q.  Then,
to sign M with the private key a:

    1. choose a secret random k relatively prime to q-1
    2. compute r = g^k mod p mod q
    3. compute s = (M + ar) * k^-1 mod q

Alice sends [M,r,s] to Bob who uses her public key y = g^a to check
whether

    r = ( g^(M*s^-1) * y^(r*s^-1) mod p ) mod q

I'll leave it to you to check that this can only happen if it was really
Alice.  :-)

All of these "proofs" are really just simple applications of Fermat's
little theorem--computing mod q-1 in the exponent in this case; very
similar to the proof that RSA decryption inverts encryption.

Michael

----------
  Michael J. Markowitz, VP R&D      markowitz@dockmaster.ncsc.mil
  Information Security Corp.        708 405-0500, fax: 708 405-0506
  1141 Lake Cook Rd., Suite D       MCI:  363-1959
  Deerfield, IL  60302              CIS: 76206,2617