          Copyright (c) mjh-EDV Beratung, 1996-1999
     mjh-EDV Beratung - 63263 Neu-Isenburg - Rosenstrasse 12
          Tel +49 6102 328279 - Fax +49 6102 328278
                Email info@mjh.teddy-net.com

    Author: Jordan Hrycaj <jordan@mjh.teddy-net.com>

   $Id: README.PUB-KEY-ALGO,v 1.1 1999/10/18 22:31:39 jordan Exp $

   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Library General Public
   License as published by the Free Software Foundation; either
   version 2 of the License, or (at your option) any later version.

   This library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Library General Public License for more details.

   -----------------------------------------------------------------

Generating a primitive element for a prime module
=================================================

For El Gamal, I need a large prime p, and a generator or primitive element 
g for the cyclic group generated by the multiplicative group of p.  So, I 
set for some q, r and s,

	p := q * r * s + 1

where q is a large prime, and r,s are small primes, or 1.  Then, for g being
a generator it is sufficient that the powers

         qr               qs                   rs
	g  != 1 (mod p), g   != 1 (mod p) and g   != 1 (mod p).
	

Note: It is just convenient chosing primes r and s, so that they can be
      represented by a short number in C.  Also, g is chosen small so 
      that it can be held by an int number in C.


The algorithm goes as follows:
------------------------------

1	repeat at most TRY_GENERATE_PRIME_MODULE times

1.1	      repeat at most TRY_RANDOM_IS_PRIME times

1.1.1		   generate an odd large random number q

1.1.2		   continue with 1.1 if q is composite

1.1.3		   repeat at most TRY_PRIME_HAS_GENERATOR times

1.1.3.1		        get random numbers r,s small primes or 1

1.1.3.2			continue with 1.1.3, if both r and s are 1

1.1.3.3			continue with 1.1.3, if qrs+1 is composite

1.1.3.4			otherwise, set p := qrs+1, so p is a prime

1.1.3.5			for g running through the integers 2 ... UINT_MAX

1.1.3.5.1		   continue with 1.1.3.5 if g^rs == 1 (mod p)

1.1.3.5.2		   continue with 1.1.3.5 if g^qr == 1 (mod p)
 
1.1.3.5.3		   continue with 1.1.3.5 if g^qs == 1 (mod p)

1.1.3.5.4		   stop: g is primitive element

1.1.3.5                 end for 1.1.3.5

1.1.4              end repeat 1.1.3

1.2           end repeat 1.1

2	end repeat 1

3       stop: algorithm failed


While the algorithm is running, you see the software printing some
message, letters and periods, as explained below:


   	Generating primes: ...............q..........pg
	
                                          ^          ^^
                                          |          ||
found large prime q in step 1.1.3 --------+          ||
                                                     ||
found some prime qrs+1 in step 1.1.3.4 --------------+|
                                                      |
found some generator g in step 1.1.3.5.4 -------------+


When the algorithm restarts with step 1.1 or 1.1.3, it prints a semicolon, 
advances to a new line and produces a similar output.  The outer loop 1 is 
not really necessare and due to the current implementation, only.


Generating a large prime
========================

It is done by choosing large odd random numbers and testing, whether they
satisfy the prime condition.  Testing is done by two steps: a quick test
against a table of all small primes less than 5000, and the probabilistic
Miller Rabin test if the quick test did not prove the number composite.

When the latter test succeeded, the number is a prime with some error
probabilty smaller than than 2^(-PRIME_PROBABBILTY_WEIGHT).  The parameter
PRIME_PROBABBILTY_WEIGHT is set in peks-internal.h.



The El Gamal public key scheme
==============================

Use a large prime p and a primitive element g (mod p). Choose a secret 
number a. The server holds the private key.

Private key: (p, g, a)
                                   a
Public key:  (p, g, u) where u == g  (mod p)

Now, let us look at the encryption handshake between a server (the private 
key owner) and a client. The purpose of that handshake is the trusted 
transmission of a message m (mod p) from the client to the server.

Server : sends (p, g, u) to the client

Client:  chooses a secret number b and sends (v, w) to the server
         where 
                      b                       b
                v == g  (mod p) and w == m * u   (mod p)

Server:  the server calculates m as

                 -a         -ba       ab 
                v   * w == g   * m * g   == m (mod p)
                
and that's it.  The hypothesis behind is just the intractability of
calculating the number a (mod p) when g^a (mod p) is known, only.



The El Gamal signature scheme for client authentication:
========================================================

Here we use El Gamal signature variations as listed in table 11.5 from 
A. Menezes, P.van Oorschot, S. Vanstone (Eds.), "Handbook of Applied  
Cryptography", CRC Press 1997, ISBN 0-8493-8523-7, pg 457 ff.  We refer 
to the line numbers from that table to distinguish the variations, below.


Use a large prime p and a primitive element g (mod p). Choose a secret 
number a. The client holds the private key.


Private key: (p, g, a)
                                   a
Public key:  (p, g, u) where u == g  (mod p)


Client:  sends (p, g, u) to the server


Server:  checks whether the public key belongs to the client, then
	 a random text m chosen and sent to the client


Client:  chooses a secret number b relatively prime to p-1 (so b has an
         inverse (mod p-1)) and sends (v, w) to the server where 

                      b
                v == g  (mod p) (mod p) and for

         variation 1 (basic scheme):

                                 -1
                w == (m - a v) b   (mod p-1) or for

         variation 3:

                w == (mb + av) (mod p-1)


Server: the server accepts the signature if for

         variation 1 (basic scheme):

                  v   w      m
                u   v   == g   (mod p) or for

         variation 3:

                  v   m      w
                u   v   == g   (mod p)

         holds.


References:

	Bruce Schneier; Applied Cryprography; NY, Wiley & Sons, 2nd ed 1996
	ISBN 0-471-11709-9

	D.R. Stinson; Cryptography; Boca Raton, CRC Press 1995, 
	ISBN 0-8493-8521-0

	A. Menezes, P.van Oorschot, S. Vanstone  (Eds.): Handbook of Applied 
	Cryptography, CRC Press 1997, ISBN 0-8493-8523-7

jordan