Korva is a scroll of the internet’s best ideas.
RSA hides a key in two primes
Signing with keys
A message is signed with a private key, and anyone can check it with the public key. That lets a server prove its identity or a piece of code be signed, and it sits behind loads of the digital signatures and certificates on the internet.
The two secret primes
The public key contains a number called N, a semi-prime: one prime P multiplied by another prime Q. N goes out on certificates all the time, while P and Q stay secret. With P and Q, the private key can be derived, and whoever holds a server's private key could forge signatures for that site, which makes spoof websites and phishing attacks much easier.
Why guessing fails
Getting P and Q from N by guessing would probably take hundreds of millions of years with decent compute at any realistic key size. A list of known primes does not shrink the search. Primality tests give high confidence that a number is prime, but nobody keeps a list of 2,000-bit primes. Every bit added doubles the search space, and 2,000 bits is some 600 digits.
How does a public key check a signature?
In RSA, the signer raises a fingerprint of the message, called a hash, to the power of the private exponent modulo N. The verifier raises the result to the public exponent modulo N and compares it with the hash. This works because the two exponents are chosen so that applying one and then the other returns the original number. The scheme is named for Ron Rivest, Adi Shamir, and Leonard Adleman, who published it in 1977.
Why does knowing P and Q give the private key?
The private exponent is the modular inverse of the public exponent, taken modulo (P minus 1) times (Q minus 1). Computing that modulus requires P and Q individually. Without them, finding it is believed to be as hard as factoring N itself. With P and Q, a short run of Euclid's algorithm produces the private exponent.
How hard is factoring in practice?
The fastest known classical method for large numbers is the general number field sieve. In 2020, a research team factored the 829-bit challenge number RSA-250 with it, using roughly 2,700 core-years of computing time. Each added bit raises the cost, which is why keys in use today are 2,048 bits or longer. A 2,048-bit modulus has 617 decimal digits.
More from Computerphile
