2
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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)$ $\endgroup$
    – fgrieu ♦
    Commented Jan 26, 2020 at 11:00
  • $\begingroup$ 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? $\endgroup$
    – fgrieu ♦
    Commented Jan 26, 2020 at 11:05
  • 1
    $\begingroup$ 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$, $\endgroup$
    – fgrieu ♦
    Commented Jan 26, 2020 at 11:38

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – fgrieu ♦
    Commented Jan 26, 2020 at 14:36
  • $\begingroup$ ok thanks alot @fgrieu $\endgroup$
    – Vala Khosravi
    Commented Jan 26, 2020 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.