Modular Exponentiation

RSA is built on modular arithmetic. Computing a^b mod n for large numbers is the core operation.

Naive: compute a^b (a HUGE number), then take mod. For RSA-2048, this number has thousands of digits and overflows everything.

Square-and-multiply computes a^b mod n efficiently:

result = 1
base = a mod n
while b > 0:
    if b is odd:
        result = (result * base) mod n
    base = (base * base) mod n
    b = b >> 1
return result

Time: O(log b) multiplications, each mod n. For 2048-bit numbers: ~3000 multiplications. Fast.

Example: 7^560 mod 561:

b=560 (binary 1000110000)
Process bits right-to-left, squaring base:
b=0: skip; base² mod 561
b=0: skip; base² mod 561
... 4 zeros total ...
b=1 (bit 4): result *= base; base²
b=1 (bit 5): result *= base; base²
b=0: skip
b=0: skip
b=0: skip
b=1 (bit 9): result *= base

This is what pow(a, b, n) does in Python. Most languages have built-in modular exponentiation.

For larger gains: Montgomery multiplication, Barrett reduction. Used in production crypto libraries.

The loop leaks the exponent

Look again at the if b is odd branch. When that bit is 1 the loop performs a multiply; when it is 0 it does not. During decryption or signing those bits belong to the private exponent, so how long the loop runs -- and how much power it draws -- is a direct readout of the key. Paul Kocher published exactly this attack in 1996 and recovered private keys from timing measurements alone.

Production implementations therefore never branch on a key bit. They either run a Montgomery ladder, which does one square and one multiply every iteration and only changes which register receives the result, or they multiply unconditionally and throw the result away when the bit is 0. The version you are about to write is the readable one, not the safe one -- and that gap is what the attacks lesson later in this course is about.