Crypto 2 of 2 — Part 1
To send a Caesar secret, both people must first share the shift. That means the key has to travel, and a key that can be intercepted is a lock that can be picked. This problem haunted secret-keeping for two thousand years. Then in the 1970s, a few people found something that sounds impossible: you can hand your lock to the entire world, enemies included, and it still only opens for you.
Think of a street mailbox. Anyone can drop a letter through the slot. Only you hold the key to take the mail out. The slot is public. The key is private. Anyone can give you a secret; only you can read it. That's public-key encryption: two keys as a matched pair, one locks, one unlocks, not the same key. Publish the locking one, keep the unlocking one.
In Caesar, a key was a number from 0 to 25. Here, you build one from two prime numbers. Pick your primes below, and the page derives the rest.
In Caesar's cipher the key was one number from 0 to 25 -- simple, but easy to steal. Here you build a key from two prime numbers.
Multiplied together, p and q give you n:
Anyone can see n -- it goes on your public key. What they can't easily do is factor it back into the two primes that made it. That difficulty is the lock.
e is what encrypts. Someone raises each letter's number to the power e, then wraps the result using n. Only d (your private key, revealed below) can unscramble it.
Your public key is the pair (e, n). Share it with anyone who wants to send you an encrypted message.
d is not chosen -- it's calculated from a number called the totient of n. Of all the numbers from 1 to n, how many share no factor with n? Since n = p × q, the only ones that do share a factor are multiples of p or q. Everything else is counted. There's a shortcut:
The crossout shows which numbers get eliminated:
These two tools work independently. Share your public key (e, n) with a friend, have them encrypt a message here, and decrypt it with your private key d.
Enter the recipient's public key (e and n) -- the person who will decrypt this.
Space-separated numbers. Without the private key d, they're noise.
Enter your d and n from Steps 1 and 2, then paste the ciphertext you received.
What does an eavesdropper see? The public key, containing n. To break in they need the private key, which requires the totient, which requires the two primes that multiply to n. They must un-multiply n. For n = 33 that's mental math -- that's why toy keys are toys. Real keys use a 600-digit n; multiplying two 300-digit primes is easy, pulling the product back apart is something no computer that will ever exist could finish before the sun burns out.
The lock is a public display. The only thing hidden is the two primes -- and hiding those is enough. Learn more: Public-key cryptography · RSA