RSA and prime numbers
An extension of the topic of prime numbers and factorization. The RSA system bases its security on an asymmetry: multiplying two large primes p×q=n is instant, but factoring a large n back into p and q is computationally very hard. This asymmetry is the foundation of encryption on the internet. Ronald Rivest, Adi Shamir and Leonard Adleman published the RSA system in 1978, and received the Turing Award for it in 2002.
I’ll give you a number — decide whether it is prime (RSA builds its keys from these) or composite.
What just happened?
You increased the digit count of the primes p and q. Multiplying p·q stayed instant, but the attempt to recover p and q from n alone became incomparably harder — this asymmetry is exactly what protects your data on the internet.
The RSA system:
Ronald Rivest, Adi Shamir and Leonard Adleman published the RSA system in 1978 — the first practical, widely used public-key cryptosystem. The public key (for encryption, may be public) contains the product n = p × q of two secret, large primes; the private key (for decryption) requires knowing p and q separately.
Why is it secure?
Because factoring a very large number n back into its primes is, given current mathematical knowledge and computing power, practically infeasible in any reasonable time (for numbers with hundreds of digits) — even knowing n publicly, an attacker cannot in practice recover p and q. Hence:
where d is the digit count of p and q — multiplication grows mildly (polynomially) with d, while factoring grows sharply (sub-exponentially) with d.
Where do you meet this?
RSA is today the foundation of encryption on the internet — HTTPS (the padlock in the browser), online banking, digital signatures. For this achievement Rivest, Shamir and Adleman received the Turing Award in 2002 — the highest honour in computer science, the discipline’s equivalent of the Nobel Prize.
Why you need this for the exam:
Primes and factorization into primes are a standard exam topic in mathematics — RSA shows that this “school” mathematics has a very real application: it protects every login and every online transaction.
Remember: multiplying large primes is fast, while factoring their product is very hard. This asymmetry is the foundation of RSA’s security and of most of today’s internet communication.
Theory & formulas
Computational asymmetry
Multiplying large primes is fast: . The reverse task — factoring into and — is, for large numbers, computationally very hard.
Keys
The modulus is public (the public key), while are secret. Encryption and decryption use arithmetic modulo :
Security
As long as no fast factorization is known, recovering the private key from the public one is practically impossible.
Notation: primes, modulus, public exponent, private exponent, message, ciphertext.
Frequently asked questions
›Why is RSA secure?
Because multiplying large primes is fast, but factoring the product back into its prime factors is computationally very hard.
›What is the public key in RSA?
The product n=p×q of two secret, large primes — it can be public, because recovering p and q from it is hard.
›Who created the RSA system?
Ronald Rivest, Adi Shamir and Leonard Adleman, in 1978 — Turing Award in 2002.
Teaching? Embed this experiment on your site.
Free widget — paste it on your school site, blog or notes. It links to the full version.