Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
  1. When there is no hash function used, $s = k-x \cdot m \mod {q}$ instead of $s = k-x \cdot H(m||r) \mod{q}$?
  2. When a hash function is defined as $H(m)$ instead of $H(m||r)$?

Ref: Schnorr Signature

share|improve this question
    
If you're going to post homework, it's polite to show that you have made some effort. So how far have you got, and what specific problems do you have? –  Peter Taylor Feb 25 '11 at 9:46
    
My understanding is as follows: When m is used as a plain text, Then it can be divided across the equation: s.m^-1 = k.m^-1 - x mod q. Two signatures to the same msg then can solve x from this equation which is total break. I am not able think differently for the second case because attacker can get the hash from the plain text. Apology, its my first time here and I am a beginner in this field. –  bala maverick Feb 25 '11 at 10:07
    
In case 1, is $e$ still the same $H(m || r)$? –  Henno Brandsma Feb 25 '11 at 21:46
    
In case 2, what is the full signature? How do you verify it? –  Henno Brandsma Feb 25 '11 at 21:52
add comment

1 Answer

up vote 0 down vote accepted

As to 2: if $e= H(m)$ and $s = k - x \cdot H(m)$, the $k$ serves no purpose any more. Anyone can create $H(m)$ and there is no way to verify that $s$ has been created by the one possessing the private key $x$. In the original scheme, $g^s \cdot y^e$ yields $g^k = r$, so that we can verify that $e = H(m \| r)$ is correct. In variation 2, the $r$ has been eliminated, and cannot be computed by a verifier. This is not even a signature scheme, really, as there is no verifying beyond checking $e = H(m)$.

To address variation 1, as in the comment: if we use $(r,s)$ where $s = k - x \cdot m$, then the verifying equation becomes $g^s \cdot y^m = r$, given $(r,s)$ and the message $m$ and public key $y$; if it holds it's a valid signature (no need for hashing). But then from a valid signature $(r,s)$ for message $m$ we generate one for $m+1$ by multiplying $r$ by $y$, and keeping $s$. The check then becomes $$g^s \cdot y^{m+1} = g^s \cdot y^m \cdot y = r \cdot y$$ which is valid too. So then also the hashing stays necessary.

And if we use $e = H(m)$ and so $(r,s) = (g^k, k - x \cdot H(m))$ as the signature, we can do a similar thing: the verifying equation becomes $g^s \cdot y^{H(m)} = r$ (valid iff true) and then $(g \cdot r, s+1)$ is also a valid signature for $m$: verifying gives $$g^{s+1} \cdot y^{H(m)} = g \cdot (g^s \cdot y^{H(m)}) = g \cdot r$$ as $(r,s)$ was valid, and so the new one is valid too.

Note also that if we re-use the same $k$ (and thus $r = g^k$) for 2 signatures for different messages (in the secure, normal scheme), and the opponent knows or guesses this, then we can compute $x$, the secret key: we then have $(e_1, s_1)$ and $(e_2, s_2)$ where $e_1 = H(m_1 \| r)$, $e_2 = H(m_2 \| r)$, $s_1 = k - x \cdot e_1$, $s_2 = k - x \cdot e_2$; the opponent computes $$s_1 - s_2 = x \cdot (e_2 - e_1)$$ and $s_1, s_2, e_1, e_2$ are known, allowing us to solve for $x$, in most cases. Of course, for a large enough group, and good random choices, this is very unlikely to happen.

As you see, it's quite intricate to see why we need certain stuff.

share|improve this answer
    
Thanks! I am almost getting it.. It is that there is no binding between the randomness and the signature components. Am i right? –  bala maverick Feb 26 '11 at 11:05
    
++ in this case 2: when we have e=H(m) then why cant we pass the signature as (r,s). Will it be of any use? –  bala maverick Feb 26 '11 at 11:11
    
Thanks for the effort. A brilliant explanation, I am getting a clearer picture now of why we use certain primitives. !! #clear –  bala maverick Feb 28 '11 at 3:24
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.