Number Theory: Exponentiation with Fast Powering and Montgomery Ladder

17 Dec 2021

Notes Cryptography Number Theory: Exponentiation with Fast Powering and Montgomery Ladder

§ Motivation

We often use exponentiation over finite fields in cryptography, as solving for $a$ given $g, h, n$ in the discrete log problem $g^a \equiv_n h$ is very difficult. However, our exponents are often quite large and computing them through the naïve method of repeated multiplication is not the fastest method asymptotically.

Suppose we wanted to compute $3^{387} \pmod{100}$ , in this case we must compute $387$ multiplications of the base $3$ in the naïve method. With fast-powering we can get it down to $\log_2(387) \approx 9$ steps which have at most $2$ multiplications each.

This reduction in the number of steps is doubly important, because naïve integer multiplication in binary is $\mathcal{O}\left(n^2\right)$ . In cryptography we work with very large bases and exponents, so these time complexities are very important in terms of practicality. So, using both naïve exponentiation and multiplication, we can expect $\mathcal{O}\left(n^3\right)$ time complexity. We can get better asymptotic times for multiplication using Karatsuba, Toom-k, or fast-fourier transforms for increasingly larger numbers; thusly reducing the asymptotic run-time of the fast-powering approach.

Additionally, we can use a result from Euler's theorem in certain cases to reduce the exponent before attempting to compute the exponent value.

§ Fast Powering

Most texts refer to this method as Exponentiation by squaring instead of fast-powering.

Fast Powering

Suppose for a large $A$ we want to compute $g^A \pmod{N}$ , we first want to find the binary expansion of $A$ :

A = \sum_{i=0}^{m}A_i2^i = A_0 + A_1\cdot2 + A_2\cdot2^2 + \dots + A_m\cdot2^m

Then, for each power of two we compute

\begin{align*} g^{2^0} &\equiv a_0\pmod{N}\\ g^{2^1} &\equiv (a_0)^2 \equiv a_1\pmod{N}\\ g^{2^2} &\equiv (a_1)^2 \equiv a_2\pmod{N}\\ &\mkern.5em\vdots\\ g^{2^m} &\equiv (a_{m-1})^2 \equiv a_m\pmod{N}. \end{align*}

Finally, we compute

g^A \equiv \prod_{i=0}^m g^{A_i\cdot 2^i} \equiv g^{A_0} \left(g^2\right)^{A_1}\dots\left(g^{2m}\right)^{A_m} \pmod{N}

§ Montgomery Ladder

Side Channel Attacks

Suppose we performed fast powering, as described previously, for an application like RSA.

In this case Mallory, a malicious actor, wants to recover the our private exponent and has the means to profile the fast-powering algorithm.

Mallory knows the public-key information: the modulus $N$ and the public exponent $e$ .

Mallory sends an encrypted message $C \equiv_N m^e$ to us, and we try to decrypt it with our private key $m \equiv_N m^d$ .

Because Mallory has profiling capabilities, she can tell when the program is running relatively slower or faster.

By counting the slow (squaring) and faster (multiplication) frames, it is possible for her to recover some information about $d$ .

The Montgomery ladder method attempts to mitigate the viability of side-channel attacks by performing a squaring and multiplication at each step.

Montgomery Ladder

# Inputs: base $g$ , binary expansion $A = \{A_i\}_{i=0}^{m}$ of $g$
function MontgomeryLadder( $g$ $g$ , $A$ $A$ )
- $x_1$ $\leftarrow$ $g$
- $x_2$ $\leftarrow$ $g^2$
- for $i$ $i$ in $\{m - 2, \dots, 0\}$ ${m - 2, \dots, 0}$ do
  - if $A_i \equiv 0$ $A_{i} \equiv 0$ then
    - $x_2$ $\leftarrow$ $x_1 * x_2$
    - $x_1$ $\leftarrow$ $x_1^2$
  - else
    - $x_1$ $\leftarrow$ $x_1 * x_2$
    - $x_2$ $\leftarrow$ $x_2^2$
- return $x_1$