0
$\begingroup$

It's my understanding that the integer base and exponents chosen to create the initial public keys in DH are from the remainders of a modulus.

For example, if the value of the modulus is $N=11$, a set of remainders "produced" is {0,1,2,3,4,5,6,7,8,9,10}, however, I could also refer to the remainders of $N$ as 11,12,13,14,15,16,17,18,19,20,21.

Is there a way to differentiate by name the remainders {0,1,2,3,4,5,6,7,8,9,10}?

For example, is it accurate to refer to {0,1,2,3,4,5,6,7,8,9,10} as the canonical remainders of $\pmod N$? If yes, then can I refer to a particular base used as the canonical base and the exponent used the canonical exponent? Or is there a different terminology for these elements?

$\endgroup$
  • 1
    $\begingroup$ Formally mathematicians consider the elements of $Z_n$ aka $Z/nZ$ as congruence classes, but you are right we often represent and always(?) implement them using the integers 0..n-1, or 1.. for the multiplicative group, usually without saying so explicitly IME. The base or generator is a group element, but exponents are effectively modulo (less than) the order of g, which is also the order of the subgroup generated by g; for n prime this is at most n-1, but may be less, sometimes substantially less. $\endgroup$ – dave_thompson_085 Mar 6 '19 at 6:29
  • $\begingroup$ I appreciate the insight and my intent in asking was to clarify and make explicit what seems to always be implicit. IMHO it seems confusing for someone trying to understand the internals of how DH works not to find a more definitive statement of which equivalence class is being used. Also, while I understand the literal meaning of you saying, "The base or generator is a group element", but doesn't the base also have to be within the remainder/equivalence class as well? Finally, forgive my ignorance what does IME stand for :) ? $\endgroup$ – JohnGalt Mar 6 '19 at 16:02
  • $\begingroup$ I don't know what you're asking by "within the remainder/equivalence class". If we treat the mod-n elements (formally) as classes, then the base/generator is one of them, i.e. it is a class which is an element of the class of classes. If we treat the mod-n elements as numbers 0..n-1, then the base/generator is one of them. Either way it is one of the group elements. IME = in my experience. $\endgroup$ – dave_thompson_085 Mar 8 '19 at 5:14
3
$\begingroup$

The space $\mathbb Z/n\mathbb Z$ is usually taken to consist of equivalence classes modulo $n$ called residue classes—equivalence classes of integers under the equivalence relation $a \sim b$ if and only if $n$ divides $a - b$. For example, $\mathbb Z/3\mathbb Z$ consists of the three equivalence classes

\begin{align} 3\mathbb Z &= \{\dots, -3, 0, 3, 6, \dots\}, \\ 1 + 3\mathbb Z &= \{\dots, -2, 1, 4, 7, \dots\}, \\ 2 + 3\mathbb Z &= \{\dots, -1, 2, 5, 8, \dots\}. \end{align}

Residue classes are sometimes also called cosets in group theory.

Any set of distinct representatives of all the equivalence classes modulo $n$ is called a complete residue system modulo $n$. For example, $\{0,1,2\}$ is a complete residue system modulo 3, as is $\{99,-26,-1\}$.

Usually if we want to choose particular representatives for computation, we choose the least nonnegative residues like $\{0,1,2\}$, where each number is taken to represent the equivalence class it is an element of.

There are also more exciting systems like Montgomery residues in radix $r$, where a coset $a + n\mathbb Z$ is represented by the integer $a \cdot r^{-1} \bmod n$, where $r^{-1}$ is an integer such that $r \cdot r^{-1} \equiv 1 \pmod n$. For instance, in radix 8, modulo 5 we have the representatives

\begin{align} 0 &\mapsto 0 + 5\mathbb Z, \\ 2 &\mapsto 1 + 5\mathbb Z, \\ 4 &\mapsto 2 + 5\mathbb Z, \\ 1 &\mapsto 3 + 5\mathbb Z, \\ 3 &\mapsto 4 + 5\mathbb Z. \end{align}

This peculiar-looking function has the property that we can compute a representative of its image by $$\rho(x) = \bigr(x + n\cdot[(x \bmod r) \cdot n' \bmod r]\bigr)/r,$$ where the only divisor involved in the computation is $r$. Here $n' n \equiv 1 \pmod r$, and the result is either the least nonnegative residue modulo $n$, or the next one greater, so you can get the least nonnegative residue with a single conditional subtraction. The form $a \cdot r^{-1}$ is preserved by addition and subtraction, $(a \pm b) \cdot r^{-1} = a \cdot r^{-1} \pm b \cdot r^{-1}$, and while it is not preserved by multiplication, it can be restored by evaluating $\rho$: $$(a \cdot b) \cdot r^{-1} = \rho\bigl((a \cdot r^{-1}) \cdot (b \cdot r^{-1})\bigr).$$ This technique is called Montgomery multiplication. When $r$ is a natural machine word size like $2^{32}$, this representation can be considerably faster without timing side channels than reduction modulo a general odd $n$.

| improve this answer | |
$\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.