First part: ElGamal encryption system, cracking it using CADO-NFS

All variable names as in Wikipedia's explanation of ElGamal signing scheme.

As in ElGamal encryption scheme, we reuse these parameters and keys:

g, p are public parameters. x, y are keys. x - private, y - public.

Let m be a message.

Generate 'ephemeral key', k. Must be coprime to p-1.

Compute \( r=g^k \pmod p \). This is how k is transmitted in 'obfuscated' way.

Now find such a s, so that the following equation would hold:

\[ m = xr + sk \pmod{p-1} \]m, r and s are published as message + signature.

Here, let's recall generalized version of Fermat little theorem. If g and p are coprimes and \( x=y \pmod p-1 \), then \( g^x=g^y \pmod p \).

Back to our equation. Verification step. Since g is coprime to p, due the theorem:

\[ m = xr + sk \pmod {p-1} \]... can be transformed to:

\[ g^m = g^{xr + sk} \pmod p \](g and p must be coprimes -- they are, since g is a primitive root of p.)

... and can be rewritten further to:

\[ (g^{x})^r (g^{k})^s \pmod p \] \[ (y)^r (r)^s \pmod p \]Verification step doesn't use x (private key), only y (public key). So anyone, having g, p, y can verify signature.

So the last verification step is:

if pow(g, m, p) == divmod(pow(y, r, p) * pow(r, s, p), p)[1]: print ("verification passed")

Now let's back to finding "such a s".

Rewriting this:

\[ m = xr + sk \pmod {p-1} \]Would result in:

\[ \frac{m - xr}{k} \pmod {p-1} \]However we can't use division operation, we must use inverse modulo:

\[ (m - xr)k^{-1} \pmod {p-1} \]As in ElGamal encryption scheme, the problem of cracking is the problem of finding the 'ephemeral key' k. And again, to do this, the discrete logarithm is to be found.

Now a practical example. g/p parameters and key generation functions are the same as in the previous example.

Parameters:

p, g = (1123, 2)

Keys:

secret key = 108 full public key g, p, y = (2, 1123, 368)

The signing code:

#!/usr/bin/env python3 import math, random # private key: x=108 # g/p parameters and public key: g, p, h = 2, 1123, 368 m=123 assert m>=0 and m<=p # AKA ephemeral key # random for each message # must be coprime to $p-1$ while True: k=random.randint(2, p-2) if math.gcd(k, p-1)==1: break r=pow(g, k, p) # publish $k$ in 'obfuscated' form s=divmod((m - x*r) * pow(k, -1, p-1), p-1)[1] # the same as (m - x*r) / k mod p-1 assert s!=0 print ("m, r, s=", m, r, s)

The verification code:

#!/usr/bin/env python3 import sys # g/p parameters and public key: g, p, y = 2, 1123, 368 m=int(sys.argv[1]) r=int(sys.argv[2]) s=int(sys.argv[3]) if pow(g, m, p) == divmod(pow(y, r, p) * pow(r, s, p), p)[1]: print ("verification passed") else: print ("verification NOT passed")

The log:

% ./sign.py m, r, s= 123 107 159 % ./verify.py 123 107 159 verification passed

List of my other blog posts. My company.

Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.