Week 7: Coding ElGamal Encryption and Running Tests

May 31, 2022

Hello everyone and welcome back to my blog!

This week I built off of some of the coding I had done for RSA encryption and coded ElGamal encryption and ran some tests which seemed to reveal more about the similarities and differences between ElGamal and RSA encryption.

When these algorithms are used in the real world, they are done with 1000 to 2000 bit primes, while the primes that I have generated are only about 13 digits long. I found that even with these small primes it would take typical methods (to try to break RSA, I tried the usual method of prime factorization of simply testing numbers smaller than N to see if they divide N) too long to break the encryption to be practical.

I also wrote code to show the maximum length of a message that either encryption algorithm can encrypt. If primes of about the same order of magnitude are generated for the 2 algorithms, RSA is able to encrypt message of about twice the length as ElGamal (because RSA uses 2 primes while ElGamal uses only 1).

ElGamal encryption also differs from RSA encryption in that it needs (or rather is greatly improved by generating) a primitive root modulo p (where p is the prime that was generated for encryption). This leads to interesting methods of generating “safe primes” specifically for use in ElGamal encryption. These primes are generated in such a way as to make finding a primitive root of them easier.

Leave a Reply