Ancient encryption technology

See how we've hidden private information throughout history

Caesar Cipher

The first and most widely known encryption method is the Caesar cipher in 58 BC.

encryption

The encryption method of Caesar Cipher is that at the beginning of encryption and decryption, both parties need to determine a shift length. The encryption party shifts the words in the plaintext one by one according to the selected shift length to obtain the encrypted content; the decryption party shifts the ciphertext in the reverse direction according to the selected shift length to obtain the plaintext.

For example, for the encryption condition, the plaintext is hello, and the encryption process with a translation length of 3 is:

1. According to the order of the 26 English letters, h is 3 letters behind it, which is k.
2. According to the first step, the remaining plaintext letters can be deduced in the same way, and the ciphertext can be obtained as khoor

Cracking

There are two key points to cracking the Caesar cipher:

1. A statistical chart showing the frequency of letters in the language used in the plain text (this can be done through a large number of statistical analysis books in the language)
2. A frequency chart of the occurrence of the letter in the ciphertext obtained by a large number of statistics
3. A simple shift of the graphs obtained in steps 1 and 2 will reveal the shift used in encryption.

The reason why the Caesar cipher can be cracked in this way is that human language is actually a regular thing, and the frequency of each letter in the language is also part of this regularity (this is often overlooked). For the selected displacement, it is actually just a translation of the original letter frequency chart - because each letter is translated by a fixed length.

Multi-word encryption

In the middle of the 15th century, encryption methods advanced to polyalphabetic cipher.

encryption

The encryption method of multi-code encryption is that at the beginning of encryption, both the encryption and decryption parties must first determine a shift word. The encryption party must first convert the determined shift word into a corresponding set of numbers (called a code sequence) in advance, and then for a given plaintext, continuously shift it cyclically according to the length of the converted code sequence. The decryption party must also first convert the shift word into its corresponding code sequence, and then for a given ciphertext, continuously reverse shift the ciphertext letters cyclically according to the length of the converted code sequence.

For example, for the encryption condition, the encryption process of the plain text is hello and the translation word is hi:

1. First, convert the translation word hi into a set of corresponding numbers. Here, according to the order of appearance of the 26 letters in English, the corresponding set of numbers after the letters in the translation word hi are replaced is 78 (starting from 0)

2. Now we need to shift the plaintext one by one in a cycle according to a set of shift numbers after conversion.

    hello
    + + + + + (translate in the order in which the plain text letters appear in the 26-letter alphabet)
    7 8 7 8 7
    -----------
    omstv

3. Finally, according to the above transformation, the ciphertext omstv is obtained

For the decryption party, he needs to know the translation word hi, of course, this is agreed upon in advance by both parties. The decryption method is not detailed, it is the reverse process of encryption.

Cracking

Compared to the cracking process of Caesar cipher - analyzing and statistically analyzing the chart of letter frequencies in the ciphertext, and then comparing it with the chart of letter frequencies in the language used in the plaintext, the translation amount can be obtained. Multi-letter code encryption increases the difficulty of obtaining the effective letter frequencies from the ciphertext. However, the principle of its decryption is still not complicated.

For crackers, they are more concerned about the length of the word sequence used in multi-word encryption, such as the length of the word sequence 78 in the above example is 2. In addition, the reason why the concept of "loop" is emphasized in the explanation of the encryption process above is that when you understand the concept of "loop", you will find that in the above example, h, the first l, and o all use 7 as their translation amount, so the problem actually goes back to the Caesar cipher.

Therefore, for crackers, they only need to keep guessing the length of the code, because the plaintext is cyclically shifted according to the length of the code sequence, and the beginning of one cycle and the beginning of the next cycle must use the same shift amount. As long as they follow this rule, they can pick out the encrypted letters separated by the length of a guessed code sequence for frequency analysis and statistics, and then compare them with the letter frequency of the plaintext to get the shift amount - back to the cracking process of the Caesar cipher.

One-time password

In the late 19th century, a fairly strong encryption method called one-time pad was developed.

encryption

The so-called one-time pad, the length of the encrypted code is no longer the fixed length mentioned above, it uses a random method to obtain a random code sequence with the same length as the plain text letters.

The first thing to know is that for the English alphabet, there are only 26 possible translations for each letter. Because for any counting system with a fixed length (actually a modular system), a translation that exceeds its module will start from the beginning (complement), here you can imagine a clock with 26 hour scales, if the translation from 0 o'clock clockwise is 27, the actual result is 1 o'clock - there is no difference from directly translating 1 clockwise.

Then, the one-time pad encryption process for the plaintext hello can be as follows:

1. Get a random number between 0 and 25. Suppose the random number is 3.

   1. Record this random number
   2. Shift the plaintext h by 3 to become k

2. Get a random number between 0 and 25. Suppose the random number is 5.

   1. Record this random number
   2. Shift the plaintext e by 5 to j

3. And so on...

So assuming the random code sequence is 35685, the corresponding ciphertext is kjrtt.
If encryption is required again, a random code sequence of the same length as the plaintext needs to be generated again.

Of course, the receiver needs to know both the random code sequence and the corresponding ciphertext each time.

Cracking

For the ciphertext obtained by one-time pad encryption, the cracker needs to face two problems:

1. The length of the code sequence used for encryption is the same as the plaintext, so there is no "loop" problem in "multi-code encryption".
2. The frequency of occurrence of each letter in the ciphertext will be the same, because each plaintext letter randomly corresponds to one of the 26 letters, and their probability of occurrence is the same.

Since there is no pattern to the ciphertext, the cracker can only try to get the plaintext by brute force. However, for the plaintext hello, its ciphertext will be one of 26*26*26*26*26 = 11881376 combinations, and this is only the case when there are only 5 letters.

***Confidentiality

Understand this game: Eve invites Bob to a room, and Bob finds that there is nothing in the room except a deck of cards, several locks (locks with keys and combination locks), and an empty square. Eve asks Bob to choose a card and then hide it to the best of his ability. The rules are simple. Bob cannot take anything out of the room, all cards and keys must remain in the room, and at most one card can be placed in the empty square. Eve guarantees that he has not touched the locks. If Eve cannot find the card Bob has hidden, Bob wins. So what should Bob do?

First, Bob chooses a 6 of diamonds and throws it into the empty box. Then he starts to think about which lock to use to lock the box. It seems that using a combination lock is a good choice, but Bob soon realizes a problem - the remaining cards on the table will reveal his choice. The lock is just a trap. He can't take the card out of the deck, so he puts the selected card back into the deck and reshuffles the deck to disrupt their original order. Now, the card Bob chooses can be any card in the deck, and he can leave the room with confidence.

***, Bob wins the game because the best Eve can do is guess the card he chose - Bob left no information about his choice. Even if Eve is given a computer with no performance limitations, she can only guess, which is what we call "*** confidentiality".

On September 1, 1945, 29-year-old Claude Shannon published a confidentiality paper that proved for the first time from a mathematical perspective how and why "one-time pad" has perfect confidentiality. Claude Shannon thought about encryption schemes in the following way:

• Imagine Alice writes a 20-letter message to Bob. This is like extracting a specific page from the message space. The message space can be imagined as a set of all possible combinations of 20 letters.

• Alice then needs to randomly generate a 20-letter key (code) between 0 and 25. The key space is a collection of all random combinations, so generating a key is like randomly drawing a page from the key space.

• Alice then applies the key as a translation to the plaintext message to obtain the ciphertext. The ciphertext space represents the set of all possible encryption result combinations. When she selects and applies a key, the result will uniquely correspond to a page in the ciphertext space.

• Note that the size of the message space is equal to the size of the key space, which is equal to the size of the ciphertext space. This is the definition of "absolute confidentiality". So when only the ciphertext is known, the only information that can be obtained is: this ciphertext uniquely corresponds to a page in the message ciphertext. Because cracking can only be done by guessing, no matter how powerful the computer is, it will not improve anything except shortening the guessing time when facing an algorithm that can only rely on guessing.

Now, with one-time pads, the only problem we face is how we share those long keys in advance.

Pseudo-random number generator

When we observe the natural world, we find random fluctuations everywhere. We can measure and generate true random numbers by taking a familiar fluctuation, such as noise. When we sample the noise, we get numbers. For example, by measuring the current of a TV over a period of time, we can generate a sequence of true random numbers. In order to visualize a sequence of numbers, we can draw the path of change for each number in the sequence, which is also called a random walk. According to the visualized image, at any point in a true random sequence, it is impossible to predict where the next point will appear. Random processes are supposed to be non-deterministic because they cannot be determined in advance.

On the other hand, machines are deterministic, and their operations are predictable and repeatable. Since random numbers need to be obtained continuously and quickly, and the previous computers had limited storage capacity, it is not practical to directly store a random number of fixed length. Therefore, in early computers, scientists invented an algorithm to mechanically simulate the disorder phenomenon in randomness. This algorithm is called the Middle-square method.

For example, to use this algorithm to generate a 4-digit pseudo-random number, you need to first select a 4-digit number as the starting value (seed) of the entire process, and after multiplying (squaring) this 4-digit number by itself, you will get an 8-digit number (if it is less than 8 digits, add 0 in front to make it 8 digits). After getting the 8-digit result, take out 4 digits as the result, or as the seed for the next operation, and repeat the above process to get more 4-digit pseudo-random numbers.

The only guarantee of randomness for this method is the random seed that was chosen initially. The same seed will produce the same sequence. So what is the difference between a random sequence and a pseudo-random sequence? Pseudo-random sequences can be visualized by the random walk mentioned above. It turns out that if a seed is used before, the next result will repeat the previous intermediate result. The period before the pseudo-random sequence repeats is called the period. This period is strictly limited by the length of the seed that was chosen initially. For example, if we use a 2-digit seed, we can generate 100 2-digit combinations before the result sequence repeats. Once an intermediate result with the same 2-digit seed appears, the next intermediate result will repeat periodically. A 3-digit seed can generate 1,000 3-digit combinations. A 4-digit seed can generate 10,000 4-digit combinations. If we use a very long seed, we can generate a pseudo-random sequence of results with a very long period.

Another problem we need to face is that once we choose a pseudo-random way to generate random numbers, we will lose many sequences that should appear in the true random sequence. For example, Alice needs to generate a true random combination of 20 characters for a plaintext of 20 characters, then the combination of these random characters has 26^20 possibilities.
This will be an astronomical number. For comparison, suppose Alice uses the pseudo-random method mentioned above and uses a 4-bit seed. That is, using the pseudo-random method, she can only choose 10,000 possible seeds, and therefore can only generate 10,000 different digital sequences. We can choose the first 20 of the generated sequences as the code. It can be found that the result of using the pseudo-random method has greatly reduced our key space, and the small size of the key space has become the size of the seed space.

As a pseudo-random cracking method, we can keep guessing all possible seeds. This brings us to a common problem in computers, what is possible and what is possible within a certain period of time. When we buy a bicycle combination lock, the same logic is actually used. We know that everyone can try all possible combinations of numbers on the combination lock until they find the matching one and open the lock. However, this process will take them several days, so for a period of time within 8 hours, we can think that the lock is almost safe. Under the above pseudo-random generation method, the degree of confidentiality will increase with the length of the seed. If the most powerful computer takes hundreds of years to try out all the possibilities of the seed, we can think that this method is almost safe, but not absolutely confidential. With the continuous development of computers, the length of the seed also needs to continue to grow accordingly.

Using the pseudo-random method mentioned above, Alice and Bob do not need to share a long code sequence in advance. They only need to share a corresponding random seed, and then use that seed to generate a seemingly random sequence as a code sequence. However, what will happen when they cannot share the random seed face to face?