ElGamal Encryption with the RFC 9500 Test Key Set

One of the highlights of my academic career has been talking with the mighty Tahir ElGamal, and who created the ElGamal encryption method…

ElGamal Encryption with the RFC 9500 Test Key Set

One of the highlights of my academic career has been talking with the mighty Tahir ElGamal, and who created the ElGamal encryption method. In this page, I will outline how ElGamal encryption works and outline a new set of test vectors within RFC 9500 [here].

Taher is one of the giants of cybersecurity, and his work on Netscape led to the creation of SSL. Along with this, he published this paper in 1985 [here]:

It was true classic and has been since been referenced over 12,500 times. Within the paper, Tahir outlined encryption and digital signature methods. His ‘base’ was to take John Napier’s logarithms and make them discrete. This discrete element meant that we only dealt with positive integer values and where we worked within a finite field. This field was defined by a prime number (p).

While the core ElGamal encryption method was overtaken in its usage by RSA, and then by ECC (Elliptic Curve Cryptography), the signature method was adopted as the Digital Signature Standard (DSS) by NIST. This has since scaled into ECC to become ECDSA, and which is used by Bitcoin and Ethereum.

Tahir studied electrical engineering at Stanford University in the late 1970s. It was there that he met Marty Hellman and who helped him spark an interest in cryptography. He received his PhD in 1984 and it was Marty who introduced him to Paul Kocker at Netscape Communications. Together, Paul and Tahir worked on a method to implement end-to-end encryption and published SSL 3.0 in November 1996.

Examples are at:

https://asecuritysite.com/elgamal

The ElGamal Method

Befre we start we need to look at some of the basics of logarithms and where:

{g^a}^b is g^{ab}

and:

g^a . g^b = g^{a+b}

To make these discrete to add (mod p) in our operations and where p is a prime number. This constrains our integrates with a finite field, between 0 and p-1.

In the ElGamal method, 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)

b=y^k.M (mod p)

Bob then receives these (a and b), and then uses his private key (x) to decrypt the values and discover the message:

M=b/(a^x) (mod p)

With the divide by (a^x) we basically take the inverse of (a^x) mod p, and then multiply. The operation works because:

RFC 5900

With ElGamal we have a public key (P,G,Y) and a private key (x). In Dec 2023 RFC 9500 [here] was published and defines RSA, DLP (Discrete Logarithm Problem) and ECDLP (Elliptic Curve DLP) keys for testing. With DLP, we have discrete log methods such as the Diffie-Hellman method and ElGamal, and with ECDLP, we have elliptic curve methods, such as for ECDH and ECDSA.

With this, we can specify g, x, and p, and then compute Y with:


p=0x030CDFC38FC3E4212790B0A41E45B4E4E880DE8ABFD3AECA0B238FB6CD730CC318769336D5B180B2802A01BE4BC1AB84FCE2FF489B50C2D29DE91EC0E65B6064FD0DE537EABA1C6CDD27DC3030481E8BB960AA8B8AEF933530E6B1CC5160BBFAAF850FF6578112337D53034E4163DC6503BDF8892581141FAB8255B6D9727BB3
q=0xEC41B9C0621D5BDCAF11D5198F7208882E65BBDF
g=0x016487ACCFCD955051E06E1C5BEF452C1263C75D2B36504FB4275735C283320B63AC91C6F4020932531CAB04B1CD72FDF29DE24E271797A7DD2197676931F9331D1F59EEE5BA2C7D54AE135C7F794137D8D80EB629288E268A3BEBD21F16A403F1D5DAD83C1C478017A3CD266F1BA49B890DC089212E72261DA367AF803B0250
x=0x11ED99785A813A1B0E96ECD38D7F9BCE9EBFD6FA

Y=pow(g,x,p)

The public key is then (Y,g,p) and the private key is x. Overall, it should be extremely difficult to determine x, even through we know Y, g and p. To encrypt, we convert the message into an integer(M), and then generate a random value (k). From this we compute the two cipher elements of a and b:

M=  bytes_to_long(msg.encode('utf-8')) 

k=random.randint(0,q)
a=pow(g,k,p)
b=(pow(Y,k,p)*M) % p

To decrypt, we take a, b and the private key (x):

 recovered=(b* pow(pow(a,x,p),-1,p)) %p

The full code is [here]:


import sys
from Crypto.PublicKey import DSA
from Crypto.Util.number import *
import random

msg="hello"
test=1


if (len(sys.argv)>1):
 msg=sys.argv[1]
if (len(sys.argv)>2):
 test=int(sys.argv[2])

try:
 M=  bytes_to_long(msg.encode('utf-8'))

 if (test==1):
     p=0x030CDFC38FC3E4212790B0A41E45B4E4E880DE8ABFD3AECA0B238FB6CD730CC318769336D5B180B2802A01BE4BC1AB84FCE2FF489B50C2D29DE91EC0E65B6064FD0DE537EABA1C6CDD27DC3030481E8BB960AA8B8AEF933530E6B1CC5160BBFAAF850FF6578112337D53034E4163DC6503BDF8892581141FAB8255B6D9727BB3
     q=0xEC41B9C0621D5BDCAF11D5198F7208882E65BBDF
     g=0x016487ACCFCD955051E06E1C5BEF452C1263C75D2B36504FB4275735C283320B63AC91C6F4020932531CAB04B1CD72FDF29DE24E271797A7DD2197676931F9331D1F59EEE5BA2C7D54AE135C7F794137D8D80EB629288E268A3BEBD21F16A403F1D5DAD83C1C478017A3CD266F1BA49B890DC089212E72261DA367AF803B0250 
     x=0x11ED99785A813A1B0E96ECD38D7F9BCE9EBFD6FA
 if (test==2):
     p=0x032DD5537D337A913437D35EA3433DB0E7B721298FBA8727F2F9BE856D6A146B92988D5082F2C572B7703763E82454A7A4A2259B29ACE9B0BC9B4B4D985D6A9C8CB630E4E09F48079F1BE8076971DE92685670B94CC9687DDC233B30AF2294B030A6B497F646F94E1C17E83A904C2C1B684410CE048FD9CD6405A14AA68C2B8F7F8BD06E9F64C4BB69CCBFBC8056AE414A8B2E35D6205CDEFB2A24A379B8A116175095FF57FF6155128686D99B8E1F2444631271F09C334F3722452FE9263FC3349E6F3307A6754FFD89D44327387DFD4018A02AEA6EF4C636A769E7CEB73719197249A841A30BE0C4BE8ECB107F3802DC4583F8E01294D52B621367BD0C1953
     q=0x019509B2EDA83B0882731B3FE89C2EF69DB8D83612345D1A66A583B911
     g=0xAC5D120E46D2BAD6878847CCE870A69EDCADC86C859C49BAF7ADE41ED9368EC23B6454FB60EADAACC6642A6FDD322B99AB147581B21BEBE06294E3820BC556FA5411B31C373B39A67D518A547713415C67ACEF18BC6BA94C95600CB5BDA83C84AD58E5491D26261ED4E535ADB22E35B06CC2B4C89DA2DC63E29EDA06F013807246558932E9F2DC8B932E6B84B407F571509D06F79430E95D46B2D02614288417999886A67145ED746A0CA8C0444103F503E6BBE74561C3ACD19AE57A8267A1BC3C493083BB16C597A8AC9981FB70458717FB649CA461D470B4B35E3E9864FA1A599BC01E6FE9930A51F579B084017425B8D0A1023FAEDDDC57D1CE56251CDA 
     x=0x6405BCDEB4F768290223CE5DB52A8A30C28ADC7802D9681EDCB434E5 

 Y=pow(g,x,p)

 k=random.randint(0,q)
 a=pow(g,k,p)
 b=(pow(Y,k,p)*M) % p

 recovered=(b* pow(pow(a,x,p),-1,p)) %p

 print("=== DSA Private key ===")
 print (f"p={hex(p)}\nq={hex(q)}\ng={hex(g)}\nx={hex(x)}")
 print (f"Y={hex(Y)}")


 print("\n===Encryption ===")
 print (f"\nMessage={msg} ({M})")
 print (f"cipher: a={a}\nb={b}\n")
 print (f"Decrypt={long_to_bytes(recovered).decode()}")

 print("\n=== Private Key PEM format ===")
 dsaKey = DSA.construct( (Y,g,p,q,x ) )
 pubKeyPEM = dsaKey.exportKey()
 print(pubKeyPEM.decode('ascii'))



 if (test==1):
  print("\n=== Importing PEM format ===")
  key=DSA.import_key("-----BEGIN DSA PRIVATE KEY-----\nMIIBuQIBAAKBgAMM38OPw+QhJ5CwpB5FtOTogN6Kv9Ouygsjj7bNcwzDGHaTNtWx\ngLKAKgG+S8GrhPzi/0ibUMLSnekewOZbYGT9DeU36rocbN0n3DAwSB6LuWCqi4rv\nkzUw5rHMUWC7+q+FD/ZXgRIzfVMDTkFj3GUDvfiJJYEUH6uCVbbZcnuzAhUA7EG5\nwGIdW9yvEdUZj3IIiC5lu98CgYABZIesz82VUFHgbhxb70UsEmPHXSs2UE+0J1c1\nwoMyC2Oskcb0AgkyUxyrBLHNcv3yneJOJxeXp90hl2dpMfkzHR9Z7uW6LH1UrhNc\nf3lBN9jYDrYpKI4mijvr0h8WpAPx1drYPBxHgBejzSZvG6SbiQ3AiSEuciYdo2ev\ngDsCUAKBgAIguULCXETaUrDRdoLqxDbqfoHsn3bhBXUyqmfq3QStuP1hgboLJfKE\n2qqqBfPIQDTUF9N7bgpjMYoKeR8dDdT2ivrjNapdvqPy9tbdcwkmJH/cTRuC34wt\nh66NNq253SUTV46LmapqDt9nX/wv3rZLJuW+2FMt/ZgRD8/J7fk4AhQR7Zl4WoE6\nGw6W7NONf5vOnr/W+g==\n-----END DSA PRIVATE KEY-----")
  print(f"P={hex(key.p)})")
  print(f"q={hex(key.q)})")
  print(f"g={hex(key.g)})")
  print(f"x={hex(key.x)})")
  print(f"y={hex(key.y)})")


except Exception as e:
    print(e)

And a sample run shows that the test vectors match [here]:

=== DSA Private key ===
p=0x30cdfc38fc3e4212790b0a41e45b4e4e880de8abfd3aeca0b238fb6cd730cc318769336d5b180b2802a01be4bc1ab84fce2ff489b50c2d29de91ec0e65b6064fd0de537eaba1c6cdd27dc3030481e8bb960aa8b8aef933530e6b1cc5160bbfaaf850ff6578112337d53034e4163dc6503bdf8892581141fab8255b6d9727bb3
q=0xec41b9c0621d5bdcaf11d5198f7208882e65bbdf
g=0x16487accfcd955051e06e1c5bef452c1263c75d2b36504fb4275735c283320b63ac91c6f4020932531cab04b1cd72fdf29de24e271797a7dd2197676931f9331d1f59eee5ba2c7d54ae135c7f794137d8d80eb629288e268a3bebd21f16a403f1d5dad83c1c478017a3cd266f1ba49b890dc089212e72261da367af803b0250
x=0x11ed99785a813a1b0e96ecd38d7f9bce9ebfd6fa
Y=0x220b942c25c44da52b0d17682eac436ea7e81ec9f76e1057532aa67eadd04adb8fd6181ba0b25f284daaaaa05f3c84034d417d37b6e0a63318a0a791f1d0dd4f68afae335aa5dbea3f2f6d6dd730926247fdc4d1b82df8c2d87ae8d36adb9dd2513578e8b99aa6a0edf675ffc2fdeb64b26e5bed8532dfd98110fcfc9edf938

===Encryption ===

Message=hello (448378203247)
cipher: a=718624607544348824114843109939777081636698910201327815419239459592200825716309375273697809580898212630615486560160913282647663325272931938560688272870144677691819038084276115498364788692216887870264105060662208792957685755140781978262341403194869524515404896545464994158674274656398727194775501417904891567
b=1688389900932357430739713987971253606732569951340070881392069934477880804477046813552444576954681684669782659254871781089443660828552795687198499552800464420527900509405845392635062399768805093061234925657410997805897053391569069231155687477639878213650360449866178012182084313707261274512859377096889658886

Decrypt=hello

=== Private Key PEM format ===
-----BEGIN PRIVATE KEY-----
MIIBSQIBADCCASoGByqGSM44BAEwggEdAoGAAwzfw4/D5CEnkLCkHkW05OiA3oq/
067KCyOPts1zDMMYdpM21bGAsoAqAb5LwauE/OL/SJtQwtKd6R7A5ltgZP0N5Tfq
uhxs3SfcMDBIHou5YKqLiu+TNTDmscxRYLv6r4UP9leBEjN9UwNOQWPcZQO9+Ikl
gRQfq4JVttlye7MCFQDsQbnAYh1b3K8R1RmPcgiILmW73wKBgAFkh6zPzZVQUeBu
HFvvRSwSY8ddKzZQT7QnVzXCgzILY6yRxvQCCTJTHKsEsc1y/fKd4k4nF5en3SGX
Z2kx+TMdH1nu5bosfVSuE1x/eUE32NgOtikojiaKO+vSHxakA/HV2tg8HEeAF6PN
Jm8bpJuJDcCJIS5yJh2jZ6+AOwJQBBYCFBHtmXhagTobDpbs041/m86ev9b6
-----END PRIVATE KEY-----

=== Importing PEM format ===
P=0x30cdfc38fc3e4212790b0a41e45b4e4e880de8abfd3aeca0b238fb6cd730cc318769336d5b180b2802a01be4bc1ab84fce2ff489b50c2d29de91ec0e65b6064fd0de537eaba1c6cdd27dc3030481e8bb960aa8b8aef933530e6b1cc5160bbfaaf850ff6578112337d53034e4163dc6503bdf8892581141fab8255b6d9727bb3)
q=0xec41b9c0621d5bdcaf11d5198f7208882e65bbdf)
g=0x16487accfcd955051e06e1c5bef452c1263c75d2b36504fb4275735c283320b63ac91c6f4020932531cab04b1cd72fdf29de24e271797a7dd2197676931f9331d1f59eee5ba2c7d54ae135c7f794137d8d80eb629288e268a3bebd21f16a403f1d5dad83c1c478017a3cd266f1ba49b890dc089212e72261da367af803b0250)
x=0x11ed99785a813a1b0e96ecd38d7f9bce9ebfd6fa)
y=0x220b942c25c44da52b0d17682eac436ea7e81ec9f76e1057532aa67eadd04adb8fd6181ba0b25f284daaaaa05f3c84034d417d37b6e0a63318a0a791f1d0dd4f68afae335aa5dbea3f2f6d6dd730926247fdc4d1b82df8c2d87ae8d36adb9dd2513578e8b99aa6a0edf675ffc2fdeb64b26e5bed8532dfd98110fcfc9edf938)

and for a 2,048-bit key [here]:

...
=== DSA Private key ===
p=0x32dd5537d337a913437d35ea3433db0e7b721298fba8727f2f9be856d6a146b92988d5082f2c572b7703763e82454a7a4a2259b29ace9b0bc9b4b4d985d6a9c8cb630e4e09f48079f1be8076971de92685670b94cc9687ddc233b30af2294b030a6b497f646f94e1c17e83a904c2c1b684410ce048fd9cd6405a14aa68c2b8f7f8bd06e9f64c4bb69ccbfbc8056ae414a8b2e35d6205cdefb2a24a379b8a116175095ff57ff6155128686d99b8e1f2444631271f09c334f3722452fe9263fc3349e6f3307a6754ffd89d44327387dfd4018a02aea6ef4c636a769e7ceb73719197249a841a30be0c4be8ecb107f3802dc4583f8e01294d52b621367bd0c1953
q=0x19509b2eda83b0882731b3fe89c2ef69db8d83612345d1a66a583b911
g=0xac5d120e46d2bad6878847cce870a69edcadc86c859c49baf7ade41ed9368ec23b6454fb60eadaacc6642a6fdd322b99ab147581b21bebe06294e3820bc556fa5411b31c373b39a67d518a547713415c67acef18bc6ba94c95600cb5bda83c84ad58e5491d26261ed4e535adb22e35b06cc2b4c89da2dc63e29eda06f013807246558932e9f2dc8b932e6b84b407f571509d06f79430e95d46b2d02614288417999886a67145ed746a0ca8c0444103f503e6bbe74561c3acd19ae57a8267a1bc3c493083bb16c597a8ac9981fb70458717fb649ca461d470b4b35e3e9864fa1a599bc01e6fe9930a51f579b084017425b8d0a1023faedddc57d1ce56251cda
x=0x6405bcdeb4f768290223ce5db52a8a30c28adc7802d9681edcb434e5
Y=0x23037b2d9c99e753fd279bffcdee9929c9ba1deaa970b0372af7335e55021374299f361027c8d65d57afb4d3ccd2b4724b53f09ebe28cbf499f6b4f863349198b24b2ab0d4cecb6c4fd7e672d4b2aca9d39e3ae20f8ecd7fd77107ce54a66ddee9744e48cf8dd6ba9a528c751f008c66f192a204ec7f93876910179b1311d975b4925c5699029fbd114a5e790190a4d389b948f8f576a8e45a56be0d4fd6cea631c5f537ef918598e30522f9364506618c04584ca6fd075121221a460f980c54f801d7d6d219df2a1dbea3c8a03a09f6be91bb6296d791a2a8380e89d0cdd26f7663e069a833149ad442b2c13988771f654b81f50e0d7264247d678eaebb0f9
a=0x187cbf4cc520e37916f43b41777a535cd425b2b19ed7b3e5bc806412b1e01b9b144dee105895bb38124be951bd1f17f7fe6b331efd657e0d20450554e711db28a496ef2847676bde0c930926bfcfb11e0af9d7603283d3d969c59e9ce751ea540b0c58689e9e45b742601fbcfa04258b772f76339d7d86770e8bc26ede4e4d4f9b95fb8bbaa101ea5c02083d3d91cef7e27370ea7765f0e8c95b30bca95ed95d8ebdca3db4f2d1f617a4773a3d579ee0ee490b7b1d86f0ff3b4ad6dfad40ed739c02a753b51c2acaa2b4c3c02c03b9d9c91bc62079ef9699c636b6aba6361ca9e0be264559375fbcf1bda7b76d8dedbe3f8c31883575c8ed8752c9f4142a4f3

b=0x18bb3ef7591138dbae4cba6a8b070d4488a62ef0ecb9f285698c9620b2eb5bfec5293ab21842ca0ebc1468b25541a6c5d4318c039087c414484ba66836d18c720d34456b234f043daea45a2c2f46011aacd1073b19244cebaa3eae0f08b024c76bc80852ed2b7d450040b152d7fa46a76562584f2e92ad5a44f1cdc0d0c52efe862c4c2ffac9633f4961a15a569fa0ee490a591151870f16d73218ff6f67155aa7af68bf02c0d94722ef7c142b1b3e82ac5670d07b5597bb9ed368fec6c86a98c1d99c0e820badfba0f86912aff729a5e40105d67b05c4ec7d246e0457041386b03cf2c48089af0f0aea1d2c5d7223f93c9606b548ad31c641a8b98c151211a


===Encryption ===

Message=hello (448378203247)
cipher=193202155521335760641306527726634239865543464836190630383640121189565496748140956103121577927684810942350518145779763242294318341650220439540840383442775250079615095264457251820155251260606697348566379017602984621410126665641743904657311225668194981086319661979753320252365945045811792426189679563775461692176941866833688535179148060681882210761857584939723633782355178318423401733041108803691094691999721178627498509729406620482408633843090681134940770483440933164917203034974720801149737356761363545342380929948093262578565615239656626731414110840412401365186230170193132619860982864876461110081350711468001240307,195128359016592704889753901422884833431063706204900654913680719799667285170022870986124292507022924680159942842299791967261642471509469121798810878858303102718856247062277036490799945275872269469434124130155560296008914523020815924831402678358178191738416049194695322135650426607768742267467277189034264418785030728275990098554884504732572324473772754408691719135240867630639190188231628815117353459646270744409422910333035826679259808112275501606967637657855215647091094192027815493587568843731779134185063747368761452054432836074749366318505687131964227341103878134524713988621982287392955093334173123388095144218

Decrypt=hello

=== Private Key PEM format ===
-----BEGIN PRIVATE KEY-----
MIICWwIBADCCAjQGByqGSM44BAEwggInAoIBAAMt1VN9M3qRNDfTXqNDPbDntyEp
j7qHJ/L5voVtahRrkpiNUILyxXK3cDdj6CRUp6SiJZsprOmwvJtLTZhdapyMtjDk
4J9IB58b6Adpcd6SaFZwuUzJaH3cIzswryKUsDCmtJf2RvlOHBfoOpBMLBtoRBDO
BI/ZzWQFoUqmjCuPf4vQbp9kxLtpzL+8gFauQUqLLjXWIFze+yoko3m4oRYXUJX/
V/9hVRKGhtmbjh8kRGMScfCcM083IkUv6SY/wzSebzMHpnVP/YnUQyc4ff1AGKAq
6m70xjanaefOtzcZGXJJqEGjC+DEvo7LEH84AtxFg/jgEpTVK2ITZ70MGVMCHQGV
CbLtqDsIgnMbP+icLvaduNg2EjRdGmalg7kRAoIBAACsXRIORtK61oeIR8zocKae
3K3IbIWcSbr3reQe2TaOwjtkVPtg6tqsxmQqb90yK5mrFHWBshvr4GKU44ILxVb6
VBGzHDc7OaZ9UYpUdxNBXGes7xi8a6lMlWAMtb2oPIStWOVJHSYmHtTlNa2yLjWw
bMK0yJ2i3GPintoG8BOAckZViTLp8tyLky5rhLQH9XFQnQb3lDDpXUay0CYUKIQX
mZiGpnFF7XRqDKjAREED9QPmu+dFYcOs0ZrleoJnobw8STCDuxbFl6ismYH7cEWH
F/tknKRh1HC0s14+mGT6GlmbwB5v6ZMKUfV5sIQBdCW40KECP67d3FfRzlYlHNoE
HgIcZAW83rT3aCkCI85dtSqKMMKK3HgC2Wge3LQ05Q==
-----END PRIVATE KEY-----

References

[1] ElGamal, T. (1985). A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE transactions on information theory, 31(4), 469–472.

[2] RFC 9500, https://datatracker.ietf.org/doc/rfc9500/