2
$\begingroup$

Reading through the DSA signature specification, one thing stood out for me.

$r = (g^k \bmod{p} ) \bmod{q}$

Then $s$ is computed. In the computation above, why is the modulo $p$ required, given we are anyway reducing it with a modulo $q$?

To clarify, just doing a modulo $q$ will achieve the result of reducing the number to within the bounds of q. Doing a modulo $p$ seems like an extra step and that indicates that a simple reduction of the number to the bounds q is not the only objective. Why is modulo $p$ needed, cryptographically speaking?

$\endgroup$
  • $\begingroup$ One thing to note is that $(x \bmod{p}) \bmod{q} \neq x \bmod{q}$. $\endgroup$ – puzzlepalace Mar 15 '18 at 19:35
  • $\begingroup$ Of course. That was my point. Eventually the integer is being reduced to modulo q. So why do a modulo p, as directly doing the mod q will achieve the same result of reducing the integer to within the bounds of q. $\endgroup$ – stflow Mar 15 '18 at 19:59
2
$\begingroup$

The way you should think of it is not as $(g^k \bmod p) \bmod q$ but as computing exponentiation by the integer $k$ of the order-$q$ element $g$ of the group $G = (\mathbb Z/p\mathbb Z)^\times$—which happens to be the multiplicative group of units modulo $p$ and to correspond to reducing the integer $g^k$ modulo $p$—and then randomly projecting that onto $\mathbb Z/q\mathbb Z$. But for security it is sufficient to work with some more or less evenly distributed function from $G$ into the group $\mathbb Z/q\mathbb Z$ of exponents of $g$ (recall $g$ has order $q$), and the map $h \mapsto h \bmod q$ seems to work well enough as such a function.

In more detail: The general form of (EC)DSA is the following structure:

  • Parameters:
    • Group $G$ in which discrete logs are hard.
    • Element $g \in G$ of large prime order $q$.
    • Random function $H\colon \{0,1\}^* \to \mathbb Z/q\mathbb Z$.
    • More or less evenly distributed function $F\colon G \to \mathbb Z/q\mathbb Z$.
  • Public key: Element $y \in G$.
  • Verification: A signature on a message $m$ is a pair of exponents $r, s \in \mathbb Z/q\mathbb Z$ satisfying the equation $$r = F(g^{H(m) \cdot s^{-1}} y^{r s^{-1}}).$$
  • Key generation: Pick uniform random $x \in \mathbb Z/q\mathbb Z$; public key is $y = g^x$.
  • Signing: Pick $k \in \mathbb Z/q\mathbb Z$ uniformly at random (reject $0$ and $1$ if you're a stick in the mud); compute $r = F(g^k)$ (reject $0$ if you're a stick in the mud) and $s = k^{-1} (H(m) + x r)$.

For DSA, we have $G = (\mathbb Z/p\mathbb Z)^\times$ and $F\colon h \mapsto h \bmod q$ (taking $h$ to be its least nonnegative residue modulo $p$). For ECDSA, we replace the exponentiation $g^x$ for integer $g$ by the scalar multiplication $[x]B$ for curve point $B$, so we have $G = E(k)$, the $k$-rational points of some curve $E$ over a field $k$, and $F\colon P \mapsto x(P) \bmod q$. And, as an additional tweak, in the signature for ECDSA we encode $x(P)$ instead of $F(P) = x(P) \bmod q$, because by Hasse's theorem $\#k \approx q$ (as long as the cofactor is small; for the curves typically used in ECDSA, it's usually 1), so unlike in finite-field DSA the additional reduction modulo $q$ for encoding the signature doesn't save much space.

If the choice of $F$ feels like it's all very arbitrary, you would be right. (EC)DSA was a wacky bizarro design motivated mainly by a desire to avoid a patent-wielding Claus Schnorr in the early '90s, and nobody would care about this nonsense any more except (EC)DSA has now been carved into the stone of bureaucratic United States federal government standards standards that nobody in the Western world ever got fired for following.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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