# Why ElGamal signature is insecure with nonrandom k?

In ElGamal signature scheme like:

Keygen: $$\beta:=\alpha^a\bmod p$$ where $$\alpha$$ and $$p$$ are large prime numbers. Public key is $$(p,\alpha,\beta)$$ and secret key is $$a$$.

Sign: Choosing random $$k$$ such that $$\gcd(k,p-1)=1$$, calculating $$r:=a^k\bmod p$$ and $$s:=k^{-1}\cdot(m-a\,r)\bmod(p-1)$$; then we send $$(m,r,s)$$

Verify: Calculating $$v_1:=\beta^r\cdot r^s\bmod p$$ and $$v_2:=\alpha^m\bmod p$$; then if $$v_1$$ and $$v_2$$ are equal the signature verifies.

In the booklet I'm reading for cryptography course it is said that if $$k$$ is non-random this signature scheme is insecure. What's the reason?

• The equation really is $s:=k^{-1}\cdot(m-a\,r)\bmod(p-1)$, NOT $s:=k^{-1}\cdot(m-a\,r)\bmod p-1$, which reads as $s:=(k^{-1}\cdot(m-a\,r)\bmod p)-1$. If you don't understand why, write down a proof that the verification procedure works absent alteration of $(m,r,s)$
– fgrieu
Jan 26 '20 at 11:00
• Hint for the question; what can an adversary do if s/he can guess $k$, because it was chosen in too small a set? Independently: what can an adversary do if different messages get signed with the same random $k$, because it was generated using a RNG with a broken source of true randomness?
– fgrieu
Jan 26 '20 at 11:05
• Note: if your reference writes $s:=k^{-1}\cdot(m-a\,r)\pmod{p-1}$, well that's not quite standard notation, but it is understandable and the modulus is unambiguously $p-1$. In the original question I had been criticizing $\beta=\alpha^a\ (mod\ p)$ which (especially since it uses $=$ rather than $:=$ ) is quite interpretable as $\beta\equiv\alpha^a\pmod p$, which again only means that $p$ divides $\alpha^a-\beta$ and thus allows an infinity of choices for $\beta$,
– fgrieu
Jan 26 '20 at 11:38

If we use constant $$k$$ in this scheme we can find the secret key like this:

We know $$(m_1,r_1,s_1)$$ and $$(m_2,r_2,s_2)$$ for two different plaintext, as k is constant $$r_1=r_2=r$$ so we have this equivalence: $$s_1k-m_1\equiv-ar\equiv s_1k-m_1\ mod\ p-1 \Rightarrow (s_1-s_2)k \equiv m_1-m_2\ mod\ p-1$$

This equivalence has $$d$$ answer where $$d=gcd(s_1-s_2,p-1)$$, $$d$$ is usually small so we can find $$k$$ using brute force on $$r\equiv \alpha^k\ mod\ p$$.

Now we know $$k$$ we can caluculate $$a$$ using $$a.r\equiv m_1-k.s_1$$ equivalence. Number of answer for this equivalence is $$gcd(r,p-1)$$ by comparing $$\beta$$ and $$\alpha^a$$ we can find $$a$$.

Now we know secret key and sign every plain text we want and that's insecure.

• I guess the first equation should be$$s_1\,k-m_1\equiv-a\,r\equiv s_2\,k-m_2\pmod{p-1}\implies(s_1-s_2)\,k \equiv m_1-m_2\pmod{p-1}$$Notice the change of some indices from $1$ to $2$, proper notation for equivalence modulo, use of thin space for multiplication rather than $.$ (when multiplication needs to be made explicit with a dot, a common choice is $\cdot$ )... Right-click on an equation then Show Math As Tex Commands reveals the LaTex used. See this for common idioms. Independently: a single signature with guessable $k$ allows attack.
– fgrieu
Jan 26 '20 at 14:36
• ok thanks alot @fgrieu Jan 26 '20 at 16:00