Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Is ElGamal still unforgable if the adversary knows the value of $r$ that was calculated by $g^k$?

When we do sign the message $msg$, we calculate $r = g^k$.

As we know the regular ElGamal existentially forgeable:

  • $e$ is picked randomly from $\mathbb{Z}_{p-1}$
  • $r = g^e \cdot y$ mod $p$ and $s$ is $-r$ mod $p$
  • When we check if it was forged we check for $y^r \cdot r^s = g^m$. Thus $g^{xr} \cdot (g^{e} y)^ {-r} = g^{-er} = g^{es} = g^m$. Where $m = H(msg)$.

if now $m = H(msg) + r$ (concatenate $r$ to $H(msg)$ is it now unforgable ?

share|improve this question
    
$r$ is part of the signature. That value needs to be known, otherwise you cannot verify a signature. Do you mean $k$? –  DrLecter Apr 17 at 6:08
    
No i don't. In regular attack we say that g^xr (g^e y)^-r = g^-er = g^es = g^m. where m = h(M). if now m is something like r + h(M) is it still unforgable –  borgnimor Apr 17 at 6:31
    
could you please edit this into the question and describe what your variables are. –  DrLecter Apr 17 at 6:35
    
yes i will do that –  borgnimor Apr 17 at 6:40
add comment

1 Answer 1

It seems that you mix things up.

ElGamal signatures are existentially forgeable in various different ways if it's not using the hash-then-sign paradigm, i.e., you sign the message directly instead of signing the message $m=H(M)$ with $H$ being a secure cryptographic hash function.

Given the type of forgery in your question that works, you compute your $m$ as $m=es \bmod p-1$ and have no full control over the choice of $m$. Note that you would have to find $M$ such that $m=H(M)$ for your forgery to be valid, which means that you need a preimage $M$ of $m$ under $H$ which is not feasible if $H$ is secure. This is because the verification algorithm will get $M$ and signature $(r,s)$ and will check if $$y^r r^s\equiv g^{H(M)} \pmod p $$ holds.

You could modify the computation to $m=H(M)\|r$ and to adapt the verification algorithm to check if $y^r r^s\equiv g^{H(M)\|r} \pmod p $, but I do not see any immediate reason why you should do so. AFAIK hashing the message prevents any existential forgeries of ElGamal signatures as long as $H$ is secure.

share|improve this answer
    
I am not sure that concatenating r will not help you in some why. Such as eventually you will be able to forge every message. –  borgnimor Apr 17 at 15:23
    
@borgnimor ah ok, you proposed this as a countermeasure to existential forgeability? I didn't get this before. I do not really see problems with your approach but I do not see any point for doing so, if hashing is already sufficient. –  DrLecter Apr 17 at 15:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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