ElGamal Encryption and Decryption[ElGamal Home][Home]
With ElGamal signing, Alice has a public key (\(Y,g,p\)) and a private key of \(x\). The public key is \(Y=g^x \pmod p\).
|
Outline
With ElGamal, Alice selects a generator (\(g\)), prime number of \(p\) and a private key of \(x\). Her public key is then (\(Y,g,p\)) and where \(Y\) is:
\(Y=g^x \pmod p\)
For Alice to encrypt for Bob, she takes the message (\(M\)) and converts it into an integer value (\(m\)). Next she uses Bob's public key, and generates a random number (\(k\)) and calculates:
\(a=g^k \pmod p\)
\(b=Y^k \times m \pmod p\)
This is the encrypted message. For Bob to decrypt, he uses his private key (\(x\)) to give:
\(m_{rec}=b \times {(a^x)}^{-1} \pmod p\)
We can then convert this integer value back into a string. This works because:
\(m_{rec}=b \times {(a^x)}^{-1} = Y^k.{{(g^k)}^x)}^{-1}.m = m.g^{xk}.g^{-kx} = m \pmod p\)
Coding
The coding is here:
from Crypto.Util.number import * from Crypto import Random import Crypto import random import libnum import sys import hashlib def primitive_root(p_val: int) -> int: while True: g = random.randrange(3, p_val) if pow(g, 2, p_val) == 1: continue if pow(g, p_val, p_val) == 1: continue return g bits=512 M="hello" if (len(sys.argv)>1): M=sys.argv[1] if (len(sys.argv)>2): bits=int(sys.argv[2]) p = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes) m = int.from_bytes(M.encode(),byteorder='big' ) g = primitive_root(p) x = random.randrange(3, p) Y = pow(g,x,p) print (f"Message:\nm={M}") print (f"Public key:\ng={g}\nY={Y}\np={p}\n\nPrivate key\nx={x}") k=random.randrange(3, p) a=pow(g,k,p) b=(pow(Y,k,p)*m) % p print (f"\nEncrypted\na={a}\nb={b}") M_recovered=(b*libnum.invmod(pow(a,x,p),p)) % p m_rec= int.to_bytes(M_recovered,len(M),byteorder='big' ) print ("\nResult: ",m_rec.decode() )
A sample run for 80-bit primes:
Message: m=hello Public key: g=73882849661946102475989 Y=6148958276472993757854 p=987831459342416188681949 Private key x=25393887831632137686747 Encrypted a=910505382921592948768722 b=249509736562872795126620 Result: hello
and for 256 bit primes:
Message: m=hello Public key: g=26034301491355787777162147912928940912000036589980782513766037632634436940606 Y=12515183918325666729243118235410285757154807838620882367310084434798669234194 p=96636896466728245857154692451827751320163228542555146228835153881023742679533 Private key x=26103460811980424767940113843457253784045210655665734277872851986797269694634 Encrypted a=58387224053962676728202168482903847337366063300776840909741084132886454580958 b=26292622147024715875348026959314030479887579551939946335705050279811842805615 Result: hello