# DSA: why using mod p mod q and not just mod p

I'd like to know, in DSA we compute several values modulo $$p$$ and modulo $$q$$, like $$r = (g^k \bmod p) \bmod q$$ or $$v = (g^{u_1}h^{u_2} \bmod p) \bmod q$$.

As far as I understand, we want to use two different primes $$p$$ and $$q$$ instead of just one to make sure that $$g$$ is of prime order $$q$$ in order to be able to invert elements (let me know if my understanding is wrong). But once we make sure to have $$g^q = 1 \bmod p$$, why do we add on top of that another modulo q? After a quick look, all the equations seems to hold if we just work modulo $$p$$...

The only reason for me that could explain it would be that because $$s$$ is computed modulo $$q$$, it's not really useful to store $$r \bmod p$$, and for "optimization" one can store directly $$(r \bmod p) \bmod q$$... Is it the reason or did I miss something?

Thanks!

Consider the function $$f\colon \mathbb Z \to \mathbb Z$$ given by $$f(x) = g^x \bmod p$$ where $$g$$ has order $$q$$ modulo $$p$$. If $$x \equiv y \pmod q$$, then necessarily $$f(x) = f(y)$$, since by hypothesis $$x = y + \ell q$$ for some $$\ell$$, so
$$$$g^x \equiv g^{y + \ell q} \equiv g^y g^{\ell q} \equiv g^y (g^q)^\ell \equiv g^y 1^\ell \equiv g^y \pmod p.$$$$
Note that $$f$$ is merely a function from integers to integers, but this proposition shows that there is additional periodic structure to its input: $$f(x) = f(x + \ell q)$$ for any $$\ell$$. So if we consider the coset $$\overline x = x + q\mathbb Z = \{\dots, x - 2q, x - q, x, x + q, x + 2q, x + 3q, \dots\}$$ of $$q \mathbb Z$$, $$f$$ is the same on every element of $$\overline x$$. Thus we can think of $$f$$ as being defined on the quotient $$\mathbb Z/q\mathbb Z$$, the set of all cosets of $$q\mathbb Z$$, rather than on $$\mathbb Z$$. More jargomatically: there is a unique natural $$\overline f\colon \mathbb Z/q\mathbb Z \to \mathbb Z$$ defined in the quotient $$\mathbb Z/q\mathbb Z$$ so that $$f = \overline f \circ \phi_q$$, where $$\phi_q\colon \mathbb Z \to \mathbb Z/q\mathbb Z$$ is the natural projection $$\phi_q(x) = x + q\mathbb Z = \overline x$$ onto $$\mathbb Z/q\mathbb Z$$.
In other words, even if we treat $$x \mapsto g^x \bmod p$$ as a function on integers, we can always break it down into two steps, the first of which is reduction modulo $$q$$. So, whether you like it or not, if you are computing $$g^x$$ for integers outside $$0 \leq x < q$$, the function can still always be defined in terms of doing $$x \bmod q$$ first.
What's much weirder is not reduction modulo $$q$$—which as above is necessary if you're going to use the result as an exponent—but the chain of reduction modulo $$p$$ and then modulo $$q$$. This was a point of contention in the provable security literature on DSA and ECDSA. You could imagine computing $$g^k \bmod q$$ directly, but it wouldn't make a functioning signature scheme. What you really want is a uniform random map from $$\mathbb Z/p\mathbb Z$$ to $$\mathbb Z/q\mathbb Z$$ which has no properties that an adversary could exploit.
It just happens that $$h \mapsto (h \bmod p) \bmod q$$ sorta kinda seems to work but as far as I know nobody has a good handle on why even in recent analyses like Fersch–Kiltz–Poettering 2016 (paywall-free), which models it roughly as a random oracle while tidying up nearly everything else about the long and sordid history of attempts to prove DSA and ECDSA security.