Q: How do you write algorithms to enycrypt things?

Physicist: There are several algorithms, but almost all of them are all based on “trap-door encryption”.  The idea is that you find some kind of mathematical process that’s easy to run forward, but effectively impossible to run backward, unless you know a trick (which you keep secret). It’s likened to a trap-door because (as every super-villain knows) it’s easy to go through a trap-door in one direction, but difficult in the other.  This is fundamentally different from the encoding schemes most people are familiar with, like “A=2, B=15, C=…” or Igpa Atinla, which are called “substitution cyphers”.  If you know how a substitution cipher is done, then you can not only encode a message, but you can decode it.

But encryption (as opposed to a “cypher”) is different.  Even if you know everything about how to encrypt (encode) a message, you will still be unable to decyrpt (decode) it.  Encryption is relatively new (publicly known since 1977).  Even the famous Enigma Device that the Germans used during WW2 was just a rolling substitution cypher.

The idea is, you allow everybody to know how to do the forward operation (which is known as the “public key”), which allows them to encrypt a message, but keep the secret to the reverse operation to yourself (the “private key”), which allows you to decrypt the messages.  You can think of it as like telling everybody else how to build safes that they can put messages in, but keep to yourself the secret behind opening those safes.

So if you want to talk to a particular person, you use their particular public key.  The central idea of encryption is that you can set up a system where other people can talk to you, perfectly securely, while sending all of their messages through a completely open and public channel.  Were you and a friend so inclined, you could communicate with each other entirely through a sign in Times Square, and no one would ever know what you were saying.  You can even do this without meeting before hand to set us a secret code!

By far the most common method today is RSA encryption.  You can think of RSA as a huge wheel with a different number written on each spoke in a scrambled order.  These numbers correspond to every possible string of letters or numbers of a particular length or shorter.  If you rotate the wheel all the way around (or a multiple of all the way around) you get your message back, but if you only rotate part of the way you get a random number (technically, a pseudo-random number).

RSA encryption. If your message is Johnny Von Purpleshirt, then by “turning the wheel” your encrypted message might be Doggington MacSmellingsomething. Decryption is just turning the wheel the rest of the way to get back to Johnny. The secret is in knowing how many “spokes” the wheel has.  If you know, then you know how to recover or decrypt the message.  If you don’t, then all you can do is encrypt.

The public key is turning the wheel a certain amount (not all the way), and the private key is how much you need to turn the wheel to get it the rest of the way.  The “secret” (and what keeps the private key private) is knowing exactly how big the wheel is.

RSA encryption is secure because the “wheel” involved typically has at least 10¹⁵⁰ “spokes”.  Even with full knowledge of the public key, the “size of the wheel” is really hard to pin down.  It could take any one of approximately 10⁷⁵ values.

If you want to send a message that’s too big to encrypt all at once, you just chop it up into smaller pieces and encrypt them one at a time.  This technique is not dissimilar to the standard means by which one eats something larger than one’s face.

Beyond RSA, if you want to create a new form of encryption (like elliptic-curve or knapsack encryption, for example), you just hire a mathematician who studies some obscure branch of number theory and wait for a while.

Completely ordinary cryptanalyst.

There are a hell of a lot of things that can be done with encryption other than just sending messages.  There’s shared random secret distribution, e-cash, e-signatures, secure voting, all kinds of stuff.  It’s awesome.

Answer Gravy: First, anything you can write with words you can turn into a number.  For example, what you’re reading now is being stored on a server somewhere in the form of a bucket of 1’s and 0’s.  So any discussion of codes and encryption can be reduced to a discussion of numbers.  This is going to be pretty dense and fast:

The ideas behind RSA encryption are modular math and some interesting consequences from group theory.  Modular arithmetic is what you’re doing when you try to figure out what time it will be in more than 12 hours.  For example, if it’s 9:00, then in 5 hours it will be 2:00.  This is “mod 12” arithmetic.  Every time a number is larger than 12 you subtract 12 until it’s smaller.  This “9:00 + 5” example can be written .

There’s a function called the Euler phi, “φ(n)”, that’s defined as the number of numbers less than n that have no prime factors in common with n.  For example, φ(10)=4.  The factors of 10 are 2 and 5, and there are 4 numbers less than 10 that don’t contain any 2’s and 5’s: 1, 3, 7, and 9.

It so happens that , for any x*.  For example, or .  Notice what happens when you raise a number to the “” power:

So, if you raise any x to a particular power (mod m) it eventually cycles back and you get x again.  The process of encrypting something is nothing more than getting x part of the way through the cycle, and decryption is just completing the cycle and coming back to x.

Now, say you’ve got a pair of numbers, k and ℓ, such that kℓ = jφ(m)+1.  To get from the original text, T, to the cyphertext, C, you just raise T to the kth power: .  k is the public key.

To recover the original text just raise C to the ℓ power: .  ℓ is the private key.

That’s basically all there is to RSA encryption.

To create m, you just need to find two large primes, p and q.  To find large primes you just pick a big number and use something like Fermat’s Little Theorem, or a more full-proof modern variant, to test whether or not your pick is prime.  Once you have those primes you can generate m=pq and φ(m)=(p-1)(q-1).

To create k you just need a random number that’s coprime to φ(m), and determining that is easy enough: you can use Euclid’s algorithm.  Once you have k and φ(m) you can find ℓ by solving a Diophantine equation, kx+φ(m)y=1, for x and y, and then ℓ = [x]_φ(m).  Alternatively, ℓ = [k^φ(φ(m))-1]_φ(m).  However, in order to calculate φ(x), you need to know the prime factors of x.  The factors of m are known, because m=pq, but the factors of φ(m) may not be known.

When you’ve got all your number-ducks in a row, you make m and k public.  This means everybody can encrypt.  But you keep ℓ, φ(m), p, and q private.  Without p and q, there’s no (easy) way to find φ(m), and without φ(m) there’s no (easy) way to find ℓ.  There is a very quick way to break encryption keys (find ℓ), but it involves hardware that doesn’t exist just yet.  Here’s how!

*More accurately, and are always true, for any x, when m is the product of two prime numbers, but is only true when x and m have no common factors.  So, for example, and .

The details behind why aren’t complicated, but they aren’t generally interesting either.  The point is, in this case the math still holds up and is easier to understand when you say ““, even though this statement isn’t exactly true.

The wagon wheel picture is from here.