The Beauty of the ElGamal Method: A Sage Implementation
One of the highlights of my academic year will be talking with Taher ElGamal:
Within the interview, he talks about how Len Adleman gave him a number of problems that needed to be solved, and where Taher just went ahead and tried lots of methods, and finally ended up with this mighty paper [here]:
It is a beautiful method, especially since it can now be used in homomorphic operations. So, let’s go ahead and implement it in Sage.
Initially, Bob creates his public key by selecting a g value and a prime number (p) and then selecting a private key (x). He then computes Y which is:
Y=g^x (mod p)
His public key is (Y,g,p) and he will send this to Alice. Alice then creates a message (M) and selects a random value (k). She then computes a and b:
a=g^k (mod p)
