The Keys

Two Primes Make a Modulus

RSA key generation starts with two primes and multiplies them into one modulus. This lesson keeps the numbers tiny so the public modulus can be checked directly.

highlighted = computed this step

Why RSA starts with primes

RSA starts by multiplying two primes into one modulus. The table shows the primes and the public modulus recomputed from them.

n=pqn=pq
Two primes make a modulusRSA key derivation recomputed from the toy primes and public exponent.Two primes make a modulus - n=55quantityvaluep5q11n=p*q55phi=(p-1)(q-1)40e3d=e^-1 mod phi27e*d mod phi1

Pick the two primes

The toy primes are p=5 and q=11. They are tiny so every arithmetic step can be checked.

p=5,q=11p=5,\quad q=11
Two primes make a modulusRSA key derivation recomputed from the toy primes and public exponent.Two primes make a modulus - n=55quantityvaluep5q11n=p*q55phi=(p-1)(q-1)40e3d=e^-1 mod phi27e*d mod phi1

Multiply into the modulus

Multiplying p by q gives n=55. The modulus is the shared arithmetic space for encryption and decryption.

5⋅11=555\cdot11=55
Two primes make a modulusRSA key derivation recomputed from the toy primes and public exponent.Two primes make a modulus - n=55quantityvaluep5q11n=p*q55phi=(p-1)(q-1)40e3d=e^-1 mod phi27e*d mod phi1

What is public and what stays secret

The modulus n can be public. The primes p and q must stay secret because they make the private exponent derivable.

n public,p,q secretn\ \text{public},\quad p,q\ \text{secret}
Two primes make a modulusRSA key derivation recomputed from the toy primes and public exponent.Two primes make a modulus - n=55quantityvaluep5q11n=p*q55phi=(p-1)(q-1)40e3d=e^-1 mod phi27e*d mod phi1

Summary

Two primes make the modulus n=55. NOTE: toy-modulus; no-padding; no-side-channel; no-production; never-roll-your-own. Exact arithmetic on deliberately tiny toy keys; real RSA uses 2048+ bit keys with padding in reviewed libraries.

n=55n=55
Two primes make a modulusRSA key derivation recomputed from the toy primes and public exponent.Two primes make a modulus - n=55quantityvaluep5q11n=p*q55phi=(p-1)(q-1)40e3d=e^-1 mod phi27e*d mod phi1