RSA: generating a key pair and exponentiating by squaring

RSA is a block cipher over integers

Rivest, Shamir and Adleman published RSA at MIT in 1978, and it is still the public-key algorithm most likely to appear on an exam paper. It is a block cipher in which the plaintext and the ciphertext are integers in the range $[0,n-1]$ for some modulus $n$. Encryption and decryption are the same operation with different exponents:

$$C=M^e\mathrm{mod}nM=C^d\mathrm{mod}n$$

The public key is the pair $\{e,n\}$ and the private key is $\{d,n\}$. The modulus is in both, so the secret is $d$ alone.

Key generation in five steps

1. Pick two distinct primes p and q, kept private.
2. Compute the modulus $n=p\cdot q$, which becomes public.
3. Compute $\varphi (n)=(p-1)(q-1)$ — Euler's totient, the count of integers below n that share no factor with it. This step is where the primality of both factors is doing the work.
4. Choose a public exponent e with $\gcd (e,\varphi (n))=1$ and $1<e<\varphi (n)$.
5. Compute the private exponent as the modular inverse $d=e^{-1}\mathrm{mod}\varphi (n)$, i.e. the d satisfying $e\cdot d\equiv 1(\mathrm{mod}\varphi (n))$.

Step 5 is the reason step 4 demands coprimality: an inverse of e modulo $\varphi (n)$ exists if and only if the two are relatively prime. Pick an e that shares a factor with $\varphi (n)$ and there is no d at all, and what you have built is not RSA.

Worked example — our key pair, end to end

Take p = 59 and q = 71.

• $n=59\cdot 71=4189$.
• $\varphi (n)=58\cdot 70=4060$.
• Choose e = 13. Check coprimality: $4060=2^2\cdot 5\cdot 7\cdot 29$, which does not include 13, so $\gcd (13,4060)=1$ and an inverse exists.
• Invert: d = 937. Verify without trusting anything — $13\cdot 937=12181$, and $12181=3\cdot 4060+1$, so $13\cdot 937\equiv 1(\mathrm{mod}4060)$. That single multiplication is the whole check, and it costs five seconds on the permitted calculator.

Publish $\{13,4189\}$; keep $\{937,4189\}$ and destroy p, q and $\varphi (n)$, because any one of them hands an attacker the private key immediately.

Now encrypt the plaintext block M = 1234: $C=1234^{13}\mathrm{mod}4189=3276$. Decrypt it: $3276^{937}\mathrm{mod}4189=1234$. The message comes back.

Doing that exponentiation by hand

$1234^{13}$ is a 41-digit number. You do not compute it. Square-and-multiply decomposes the exponent into powers of two and reduces modulo n at every single step, so no intermediate value ever exceeds $n^2$.

Write the exponent in binary: $13=1101_2=8+4+1$. So $M^{13}=M^8\cdot M^4\cdot M^1$. Build the squarings mod 4189:

• $M^1=1234$
• $M^2=1234^2\mathrm{mod}4189=2149$
• $M^4=2149^2\mathrm{mod}4189=1923$
• $M^8=1923^2\mathrm{mod}4189=3231$

Multiply the ones the binary expansion selected, reducing as you go: $3231\cdot 1923\mathrm{mod}4189=926$, then $926\cdot 1234\mathrm{mod}4189=3276$. That is four squarings and two multiplications instead of twelve multiplications and a 41-digit intermediate — and the cost of the exponent's 1 bits, versus its 0 bits, is exactly the leak the timing attack in L5.3 exploits.

Reduce at every step. Computing $1234^{13}$ first and taking the modulus last is arithmetically identical and computationally hopeless; on a 2048-bit modulus it is not merely slow, it does not fit in memory.