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.

From an old exam question:

Consider this existential forgery attack on ElGamal. Choose $u$, and $v$ such that $\operatorname{gcd}(v, p - 1) = 1$.

Compute $r := y^v g^u \mod p$ and $s := -r·v^{-1} \mod (p-1)$. (Recall that $y := g^x \mod p$.)

$s$ will be used as part of the forged signature.

(a) Prove that $σ = (m, r, s)$ is a valid signature for $m := s^u \mod (p-1)$.

(b) Suppose that a secure hash function $h$ is used and the signature must be valid for $h(m)$ instead of $m$. Explain how this protects against existential forgery.

share|improve this question
    
For (a), just look at the verification equation $g^m\, \overset?=\, y^r·r^s$, replace your values for $s$, $r$ and $m$ (and $y$), and do some simplifications until you have the same stuff at both sides. –  Paŭlo Ebermann Nov 28 '11 at 22:43
    
About your (reverted) edit: Don't forget $y = g^x$ in your calculations, as well as all occurrences of $r$ and $s$. –  Paŭlo Ebermann Nov 30 '11 at 9:01
    
Does it actually verify? I got $g^{(u^s)}$ on the LHS and $(g^u)^s$ on the RHS which aren't the same. I did it quickly though... –  PulpSpy Nov 30 '11 at 15:58
add comment

closed as too localized by Paŭlo Ebermann Dec 9 '12 at 19:10

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.