If you want to understand blockchain and blockchain projects in depth, you will inevitably need to understand cryptography. Blockchain is an integrated application of cryptography. Only by understanding cryptography can we truly understand blockchain.

Cheetah Blockchain Center is inPopular science articles on the origin of cryptographyfirst level title

Enigma encryption machine

In the early days of World War II, the overall war strength of fascism was actually far inferior to that of the allies. However, Germany and Japan adopted a large number of surprise tactics, preemptive strikes in the early days of World War II, and gained certain war advantages.

In order to effectively implement raid tactics, intelligence is very critical, so how to ensure the security of intelligence was the main goal of cryptography during World War II.

We mentioned in the previous article that in order to ensure the absolute security of information, it is necessary to encrypt the information with a one-time pad method, that is, to encrypt each letter with a random displacement. Ideally, this machine Randomly shift each input letter, and then output the encrypted letter.

The most advanced machine at that time was called the rotor encryption machine, which realized the one-time encryption very well. And the principle is actually very similar to the odometer we are familiar with.

(The wheel of the low unit rotates once, and the wheel of the high unit rotates one grid)

We all know the odometer machine and it takes a long time to repeat a week.

Imagine that we scramble the numbers on the odometer wheel, and when there is no tick forward, we add each number on the rotor to get the displacement number, and then perform displacement encryption on the letters we want to encrypt. It is the general principle of the rotor encryption machine.

The encryptor and receiver can generate the same displacement sequence according to the following method: first, they need to share the same machine, and then agree on the initial state. This is defined as the machine code setting, and then they adjust their respective machines to the same position, and finally, keep doing the same operation to get the same sequence.

For three rotors, each having 26 numbers, the displacement sequence of each sequence is repeated through the rotation of the third power of the rotor 26 (17576 numbers).

And the position of each rotor is equal to the corresponding position in the sequence,The initial machine state is called the machine code setting, and the collection of all machine code settings is called the machine code space. If the method of initially setting the machine increases, the machine code space will also increase.

When we choose a machine code setting, we choose a starting point in this space,If the machine code is set to be exposed, the entire encrypted sequence will be leaked.

Therefore, the security of this rotor encryption machine depends on the size of the code space and the randomness of the code setting.

One of the most important encryption technologies used by the Nazis during World War II was the encryption machine known as the Enigma.

Near the end of the war, the Enigma could be set in over 150 million million ways. This led the Germans to believe that the Allies had acquired the Enigma and could not verify all possible code settings.

For both parties to communicate using the Enigma, they need to first share the daily machine code settings, which allow them to adjust their respective machines to the same position. This protocol has been changed repeatedly during the war, but is usually distributed to All operators, every day, the operator will cut out the settings for that day, and this will tell them, the configuration that the machine needs for that day, for example, which rotors to use, and the order of the rotors, and then after use, the machine code settings will be be destroyed.

However, for the operator, there is still one crucial step left, before the communication, they will have to choose the initial position of each rotor, and some lazy operators make a very simple mistake, which is the same as The same mistake we make with mechanical bicycle locks, we tend to move the rotor a few times from the initial position, or reuse a common combination, which destroys the uniform distribution of the initial rotor position and, after repeated observations, makes the The army can completely restore the circuit distribution of the rotor in reverse.

This kind of low-level human error led to the final cracking of the Enigma machine, which indirectly affected the trend of the war.

first level title

pseudorandom number generator

Before understanding pseudo-random numbers, let's take a look at real random numbers. In our physical world, there are random fluctuations everywhere. By measuring random fluctuations called noise, we can generate true random numbers.The process of measuring noise is called sampling, we can obtain some random number by sampling. However, relatively speaking,Machines are deterministic, their operations are predictable and repeatable.

In 1946, von Neumann participated in the design of the military's hydrogen bomb and applied a computer named ENIAC. He intended to repeatedly calculate the simulation of the nuclear fusion process. However, this required fast access to randomly generated numbers and guaranteed These numbers are repeatable, however, ENIAC's memory is quite limited, and storing long random sequences is impossible.

Therefore, von Neumann designed an algorithm to mechanically imitate randomness. The algorithm is as follows: First, a truly random number that is called a seed is selected,This number can come from a measurement of noise, such as the current time in milliseconds, which is called a seed.Then, take this seed as input, do a simple calculation - multiply the seed by itself, and output the middle part of this result, then use this output, as the next seed, and repeat this process as many times as needed .

This is called mid-scoring, and it's one of many pseudo-random number generators. So, what is the difference between a randomly generated sequence and a pseudorandomly generated sequence?

The core difference is that if the pseudo-random number reaches a certain number, the sequence will eventually repeat.When a seed number that has been used before appears in the algorithm, the cycle begins. The length before the sequence of pseudo-random numbers repeats is called a period. The period is strictly limited by the length of the initial seed.

For example, if we use a two-digit seed, the algorithm can generate up to 100 numbers before repeating the loop, a 3-digit seed can generate 1000 numbers before repeating the loop, and a 4-digit seed can generate 1000 numbers before repeating the loop. Generates 10,000 numbers, however, if we use a large enough seed, the numbers in the sequence will expand to trillions before repeating.

There is another key difference that is very important, and that is that when you generate numbers pseudo-randomly, there will be sequences that cannot be generated.

For example, if Alice, the encryptor, generates a truly random sequence of 20 displacements, this will be equivalent to randomly selecting a sequence from a stack of all possible displacement sequences, which contains 26 to the power of 20 possibilities, This is an astronomical figure.

But if the encryptor uses a 4-digit random seed to generate a 20-digit pseudo-random number sequence, he can only make an equally general choice among 10,000 possible outcomes, which means that she can only generate 10,000 different the sequence of.

When we move from random displacement to pseudo-random displacement, it is equivalent to shrinking the key space into a relatively small seed space.

The concept of pseudo-random numbers is proposed so that the encryptor and the receiver do not need to share the entire random displacement sequence in advance, but only need to share a relatively short random seed, and then expand it into the same seemingly random sequence when needed. Can.

But what if they never meet to share this seed? This is the most important content of modern encryption technology and the core of encryption in the blockchain, which we will focus on in the next article.