6
$\begingroup$

In RSA, $C=M^e \bmod N$ and $d=e^{-1} \bmod φ(N)$ are used for encryption and signatures.

What is the exact definition of $x^u \bmod k$?

Also, what is the difference between $$x^u = y \bmod k$$ and $$x^u \equiv y\bmod k$$

$\endgroup$
3
  • $\begingroup$ Note: This is a canonical question as requested. $\endgroup$ – kelalaka Jul 11 '20 at 17:06
  • $\begingroup$ fgrieu focused on the $x^u$ portion, while I focused on the $\bmod k$ portion. What more are you looking for? $\endgroup$ – poncho Jul 13 '20 at 21:03
  • $\begingroup$ Nothing more. Just awarding. Both of you. It requires step by step. $\endgroup$ – kelalaka Jul 14 '20 at 7:05
12
+50
$\begingroup$

What is the exact definition of $x^u\bmod k$?

In RSA and most cryptographic contexts, $x^u\bmod k$ is written with:

  • $k$ in the set $\Bbb N^*$ of strictly positive integers. $k$ is the modulus (plural moduli)
  • $u$ in the set $\Bbb Z$ of signed integers. $u$ is the exponent.
  • $x$ in the set $\Bbb Z$ of signed integers, or in the set $\Bbb Z_k$ of integers modulo $k$. The later is a special case of the former, since we'll assimilate $\Bbb Z_k$ to the non-negative integers less than $k$.

$x^u\bmod k$ can be spoken « $x$ raised to the power $u$ [small pause] modulo $k$ », and becomes « $x$ to the $u$ mod $k$ », or « $x$ to $u$ » under time constraints.

For the full definition, skip to $\eqref{fgr4}$. For a gentle introduction, we'll first study the

definition with exponent $u>0$

When $u>0$, the notation $x^u\bmod k$ just stands for $\left(x^u\right)\bmod k$, where $x^u=z$ and $z\bmod k=y$ have their usual definition:

  • $x^u$ is $\underbrace{x\cdot x\cdots x\cdot x}_{u\text{ term(s)}}\,$ where $\cdot$ is integer multiplication. More formally $$x^u\,\underset{\text{def}}=\begin{cases} x&\text{if}\,u=1\\ x\cdot\left(x^{\left(u-1\right)}\right)&\text{if}\,u>1 \end{cases}\tag1\label{fgr1}$$ Note: the parentheses would usually be omitted¹.
  • $z\bmod k$ is defined to be $y$ such that $0\le y<k$ and $z-y$ is a multiple of $k$. Equivalently:
    • $z\bmod k$ is obtained from $z$ by subtracting or adding $k$ as many times as necessary for the result to be in range $[0,k)$. More formally: $$z\bmod k\,\underset{\text{def}}=\begin{cases} z&\text{if}\,0\le z<k\\ \left(z-k\right)\bmod k&\text{if}\,z\ge k\\ \left(z+k\right)\bmod k&\text{if}\,z<0 \end{cases}\tag2\label{fgr2}$$
    • If $z\ge 0$, then $z\bmod k$ is the remainder in the Euclidean division of $z$ by $k$;
      otherwise, $z\bmod k$ is $k-1-\left(\left(-z-1\right)\bmod k\right)$.
      More formally, noting $\ell$ for the quotient (with $\ell=\left\lfloor z/k\right\rfloor$ per the mathematical definition of that): $$z\bmod k\,\underset{\text{def}}=y\in\Bbb Z_k\,\text{ such that }\,\exists\ell\in\Bbb Z\,\text{ such that }\,y=z-\ell\cdot k\tag3\label{fgr3}$$

Example: We compute $3^5\bmod35$ directly from this definition. That's $x^u\bmod k$ with $x=3$, $u=5$, $k=35$. We compute $x^u=3^5=3\cdot3\cdot3\cdot3\cdot3=243$. We perform the Euclidean division of $z=243$ by $k=35$, yielding quotient $\ell=6$ and remainder $y=243-6\cdot35=33$. Thus $3^5\bmod35=33$.

In Python, the above is obtained as (3**5)%35 or pow(3,5)%35 or pow(3,5,35). The three forms internally use exponentiation by squaring, but only the later uses modular reduction of intermediary results. Using both techniques is essential for even mildly efficient modular exponentiation in RSA, e.g. encryption per $C=M^e\bmod N$ with common parameters like 2048-bit $N$ and $e=65537$.
Starting with Python 3.8, pow also handles all the following.


Extensions to any integer exponent $u$

The full² definition of $x^u\bmod k$ in cryptography is: $$\begin{array}{l} x^u\bmod k\underset{\text{def}}=\\\\ \begin{cases} y\in\Bbb Z_k,\;\exists\ell\in\Bbb Z,\;y=x^u-\ell\cdot k&\text{if }u>0\\ y\in\Bbb Z_k,\;\exists\ell\in\Bbb Z,\;y\cdot x^{-u}+\ell\cdot k=1&\text{if }u<0,\;k>1\text{ and }\gcd(x,k)=1\\ \text{undefined}&\text{if }u<0,\;k>1\text{ and }\gcd(x,k)\ne1\\ 1&\text{if }u=0,\;k>1\\ 0&\text{if }k=1\\ \end{cases}\end{array}\tag4\label{fgr4}$$ In this, $\Bbb Z_k$ stands for the non-negative integers less than $k$, or equivalently the integers modulo $k$. “$\text{such that}$” is replaced by “$,\;$” which is common practice (suppressing it is also accepted).

This definition extends $\eqref{fgr3}$ to the multiplicative group of integers modulo $k$, that is the subset $\Bbb Z_k^*$ of $\Bbb Z_k$ that forms a group under multiplication modulo $k$. For negative $u$, the notation $x^{-u}\bmod k$ is now defined as the multiplicative inverse of $x^u$ in $\Bbb Z_k^*$.

Definition $\eqref{fgr4}$ maximizes the domain where it holds the property: $$\begin{array}{l} \text{if }\,x^u\bmod k\,\text{ and }\,x^v\bmod k\,\text{ are both defined, then}\\ \quad\bigl(\left(x^u\bmod k\right)\cdot\left(x^v\bmod k\right)\bigr)\bmod k\;=\;x^{u+v}\bmod k \end{array}\tag5\label{fgr5}$$

When $u<0$ and $k>1$, the equation $y\cdot x^{-u}+\ell\cdot k=1$ follows from extending definition $\eqref{fgr3}$ with $y=x^u\bmod k$ constrained to be an integer, while insuring property $\eqref{fgr5}$. With $x^{-u}$ replaced by $z$, that becomes a Bézout identity $y\cdot z+\ell\cdot k=1$. The requirement $\gcd(x,k)=1$ pops up, as well that $y$ and $\ell$ can³ be computed per the extended Euclidean algorithm (that can yield $y<0$; we need to bring it back to positive by reducing it modulo $k$, or equivalently adding $k$).

Example: We compute $3^{-5}\bmod35$ directly from this definition. That's $x^u\bmod k$ with $x=3$, $u=-5$, $k=35$. We compute $x^{-u}=3^5=3\cdot3\cdot3\cdot3\cdot3=243$. We perform the extended Euclidean algorithm to solve for $y$ (and $\ell$ that we don't need) the Bézout identity $y\cdot 243+\ell\cdot 35=1$. Using the pseudocode of this Try It Online!, the steps are $$\begin{array}{rrrrrrr|rrr} r&r'&s&s'&t&t'&q&z\cdot s+k\cdot t&=&r\\ \hline 243&35&1&0&0&1&6&243\cdot1+35\cdot0&=&243\\ 35&33&0&1&1&-6&1&243\cdot0+35\cdot1&=&35\\ 33&2&1&-1&-6&7&16&243\cdot1+35\cdot(-6)&=&33\\ 2&1&-1&17&7&-118&2&243\cdot(-1)+35\cdot7&=&2\\ 1&0&17&-35&-118&243&&243\cdot17+35\cdot(-118)&=&1 \end{array}$$ and that yields $y=17$, $\ell=-118$. Thus $3^{-5}\bmod35=17$.

The definition $\eqref{fgr4}$ is such that $$\begin{array}{l} \text{if any two among the three $\;x^u\bmod k$, $\;\;x^v\bmod k$, $\;\;x^{u\cdot v}\bmod k$}\\ \text{are defined, then all three quantities are defined, and}\\ \quad\left(x^u\bmod k\right)^v\bmod k\;=\;x^{u\cdot v}\bmod k\;=\;\left(x^v\bmod k\right)^u\bmod k \end{array}\tag6\label{fgr6}$$ Applied for a negative $w$ with positive $u=-w$ and $v=-1$, $\eqref{fgr6}$ allows computing $x^w\bmod k$ using modular exponentiation with a positive exponent, and (after or before that) a modular inversion, thus avoiding monstrously large input to the extended Euclidean algorithm, and using alternative algorithms.


The meaning of $\bmod$ [reference to Monty-Python intentional]

In some contexts including the definition of RSA, we need to distinguish two kinds of $\bmod$

  1. An operator, yielding e.g. the remainder of Euclidean division when applied to two strictly positive integers. It is to be typeset using \bmod k in $\LaTeX$ / MathJax (see this, or this for more). In this case, that operator's result, when and if defined, is always a non-negative integer less than the modulus. And, depending on context, that operator has
    • two arguments like in $7\bmod5$, or in $7\bmod5\,=\,2$, or in $2\,=\,7\bmod5$. The first is the integer $2$, the later two are two true statements.
    • three arguments like in $3^{-1}\bmod5$, or in $3^{-1}\bmod5\,=\,2$, or in $2\,=\,3^{-1}\bmod5$. The first is the integer $2$, the later two are two true statements.
  2. The indication of modular equivalence (class) in what stands on its left. That is best typeset:
    • As \pmod k in $\LaTeX$ / MathJax, which shows as “$\pmod k$” with an opening parenthesis “$($” immediately before $\bmod$ and a closing parenthesis “$)$” after the modulus.
    • And⁴ with the sign $\equiv$ rather than $=$ anywhere on its left.
    • And with only the closing parenthesis on the right of the modulus.

Example of typographically and mathematically correct usages of modular equivalence:

  • Definition: $r\equiv s\bmod m\;\underset{\text{def}}\iff\;\exists\ell\in\Bbb Z,\,r=s+\ell\cdot m$
  • In any valid RSA public/private key, $e\cdot d\equiv1\pmod{\lambda(N)}$
  • It holds $7\equiv2 \pmod 5$ thus $2\equiv7 \pmod 5$
  • It holds $3^5\equiv243\equiv33 \pmod{35}$ thus $33\equiv3^5 \pmod{35}$
  • $\lambda(35)=12$ and $-5=7 \pmod{12}$, thus $3^{-5}\equiv3^7\equiv2187\equiv17 \pmod{35}$.
  • $7\pmod 5$ can be seen as the infinite set $\{\ldots,-8,-3,2,7,12,\ldots\}$.

Sometime a statement is false with the operator from, that would be true as a modular equivalence: $7=7\bmod5$ stands for $7\,=\,(7\bmod5)$ thus is false, when $7\equiv7 \pmod 5$ is true.

The distinction matters in RSA encryption, with ciphertext $C$ specified by $C=M^e\bmod N$ where $M$ represents the message. In this, $\bmod$ is an operator, thus implies $0\le C<N$, which is important. An encryption system only specified to output $C$ such that $C\equiv M^e\pmod N$ could output $C=M^e$ and be totally insecure, or leak some sensitive information by selectively producing $C=(M^e\bmod N)+N$.


What is the difference between $x^u=y\bmod k$ and $x^u\equiv y\bmod k$ ?

The cardinal way to read the correct $x^u=y\bmod k$ is as $x^u=(y\bmod k)$ with $\bmod$ an operator. Unambiguously, that implies $x^u\equiv y\pmod k$, that is $y-x^u$ is a multiple of $k$. Formally, $x^u=(y\bmod k)$ also implies $0\le x^u<k$. But it is not often that $0\le x^u<k$ is meant, thus I try to not use $x^u=y\bmod k$, and would use $x^u=(y\bmod k)$ only if $0\le x^u<k$ was intended.

I'm reading $x^u\equiv y\bmod k$ (using \bmod) as a slight $\TeX$po™ of $x^u \equiv y\mod k$ (using \mod, which adds spacing on the left to indicate that it is not an operator) or $x^u\equiv y\pmod k$ (using \pmod, which adds parentheses to more clearly indicate the same thing). Thus here $\bmod$ stands for modular equivalence. I avoid \mod when \pmod rather than \bmod is meant, because except in contexts like tex-SE or a JOC paper, 90% of the audience will not interpret the slight extra space correctly.


¹ Raising to a power is performed before multiplication (thus before addition), tough after any operation in the exponent. The exponent is on the right, and is typographically distinguishable by being higher and in smaller characters. If that's not feasible, it is often used ** or ^^ (or ^ when confusion with eXlusive-OR operator $\oplus$ is impossible), and parentheses.

² Sometime $x^u\bmod 1$ and/or $x^0\bmod k$ with $\gcd(x,k)\ne1$ are left undefined or unspecified, for simplicity and because they are seldom practically useful.

³ Since we do not need $\ell$, we can simplify the extended Euclidean algorithm by removing the two variables $t$ and $t'$. When performing the algorithm by hand, that has the drawback we can't check intermediary results. But we can still check $y\cdot z\bmod k=1$ in the end.

⁴ Sometime, this $\equiv$ becomes $=$, or the $($ immediately on the left of $\bmod$ vanishes [together owith the matching $)$ after the modulus]. But absent at least one of these indications, the meaning changes: we are back to the $\bmod$ operator.

$\endgroup$
8
$\begingroup$

It sounds like the questions can be summarized as "when a cryptographer writes $\bmod$, what do they mean?

Well, it turns out that $\bmod$ has (at least) three subtly different meanings, based on context:

  • It can be a function that takes two integers, and evaluates to an integer. In this context, the expression $a \bmod b$ is that value that can be expressed as $a + bi$ for some integer $i$ with $0 \le a + bi < b$ (assuming $b > 0$); this integer $i$ can be positive, negative or zero. This is the % operation in some computer languages (C, for example), and it is actually somewhat rare in cryptography, in that most uses of $\bmod$ can be better understood to be one of other two meanings.

  • It can be a notation that two values are taken as "equal" if they differ by a multiple of the modulus; that is, when we write $a = b \bmod n$ (or $a \equiv b \bmod n$, or as I generally prefer, $a = b \pmod n$), that is a claim that there is an integer $i$ such that $a - b = i\cdot n$. This meaning differs from the previous in that it is not an operation on $b$; for example, $103 = 3 \bmod {100}$, even though the first meaning would have $3 \bmod 100$ would evaluate to 3.

  • It can be a note that the operations are to be understood to be taken over the ring $\mathbb{Z}_n$, rather than the integers (also known as $\mathbb{Z}$). The addition, subtraction and multiplication operations in that ring can be implemented as "perform the operations as if they were over the integers, and then reduce things modulo $n$"; however, division and computing inverses cannot be. For example, when we write $e^{-1} \bmod{ \phi(n) }$, this is the meaning we are using.

And, to make things even more fun, somethings the $\bmod$ notation is implicit. When we write $g^{xy^{-1}}$, the $xy^{-1}$ is computed modulo the group order of $g$ (meaning 3); the reader is assumed to just know that.

With that, here are the answers to your questions:

What is the exact definition of $x^u \bmod k$?

Both the first and third meanings work here; you take $u$ copies of $x$, and multiply them together (either in the ring $\mathbb{Z}_k$, or after you perform the multiplications, you then apply the modulo operation - both strategies evaluate to the same thing.

Also, what is the difference between $$x^u = y \bmod k$$ and $$x^u \equiv y\bmod k$$

No real difference; both are ways to use meaning two.

$\endgroup$
3
  • $\begingroup$ I know no reference with a discussion on notation that recommends or even condones one making $103 = 3 \bmod {100}$ (using \bmod) a true statement. IMHO, even $103 = 3 \mod {100}$ (using \mod) is to be frowned at in a crypto context. Take in particular the standard definition of encryption by $C=M^e\bmod N$ : that must be understood as implying $0\le C<N$. Notice that the difference for $\LaTeX$ goes beyond the extra space: \mod has the syntax of \pmod and requires a second argument [else we get $\mod$ ]; when \bmod does not [we get $\bmod$ ], and is an operator just like $\times$. $\endgroup$ – fgrieu Jul 17 '20 at 6:45
  • 1
    $\begingroup$ @fgrieu: I have seen a lot of cases where we write $a = b \bmod c$ when we really meant $a \equiv b \pmod c$, and in particular, in cases where $a \ne (b \bmod c)$. I am talking about $\bmod$ as is commonly used (and not as formally defined in some terminology manual), and that is a common usage. $\endgroup$ – poncho Jul 17 '20 at 13:01
  • $\begingroup$ I'm in full agreement with that last comment! $\endgroup$ – fgrieu Jul 17 '20 at 14:48

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.