How to Make an Unbreakable Code

By Edward B. Burger, Southwestern University

Throughout history, people have had a desire to keep certain information hidden from other people. Communications involving business transactions, national security, military plans, and even some romantic trysts needed to be kept secret from various parties. Enter the search for an unbreakable code.

The earliest known example of cryptography was found in Egyptian hieroglyphics around 2500 BCE. This may have been more for amusement than for secret communication. The earliest simple substitution ciphers, known as monoalphabetic substitution ciphers, may have been used by Hebrew scholars around 550 BCE.

In a monoalphabetic substitution cipher, one letter is substituted for another. For example, every occurrence of the letter A might be replaced by the letter W, all Bs might be replaced by the letter M, all Cs might get replaced by the letter R, and so forth, down the alphabet. With this particular scheme that I just made up, the word CAB would be encoded to read “RWM.”

Caesar Talks to His Generals

A Caesar cipher is a special case of the monoalphabetic substitution cipher in which each letter is replaced by the letter a fixed number of positions down the alphabet. For example, if we replace A by C—notice that C is two letters away from A—then B would be replaced by two letters away from it, which would be D; C would be replaced by two letters away, which would be E; and so forth, all the way down to Z. When we get to Z, we come back to the beginning of the alphabet; so for Z, we go two letters later, which would be B. The Caesar cipher is named after Julius Caesar, who, in the 1st century BCE, used such a cipher with a shift of three to communicate with his generals. Such monoalphabetic encryption schemes are very easy to break.

This is a transcript from the video series An Introduction to Number Theory. Watch it now, on The Great Courses.

In the basic ciphers, to decode an encrypted message, one reverses the encryption process. Thus, if people know how to encode a message sent to us, then they also have the power to decode other messages.

Learn more about what is to be expected from randomness

In Search of the Perfect Code

Wouldn’t it be great to have a coding scheme such that when people use it to send us messages, the encoding process is easy for them to use while at the same time, we’re certain that we’re the only ones able to decode the messages?

In this fantasy cipher, we wouldn’t have to trust our friends at all. If they lose the codebook and it gets into the wrong hands, it would not jeopardize the coding scheme. In other words, in our fantasy cipher, knowing how to encode messages would not provide any information as to how to decode it.

If this fantasy were real, then there would be no need to keep the encoding process a guarded secret. Instructions describing how to encode messages could be made public, and only the decoding process would need to be kept secret. In fact, in this fantasy, the encoded messages themselves could be made public as well. Our friends could take out ads in The New York Times with an encrypted message directed to us. Everyone would see it, but we’d be the only people who would know how to decode it.

The problem is, if a nemesis of ours sees a secret message sent, why couldn’t he take the encryption process—which we made public—and just run that process backward to decode the message made just for us? This is a problem. To make this fantasy a reality, we would need to have a secret hidden within the public encryption process. Even though we make this process public, there’s something secret.

We’re now ready to apply number theoretic concepts to show that just such a crypto-fantasy can be a reality. The main question remains: How can the encryption scheme be at once public—everyone knows how to encode messages—and private—only the rightful receiver can decode the messages? Such amazing ciphers are known as public key codes, because the key for encryption is made public.

Learn more about why negative times negative is always positive

Make Your Own Code in Eight Perfect Shuffles

We’ll make our fantasy a reality by combining the concepts of prime numbers together with modular arithmetic in an extremely clever and elegant way. We begin with a metaphor that captures the idea of this modern encryption scheme. Take a brand-new deck of 52 playing cards. If you were to take it and perform eight perfect shuffles, also known as faro shuffles—you cut the deck exactly in half: 26 and 26—and then shuffle without making a mistake. If you make eight perfect shuffles, then look at the cards, and magically, they’ll return to their original order. It’s absolutely amazing, but if you try it, you have to be able to perform eight perfect shuffles in a row.

Suppose now that we performed just five perfect shuffles: the order of the cards would look thoroughly mixed up, without any semblance of pattern or structure. However, we know a systematic method that would return this mess back to a familiar, less chaotic pattern. We’d perform three more shuffles, bringing the number of shuffles up to eight, and voilà—the cards are transformed from a random mess back to their original order.

Notice that we could employ this shuffling idea to produce an encryption scheme. Our friend could write her message to us, one letter on each card; so she could say: M, A, T, H, and so forth. Then she would just shuffle a certain pre-agreed amount of times. Let’s say five. So she performs five perfect shuffles, and then she delivers the deck of cards to us. If anyone looks at them, it looks jumbled, but we know exactly what to do. We would shuffle three times and then we would be able to read the message. Of course, if we were to use this encryption scheme, anyone sending us a coded message could decode any other message sent to us as easily as we could. Easy, assuming that we can do perfect shuffles. To have such a scheme truly fulfill our encryption fantasy, we would need to first figure out how to mathematically shuffle our message and then how to make that shuffling process public without allowing others to unshuffle our message.

Learn more about how patterns hold the key to astounding feats of mental calculation

Number Theory Provides the Key

Here’s the moment where we introduce number theory. The public feature arises from the fact that factoring extremely large natural numbers is impossible, for all practical purposes, despite knowing that such a factorization is possible in theory. Now we’re going to make a distinction between practice and theory.

To see the basic idea behind this public-versus-secret dichotomy, suppose that someone announced the number 6 and also revealed a secret. The secret is that this number is the product of exactly two primes. Can we uncover the secret? Of course:
6 = 2 × 3. There. In some sense, we just broke the code. What if, instead of 6, the announced number that’s the product of two primes was 91? Can we break this code? With some thought, maybe a little bit of arithmetic, we could figure out that 91 is 7 × 13, and thus we’ve broken this code as well, although it took us a little bit longer.

What if the announced number was 2,911? Can we break this code? No, not so easily. But if we use a calculator or a computer, we’d be able to discover that 2,911 equals 41 × 71, and we’ve broken that code, too.

What if the announced number was a 100-digit number? For all practical purposes, even knowing that this number is, in fact, a product of exactly two primes, we would have no way of determining what the two factors are. Even computers have limits to the size of numbers that they can factor. In this way, notice that we can both announce a piece of information publicly—namely, this enormous number—and yet, from a practical point of view, within that public information is a secret that only we, as the receiver, know.

This reality is how individuals will be able to announce an encryption process without revealing the decryption process. To encrypt messages, people need only use the huge natural number. However, to decrypt or decode an encoded message, the receiver will need the prime factors of that huge number, which, for all practical purposes, is a true secret.

Learn more about computing infinite sums with the visual approach

Common Questions About Unbreakable Codes

This article was updated on July 30, 2020

Keep Reading
Pi: The Most Important Number in the Universe?
Mathematics and Plato’s Guardians
Isaac Newton’s Influence on Modern Science