Method to solve the problem of key distribution
In the case of a large number of people, the number of keys needed for communication will increase. For example, if each of 1000 employees can communicate with another 999 people, then each person needs 999 communication keys. The total number of keys is:
1000 x 999 ÷ 2 = 499500
Very unrealistic, so this method has certain limitations.
In Diffic-Hellman key exchange, the two sides of encrypted communication need to exchange some information, even if these information is eavesdropped by eavesdroppers, there is no problem (explained in detail below).
In symmetric encryption, the encryption key and decryption key are the same, but in public key encryption, the encryption key and decryption key are different. Anyone can encrypt as long as he has an encryption key, but he cannot decrypt without a decryption key.
In public key encryption, keys are divided into encryption keys (public keys) and decryption keys (private keys).
There is a one-to-one correspondence between public key and private key. A pair of public keys and private keys are collectively called key pairs. Ciphertext encrypted with public key can only be decrypted with private key paired with public key. There is a very close relationship between the two keys in a key pair-a mathematical relationship-so the public key and the private key cannot be generated separately.
Sender: Alice Receiver: Bob Eavesdropper: Eve
The communication process is initiated by the receiver Bob.
Public key cryptography solves the problem of key distribution, but it still faces the following problems.
RSA is the most widely used public key cryptography algorithm at present, and its name consists of the initials of the surnames of its three developers, namely Ron Livingstone, adi shamir and Aderman. RSA can be used for public key cryptography and digital signature (this article only discusses public key cryptography, please look forward to the subsequent articles on digital signature). 1983 was patented in the United States, but now the patent has expired.
In RSA, plaintext, key and ciphertext are all numbers, and the RSA encryption process can be expressed by the following formula.
Ciphertext = plaintext e modulus n
Simply put, the ciphertext of RSA is the result of finding the e power mod N of the number representing plaintext. In other words, multiply the plaintext by yourself e times, and then divide the result by n to find the remainder, which is the ciphertext.
The decryption process of RSA can be expressed by the following formula.
Plain text = ciphertext D mod N
The plaintext can be obtained by looking for mod N representing the number of ciphertext to the power of d. In other words, multiply the ciphertext by yourself d times, and divide the result by n to find the remainder, and you can get plaintext.
The number n used at this time is the same as the number n used in encryption, and the combination of the number d and the number n is the decryption key of RSA, so the combination of d and n is the private key. Only those who know the numbers d and n can complete the decryption operation.
According to the formula of encryption and decryption, it can be seen that three numbers-e, d and n are needed to generate the key pair. The steps for generating RSA key pairs are as follows:
Prepare two large prime numbers p and q, multiply these two numbers, and the result is n.
N = p x q
L is the least common multiple of p- 1 and q- 1. If lcm( X, y) is used to represent "the least common multiple of x and y", l can be written as follows.
L = lcm ( p - 1，q - 1)
E is a number greater than 1 less than l, and the greatest common divisor of e and l must be 1. If gcd( X, y) is used to represent the greatest common divisor of x and y, the relationship between e and l is as follows:
1 & lt； E & ltL
Gcd( E, L) = 1 (a number d is needed to ensure decryption).
1 & lt； D & ltL
E x D mod L = 1
p = 17
q = 19
N = p x q = 17 x 19 = 323
L = lcm ( p - 1，q - 1) = lcm ( 16， 18) = 144
gcd( E，L ) = 1
There are many qualified E's: 5,7, 1 1, 13, 17,19,23,25,29,31. ...
Here we choose 5 as e, and here we already know that E = 5 N = 323, which is the public key.
E x D mod L = 1
D = 29 can satisfy the above conditions, so:
Public key: E = 5? N = 323
Private key: D = 29 N = 323
The plaintext to be encrypted must be a number less than n, because mod N is needed in the encryption operation to assume that the encrypted plaintext is 123.
Clear text E mod N = 123 5 mod 323 = 225 (ciphertext)
Decrypt ciphertext 225
Ciphertext d mod n = 225 29mod323 = 22510x22510x225 9mod323 = (22510mod323) x (22510mod323) =16x16x191mod323 = 48896mod323 =123 (plain text)
If there is no mod N, that is:
Plain text = ciphertext D mod N
It is not difficult to find plaintext through ciphertext, because it can be regarded as a problem of finding logarithm.
But after adding mod N, finding plaintext becomes a problem of finding discrete logarithm, which is very difficult, because human beings have not found an efficient algorithm to find discrete logarithm.
As long as you know D, you can decrypt the ciphertext and try D to decrypt RSA violently one by one. The difficulty of brute force cracking will increase as the length of d increases. When d is long enough, the number of d can't be found in violent cracking in real time.
At present, the length of P and Q used by RSA is greater than 1024 bits, and the length of N is greater than 2048 bits. Because the length of e and d can be almost the same as the length of n, it needs more than 2048 bits to crack d violently. At this length, it is extremely difficult to find d by violent cracking.
E x D mod L = 1 L = lcm ( p - 1，q - 1)
To calculate d from e, you need to use p and q, but the cryptographer doesn't know p and q.
For RSA, it is very important that prime numbers P and Q cannot be deciphered. Giving P and Q to the cryptographer is equivalent to giving the private key to the cryptographer.
P and q can't be known by cryptographers, but N = p x q, n is public, and both p and q are prime numbers, so finding p and q from n can only be achieved by decomposing the n factor into prime numbers, so:
Once we find an efficient algorithm for prime factorization of large integers, we can decipher RSA.
Although this method can't decipher RSA, it is an effective attack on confidentiality.
The so-called man-in-the-middle attack is an attack in which Mallory, an active attacker, enters between the sender and the receiver, pretending to be the receiver for the sender and pretending to be the sender for the receiver. Here, Mallory is the "middleman".
This attack is not only aimed at RSA, but also at any public key password. In this process, the public key password has not been cracked, and all cryptographic algorithms work normally and ensure confidentiality. However, the so-called secrecy is not between Alice and Bob, but between Alice and Mallory, and between Mallory and Bob. Public key encryption alone cannot resist man-in-the-middle attacks.
In order to prevent man-in-the-middle attack, we also need a means to confirm whether the received public key really belongs to Bob, which is called authentication. In this case, we can use a public key certificate (we will update the article to discuss it later)
When many servers on the network receive data with incorrect format, they will return an error message to the communication object, prompting that "there is something wrong with the data here". However, this seemingly intimate design will give attackers an opportunity. Attackers can repeatedly send their forged ciphertext to the server, and then analyze the returned error message and response time to get some information about the key and plaintext.
In order to resist this attack, ciphertext can be authenticated, and RSA-OAEP (Optimal Asymmetric Encryption Filling) is an improved RSA algorithm designed based on this idea.
When RSA-OAEP is encrypted, some authentication information will be filled in front of plaintext, including the hash value of plaintext and a certain number of zeros, and then RSA will be used for encryption. In the process of decryption, if the correct authentication information is not found at the beginning of the decrypted data, it can be judged that there is a problem and a fixed error message can be returned (the key point is that the specific error content cannot be informed to the developer).
In practical application, RSA-OAEP will also use random numbers to make the generated ciphertext present different arrangements, thus further improving security.
With the development of computer technology, passwords that were previously considered safe will be cracked, which is called password deterioration. In view of this: