The one-way function

The public key is based on a mathematical asymmetry: an operation that is easy in one direction but impossible in the other.

The key example

Multiplying two prime numbers is instantaneous:

p = 6 700 417
q = 2 147 483 647
p × q = 14 388 460 000 000 000 (approximately)

Finding p and q from the product alone is very difficult. For numbers each 300 digits long, no known algorithm can do this within a reasonable time, even with every computer on the planet.

This is the factoring problem.

What you need to understand

The difficulty has not been demonstrated: it has not been proven that factorisation is impossible to carry out quickly. It has merely been observed that, despite decades of effort, no one has managed to do so.

This is a key difference compared to a disposable face mask:

	Disposable face mask	RSA
Security	proven	assumed
Based on	information	computational difficulty
Withstands	any level of power	the means known today

If someone were to discover a fast factorisation algorithm tomorrow, RSA would collapse overnight. This is an accepted risk, not an oversight.

The quantum threat

This is not science fiction: Shor’s algorithm, published in 1994, efficiently factors numbers… on a quantum computer. Current machines are a long way from the scale required, but the risk has been identified.

That is why standardisation bodies have been working for several years on post-quantum cryptography, based on other difficult problems rather than factorisation.