Basic El Gamal for message encryption.

To set up El Gamal we want to choose a large prime and a generator.

>	p := nextprime(rand(1..10^35)());

>	p := 27419669081321110693270343633073797;

p =

In order to find a generator, we want to factor p-1.

>	ifactor(p-1);

We see that p-1 has 3 primes in its factorization.

>	q1 := 2: q2 := 23: q3 := 298039881318707724926851561229063:

To test if x is a generator, we check that the order of x does not divide (p-1)/q for each prime q that factors p.

>	gentest := x ->    [Power(x,(p-1)/q1) mod p, Power(x,(p-1)/q2) mod p,     Power(x,(p-1)/q3) mod p]:

>	gentest(2); gentest(3); gentest(5);

Thus we see that 2, 3, and 5 are generators of Z_p.  Let alpha = 5.

>	alpha := 5;

Now we choose a secret exponent a, and compute beta = alpha^a. and publish (p, alpha, beta)

>	a := rand(10..p-10)();

>	a := 8121769181099576933380904991576322;

>	beta := Power(alpha, a) mod p;

We now publish our public key, [p, alpha, beta].

>	publicKey := [p, alpha, beta];

To send the message "fred", Bob first turns the message into a number.  (He uses the simple rule turning a to 01, b to 02, ..., z to 26.)

>	message := 6180504;

Bob then randomly chooses k1 and computes r1 and t1 which are sent to us

>	k1 := rand(10..p-10)();

>	k1 := 4642553004401863428498260672540153;

>	r1 := Power(alpha,k1) mod p;

>	t1 := (Power(beta,k1) mod p)*(message) mod p;

>	sent := [r1,t1];

We decrypt in the usual fashon and recogn1ze the message as fred.

>	received := sent[2]*(Power(1/sent[1],a) mod p) mod p;

El Gamal for digital signatures

Suppose instead of receiving the mesage fred in secret, we want to send the message "fred" signed.

Recall the public key and the private key a.

>	myTotKey := [p, alpha, beta, a];

We choose a random k2

>	k2 := rand(10..p-10)();

>	k2 := 5248972213589823234356031982495167;

We want k2 to be relatively prime to p-1, so we find the gcd and divide it out.

>	comFact := igcd(k2, p-1); k2 := k2/comFact;

Compute r2 and s2.

>	r2 := Power(alpha, k2) mod p;

>	s2 := (message - r2*a)/k2 mod (p-1);

I send (message, r2, s2).

>	signed := [message,r2, s2];

To verify, I compute v1 and v2 and see they are the same.

>	v1 := (Power(beta,signed[2]) mod p)*       (Power(signed[2],signed[3]) mod p) mod p;

>	v2 := Power(alpha, message) mod p;

Finding elements of high order

There is an obvious catch if the use of El Gamal as described above.  To find a generator of Z_p, we need to factor p-1.  But for El Gamal to be secure p should be big enough that factoring p-1 is not a tractible problem.  To fix this problem, it should be noted that we don't really need a generator, we simply need an element of large order.  A solution is to collect the small factors of p-1.  Anything raised to that power will have an order diving the remaining large factor of p-1.

Consider how this works with a prime of 200 digits.

>	p := nextprime(rand(1..10^200)());

>	p:= 79490457039169594160088430571674960498834085812920457916453747019461644031395307920624947349951053530086146486307198155590763466429392673709525428510973272600608981219760099374675982933766845473509941:

We first find the product of primes less than 1000.  These will be the small factors we eliminate.

>	smallPrimes := 2: test := 2: while (test < 1000) do test := nextprime(test): smallPrimes := smallPrimes*test: od: smallPrimes;

Using the gcd, we remove all the small prime factors of p-1.

>	k := p-1: comFact := igcd(smallPrimes, k): while (comFact > 1) do k := k/comFact; comFact := igcd(smallPrimes, k): od: k;

>	removedFactors := (p-1)/k;

Now any element x^removedFactors will have order dividing k,

>	alpha := Power(2, removedFactors) mod p;

With high probability, alpha has order k.

>