Tell me more ×
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.
up vote 2 down vote favorite

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

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, see the FAQ.

Browse other questions tagged or ask your own question.