ElGamal is a public key encryption method, and which has a public key (\(P,G,Y\)) and a private key (\(x\)). The following will encrypt a value using ElGamal:
ElGamal Encryption |
Theory
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 \pmod 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 \pmod p\)
\(b=y^k M \pmod p\)
Bob then receives these and decrypts with:
\(M=\frac{b}{a^x} \pmod p\)
This works because \(\frac{b}{a^x} \pmod p = \frac{y^k M}{ {(g^k)}^x } \pmod p = \frac{{(g^x)}^k M}{ {(g^k)}^x } \pmod p = = \frac{g^{xk} M} { g^{xk} } \pmod p = M \)
Code
An outline of the code is:
import libnum import random import sys def getG(p): for x in range (1,p): rand = x exp=1 next = rand % p while (next != 1 ): next = (next*rand) % p exp = exp+1 if (exp==p-1): return rand M=5 p=1009 if (len(sys.argv)>1): M=int(sys.argv[1]) if (len(sys.argv)>2): p=int(sys.argv[2]) g=getG(p) x=random.randint(1,p) Y= pow(g,x,p) k=random.randint(1,p) a=pow(g,k,p) b=(pow(Y,k,p)*M) %p message = (b * libnum.invmod(pow(a,x,p),p)) % p print("\nBob Private key (x)=",x) print("Bob picks g=",g) print("Bob computes Y=",Y) print("Bob Public key (P,g,Y)=",p,g,Y) print("\nMessage=",M) print("Alice select random k=",k) print("\n\nCipher=",a,b) print("\nDecrypt=",message)
A sample run is:
Bob Public key (P,g,Y)= 1009 11 945 Bob Private key (x)= 780 Message= 300 Alice random k= 329 Cipher= 440 432 Decrypt= 300