Encryption with ElGamal

Almost every working day, I have the privilege to work in a place that once hosted one the greats: John Napier. It was John who discovered…

Encryption with ElGamal

Almost every working day, I have the privilege to work in a place that once hosted one the greats: John Napier. It was John who discovered logarithms, and showed that g^a times g^b is g^(a+b), and that g^a divided by g^b is g^(a-b). In our modern world, we use this type of method so often in our cryptography implementation, and it often provides the core around privacy-enhancing methods (such as with Zero-Knowledge Proof and Anonymisation). As our numbers become very large, though, we often define them within a finite field (Z_p), and where we select a large prime number (p), and then perform all our operations with the magic of the (mod p) operation.

I think if John Napier were alive today he would wonder at how discrete logarithms have been used to secure our world. 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 which became the core of the DSA signature method). In 2009, Elgamal was award the RSA Conference 2009 Lifetime Achievement Award and where he was dubbed the “father of SSL”:

ElGamal method

At its core of the ElGamal public key method is the Discrete Logarithm Problem, and where we have:

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, and also encrypt data. 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 encryption, we use the public key to encrypt, and the private key to decrypt.

With ElGamal, initially, Bob creates his public key by selecting a g value and a prime number (p) and then generating his private key (x). He then computes Y as [here]:

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:

Bob then receives these and decrypts with:

This works because:

You can try this here.

GPG and ElGamal

It was Phil Zimmerman who created the PGP (Pretty Good Privacy), and which has advanced to the GNU Privacy Guard (GPG). Overall GPG is a program that is based on OpenPGP and can generate key pairs, encrypt and decrypt data, along with digitally sign files and verify digital signatures. For public key encryption of data, we can use RSA or ElGamal. With this, Bob can encrypt with Alice’s public key, and then she can decrypt the ciphered message with her private key.

We can generate an RSA key pair with (and where we store the key with a given real name and an associated email address):

input_data = gpg.gen_key_input(key_type="RSA", key_usage='encrypt', 
   key_length=1024,passphrase=password,name_real=user,name_email=email)

For ElGamal encryption, we define a subkey type of “ELG-E”:

input_data = gpg.gen_key_input(key_type="RSA",subkey_type="ELG-E",
   key_usage='encrypt',key_length=1024,subkey_length=1024,passphrase=password,name_real=user,name_email=email)

With a message we can then encrypt with:

enc_data = gpg.encrypt(message,email)
print ("Encrypt:\n",str(enc_data).replace(chr(13),''))

This gives an Armor message of:

Next, we can decrypt this with:

ver = gpg.decrypt(str(enc_data),passphrase=password)
print ("Decrypted:\n",ver)

The following is the code [here]:

import gnupg
import sys
gpg = gnupg.GPG(gnupghome="c:\\gpg")
enc="rsa-1024"
password="password"
user="Fred Bloggs"
email="[email protected]"
message="Hello"
if (len(sys.argv)>1):
   enc=str(sys.argv[1])
if (len(sys.argv)>2):
  password=str(sys.argv[2])
if (len(sys.argv)>3):
  user=str(sys.argv[3])
if (len(sys.argv)>4):
  email=str(sys.argv[4])
if (len(sys.argv)>5):
  message=str(sys.argv[5])
if (enc=="elg-1024"):
 input_data = gpg.gen_key_input(key_type="RSA",subkey_type="ELG-E",key_usage='encrypt',key_length=1024,subkey_length=1024,passphrase=password,name_real=user,name_email=email)
elif (enc=="elg-2048"):
 input_data = gpg.gen_key_input(key_type="RSA",subkey_type="ELG-E",key_usage='encrypt',key_length=2048,subkey_length=2048,passphrase=password,name_real=user,name_email=email)
elif (enc=="rsa-1024"):
 input_data = gpg.gen_key_input(key_type="RSA",key_usage='encrypt',key_length=1024,passphrase=password,name_real=user,name_email=email)
elif (enc=="rsa-2048"):
 input_data = gpg.gen_key_input(key_type="RSA",key_usage='encrypt',key_length=2048,passphrase=password,name_real=user,name_email=email)
elif (enc=="rsa-3072"):
 input_data = gpg.gen_key_input(key_type="RSA",key_usage='encrypt',key_length=3072,passphrase=password,name_real=user,name_email=email)
else:
 print ("Can't find key type")
key = gpg.gen_key(input_data)
fp = key.fingerprint

print ("Key ID:\t\t",fp) 
print ("Type:\t\t",enc)
print ("Email:\t\t",email)

print ("Message:\t",message)
enc_data = gpg.encrypt(message,email)
print ("Encrypt:\n",str(enc_data).replace(chr(13),''))

ver = gpg.decrypt(str(enc_data),passphrase=password)
print ("Decrypted:\n",ver)

print("\n\n\n")
ascii_armored_public_keys = gpg.export_keys(fp)
print("Public key (used to encrypt):\n",ascii_armored_public_keys.replace(chr(13),''))
ascii_armored_private_keys = gpg.export_keys(fp,True,passphrase=password)
print("Private key (used to decrypt):\n",ascii_armored_private_keys.replace(chr(13),''))
print("Private key deleted: ",gpg.delete_keys(fp,True,passphrase=password))
print("Public key deleted: ",gpg.delete_keys(fp))

In the following we use 1,024 bit ElGamal encryption [here]:

Key ID:		 564C560A5EF9FE3DF1CFF93F340A7C59C4256127
Type:		 elg-1024
Email:		 [email protected]
Message:	 Hello, how are you?
Encrypt:
 -----BEGIN PGP MESSAGE-----
hQEOA7aAyFn1TsRNEAP/Z9mafT3V/0Wmqql0WBpyrmVvKbRJGeKQYxQtCMACjPiP
PUUU0GceMaj4oLX+6JDVJNVBSoUXKg/fy6kX5k79qbtsKdfAV93AMRLEcgqk+sis
dCNMpuFjBYBcy/CBRIgPOxCGr657BevTkrKjNVqrUCQYU7uZQlAfemxCk76TL/YE
AIk/xG+VF+BlxGH9vT34K1p9PdDBgx6xm1DQTbmj820fmaYS6ijQ03on314X4geZ
0O+vvPmkPUm9Pzd8XmYc4irD+9Tm88kdHM7Y6yGYFc6TSSUAbxLIWCjp4HbWBPg6
qVWZe74mrEksa9eXs0Gokw99uXwd3ksEK5kszE3eiUda1FgBCQIQe3AQSVd378SV
jOjaAKBo2v1CIuJwuntesEDK71SiCtM3cGL26gkGrjapplgA0jXj/ANLfSkph5tY
kf9svxDNKSm6T/g28nHzSO3QZr1b3ymOvF9t
=nSbD
-----END PGP MESSAGE-----
Decrypted:
 Hello, how are you?

Public key (used to encrypt):
 -----BEGIN PGP PUBLIC KEY BLOCK-----

mI0EY+3NtQEEALp2YB2RWWND/zH/FWeHM+Oqj332afsUH29CPMgKw7mGRBjHeSph
U6GGj8br+l8SKz7IlkwjKdmCloq6wOiCYWGh7MAJVf1I7VdYV4MlNcCR5s6YqYcA
ssZujpho8J9a+cspzUjcOvdHYZpf+vJ9G/FGbGEqFTzdpBzyKgadlGHdABEBAAG0
G0ZyZWQgQmxvZ2dzIDxmcmVkQGhvbWUuY29tPojRBBMBCAA7FiEEVkxWCl75/j3x
z/k/NAp8WcQlYScFAmPtzbUCGw0FCwkIBwICIgIGFQoJCAsCBBYCAwECHgcCF4AA
CgkQNAp8WcQlYSdFTQP/ZS4GhS5FlR5Su5czFJTtXgL6QE1T7G3YIswbQoybs0mB
S3wlaoxuJAvWI4L0CStksPq0tTxOJPSILZDK5ODCIpZ231JwA8aNzZulwljSXl+3
ZQyxY0GBIkZEl1vTXArtVddw/Prf5twrEW4+9hGOiHVW1FAwZlxsD+JGa7H/oTO5
AQ0EY+3NtRAEAKVfhXlhKk9JYr/KH6spM1cyqCboSoSdgdFXSSqIYH3KHehecV4u
9Edmb0ObGJA3qZE/9GXEShp4wg0ixQBVYdoBPpQ5VCd+Add5oYoKS9YuOXTsJk4P
7fB6Fe+/ITej1EyFTAnCR2FANXLqzlvfsiiSYp5F9QEHDAUa7m1K0J5HAAQLA/9B
muDTYuG+lWlqkw/8fz7hYXVNn71VhrXv9LM3hNa0Pd3gxmmiufchyh8+MhXaso5L
Wu0AKHB2jwwLPmKoLXhWLOaAQhUrZVNTzjzkXsvZM3eeIsU/EK2B/wDxQqTTt4xe
Wn8ZjyXKv6n03vK59F//RZTTqxv4TPwtoSwcJaLMsYi2BBgBCAAgFiEEVkxWCl75
/j3xz/k/NAp8WcQlYScFAmPtzbUCGwwACgkQNAp8WcQlYSeOrgP/f7lbxLNMeqCx
vBBqpuImQvBK6PlbrDoKYshNlrm0vC27w/c92Gl/IzPaHI0gNrLGEfe7REFLhDFk
wn6qX49GSlBQYSkNlyrseCGeQN7NgoedYQSHVACu/k6soj9ROe1aD76dnvqZT2Ff
EKzTLT3aNp5yvakX9Qhrix0wFvT6zLk=
=OvBs
-----END PGP PUBLIC KEY BLOCK-----
Private key (used to decrypt):
 -----BEGIN PGP PRIVATE KEY BLOCK-----
lQIGBGPtzbUBBAC6dmAdkVljQ/8x/xVnhzPjqo999mn7FB9vQjzICsO5hkQYx3kq
YVOhho/G6/pfEis+yJZMIynZgpaKusDogmFhoezACVX9SO1XWFeDJTXAkebOmKmH
ALLGbo6YaPCfWvnLKc1I3Dr3R2GaX/ryfRvxRmxhKhU83aQc8ioGnZRh3QARAQAB
/gcDAm6cjdqc3rETylAbIDTtdJ/UVW4btDVqvQh/ul2HtimKvkZL5BQdet1A7ltr
KW83IKHR6b6NwInJjgvGP6QjUXrr+Wg5tybOn0BGA5fA8CTnxr4d2ju86mHv+5+a
h3wnhIOmVr87Q1C3PXD7z9eK/JYON5NS0vW2Ia+CLPpzkSYAuIVxxKkmHPbI4O7a
ryzHjIllZIh+irMht5rC9DMFcstXGChXeMmV/1duPJV2GDODHDB58bd1uKjz0FQY
2dq182tRwrY2ruCLSeKASz+jDory7bgdzyc4HXMfnUATC9++KE4u7fqSUKbCnKv+
kqhzbelvMdXXDTW3LzOKDxBVnbAZ9j11n76o9HWu5nvx44WEqzpSkQ6yQ+wr9T3R
ZT1Mno+f9mq6O+2FrIvs6qo0usqyKQiuIIvaESLKquDNR4mUVZM4C/D964vFAas6
VGwc0nGsPxhHMxZt3AwxBcq5cWd6K6uivqPYzt9hWlcjhqVTrN2zCiO0G0ZyZWQg
QmxvZ2dzIDxmcmVkQGhvbWUuY29tPojRBBMBCAA7FiEEVkxWCl75/j3xz/k/NAp8
WcQlYScFAmPtzbUCGw0FCwkIBwICIgIGFQoJCAsCBBYCAwECHgcCF4AACgkQNAp8
WcQlYSdFTQP/ZS4GhS5FlR5Su5czFJTtXgL6QE1T7G3YIswbQoybs0mBS3wlaoxu
JAvWI4L0CStksPq0tTxOJPSILZDK5ODCIpZ231JwA8aNzZulwljSXl+3ZQyxY0GB
IkZEl1vTXArtVddw/Prf5twrEW4+9hGOiHVW1FAwZlxsD+JGa7H/oTOdAWAEY+3N
tRAEAKVfhXlhKk9JYr/KH6spM1cyqCboSoSdgdFXSSqIYH3KHehecV4u9Edmb0Ob
GJA3qZE/9GXEShp4wg0ixQBVYdoBPpQ5VCd+Add5oYoKS9YuOXTsJk4P7fB6Fe+/
ITej1EyFTAnCR2FANXLqzlvfsiiSYp5F9QEHDAUa7m1K0J5HAAQLA/9BmuDTYuG+
lWlqkw/8fz7hYXVNn71VhrXv9LM3hNa0Pd3gxmmiufchyh8+MhXaso5LWu0AKHB2
jwwLPmKoLXhWLOaAQhUrZVNTzjzkXsvZM3eeIsU/EK2B/wDxQqTTt4xeWn8ZjyXK
v6n03vK59F//RZTTqxv4TPwtoSwcJaLMsf4HAwKDzLq48fc1HsryHRlr0Ita0obq
M95qx2ogtFurfnVwnPjEITXbkGeKKNe84iR2cWrEcINQuam9mQ7WUBPHUpWwTaxD
ZkTfC3gmlsTKhkSJiLYEGAEIACAWIQRWTFYKXvn+PfHP+T80CnxZxCVhJwUCY+3N
tQIbDAAKCRA0CnxZxCVhJ46uA/9/uVvEs0x6oLG8EGqm4iZC8Ero+VusOgpiyE2W
ubS8LbvD9z3YaX8jM9ocjSA2ssYR97tEQUuEMWTCfqpfj0ZKUFBhKQ2XKux4IZ5A
3s2Ch51hBIdUAK7+TqyiP1E57VoPvp2e+plPYV8QrNMtPdo2nnK9qRf1CGuLHTAW
9PrMuQ==
=lvMk
-----END PGP PRIVATE KEY BLOCK-----
Private key deleted:  ok
Public key deleted:  ok

If we check the key for its type we get [here]:

Conclusion

While RSA is the most widely used method for encrypting with public key, ElGamal provides additional attributes, such as in the application of homomorphic encryption. While it was created in 1985, it is still relevant these days, so don’t automatically dismiss it.