With ElGamal encryption [1], Bob selects 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\) so that \(a=g^k \pmod p\) and \(b=y^k M \pmod p\). Bob then receives these (\(a\) and \(b\)), and then uses his private key (\(x\)) to decrypt the values and discover the message: \(M=\frac{b}{a^x} \pmod p\).
ElGamal using Bouncy Castle and C# |
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 (\(a\) and \(b\)), and then uses his private key (\(x\)) to decrypt the values and discover the message:
\(M=\frac{b}{a^x} \pmod p\)
Finding a safe generator (\(g\))
Now, we can't just use any base generator value of \(g\), and which must be a primitive root of \(p\). For this, we start with our prime (\(p\)), and then the order of the group will be \(p-1\). We can then factorize \(p-1\) into prime factors. For example, if \(p=97\), we have \(p-1=96\), and which can be factorized with \(2\times 2 \times 2 \times 2 \times 2 \times 3\). The prime factors of this are thus 2 and 3. We then check that \(g^x \pmod p\) for all these prime factors and make sure the result is not 1.
Code
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);
The full code is:
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(serializedKey2)); } catch (Exception e) { Console.WriteLine("Error: {0}",e.Message); } } } }
A sample run for a 256-bit key pair is:
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:p>
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 [DER parse]:
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”.
A talk with Taher ElGamal:
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 [here].