Cryptography explained in simple words.

Imagine two people who share an important secret have to split up. This requires them to communicate private information from a distance. However, an eavesdropper named Eve also wants this information and has the ability to intercept their messages. So, Alice decides to communicate using letters written in some kind of secret code. The following analogy is helpful: first Alice locks her message in a box using a lock that only her and Bob know the combination to. this is known as encryption. Then, the locked message is sent to Bob. When Bob receives the Box, he opens it using the code they shared in advance, this is called decryption. Cryptography begins when we abandoned physical locks and used ciphers instead. Think of them as virtual locks. Ciphers allow Alice and Bob to scramble and descramble their messages so that they would appear meaningless if Eve intercepted them. Cryptography has been around for thousands of years. It has decided Wars and is at the heart of the worldwide communication network. Today, the fascinating story of cryptography requires us to understand two very old ideas related to number theory and probability theory.

Imagine we are living in prehistoric times. Now, consider the following: how did we keep track of time without a clock? All clocks are based on some repetitive pattern which divides the flow of time into equal segments. To find these repetitive patterns, we look towards the heavens. The Sun rising and falling each day is the most obvious however to keep track of longer periods of time we looked for longer cycles. For this, we looked to the moon which seemed to gradually grow and shrink over many days. When we count the number of days between full moons, we arrive at the number 29. This is the origin of a month. However, if we try to divide 29 into equal pieces we run into a problem: it is impossible. The only way to divide 29 into equal pieces is to break it back down into single units. 29 is a prime number, think of it as unbreakable. If a number can be broken down into equal pieces greater than one, we call it a composite number. Now, if we are curious, we may wonder how many prime numbers are there and how big do they get. Let's start by dividing all numbers into two categories. We list the primes on the left and the composites on the right. At first, they seem to dance back and forth, there is no obvious pattern here so let's use a modern technique. To see the big picture the trick is to use a Ulam spiral. First, we list all possible numbers in order in a growing spiral then we color all the prime numbers blue. Finally, we zoom out to see millions of numbers this is the pattern of primes which goes on and on forever. Incredibly, the entire structure of this pattern is still unsolved today. We are onto something so let's fast forward to around 300 BC in ancient Greece. A philosopher known as Euclid of Alexandria understood that all numbers could be split into these two distinct categories. He began by realizing that any number can be divided down over and over until you reach a group of smallest equal numbers and by definition these smallest numbers are always prime. So, he knew that all numbers are somehow built out of smaller primes. To be clear, imagine the universe of all numbers and ignore the primes. Now pick any composite number and break it down and you are always left with prime numbers. So, Euclid knew that every number could be expressed using a group of smaller primes. Think of these as building blocks. No matter what number you choose it can always be built with an addition of smaller Prime's. This is the root of his discovery known as the fundamental theorem of arithmetic. As follows, take any number say 30 and find all the prime numbers it divides into equally this we know as factorization. This will give us the prime factors. In this case, 2 3 & 5 are the prime factors of 30. Euclid realized that you could then multiply these prime factors a specific number of times to build the original number, in this case you simply multiply each factor wants to build 30, 2 times 3 times 5 is the prime factorization of 30. Think of it as a special key or combination. There is no other way to build 30 using some other groups of prime numbers multiplied together. So, every possible number has a one and only 1 prime factorization. A good analogy is to imagine each number as a different lock. The unique key for each lock would be its prime factorization. No 2 locks share a key, no two numbers share a prime factorization.

In the 16th century, an Italian mathematician named Cardano had a well-known gambling addiction. He wrote letters in which he bragged about his ability to beat his friends at dice games. His trick was to place his bets using his ideas from mathematics instead of hunches or luck. He came up with a method of calculating the exact probability of random events such as say rolling Snake Eyes (two dice showing one). It is based on a powerful property Cardano noticed. Every outcome no matter how many dice you roll, is equally likely. this allowed him to calculate the probability by developing what's now called a probability space. First, he counts all possible outcomes known as the sample space. For a single dice, these are the six possible phases. then he defines the event in question, such as rolling a 1, which can occur in one way. The probability is then found by dividing the event by all possible events. Which in this case works out to 1/6. Realize the cold calculating logic here, there is no such thing as a lucky number, no divine intervention, the probability of rolling any number is exactly 1/6. Now, the same logic applies when we roll multiple dice. Imagine you needed to know the probability of rolling a pair. First, he counts the size of the sample space with two dice rolls there are 36 possible outcomes, 6 times 6. Then you count the number of ways this event can occur there are 6 different pairs. So, 6 divided by 36 is the probability of rolling a pair, also 1/6. This simple yet powerful idea allowed Cardano to bet according to the true probability while his opponent's place their bets based on hunches and lucky numbers. Remember, this works with multiple rolls imagine we needed to know the exact probability of rolling three ones. Simple, first we figure out the size of the sample space for three dice, this is 6 times 6 times 6 or 216 and there is only one way to roll three 1s. So, the probability is 1 divided by 216 this was the trick it was not based on magic but mathematics. Remember, to calculate the probability of a random event such as a dice roll you divide the number of ways that event can occur by all possible outcomes.

Consider the following: imagine two rooms. Inside each room is a switch. In one room, there is a man who flips his switch according to a coin flip. if he lands heads the switch is on, if he lands tails the switch is off. In the other room, a woman switches her light based on a blind guess she tries to simulate randomness without a coin. Then we start a clock and they make their switches in unison. Can you determine which lightbulb is being switched by a coin flip? The answer is yes, but how? The trick is to think about properties of each sequence rather than looking for any specific patterns. For example, first we may try to count the number of ones and zeros which occur in each sequence. This is close but not enough since they will both seem fairly even. The answer is to count sequences of numbers such as runs of three consecutive switches. A true random sequence will be equally likely to contain every sequence of any length. This is called the frequency stability property. Humans favor certain sequences when they make guesses resulting in uneven pattern. One reason this happens is because we make the mistake of thinking certain outcomes are less random than others. But realize, there is no such thing as a lucky nerve, there is no such thing as a lucky sequence. If we flip a coin ten times it is equally likely to come up all heads all tails or any other sequence you can think of.

The first well-known cipher, a substitution cipher was used by Julius Caesar around 58 BC. It is now referred to as the Caesar cipher. Caesar shifted each letter in his military commands in order to make them appear meaningless should the enemy intercept it. imagine Alice and Bob decided to communicate using the Caesar cipher. First, they would need to agree in advance on a shift to use, say three. So, to encrypt her message Alice would need to apply a shift of three to each letter in her original message so “A” becomes “D”, “B” becomes “E”, “C” becomes “F” and so on. This unreadable or encrypted message is then sent to Bob openly. Then Bob simply subtracts the shift of three from each letter in order to read the original message. Incredibly, this basic cipher was used by military leaders for hundreds of years after. However, a lock is only as strong as its weakest point. A lock breaker may look for mechanical flaws or failing that extract information in order to narrow down the correct combination. The process of lock breaking and cold breaking are very similar. The weakness of the Caesar cipher was published 800 years later by an Arab mathematician named Al-Kindi. He broke the Caesar cipher by using a clue based on an important property of the language a message is written in. If you scan text from any book and count the frequency of each letter you will find a fairly consistent pattern. This can be thought of as a fingerprint, we leave this fingerprint when we communicate without realizing it. This clue is one of the most valuable tools for a codebreaker. To break this cipher, they count up the frequencies of each letter in the encrypted text and check how far the fingerprint has shifted. For example, if “H” is the most popular letter in the encrypted message instead of “E” then the shift was likely three. So they reverse the shift in order to reveal the original message. This is called frequency analysis and it was a blow to the security of the Caesar cipher

a strong cypher is one which disguises your fingerprint. To make a lighter fingerprint, is to flatten this distribution of letter frequencies. By the mid 15th century, we had advanced the polyalphabetic ciphers to accomplish this. Imagine Alice and Bob shared a secret Shift word. First, Alice converts the word into numbers according to the letter position in the alphabet. Next, this sequence of numbers is repeated along the message. Then, each letter in the message is encrypted by shifting according to the number below it. Now, she is using multiple shifts instead of a single shift across the message as Caesar had done before. Then the encrypted message is sent openly to Bob. Bob decrypt the message by subtracting the shifts according to the secret word he also has a copy of. Now imagine a Code Breaker, Eve, intercepts a series of messages and calculates the letter frequencies. She will find a flatter distribution or a lighter fingerprint. So how could she break this? Remember, codebreakers look for information leaked, the same is finding a partial fingerprint. Anytime there is a differential in letter frequencies, a leak of information occurs. This difference is caused by repetition in the encrypted message. In this case Alice's cipher contains a repeating codeword. To break the encryption, Eve would first need to determine the length of this shift board used not the word itself. She will need to go through and check the frequency distribution of different intervals. When she checks the frequency distribution of every fifth letter the fingerprint will reveal itself. The problem now is to break five Caesar ciphers and a repeating sequence. Individually this is a trivial task as we have seen before. The added strength of this cipher is the time taken to determine the length of the shift word used. The longer the shift word the stronger the cipher.

For over 400 years the problem remained: how could Alice design a cipher that hides her fingerprint thus stopping a leak of information? The answer is randomness. Imagine Alice rolled a twenty six sided die to generate a long list of random shifts and shared this with Bob instead of a code word. Now to encrypt her message, Alice uses the list of random shifts instead. It is important that this list of shifts be as long as the message as to avoid any repetition. Then, she sends it to Bob who decrypts the message using the same list of a random shifts she had given him. Now, Eve will have a problem because the resulting encrypted message will have two powerful properties: one, the shifts never fall into a repetitive pattern and two, the encrypted message will have a uniform frequency distribution. Because there is no frequency differential and therefore no leak, it is now impossible for Eve to break the encryption. This is the strongest possible method of encryption and it emerged towards the end of the 19th century. It is now known as the one-time pad. In order to visualize the strength of the one-time pad we must understand the combinatorial explosion which takes place. For example, the Caesar cipher shifted every letter by the same shift, which was some number between 1 and 26. So, if Alice was to encrypt her name it would result in one of 26 possible encryptions a small number of possibilities easy to check them all known as brute-force search. Compare this to the one-time pad where each letter would be shifted by a different number between 1 and 26. now think about the number of possible encryptions it's going to be 26 multiplied by itself 5 times which is almost 12 million. Sometimes, it's hard to visualize so imagine she wrote her name on a single page and on top of it stacked every possible encryption. How high do you think this would be? With almost 12 million possible 5 letter sequences, this stack of paper would be enormous. Over 1 kilometer high. When Alice encrypts her name using the one-time pad, it is the same as picking one of these pages at random. From the perspective of Eve, the codebreaker, every five letter encrypted word she has is equally likely to be any word in this stack. So, this is perfect secrecy in action.