3
$\begingroup$

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!

$\endgroup$

1 Answer 1

5
$\begingroup$

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

\begin{equation} 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. \end{equation}

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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