ElGamal signing and signature verification but with bigger numbers

Last time we looked at ElGamal encryption and decryption but with bigger numbers. This time let’s look at signing and signature verification.

As before we choose the prime p = 2255 – 19 and the generator g = 2. We’ll let A keep her private key x = 37472449428228375763830797714320932193767211994174601506224685902244496215115 and its associated public key gx mod p = 15440027450603317705548401356286425311467546169515779468886789260083908558514.

We’ll choose a different message this time:

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

A wants to sign the message. She passes the signing routine the prime p, the generator g, her private key x, and the message m. It returns the signature (r, s).

> cd elgamal
> .\sign.ps1 -prime $p -generator $g -signerPrivateKey $x -message $m
Signer chooses a random number k = 24618296997275480932053592551920025862416126779629427099702631482415856443479 such that gcd(k = 24618296997275480932053592551920025862416126779629427099702631482415856443479, p - 1 = 57896044618658097711785492504343953926634992332820282019728792003956564819948) = 1
Signer calculates the signature (r, s) = (3025781994294452178840475154004769894024031449788332246545481203211043144236, 20885180761607031118214763642348557339838023745006310985614125237008647415483)
These are calculated so g^m = y^r r^s mod p
Take r = g^k
Now we have g^m = g^(x r) g^(k s) mod p
Which is to say m = x r + k s mod (p - 1)
We want to solve for s - this is why we needed gcd(k, p - 1) is 1
    * r = (g = 2)^(k = 24618296997275480932053592551920025862416126779629427099702631482415856443479) mod (p = 57896044618658097711785492504343953926634992332820282019728792003956564819949) = 3025781994294452178840475154004769894024031449788332246545481203211043144236
    * s which makes (m = 3271986818346674557032810660246111638748594301259911249641768028517949236833) = (x = 37472449428228375763830797714320932193767211994174601506224685902244496215115) * (r = 3025781994294452178840475154004769894024031449788332246545481203211043144236) + (k = 24618296997275480932053592551920025862416126779629427099702631482415856443479) * (s = 20885180761607031118214763642348557339838023745006310985614125237008647415483) mod (p - 1 = 57896044618658097711785492504343953926634992332820282019728792003956564819948)
Signature is (r, s) = (3025781994294452178840475154004769894024031449788332246545481203211043144236, 20885180761607031118214763642348557339838023745006310985614125237008647415483)
> $signature = @([bigint]::Parse("3025781994294452178840475154004769894024031449788332246545481203211043144236"), [bigint]::Parse("20885180761607031118214763642348557339838023745006310985614125237008647415483"))
> $signature
3025781994294452178840475154004769894024031449788332246545481203211043144236
20885180761607031118214763642348557339838023745006310985614125237008647415483

Now B, the reader of the message, wants to verify that A really wrote it. He passes the signature verification routine the prime p, the generator g, A‘s public key gx, the message m, and the signature (r, s). It returns whether the signature is valid.

It should be valid…

> .\verify-signature.ps1 -prime $p -generator $g -signerPublicKey $g_x -message $m -signature $signature
Signature verifier calculates (g = 2)^(m = 3271986818346674557032810660246111638748594301259911249641768028517949236833) = 14784288759268166937333969698279404318706460490042691327601374955158440934277
Signature verifier calculates = (y = 15440027450603317705548401356286425311467546169515779468886789260083908558514)^(r = 3025781994294452178840475154004769894024031449788332246545481203211043144236) (r = 3025781994294452178840475154004769894024031449788332246545481203211043144236)^(s = 20885180761607031118214763642348557339838023745006310985614125237008647415483) mod (p = 57896044618658097711785492504343953926634992332820282019728792003956564819949) = 14784288759268166937333969698279404318706460490042691327601374955158440934277
Signature is valid
Signature is valid.

… and it is!

Now suppose someone had tampered with the message, e.g. replacing m with m – 1, and tried to pass it off as the original, with A‘s signature. The signature should now be invalid…

> .\verify-signature.ps1 -prime $p -generator $g -signerPublicKey $g_x -message ($m - 1) -signature $signature
Signature verifier calculates (g = 2)^(m = 3271986818346674557032810660246111638748594301259911249641768028517949236832) = 36340166688963132324559731101311679122670726411431486673665083479557502877113
Signature verifier calculates = (y = 15440027450603317705548401356286425311467546169515779468886789260083908558514)^(r = 3025781994294452178840475154004769894024031449788332246545481203211043144236) (r = 3025781994294452178840475154004769894024031449788332246545481203211043144236)^(s = 20885180761607031118214763642348557339838023745006310985614125237008647415483) mod (p = 57896044618658097711785492504343953926634992332820282019728792003956564819949) = 14784288759268166937333969698279404318706460490042691327601374955158440934277
Signature is invalid
Signature is invalid. 

… and it is!

So the same routines all work even if the numbers are big.

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