Multiply two big primes and you get a number nobody can factor back apart in a lifetime. RSA turns that one-way street into a public lock: everyone can encrypt to you, only you can decrypt. Its engine is modular exponentiation on huge numbers — which is exactly the bignum this campaign just put into I-13. RSA now round-trips in real I-13.
THE TECHNIQUE encrypt with (e,n), decrypt with (d,n)
Pick primes p, q; let n = pq. Choose e; find d so that e·d ≡ 1 mod (p−1)(q−1). Then c = me mod n encrypts, and m = cd mod n decrypts. Knowing d without factoring n is the hard part. Try it (toy primes p=61, q=53). live demo
HISTORY & CREDIT public in 1977, secret since 1973
The famous initials are three; a fourth man had it years earlier and could tell no one. cited
1969–73 · at Britain’s GCHQ, James Ellis conceives “non-secret encryption” (1969); Clifford Cocks works out the RSA scheme in 1973 — and it is stamped classified. 1977 · Ron Rivest, Adi Shamir & Leonard Adleman (MIT) independently discover it and unveil it — an MIT memo and Martin Gardner’s column in 1977; the formal CACM paper follows in 1978. The public birth, and the name. 1997 · GCHQ declassifies Cocks’s work; he receives credit two decades late (and, later, a CBE). security · rests on the hardness of factoring; the RSA-129 challenge number took 17 years and a global effort to crack.
The same idea, twice: once in the open to fame, once in a vault to silence. restored
RECOMMEND FOR I-13 the bignum payoff — RSA runs
RSA is modular exponentiation, and with the bignum the campaign just added, it round-trips exactly in real I-13 (encrypt m=65, then decrypt back to 65):
$ i13 run rsa.i13 # big(), modexp over bignum
cipher = 2790 # 65^17 mod 3233
plain = 65 # 2790^2753 mod 3233 -> back to the message
Recommend:nothing new — and it is the clearest bignum dividend yet. Dart 032 (Rabin–Miller) and 035 (Diffie–Hellman) flagged bignum as the wall; the author built it; RSA — the algorithm that is the internet’s padlock — now runs whole in the counted language, toy primes and all. Honest note: real 2048-bit RSA also wants prime generation (Rabin–Miller, dart 032) at scale — which bignum + a seeded PRNG now make expressible. The pieces the darts asked for, assembled.