Re: attack against ElGamal (and related algorithms)

From: Tom St Denis (tomstdenis_at_iahu.ca)
Date: 12/21/03 

Date: Sun, 21 Dec 2003 15:31:18 GMT

"Atom 'Smasher'" <ngbz@fhfcvpvbhf.bet> wrote in message
news:vuav1vi02lnof1@corp.supernews.com...
> from several references i've been reading that the Achilles Heel of
ElGamal
> (and related algorithms) is that "k" MUST be unique for each signing
and/or
> encryption....

More than that. k MUST be random as well.

>
> If Eve ever gets two messages signed OR ENCRYPTED using the same
"k"...
> she can recover "x". ["x" being the secret key]
> -- Bruce Schneier, Applied Cryptography, 2nd Ed. pg 477
>
> i've been unable to find any mathematical demonstrations of that [and i'm
> not schooled enough to figure it out]. if that's true, then there is a BIG
> HOLE in this protocol:

The typical ElGamal signature works like this

R = k * G
s = (m - x)/k mod p

Where R and G can be field elements other than integers [points on curves
for instance], s/m/x/k/p are integers, m being the message, x being the
private key and finally * doesn't strictly mean multiplication [can be point
multiplication, exponentiation].

You verify the signature if

s*R + Y = m*G

Since s*R = (m-x)*G and Y is equal to x*G.

The "k" parameter act's like a blinding value. That is given s you cannot
determine [uniquely] what x is. Also this relies on the fact that finding x
from x*G or (m-x)*G is hard todo.

If you re-used k for two related messages you would have

s = (m-x)/k
s' = (m'-x)/k

Since the attacker knows m there are only two unknowns for two knowns. You
can now solve for x. This is why k must be random [not just unique] for
every message you sign [or encrypt].

Tom

Loading