ElGamal Encryption with Elliptic Curves
Towards partial homomorphic encryption with elliptic curves
--
I think if John Napier were alive today he would wonder at how discrete logarithms have been used to secure our world. And, I am also sure he would strike up an immediate bond with Taher Elgamal and who, in 1985, published this classic paper [here]:
Within the paper, he proposed the ElGamal discrete logarithm encryption system and also the ElGamal signature scheme (and which became the core of the DSA signature method). In 2009, Elgamal was awarded the RSA Conference 2009 Lifetime Achievement Award, and where he was dubbed the “father of SSL”.
At the core of the ElGamal public key methods is the Discrete Logarithm Problem, and where we have:
Y= g^x (mod p)
and where it is difficult to determine x, even if we have Y, g and p (as long as p is a large enough prime number). And so it is used in the Diffie-Hellman method for key exchange. We also use it to sign a message, and where we create a key pair (a public key and a private key). The private key is used to encrypt something (such as the hash of the message), and then the public key is used to prove the signing.
With ElGamal, initially, Alice creates her public key by selecting a g value and a prime number (p) and then selecting a private key (x). She then computes Y which is [here]:
Her public key is (Y,g,p) and she will send this to Bob. Bob then creates a message (M) and selects a random value (r). She then computes a and b:
Bob then receives these and decrypts with:
Thus works as:
You can try this here.
ElGamal and ECC
But, Elliptic Curve Cryptography (ECC) methods are just everywhere just now. With ECC, we take points on a defined curve — such as Curve 25519 — and then perform point…
