Crypto Magic: So What Does ElGamal Encryption Actually Look Like?

Crypto Magic: So What Does ElGamal Encryption Actually Look Like?

One of the highlights of my academic year is to talk with world leaders in cryptography, and Tahir ElGamal is a true leader:

His greatest academic contribution was the ElGamal encryption method, and which is being used by many applications for enhanced privacy and homomorphic operations. For this, Taher, 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.

And so we have Y, g, p for the public key, and r for the private key. Let’s now code with C#.

First we install the Bouncy Castle library:

dotnet add package BouncyCastle.Cryptography

For the generation of g and p for a given key size of s, we can use:

ElGamalParametersGenerator parGen = new ElGamalParametersGenerator();
parGen.Init(s, 10, new SecureRandom());
ElGamalParameters elParams = parGen.GenerateParameters();

Once we have the g and p parameters, we can generate the keys:

ElGamalKeyPairGenerator pGen = new ElGamalKeyPairGenerator ();
pGen.Init(new ElGamalKeyGenerationParameters(new SecureRandom(),elParams));
AsymmetricCipherKeyPair pair = pGen.GenerateKeyPair();

To encrypt, we use the public key (pair.Public):

ElGamalEngine cryptEng = new ElGamalEngine ();
cryptEng.Init(true, pair.Public);
byte[] data = Encoding.ASCII.GetBytes(str);
byte[] enc = cryptEng.ProcessBlock(data,0, data.Length);

and to decrypt, we use our private key (pair.Private):

ElGamalEngine decryptEng = new ElGamalEngine();
decryptEng.Init(false, pair.Private);
byte[] plain = decryptEng.ProcessBlock(enc,0,enc.Length);

Next some code [here]:

namespace ElGamal
{
using Org.BouncyCastle.Crypto;
using Org.BouncyCastle.Crypto.Engines;
using Org.BouncyCastle.Crypto.Parameters;
using Org.BouncyCastle.Security;
using Org.BouncyCastle.Crypto.Generators;
using System.Text;

    using Org.BouncyCastle.Asn1.Pkcs;
    using Org.BouncyCastle.Pkcs;
    using Org.BouncyCastle.X509;

    class Program
    {
        static void Main(string[] args)
        {

            string str="Hello";
            string size="256";

            
            if (args.Length >0) str=args[0];
            if (args.Length >1) size=args[1]; 

              int s = Convert.ToInt32(size);


            try { 

// Compute g, p
   ElGamalParametersGenerator parGen = new ElGamalParametersGenerator();

   parGen.Init(s, 10, new SecureRandom());
   ElGamalParameters elParams = parGen.GenerateParameters();

// Generate keypair
            ElGamalKeyPairGenerator pGen = new ElGamalKeyPairGenerator ();


            pGen.Init(new ElGamalKeyGenerationParameters(new SecureRandom(),elParams));


            AsymmetricCipherKeyPair pair = pGen.GenerateKeyPair();

// Encrypt

            ElGamalEngine cryptEng = new ElGamalEngine ();

            cryptEng.Init(true, pair.Public);

            byte[] data = Encoding.ASCII.GetBytes(str);

            byte[] enc = cryptEng.ProcessBlock(data,0, data.Length);

// Decrypt
            ElGamalEngine decryptEng = new ElGamalEngine();
            decryptEng.Init(false, pair.Private);
            byte[] plain = decryptEng.ProcessBlock(enc,0,enc.Length);

       


            Console.WriteLine("Plain: {0} ",str);
            Console.WriteLine("Plain: {0} ",Convert.ToBase64String(enc));
            Console.WriteLine("\nDecrypted: {0}" ,System.Text.Encoding.UTF8.GetString(plain));

            PrivateKeyInfo k = PrivateKeyInfoFactory.CreatePrivateKeyInfo(pair.Private);
            byte[] serializedKey = k.ToAsn1Object().GetDerEncoded();

    Console.WriteLine("\n== Key parameters ==");
     Console.WriteLine("G: {0}",elParams.G);
          Console.WriteLine("P: {0}",elParams.P);

              Console.WriteLine("\n== Keys ==");
              Console.WriteLine("Key size: {0}",size);

            Console.WriteLine("Private key: {0}",Convert.ToHexString(serializedKey));

          byte[] serializedKey2 = SubjectPublicKeyInfoFactory.CreateSubjectPublicKeyInfo(pair.Public).ToAsn1Object().GetDerEncoded();
          Console.WriteLine("Public key: {0}",Convert.ToHexString(serializedKey));
            
              } catch (Exception e) {
                Console.WriteLine("Error: {0}",e.Message);
            }

        }
    }
}

A sample run for a 256-bit key pair is [here]:

Plain: Hello 
Plain: PdP6OcI0vCUqZo4cBbcJ1DdJjjbufXifno5jeXlFzPYuxakZ8wivpVuxG4WxM8Mn7rEuU/8GT39cl/Vfb/nRuQ== 

Decrypted: Hello

== Key parameters ==
G: 49391246408797834108678101222037791267484305326785474540831508386999279353904
P: 105995669734486387650800091235700448872887161077526715453789035667703192939327

== Keys ==
Key size: 256
Private key: 3078020100304F06062B0E070201013045022100EA576C4D40FF3D9BC36D0510A894FCB172CE6181930C0AF7F2083C70BE18EB3F02206D32746DB241551C7FDDAD5FA5AB4505DBE0CB21E0E06FB7F3BF6D8D3D950030042202204A39790171EFA24A6C74A116819FDFD4B99458928DB9A2CC0E262BE19F9456DD
Public key: 3075304F06062B0E070201013045022100EA576C4D40FF3D9BC36D0510A894FCB172CE6181930C0AF7F2083C70BE18EB3F02206D32746DB241551C7FDDAD5FA5AB4505DBE0CB21E0E06FB7F3BF6D8D3D950030032200021F55AE0B5DD49DDB3FF0BF2999CC7DA9FB326B62019301C5B02BB6FF8C62BD2C

The private key is in a DER format, and which we can parse with [DER parse]:

and which gives [DER parse]:

DER: 3078020100304F06062B0E070201013045022100EA576C4D40FF3D9BC36D0510A894FCB172CE6181930C0AF7F2083C70BE18EB3F02206D32746DB241551C7FDDAD5FA5AB4505DBE0CB21E0E06FB7F3BF6D8D3D950030042202204A39790171EFA24A6C74A116819FDFD4B99458928DB9A2CC0E262BE19F9456DD

[U] SEQUENCE (30)
  [U] INTEGER (02): 0
  [U] SEQUENCE (30)
    [U] OBJECT (06): 1.3.14.7.2.1.1
    [U] SEQUENCE (30)
      [U] INTEGER (02): 105995669734486387650800091235700448872887161077526715453789035667703192939327
      [U] INTEGER (02): 49391246408797834108678101222037791267484305326785474540831508386999279353904
  [U] OCTET STRING: 0xb'02204A39790171EFA24A6C74A116819FDFD4B99458928DB9A2CC0E262BE19F9456DD'
  Private key:  02204a39790171efa24a6c74a116819fdfd4b99458928db9a2cc0e262be19f9456dd

We can see that the private key contains G and P, and also has the private key (0x02204…). It can be seen that the OID is “1.3.14.7.2.1.1”, and which identifies ElGamal encryption. For 1K keys, we have [here]:

Plain: Hello 
Plain: oyStf28IHEe2WG7l4ZziZCpAXw3DhKpJN4Ijig59311AwrCwhRJuM5gZIlkfcbAcHCcoin6mYEfwupXeZLTFW7opvk6FGmpGlUoWVDesRKxQjnYmH1US/M+jHi/CXldWVuTuDvwoUdb3+nddXg/LTDkHn5+CApJos19wtzqvR1tFrIohm/1sHbA3wkVosT1e9CVJMtNhmQhaz9vNW5Nos4Xs5J539rpsb5Lfx1yI9XRHgrkIprYepNhAj/ItoE1Bijsm2MavCh4N4m+AiM/gXra7yeKvtMcY3m5xIhVgpkP9JxMBySp7dT1OIMWNYdBCIaCrr9WqCgHU4a3KWQMBGQ==
Decrypted: Hello
== Key parameters ==
G: 114971720190027065729450982899330055900993796473970547174328753509261920234519125287068214758265755299651814112405960051753138676380229888208554042398484634457845282198970198346290756580221865559773778410810036104857366496103999602574920985407496627514569991436921466861776700825807346754103692506921446625095
P: 159241470748569150541176961469178573580994513702890306506627656262647293013156659703661553480896688346067035085423113643204078489870008741168415740391022583784165088046301664874928792959869037647531073300314103297067061394404624625927016438386859966576215991516694010565855938646274416040757492978664549431459
== Keys ==
Key size: 1024
Private key: 308201A10201003082011406062B0E070201013082010802818100E2C4731EE3784107C1CC5EC673D520ECCBEA844F9CB544156875A6C7194173AE2BDA4476E59EBCFC9874A9B38BBC88E6B3B6770EDB01879967CD0A21C912C9AE011BE33D1590D5440377F0DEC15A1149602EC7B0FCFB93A5F18582798F0BF7C8316EDD891B8E420EA0C367E2A92FBCE55AC637F00294795CE709D3ABFA04B8A302818100A3B9A45C6B0C51AE10921BAE7FFF5FD1C0E5E71A5D4E8FA848EBF3D1130E491C7D7B4B825F081A461AD00F3C72FBC2EE52A74D48430B918DC524B3647BDBCB023301E5DECB6F4F33323BEB6D8D3F77D7FEF324AF7A7307435CE2D55E8735CC67CE7A18D1FE438643F3F8C789D6340B7E88CDA9240D241B69ADA137DD7FCF4F4704818302818066D9EAC6BD8D247DDDBDE5D33EC64753A4222A8802AA388811C5C55DCB0F3A89D91368D2DEABC05063F6E365EEC03A92DFB87D72410C0B65D9544FBA207CA3DEFF721232EE4A74D4FDACE98E294131F6A7CCC63AA22D0F4BA2B9AD63D319E97AE15A00EC40BD9FCC3E43F2DA78F81FE4F63B598A3A34B46FF9513043F23E74B6
Public key: 308201A10201003082011406062B0E070201013082010802818100E2C4731EE3784107C1CC5EC673D520ECCBEA844F9CB544156875A6C7194173AE2BDA4476E59EBCFC9874A9B38BBC88E6B3B6770EDB01879967CD0A21C912C9AE011BE33D1590D5440377F0DEC15A1149602EC7B0FCFB93A5F18582798F0BF7C8316EDD891B8E420EA0C367E2A92FBCE55AC637F00294795CE709D3ABFA04B8A302818100A3B9A45C6B0C51AE10921BAE7FFF5FD1C0E5E71A5D4E8FA848EBF3D1130E491C7D7B4B825F081A461AD00F3C72FBC2EE52A74D48430B918DC524B3647BDBCB023301E5DECB6F4F33323BEB6D8D3F77D7FEF324AF7A7307435CE2D55E8735CC67CE7A18D1FE438643F3F8C789D6340B7E88CDA9240D241B69ADA137DD7FCF4F4704818302818066D9EAC6BD8D247DDDBDE5D33EC64753A4222A8802AA388811C5C55DCB0F3A89D91368D2DEABC05063F6E365EEC03A92DFB87D72410C0B65D9544FBA207CA3DEFF721232EE4A74D4FDACE98E294131F6A7CCC63AA22D0F4BA2B9AD63D319E97AE15A00EC40BD9FCC3E43F2DA78F81FE4F63B598A3A34B46FF9513043F23E74B6 

and now we can parse the public key [here]:

DER: 3075304F06062B0E070201013045022100EA576C4D40FF3D9BC36D0510A894FCB172CE6181930C0AF7F2083C70BE18EB3F02206D32746DB241551C7FDDAD5FA5AB4505DBE0CB21E0E06FB7F3BF6D8D3D950030032200021F55AE0B5DD49DDB3FF0BF2999CC7DA9FB326B62019301C5B02BB6FF8C62BD2C

[U] SEQUENCE (30)
  [U] SEQUENCE (30)
    [U] OBJECT (06): 1.3.14.7.2.1.1
    [U] SEQUENCE (30)
      [U] INTEGER (02): 105995669734486387650800091235700448872887161077526715453789035667703192939327
      [U] INTEGER (02): 49391246408797834108678101222037791267484305326785474540831508386999279353904
  [U] BIT STRING (03): 0xb'00021F55AE0B5DD49DDB3FF0BF2999CC7DA9FB326B62019301C5B02BB6FF8C62BD2C'
  Public key (1f55ae0b5dd49ddb3ff0bf2999cc7d, a9fb326b62019301c5b02bb6ff8c62bd2c)

We have a public key of “1f55ae0b5dd49ddb3ff0bf2999cc7d, a9fb326b62019301c5b02bb6ff8c62bd2c”.

Conclusions

And, there you, go … just crypto magic!