El Gamal \302\2512007 by Mike May, S.J., Saint Louis University - maymk@slu.edu This worksheet walks through the use of El Gamal as a public key cryptographic system. restart;

To set up El Gamal we want to choose a large prime and a generator. As we explain first the system we will consider 40 digits to be large. p := nextprime(rand(1..10^40)()); p := 9574006709478958762709029785327385064807; So that we can work through the details in a specified case, we record the randomly chossen prime. p = 9574006709478958762709029785327385064807 In order to find a generator, we want to factor p-1. ifactor(p-1); We see that p-1 has 4 primes in its factorization. q1 := 2: q2 := 281: q3 := 16308979029992991981149389: q4 := 1044553377367: Recall, that any non-zero element of Z_p has order diving p-1. Thus 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, Power(x,(p-1)/q4) mod p]: gentest(2); gentest(3); gentest(4); gentest(5); gentest(6); Thus we see that 5 is a generator of Z_p. On the other hand, 2, 3, 4, and 6 are not generators, since all of them are 1 when raised to the (p-1)/2 power. Let alpha = 5. alpha := 5; Now we choose a secret exponent a, and compute beta = alpha^a. We want a to me large enough that alpha^a > p. We then publish (p, alpha, beta). a := rand(10..p-10)() mod p; a := 665638090635425982769337333168305062441; 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 which will be a masking factor. He then multiplies the message by the masking factor to obtain t1. k1 := rand(10..p-10)(); k1 := 5770340561146791077936963751366381722372; r1 := Power(alpha,k1) mod p; mask := (Power(beta,k1) mod p); t1 := mask*(message) mod p; Bob then sends us r1 and t1. sent := [r1,t1]; The point is that knowing r1 and a we can compute the masking factor, and thus compute the message without knowing k1. We decrypt in the usual fashion and recognize the message as fred. mask := Power(sent[1],a) mod p; unmask := 1/mask mod p; received := sent[2]*unmask mod p; received := sent[2]*(Power(1/sent[1],a) mod p) mod p;

1) Create an ElGamal public key with a 40 digit prime p. Explain what to publish, what to keep, and what to destroy. 2) Using the a -> 01, b -> 02 system encrypt your first name with your key. Verify that you can decrypt the message.

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 tractable 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:= 49092794627888614255232373736117193164171421985688796368074091155696787430503083082176177443020795272627379157872689335824741100361162299037843630497047192441682770986659188372406293774691775639610223; p; 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.

3) Randomly choose a 150 digit prime p. Find an element x whose order is at least 120 digits. 4) Give the order of x from the previous problem and explain how you know the order.

A second approach is to look for a prime where most of the length of (p-1) comes from a single prime. Thus we want p = m*q + 1 with q a large prime. Since p must be odd, m should be even. To make this clearer we want p = 2*k*q+1 We will try to find a 160 digit prime where (p-1) has a 150 digit prime factor. We first find the 150 digit factor. q := nextprime(rand(10^150)()); q := 570170002864821574510234060543580382783581286336601875642247683287655801078873785196700208430867701262233956192871410733840082367395866562897286138387; We next start on k, randomly picking a number in the right range, and then testing primality until we get a k that has p being prime. k := rand(10^9..4*10^9)(); k := 3335626851; p:= 2*k*q + 1: while (not(isprime(p))) do k := k+1: p := 2*k*q + 1: end do: print(p); print(isprime(p), k, ifactor(k)); In this case p-1 has 3 factors, q and the small factors 2, and k.

5) Find a 180 digit prime p where p-1 has a 170 digit factor. 6) Find a generator alpha for p.

JSFH

7) Using the prime and generator from the last exercise, produce an ElGamal key. Publish the public key on the bulletin board. 8) Use someone else's key to encrypt a short message. 9) When someone sends you a message, decrypt the message, and post the decryption. Use the other person's public key to post a response.

Legal Notice: The copyright for this application is owned by the author(s). Neither Maplesoft nor the author are responsible for any errors contained within and are not liable for any damages resulting from the use of this material. This application is intended for non-commercial, non-profit use only. Contact the author for permission if you wish to use this application in for-profit activities.