Modular Exponentiation and the Cost of One Key Operation

Every classical public-key algorithm reduces, at its core, to one arithmetic routine: raising an integer to a large power modulo another integer. RSA decryption computes $c^d \bmod n$. Diffie-Hellman computes $g^a \bmod p$. Elliptic curve scalar multiplication is the same square-and-multiply loop wearing different notation. The security of these schemes rests on the exponent being unrecoverable; the practicality rests on the exponentiation being cheap. Those two facts are in tension, and the resolution is the subject of this article.

The naive exponentiation and why it fails

Textbook exponentiation is repeated multiplication. To compute $g^{1000}$, multiply $g$ by itself a thousand times. The count is proportional to the exponent’s value, and a private exponent in RSA is a number near $2^{2048}$. Nobody can perform $2^{2048}$ multiplications; the universe is not old enough.

The fix is a change of representation. Write the exponent in binary:

$$a = \sum_{i=0}^{k-1} a_i 2^i, \qquad a_i \in {0,1}$$

Then $g^a = \prod_{i} g^{a_i 2^i}$. Each factor is obtained by repeatedly squaring $g$, and the total number of squarings equals the bit length $k$ rather than the value. Since a 2048-bit exponent has $k = 2048$, the work drops from an astronomical number to a few thousand modular multiplications. This is square-and-multiply, and it is the difference between an impossible scheme and a deployable one.

The observation behind it is not cryptographic. It is the same reason a compiler strength-reduces x * 8 to a shift: the operation’s cost should depend on the size of the representation, not on the magnitude of the number.

Reading the exponent from left to right

The left-to-right binary method keeps a running accumulator and consumes exponent bits from the most significant end. At each step the accumulator is squared; if the current bit is one, it is also multiplied by the base.

def modexp(base, exponent, modulus):
    result = 1
    base %= modulus
    for bit in bin(exponent)[2:]:        # most significant bit first
        result = (result * result) % modulus
        if bit == '1':
            result = (result * base) % modulus
    return result

For a $k$-bit exponent the loop runs $k$ times. A random exponent has about $k/2$ set bits, so the total is roughly $k$ squarings and $k/2$ multiplications. The 2048-bit case therefore costs about 3072 modular multiplications, not $2^{2048}$.

The public exponent 65537 deserves attention because it is the common choice in RSA and it is deliberately sparse. In binary it is 1 0000 0000 0000 0001: seventeen bits, two of them set. Encryption and signature verification with this exponent need sixteen squarings and one multiplication, on the order of seventeen modular multiplications in total. The private operation with a full-size $d$ needs about 3000. That ratio, near two orders of magnitude, is why a server can verify signatures far faster than it can produce them, and why the asymmetry is structural rather than an implementation artifact.

What a modular multiplication actually costs

The loop above hides the expensive part. Each (result * base) % modulus multiplies two 2048-bit integers and reduces the product. Schoolbook multiplication of two $n$-limb numbers performs $n^2$ limb multiplications; with 64-bit limbs a 2048-bit value is 32 limbs, so one product is 1024 limb multiplications. Karatsuba reduces the exponent from 2 to about 1.585 at the cost of extra additions, and becomes worthwhile above a few dozen limbs, which is exactly the range RSA uses.

The reduction step is the more interesting problem. Computing the full product and then dividing by $N$ requires a division whose quotient is as long as the product, and division is the slowest of the basic big-integer operations. Montgomery’s method avoids it by representing each residue $x$ as $xR \bmod N$ for a fixed $R = 2^{64\ell}$ chosen to align with the machine word for an $\ell$-limb modulus. Multiplication in that representation replaces trial division with a sequence of shifts, masks, and multiplications by a precomputed constant $N’ = -N^{-1} \bmod R$. The result is a value that may exceed $N$ by at most one multiple, corrected by a single conditional subtraction.

The practical consequence is that a modular exponentiation is not “a multiplication per bit” but “a multiplication plus a reduction per bit, both of which are $O(\ell^2)$ in limb count”. Doubling the modulus size roughly quadruples the per-step cost and doubles the number of steps, so the total grows as the cube of the key size. This is the arithmetic reason that 4096-bit RSA is not twice as slow as 2048-bit RSA but several times slower.

Windowed methods and the memory trade

Binary square-and-multiply uses one multiplication per set bit. A $w$-bit window precomputes all $2^w$ powers $g^0 \ldots g^{2^w-1}$ and then processes the exponent $w$ bits at a time, reducing the multiply count to about $k/w$ at the cost of $2^w$ precomputed values and some table lookups.

Window width $w$	Table entries	Multiplications for 2048-bit exponent
1 (binary)	2	about 3072
4	16	about 2576
5	32	about 2490
6	64	about 2450

The counts are arithmetic, not measurements: $k$ squarings plus $k/w$ multiplies plus $2^w$ precomputed entries. The shape is the point — returns diminish quickly. Each extra window bit doubles memory and saves about $k/w^2$ multiplications. Implementations typically settle at $w = 4$ or $5$ for a private exponent and use the sparse public exponent without any window at all, since the table would cost more than it saves.

Sliding windows improve on fixed windows by allowing variable-length gaps, so the table only needs odd powers. That halves the table for the same average window width, which is why the technique appears in most production bignum libraries under names like sliding-window exponentiation.

Constant time is a different algorithm

All of the above optimizes for average cost. A private-key operation also has to run in time independent of the secret, and that constraint invalidates the optimizations.

The naive loop branches on the exponent bit: it multiplies only when the bit is one. Branching leaks the Hamming weight of the exponent through timing, and finer measurements recover the bit positions. Kocher’s 1996 timing attack demonstrated exactly this against real Diffie-Hellman and RSA implementations. A constant-time implementation instead always performs the multiplication and selects between the squared value and the squared-multiplied value with a mask derived from the bit:

# branch-free: both candidates are computed, the bit selects one by mask
sq = acc * acc % n
prod = sq * base % n
mask = -bit                        # 0 when the bit is clear, all ones when set
acc = (sq & ~mask) | (prod & mask)

The two multiplications always happen; only the selection varies, and it is a bitwise operation with no data-dependent control flow. The cost is one extra multiplication per bit, so the constant-time version of a 2048-bit private exponentiation does about 4096 modular multiplications instead of 3072. Roughly a third more work buys the elimination of an entire attack class. Montgomery reduction and windowing survive in constant-time form; the bit-skipping and the early exit on a zero accumulator do not. Even the conditional subtraction at the end of Montgomery reduction must be replaced with a mask-based select, because a branch on whether the intermediate exceeded $n$ leaks information about the operands.

This is the first place where a recurring pattern appears: the mathematically optimal algorithm and the safely implementable algorithm are not the same algorithm, and the gap is paid in constant factors. The group structure that makes exponentiation one-way is examined in Discrete Logarithms and Group Order, and the RSA-specific use of this routine, including the Chinese remainder shortcut that halves the exponent size, appears in RSA Key Generation and the Prime Search.

Where the exponent’s size stops helping

Two exponents of the same bit length do not give the same security. If the private exponent $d$ is small, the attack surface changes entirely: Wiener’s continued-fraction attack recovers $d$ when it is below roughly $n^{1/4}$, because a small $d$ makes $ed - 1$ a small multiple of $\varphi(n)$ and that multiple is findable from the public continued fraction expansion of $e/n$. Key generation therefore rejects small $d$ even though a small $d$ would make the private operation dramatically faster. The speed is available; it is simply unsafe.

The same logic governs the group. Exponentiation is only one-way if the group order has no small factors and no special structure that admits a faster logarithm. An exponentiation routine that is correct for every modulus is not therefore secure for every modulus, which is why the choice of group is a separate design decision from the choice of loop.