ElGamal encryption and decryption but with bigger numbers

Earlier I blogged about implementing ElGamal encrypt, decrypt, sign, and verify signature. I had coded up a toy example which used small numbers to show how the math worked.

Now let’s do the same thing but with bigger numbers. We’ll just do encryption and decryption this time.

First we need a prime p. Before we used p = 101. This time we’ll use p = 2255 – 19:

> $p = [bigint]::pow(2, 255) - 19
> $p
5789604461865809771178549250434395392663499233282028201972879200395656481994

That’s nice and big.

Now we need a generator g. Last time we used g = 2. We’ll use it again, but make sure using Tonelli-Shanks that 2 is not a square mod p.

> cd tonelli-shanks
> .\tonelli-shanks.ps1 -p $p -n 2
Looking for r so that r^2 = 2 mod 57896044618658097711785492504343953926634992332820282019728792003956564819949
Skipping primality check since 57896044618658097711785492504343953926634992332820282019728792003956564819949 is large
r^2 = 2 mod 57896044618658097711785492504343953926634992332820282019728792003956564819949 has no solutions
> $g = [bigint]2
> $g
2

It’s important to do this check. If we had chosen g = 3, for example, the check would have failed, because 3 = 150298394704333910222651756369397732876262961010368454990880792759863347428352 mod 57896044618658097711785492504343953926634992332820282019728792003956564819949.

> .\tonelli-shanks.ps1 -p $p -n 3
Looking for r so that r^2 = 3 mod 57896044618658097711785492504343953926634992332820282019728792003956564819949
Skipping primality check since 57896044618658097711785492504343953926634992332820282019728792003956564819949 is large
57896044618658097711785492504343953926634992332820282019728792003956564819949 - 1 = 14474011154664524427946373126085988481658748083205070504932198000989141204987 * 2^2
2 is a nonsquare modulo 57896044618658097711785492504343953926634992332820282019728792003956564819949
Initial: m = 2, c = 19681161376707505956807079304988542015446066515923890162744021073123829784752, t = 1, r = 15029839470433391022265175636939773287626296101036845499088079275986334742835
Solutions:
15029839470433391022265175636939773287626296101036845499088079275986334742835^2 = 3 mod 57896044618658097711785492504343953926634992332820282019728792003956564819949
42866205148224706689520316867404180639008696231783436520640712727970230077114^2 = 3 mod 57896044618658097711785492504343953926634992332820282019728792003956564819949

So we use g = 2.

Now we need a recipient A. A needs a private key x which determines her public key gx mod p. Generate x at random between 0 (inclusive) and p (exclusive).

> cd random-biginteger
> .\random-biginteger.ps1 -min 0 -max $p
37472449428228375763830797714320932193767211994174601506224685902244496215115
> $x = [bigint]::Parse("37472449428228375763830797714320932193767211994174601506224685902244496215115")
> $x
37472449428228375763830797714320932193767211994174601506224685902244496215115
> $g_x = [bigint]::ModPow($g, $x, $p)
> $g_x
15440027450603317705548401356286425311467546169515779468886789260083908558514

We want to encrypt a message so that only A can read it, using her public key. So we need a plaintext message m. Generate m at random in similar fashion.

> .\random-biginteger.ps1 -min 0 -max $p
22594335182736179043379580066191528397421893149471409561964986373640506607991
> $m = [bigint]::Parse("22594335182736179043379580066191528397421893149471409561964986373640506607991")
> $m
22594335182736179043379580066191528397421893149471409561964986373640506607991

Now we’re ready to encrypt! Give the encryption routine the prime p, the generator g, the recipient’s public key gx, and the plaintext message m. It will return the ciphertext (c1, c2).

> cd elgamal
> .\encrypt.ps1 -prime $p -generator $g -recipientPublicKey $g_x -clearText $m
Encryptor chooses a random number k = 6095530983035662394415401229300894157247477933650052462284854503095419296799
Encryptor calculates the key K = (y = 15440027450603317705548401356286425311467546169515779468886789260083908558514)^(k = 6095530983035662394415401229300894157247477933650052462284854503095419296799) mod (p = 57896044618658097711785492504343953926634992332820282019728792003956564819949) = 652128534616280580041338757470258024490635838501926874091259885745358830160
Encryptor calculates the encrypted message (c1, c2) = (25051380001384562314959307721043701048687850352094011138061884132819862724667, 46849668020527693475159053259226199454750762501012280228897524972061871412373)
    * c1 = (g = 2)^(k = 6095530983035662394415401229300894157247477933650052462284854503095419296799) mod (p = 57896044618658097711785492504343953926634992332820282019728792003956564819949) = 25051380001384562314959307721043701048687850352094011138061884132819862724667
    * c2 = (K = 652128534616280580041338757470258024490635838501926874091259885745358830160)(m = 22594335182736179043379580066191528397421893149471409561964986373640506607991) mod (p = 57896044618658097711785492504343953926634992332820282019728792003956564819949) = 46849668020527693475159053259226199454750762501012280228897524972061871412373
Encryption is (c1, c2) = (25051380001384562314959307721043701048687850352094011138061884132819862724667, 46849668020527693475159053259226199454750762501012280228897524972061871412373)
> $c = @([bigint]::Parse("25051380001384562314959307721043701048687850352094011138061884132819862724667"), [bigint]::Parse("46849668020527693475159053259226199454750762501012280228897524972061871412373"))
> $c
25051380001384562314959307721043701048687850352094011138061884132819862724667
46849668020527693475159053259226199454750762501012280228897524972061871412373

We pass the ciphertext (c1, c2) to A and now she wants to read it. She gives the decryption routine the prime p, the generator g, her private key x, and the ciphertext (c1, c2). It had better return the plaintext m

> .\decrypt.ps1 -prime $p -generator $g -recipientPrivateKey $x -cipherText $c
Recipient wants to decrypt the message
Recipient recovers K = (c1 = 25051380001384562314959307721043701048687850352094011138061884132819862724667)^(x = 37472449428228375763830797714320932193767211994174601506224685902244496215115) mod (p = 57896044618658097711785492504343953926634992332820282019728792003956564819949) = 652128534616280580041338757470258024490635838501926874091259885745358830160
Recipient calculates m = (c2 = 46849668020527693475159053259226199454750762501012280228897524972061871412373)/(K = 652128534616280580041338757470258024490635838501926874091259885745358830160) mod (p = 57896044618658097711785492504343953926634992332820282019728792003956564819949) = 22594335182736179043379580066191528397421893149471409561964986373640506607991
Decrypted message 22594335182736179043379580066191528397421893149471409561964986373640506607991
> $m
22594335182736179043379580066191528397421893149471409561964986373640506607991

… and it does! Yay.

One thought on “ElGamal encryption and decryption but with bigger numbers

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s