Now! Think of a five-digit number in your mind, and how can you pass it to me quietly?
Let's look at a good way, suppose the number you want is 66666 or 12345 and so on.
Please multiply it with my 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. The last five digits of the result will be the number you want.
Looks like a magic trick, right? In fact, in addition to magic, it has a 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?
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.
But because the theory of modern cryptography sounded too stupid, 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.
Isn't this a crazy statement? The encryption method is already known to everyone, so why study it?
For example, Vernam's one-time pad theory, which complies with Shannon's perfect confidentiality, sounds even more crazy. Who can bear to use a password in exchange for one?
But if you read the pitfalls of classical cryptography, you will know how reasonable these statements 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 only one concept: change it randomly and guess what happens.
I'm not kidding, this is what is written in the journal article.
Although in Wikipedia, the classical cipher is summarized as a substitution cipher or a transposition cipher or a mixture of the two, it should be noted that it is summarized here rather than defined, which shows that the classical cipher 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?
Doesn't this perfectly meet the requirements of the classical cryptographic 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 example, the Yin Fu mentioned in the pre-Qin military book “Six Strategies” was invented by the fisherman Jiang Taigong Jiang Ziya. In order to quickly transmit battle reports from the front without being known to 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 round wooden stick called Scytale 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 and so on.
Here is left for the universal friends to supplement, butClassical cryptography has a fatal weakness: it is too symmetrical.
What does this mean? This symmetry has two meanings. First, the encryption of classical cryptography is reversible. Once you know how to encrypt, you can easily figure out how to decrypt.
So the ancients were not stupid. If they just caught someone alive, wouldn’t they know how the code 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 – the Enigma machine.
When encrypting, just enter the plain text (dianzan) you want to encrypt on the machine's keyboard, and the text that lights up is the encrypted ciphertext.
Moreover, the same letters in the plaintext will be encrypted into different ciphertexts, which effectively prevents frequency analysis.
Even 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 linked 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, you have to return to the wheel and replace them again before you can finally return 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 sample 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 patterns mentioned above, each wheel has 26 letters on it, and all 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 at one point, and the amount of calculation required for reverse calculation increased exponentially. In the era before computers, it was almost a fantasy to crack it by reverse exhaustive method.
Moreover, the Enigma machine at that time would change the initial plan every day.
This means that if the number cannot be calculated on the same day, it must be recalculated the next day, which makes 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.
In 1940, the father of computers, British mathematician Alan Turing, cracked the Enigma machine.
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, and 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 indicate that he received it.
Logically, this trivial matter can be directly reported, but it is not possible, at least not in the Germans. They must keep all the Führer's secrets, including this blind loyalty! They must be Engelma!
This rigorous and free operation quickly allowed Turing to obtain many clues about the correspondence between the clear and the secret. Based on these clues, he and his colleague Gordon Welchman invented a method called ” Bomb Machine ” The decryption machine 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 classical encryption, introduces the concept of keys, dividing 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, the encryption system cannot be cracked as long as the private key remains safe.
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, I only need to protect the private key 12039 used for decryption. This is an asymmetric encryption.
The principle is very simple. When the public key is multiplied by the private key, you will find that the result is 28400001, which means that a number within five digits multiplied by two of them in succession is equivalent to 00001.
But this is obviously not secure enough for application-level asymmetric encryption. If we want to go further,A special mathematical function is required, called a trapdoor one-way function, also known as a one-way trapdoor function.
This kind of function is very easy to calculate forward, but it is almost impossible to work backwards. However, if you know some key information, working backwards will become very easy.
For example, the very famous RSA algorithm, banks, emails, chat software, almost all the 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 remainder to get the ciphertext.
To give a simple 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 7th power according to the public key data and then take the remainder of 33 to obtain 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 to restore the plaintext 5. This realizes the separation of encryption and decryption processes.
Since it is impossible to reverse the process, can the private key be calculated from the public key?
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 sake of convenience, 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 infer the two prime numbers through factorization, according to the existing computing level, we must at least calculate that the number of readings of this article exceeds 10 million.
But in theory, quantum computers can do it, uh…
Unless you can get together 4096 logical qubits on a quantum computer to effectively run Shor's algorithm, but because quantum error correction is required, the quantum computer you operate will need at least millions of physical qubits.
Well, the most advanced ones currently only have a scale of tens to hundreds of quantum bits.
This also means that it will be almost impossible to brute-force one-way trapdoor functions in algorithms like RSA in the next few decades.
Therefore, for us now, the encryption algorithm is already very powerful, but this 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 cryptographer 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 full of enthusiasm and hope that more people will know it, realize it, be vigilant and protect themselves. This is the ultimate goal of modern cryptography.