The original intention of public key cryptography is to solve the problem of key distribution.
Alice wrote a slow letter to Bob in the distance, encrypted with powerful AES-256, but she soon realized that it was not enough to encrypt the content. She had to find a safe way to tell Bob the encryption key. If the key is also sent through the network, it is likely to be eavesdropped by Eve, a technical expert and peeping tom.
Neither the key nor the key can be sent, which is the "key distribution problem" under the symmetric cryptographic algorithm.
There are several ways to solve the key distribution problem:
This method is very effective, but it also has limitations:
Different from the first method, keys are no longer kept by communication individuals, but managed and distributed by key distribution center (KDC). When both parties need to encrypt the communication, KDC will generate a communication key for the communication and give it to both parties. Both parties only need to share the key with KDC in advance. This greatly reduces the storage and management problems of keys.
Therefore, KDC involves two types of keys:
The process of appreciating KDC:
KDC can effectively solve the key management and distribution problems in the first method by centralized means, and the security is not bad. But there are also two obvious problems:
When using public key encryption, the encryption key is different from the decryption key. As long as anyone has the encryption key, anyone can encrypt it, but only those who have the decryption key can decrypt it. So there is this process:
The problem of key distribution is naturally solved. Of course, the loss of decryption key leads to information leakage, which is not a key distribution problem.
Now, let's take a closer look at this process.
The core of the public key encryption process can be summarized as the following four sentences:
Because the encryption key is public, it is also called "public key".
Because the decryption key is private, it is also called "private key".
The public key and the private key are in one-to-one correspondence, which is called "key pair". They are like entangled quantum pairs, which are interrelated through strict mathematical calculation and cannot be produced separately.
Under the public key cryptosystem, let's see how Alice communicates with Bob.
Under the public key cryptosystem, the communication process is started by Bob:
The process seems simple, but why does it matter even if the public key is stolen? This involves the strict mathematical calculation relationship mentioned above. If the last article summarizes DES and AES algorithms of symmetric keys, then the next section will also briefly explain the mathematical principle of public key system.
Since Diffie and Hellman put forward the design idea of public key cryptography in 1976, in 1978, Ron Rivest, adi shamir and Reonard Adleman *** * published the public key cryptography algorithm, which is the famous RSA and the de facto standard of public key cryptography algorithm today. In fact, public key cryptography algorithms also include ElGamal, Rabin, elliptic curve and other algorithms. This section mainly introduces the basic mathematical principle of RSA algorithm.
A bunch of symbols, explain, e stands for encryption, d stands for decryption, and n stands for numbers.
As can be seen from the formula, RSA's mathematical formula for encryption and decryption is very simple (that is, very wonderful). The most complicated operation of RSA is not encryption and decryption, but how to generate key pairs, which is very different from symmetric key algorithm. The so-called strict mathematical calculation relationship means that E and D are not randomly selected.
The generation of key pair is the core problem of RSA, and the beauty and mystery of RSA are also hidden in it.
1. Find n
The formula for finding n: N = p × q
Where P and Q are two prime numbers, which should be very big but not very big. If it is too small, the password will be easily cracked; If it is particularly large, the calculation time will be very long. For example, the length of 5 12 bits (decimal number 155 bits) is more appropriate.
How to find such a prime number? It needs to be generated by a pseudo-random number generator (PRNG), and then it is judged whether it is a prime number. If not, it needs to be regenerated and re-judged.
Find l
The formula for finding l: L = lcm(p- 1, q- 1).
Lcm stands for "least common multiple". Note that encryption and decryption do not require L, and only appear during the process of generating key pairs.
Find e
E meets two conditions:
1) 1 & lt； E & ltL
2)gcd(E，L) = 1
Gcd stands for "greatest common divisor". Gcd(E, L) = 1 means that "the greatest common divisor of e and l is 1, that is, e and l are coprime".
In the second step, L has been calculated. In order to find E that meets the conditions, a pseudo-random number generator (PRNG) is used for the second time to generate E candidates between 1 and L, and it is judged whether the condition of "gcd(E, L) = 1" is met.
After the first three steps, the "public key: {E, N}" of the key pair is obtained.
Looking for d
D meets two conditions:
1) 1 & lt； D & ltL
2)E × D mod L = 1
As long as d meets the above two conditions, the message encrypted with {E, N} can be decrypted with {D, N}.
At this point, n, l, e and d have all been calculated, so let's sort it out again.
The process of simulation exercise includes two parts. The first part is to generate key pairs, and the second part is to encrypt and decrypt data. For the convenience of calculation, use a smaller number.
Part One: Generating Key Pairs
1. Find n
Prepare two prime numbers, p = 5, q = 7, N = 5 × 7 = 35.
Find l
L = lcm(p- 1，q- 1) = lcm (4，6) = 12
Find e
Gcd(E, L) = 1, that is, e and l are coprime, and 1
Looking for d
E × D mod L = 1, that is, 5 × D mod 12 = 1. There are several alternatives to meet the conditions of D: 5, 17, 4 1, and 17 is selected as D (if 5 is selected, the public and private keys are overlapped, which is not intuitive.
So far, we have a public key and a private key pair:
Part II: Analog Encryption and Decryption
In plain text, we also use the relatively small number -4 and RSA's encryption formula:
Ciphertext = plaintext e mod n = 4 5 mod 35 = 9
Clear text = ciphertext d mod n = 9 17 mod 35 = 4.
From this small simulation example, we can see that even if we use a small number, the intermediate result of calculation is super large. If you add a pseudo-random number generator to generate a number and judge whether it is a prime number, this process hurts when you think about it. Fortunately, modern chip technology has enabled computers to run at a sufficient speed. However, compared with ordinary logical operations, this mathematical operation is still quite slow. This is also the key performance specification of some asymmetric cryptographic cards/suites, that is, the speed of key pair generation.
In public key cryptosystem, the public key is used for encryption and the private key is used for decryption. The public key is public and the private key is hidden. Therefore:
The encryption formula is: ciphertext = plaintext e mod n.
The process of decoding is the inverse operation of this formula. Because of the addition of "modular operation" in plaintext, the inverse operation is no longer a simple logarithmic problem in mathematics, but a discrete logarithmic problem. At present, it has been recognized in the field of mathematics, and no efficient algorithm for solving discrete logarithm has been found.
The essence of violent cracking is to try one by one. In the current mainstream RSA algorithm, both p and q are greater than 1024 bits, so the length of n is greater than 2048 bits. The length of E and D is similar to that of N, so to find D, we need to use more than 2048 bits to crack it violently. Even in this simple example, it will take a long time to calculate (get) d in "9 d mod 35 = 4".
Because E and N are known, D and E are closely related mathematically (through the middle number L), can D be solved by inverse algorithm?
As can be seen from this place, P and Q are extremely critical. These two numbers are not leaked, and it is almost impossible to calculate D through the formula. That is to say, for RSA algorithm, prime numbers P and Q must not be obtained by hackers, otherwise it is equivalent to handing over the private key.
Since we can't grab it, N = p × q, and n is known, can we deduce p and q through "prime factorization"? In other words, once an efficient "prime factorization" algorithm is found, RSA algorithm can be cracked.
Fortunately, this is the same as the "discrete logarithm solution" mentioned above. At present, this algorithm has not been found in mathematics, and it is certainly impossible to prove whether "factorization of prime numbers" is really a difficult problem. So we can only rely on hard computing, and the current computing power can not be completed in real time. This is also mentioned by many people. "With the advent of the quantum age, the current encryption system will collapse." From the perspective of computing power, maybe so.
Can't rob, can't count, can you guess? That is, by "guessing P and Q".
P and Q are generated by PRNG (pseudo random number generator), so another key factor is that the algorithm of the pseudo random number generator used should be random enough.
Random numbers are extremely important for cryptography, and a special explanation will be written later.
The first three attacks are all based on the idea of "playing hardball", while "man-in-the-middle attack" is a circuitous idea, not trying to crack the cryptographic algorithm, but deceiving both parties to obtain plaintext. Specifically, Mallory, the active attacker, wandered between the sender and the receiver, pretending to be the receiver in front of the sender and pretending to be the sender in front of the receiver.
This process can be repeated many times. It should be noted that man-in-the-middle attacks can be directed not only at RSA, but also at any public key password. It can be seen that in the whole process, the public key password has not been cracked, and the cryptographic system works normally, but there is a problem with confidentiality, that is, Alice and Bob lose confidentiality, but keep confidentiality between Alice and Mallory, Mallory and Bob. Even if public key cryptography is n times stronger, it will not help. In other words, it is impossible to defend against man-in-the-middle attacks by relying on cryptographic algorithms alone.
In order to resist man-in-the-middle attacks, you need to use another weapon of the password toolbox-authentication. This topic will be discussed in the next note.
Well, this is the basic knowledge of public key cryptography.
Public key cryptosystem can perfectly solve the key problem of "key distribution" in symmetric cryptosystem, but aside from the problem of "man-in-the-middle attack", public key cryptosystem itself has a serious problem:
The processing speed of public key cryptography is much lower than that of symmetric cryptography. Not only in the generation of key pairs, but also in the encryption and decryption operations.
Therefore, in practical application scenarios, a "hybrid cryptosystem" is often constructed by combining the advantages of symmetric cryptography and public key cryptography. To put it simply: firstly, the message is encrypted with a relatively efficient symmetric password to ensure the confidentiality of the message; Then the key of symmetric cipher is encrypted with public key cipher to ensure the confidentiality of the key.
The following is the encryption and decryption flow chart of the mixed cryptosystem. The whole system is divided into two parts: the left part is the process of encrypting the session key and the right part is the process of encrypting the original message. The original message is generally long, so it is more efficient to use symmetric cryptographic algorithm; Session keys are generally short (tens to tens of bytes). Even if the operation efficiency of public key cryptography algorithm is low, the encryption and decryption of session key will not be time-consuming.
Well-known cryptographic software PGP, SSL/TLS, video surveillance public * * * networking security construction specification (GB35 1 14) and other applications all use the mixed cryptographic system.
Well, that's all for the content of public key cryptography algorithm, which has been delayed for a long time and will be more diligent in the future.
In order to avoid being handled by silly censorship robots, I don't attach photos of beautiful girls to the back (also for your health), and I change them into my photography works, hoping that it won't affect the ratings, although many boys come for girls.
Let's start with the Kanas trip.