news

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Click on the image to jump to the video!

Now! Think of a five-digit number in your mind, and how to pass it to the bad reviewer quietly?

Let's look at a good way, suppose the number you want is 66666 or 12345 and so on.

Please multiply it with the bad reviewer's lucky number 2359, take only the last five digits of the result and type it on the public screen, and I will know what number you are thinking of. Are you ready?

Now it’s time to debug. Multiply the five-digit number you got by 12039, and the last five digits of the result will be the number you thought of. Looks like a magic trick, right?

In fact, in addition to magic, it has an even more amazing origin - modern cryptography. Even your bank card, email, and chat software are inextricably linked to it.

So how does it relate to modern cryptography, how does it work, and why is it designed this way?Let’s take a look at some different cryptography!

A genius mathematician's idea of ​​modern cryptography

When talking about cryptography, we have to mention that man!Claude Elwood Shannon.

In his book "Communication Theory of Confidential Systems" published in 1949, he used mathematical methods to divide cryptography into classical cryptography and modern cryptography. However, because the theory of modern cryptography sounded too silly, it was left out for more than 30 years after its birth.

For example, Kerckhoffs' principle in modern cryptography states that the encryption method of a cryptographic system should be known to everyone. This sounds crazy. If the encryption method is known to everyone, what's the point of studying it?

For example, Vernam's one-time pad theory, which is in line with Shannon's perfect confidentiality, sounds even more crazy. Who can bear to use a password once in exchange for one? But if you read the pitfalls of classical cryptography, you will know how reasonable these remarks are!

Classical Code

In the era of classical cryptography, the concept of cryptography was relatively vague. Although it was widely used in the military field, encryption was more like an artistic act.

Anyway, there is one concept:It's just changing and moving around randomly, you can guess.

I'm not kidding, this is what the journal article says. Although in Wikipedia, classical ciphers are summarized as substitution ciphers or transposition ciphers or a mixture of the two.

But please note that this is summarized rather than defined, which shows that classical code is still an imaginative term.

For example, for foreigners, Chinese itself is actually a classical code.

For example, if we replace the sentence "what is your name" with Chinese characters one by one and then move the items, it becomes: what is your name. This perfectly meets the requirements of the classical cipher substitution movement.

Of course, this kind of reasoning is indeed very imaginative, but after all, the classical code book is using imagination to create a new language that you understand, I understand, but he doesn't.

for exampleYin Fu mentioned in the pre-Qin military book "Six Strategies"This was invented by the fisherman Jiang Taigong Jiang Ziya. In order to quickly transmit battle reports from the front without being known by the enemy, he invented a method of using fishing rods of different lengths to transmit battle reports. This is also the earliest military code recorded in Chinese historical materials.

For example, in 700 BC, the ancient Greek army used a weapon calledScytale's round wooden stick for confidential communications.

The usage is:

A long strip of parchment was wrapped around a round wooden stick and then written on; after the parchment was removed, only disorganized characters were left on it, and the content could only be seen when it was wrapped again in the same way around a stick of the same thickness.

The inspiration for the code stick in Conan comes from this.

Of course, there are many interesting classical ciphers besides these, such as Caesar cipher, fence cipher, etc. . .

I'll leave this to you, but classical cryptography has a fatal weakness: it's too symmetrical. What does this mean?

This symmetry has two meanings. First, the encryption of the classical cipher is reversible. Once you know how to encrypt, you can easily figure out how to decrypt. So the ancients were just ancient, but they were not stupid. If they caught anyone alive, they would know how the cipher worked.

Another meaning of symmetry is that no matter how you replace the plaintext, there will always be a one-to-one correspondence between plaintext and ciphertext, but this also has a big disadvantage, that is, the use of language is regular.

For example, this chart is a frequency analysis report of letter and word usage from Pitt.com after analyzing 3.5 trillion documents. This means that no matter how you replace it, or how many layers of replacement you go through, as long as there are too many intercepted ciphertexts, they will always be caught by the frequency analysis method.

Of course, although the problem has been found, it is clear that classical cryptographers have not solved this problem very well, and even indirectly proved that classical cryptography is really not good.

For example, during World War II,The pinnacle of classical cryptography - Enigma.

When encrypting, just enter the plain text (dianzan) you want to encrypt on the keyboard of the machine, and the lighted up one is the encrypted cipher text. Moreover, the same letters in the plain text will be encrypted into different cipher texts, which effectively prevents frequency analysis.

in additionEven if you know how it works, it is still difficult to crack.

How is this done?

We come to the interior of the Enigma machine, the rotor device. On the right end of the input wheel of this device, there are 26 contacts, which are connected to the 26 letters on the keyboard.

The middle part of the device is composed of multiple wheels with the same 26 contacts, but they are somewhat different from the input wheels. There are some additional complicated switching mechanisms inside the wheels, which means that the letters on the input board are replaced once every time they pass a wheel.

At the end of the device there is a device called a reflector, which still has 26 contacts. The contacts here are combined in pairs to form the same turning points as in swimming competitions.

After the letters are swapped here, they still have to return to the wheel and be replaced again before finally returning to the starting point.

This completes an encryption process. It can be seen that this is the superposition of multiple replacements, but in fact the Enigma machine has a finishing touch. Every time the keyboard is pressed, a special lever device will drive the wheel to rotate once, and there is a special wheel pattern on the wheel. After the current wheel rotates one circle, the next wheel will also rotate once.

This means that the encryption circuit used when pressing each letter is different, and the sampling frequency analysis method becomes invalid.

In addition, even if you know how it works, it is very difficult to reverse engineer such a design.

Taking the original Enigma machine as an example, it has three rows of the wheel-shaped wheels mentioned above. Each wheel has 26 letters on it and can rotate. In this way, we have more than 17,500 ways to set the initial position of the wheel.

In addition, for the sake of safety, a set of exchange mechanisms are attached to its outside, that is to say, if o and e are connected, when pressing o, it is actually equivalent to pressing e.

Assuming that we randomly select 6 pairs to exchange each time, according to the algorithm of probability theory, we have generated more than 100 billion possibilities. There are already 170 trillion possibilities for these initial positions alone.

The later Enigma machine even increased the number of roulette wheels to 8, and the amount of calculation required for reverse calculation increased exponentially. In the era without computers, it was almost a fantasy to crack it by reverse exhaustive method.

Moreover, the Enigma machine at that time would change its initial solution every day. This means that if the solution could not be calculated on the same day, it would have to be recalculated the next day. This made brute force cracking more difficult.

But those who know about World War II know that the Enigma machine was eventually cracked, even before the birth of computers.

1940, the father of computer, British mathematicianAlan Turing, the Enigma machine was cracked.

But didn't you just say that it's impossible to crack without a computer? That's true, but the Germans are too stubborn and arrogant. No matter what they say, they always say heil hitle.

Not only that, the Germans also like to report. From time to time, they would send a message to their superiors: Report to the superior, nothing happened! And then add a sentence heil hitle.

According to etiquette, the officer should also reply with a "Heilhitle" to show that he received it. Normally, such a trivial matter can be sent directly, but it is not possible, at least not in the Germans' place. All the secrets of the Führer must be kept secret, including this blind loyalty! Must be Engelma!

This rigorous and easy operation quickly allowed Turing to obtain many clues corresponding to the secrets. Based on these clues, he and his colleaguesGordon WelchmanHe invented a decryption machine called the "Bomb Machine", which actually reverse-engineered the Enigma Machine.

So this once again shows that symmetric encryption methods like classical ciphers, where knowing how to encrypt means knowing how to decrypt, will fundamentally be cracked, it's just a matter of time.

Modern Cryptography

Is there an encryption method where the sender of the information only knows how to encrypt but not how to decrypt, while the receiver of the information knows both how to encrypt and how to decrypt?

In fact, this is one of the research directions of modern cryptography, that is, how to achieve asymmetric encryption.

This encryption method, based on the classical cipher, introduces the concept of keys, dividing the keys into public keys and private keys. The public key is used for encryption, and the private key is used for decryption. In this way, even if the encryption method is made public, as long as the private key is still safe, the encryption system will not be cracked.

Therefore, the practice of modern cryptographers to make encryption methods public will not actually affect the security of the encryption system.

Remember the magic game we started with?

2359 is a public key that anyone can use to encrypt. In theory, as long as you protect the private key 12039 used for decryption, this is an asymmetric encryption.

The principle is very simple. When you multiply the public key by the private key, you will find that the result is 28400001, which means that when a number within five digits is multiplied by two of them in succession, it is equivalent to multiplying by 00001.

But this is obviously not secure enough for application-level asymmetric encryption. To go a step further, a special mathematical function must be used.

calledTrapdoor one-way function, also known as a one-way trapdoor function, this function is very easy to calculate forward, but it is almost impossible to reverse it. However, if you know some key information, reverse calculation will become very easy.

for exampleThe very famous RSA algorithm,Banks, emails, chat software, almost all digital fields you can think of are under its protection, which can be regarded as a solid application level. Its encryption principle uses a one-way trapdoor function.

When encrypting, you only need to raise the public key data to the power and then find the modulus to get the ciphertext. For example, if the number to be encrypted is 5 and the public key is (7, 33), you only need to raise the plaintext 5 to the power of 7 according to the public key data and then find the modulus of 33 to get the ciphertext 14.

If you want to reverse the plaintext by following the same idea of ​​decrypting it the same way it was encrypted, you will get stuck at the first step, because there are infinitely many possible numbers that can be 14 modulo 33, which means that it is impossible to determine what the plaintext is.

But if we have the private key (3, 33), we only need to exponentiate the ciphertext again according to the private key data. We can restore the plaintext 5. This realizes the separation of the encryption and decryption process. Since it is impossible to reverse, can we calculate the private key through the public key?

Let's take a look at the process of making private keys and public keys:

First, we select two prime numbers, the product of which is denoted as N, and calculate the function φ through the Euler function φ(n) = (p-1) * (q-1). Then we select an integer E, and E must satisfy 1. The private key is obtained by calculating the multiplication inverse of E modulo φ(n).

When we want to calculate the private key when we only know the public key, we must get the first two prime numbers.

Because the prime number chosen here is relatively small for the convenience of everyone's understanding, but usually, this prime number is very large. Even if we know the product of two prime numbers in the public key, if we want to reversely deduce the two prime numbers through factorization, according to the existing computing level, we must at least calculate until the number exceeds 10 million in this video.

But in theory, quantum computers can work, um... unless you can gather 4096 logical qubits on a quantum computer to effectively run Shor's algorithm. But because quantum requires error correction, the quantum computer you operate needs at least millions of physical qubits.

Well, the most advanced quantum computers currently have only tens to hundreds of qubits. This also means that in the next few decades, it will be almost impossible to brute-force crack the one-way trapdoor function in the RSA algorithm.

So, for us now,The encryption algorithm is already very powerful, but it does not mean absolute security.

at last

Because these powerful encryption algorithms can only ensure that the money in your bank card will not be tampered with at will.

However, if the user is not vigilant enough and enters his or her passwords on certain websites, or registers many different apps with the same username and password, these are very likely to be cracked by brute force by hackers.

Looking back at every era of cryptography, it seems that humans have always been the biggest loophole in rigorous cryptography.

As American cryptography scholar Bruce Schneier said: "Security is like a chain, it depends on the weakest link."

In the world of information security, technology can build high walls, but in the human world, emotions become the biggest loophole in security.

Although cryptography is boring, we are still passionate about it and hope that more people will know and realize it.Be vigilant and protect yourself; this is the ultimate goal of modern cryptography.

Written by:orange

Video Production:B Station Bad Review

Art editor: Huan Yan

Image, source：

The development and technology of cryptography - Xiao Wei

Classical Cryptography—Tan Yifu, Song Peifei, Li Zichen (Beijing Institute of Graphic Communication)

Algorithms that can be understood even if you are not good at math—Technical Teacher

Caesar cipher, perfect encryption, and a preliminary exploration of modern cryptography - Le Zhengchuixing

Encryption algorithm based on one-way trapdoor function——Guo Shu, Shi Taotao, Zhang Xinyu

"Graphical Cryptography" - written by Yuki Hiroshi and translated by Zhou Ziheng

Password battle - Xiaolangdi is not a wave