# Why does DSS have such formulas?

I've learnt the formulas needed for the DSA (http://en.wikipedia.org/wiki/Digital_Signature_Algorithm).
But most importantly, I don't quite understand what represents those formulas and why they are the way they are. For example, why if v = r then the signature is verified, why do r and s have such formulas etc.? RSA digital signature is so much simpler.

-

In a sense, you are correct in not understanding where the equations in DSA and ElGamal signatures come from. To a certain extent, they are just (distinct) choices from a family of equations that all seem to work, and all for the same-ish reasons. See e.g. Meta-ElGamal signature schemes by Patrick Horster, Holger Petersen, Markus Michels, http://dl.acm.org/citation.cfm?doid=191177.191197

But briefly, these schemes are secure because a signature is a solution to a very non-linear equation. If you know the secret key, it is very easy to find solutions. If you don't know the secret key, it seems to be hard.

For pedagogical reasons, I prefer Schnorr signatures. The story begins with identification protocols, specifically the identification protocol you get from the Schnorr proof of knowledge. Then you make the identification protocol non-interactive using the Fiat-Shamir heuristic. Then you make some changes to the verification equation, which are ok under the Fiat-Shamir heuristic. Finally, since you are already hashing stuff, you include the message into the hash. And you are done, you have designed the Schnorr signature scheme.

-
Nice answer! I also think that this is a nice way of approaching this matter: proof of knowledge -> non-interactive honest-verifier proof via Fiat Shamir heuristic + message as additional input into the hash function = signature (of knowledge) in the ROM. And in the simplest case for proof of knowledge of discrete logarithm we obtain Schnorr signatures. –  DrLecter Jan 9 at 14:57

The fundamental difference between RSA-groups and prime order groups is that in RSA groups the multiplicative order of the group is unknown (without knowledge of the factorization). This allows much easier constructions for unforgeable signatures (although hashing and padding are required to ensure existential unforgeability).

With knowledge of the group order, a forger has more possibilities to calculate "useful" group elements. This results in the DSA formulas (and the related ElGamals signatures) to be more complex.

Let's have a look at what these formulas actually calculate, and for simplification I'll leave out all the modulo operations (they are applied in the correct way). The goal is to get expressions which only depend on the hash $H$, the signing key $x$, and the (random) blinding value $k$.

The signature is: $$r=g^k$$ $$s=k^{-1}(H+xr) = k^{-1}(H+xg^k)$$

Let's look at the verification algorithm backwards: $$v=g^{u_1}y^{u_2} = g^{Hs^{-1}}g^{x \cdot r s^{-1}}$$ $$=g^{s^{-1} (H+xr)}$$

Here is the interresting part: A valid signature will solve like this: $$= g^{(k^{-1}(H+xg^k))^{-1} (H+xg^k)}= g^k = r$$

For a forger, this is differently: He can choose $r$ and $s$ arbitrarily, but he does not know $x$ but only $y=g^x$. To forge a valid signature, it has to fulfill this equation: $$g^{s^{-1}H}y^{s^{-1}r} = r$$ However, we can not solve this equation without calculating some discrete logarithms.

-
Probably a stupid question, but I presume 'prim order' was supposed to be 'prime order'? I know its only one letter, but if I'm wrong I'll set off to read about Prim Order groups (Seems a believable concept hence me asking) –  figlesquidge Jan 9 at 14:49
In this context I'm sure that it is prime order (and in particular I think the point he wants to make is that we have known order), since then later in the sentence the part "multiplicative order of the group is unknown" follows. –  DrLecter Jan 9 at 14:58
you're right, I missed a character there. I corrected it. –  tylo Jan 9 at 15:18