How to ensure the safe transmission of such important personal data on the Internet? Of course, it depends on various encryption algorithms. Speaking of encryption algorithms, we all know that there are hash, symmetric encryption and asymmetric encryption. Hash is a hash function, and the operation is irreversible; Symmetric encryption means that encryption and decryption use the same key, while asymmetric encryption encryption and decryption are naturally two keys. Further, it should be said that asymmetric encryption algorithms include DES, 3DES, RC4 and so on. The asymmetric encryption algorithm is naturally RSA. So what are we talking about when we talk about RSA? Today, the author will discuss with you. If there are any shortcomings, I hope you can give us more opinions and make progress together.
Introduction to RSA: 1976 was put forward by three mathematicians at MIT. To commemorate this milestone, their initials were used as the name of the algorithm. Ron Livingstone, adi shamir and Leonard Aderman.
Public key: used for encryption and signature verification.
Private key: decryption, signature.
Usually, after knowing the purpose of the public key and the private key, you can meet the basic chat needs. But our main task today is to explore the principle of RSA encryption and decryption.
When it comes to the principle of encryption algorithm, it must be related to mathematical knowledge.
Let's recall a few mathematical knowledge:
φn =φ(A * B)=φ(A)*φ(B)=(A- 1)*(B- 1)。
This formula is mainly used to calculate how many positive integers less than or equal to n have a coprime relationship with n given any positive integer n.
Where n=A*B, a and b are both prime numbers, but it is not required that a and b are both prime numbers, and they can continue to be expanded until they are both prime numbers.
After the final decomposition is completed, that is, φ(N) = φ(p 1)*φ(p2)*φ(p3) ..., p 1, p2 and p3 are all prime numbers. Another feature of Euler function is used, that is, when p is a prime number, φp = p- 1. So there is the euler theorem formula given above.
Take a look at it for example:
Calculate the Euler function of 15. Because the ratio of 15 is small, you can look at it directly. Positive integers less than 15 are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 and 165438. There are four prime numbers 1, 2, 4, 7, 8,1,13, 14 * *.
Compare our euler theorem just now.
If you are interested in other things, you can verify it yourself.
Euler function is introduced here because we will use it when calculating public key and private key.
If two positive integers m and n are coprime, then the φn power of m minus 1 can be divisible by n. ..
? Among them? .
When n is a prime number. The formula you see above becomes
? mod n？ ? 1.
This formula is also called Fermat's Little Theorem.
If two positive integers e and x are prime numbers, then there must be more than one integer d, so that e*d- 1 can be divisible by x, that is, e*d module x? ? 1。 Then d is said to be the modular inverse element of e relative to X.
After understanding the Euler function, euler theorem and modular inverse mentioned above, some chemical reactions come. Please see the picture below:
Are there any formula changes in the above picture that you don't understand? See you in the comments section if you don't understand.
Finally, we get the most important variant of the fifth formula, which is behind the red arrow:
? mod n？ ? m .
There are several relationships that need to be clarified. M and n are prime numbers, φn = x, and d is the modular inverse of e relative to X. ..
Have you seen some rudiments of encryption and decryption?
From m to m, this covers the whole process from encryption to decryption, but it lacks the whole process of ciphertext we want.
Ok, let's introduce the fourth mathematical formula in this paper:
Let's take a look at the whole exchange process:
1, client number 13, server number15;
2. The client obtains the remainder of 17 by calculating the third power of 13, and obtains the number12; Send12 to the server; At the same time, the server calculates the power of 15 of 3, takes the remainder of 17 to get the number 6, and sends it to the client. At this point, the whole exchange process is completed.
3. After the server receives the number 12, continue the calculation. The power of 15 of 12 is the remainder of 17, and the number 10 is obtained.
4. After receiving the number 6, the client continues to calculate, and the power of 6 13 is the remainder of 17 to get the number 10.
Did you look for both sides and finally get the same content 10? But this number 10 has never appeared in the network process.
Well, at this point, some people may have suddenly realized that this is the encryption process, but some people will wonder, why do you want to take three and 17? There is also a mathematical knowledge, the original root problem. That is, 3 is the original root of 17. Look at the picture.
Have you found that the power of 3 is 1~ 16, the remainder is 17, and the integer is from 1~ 16? At this time, we call 3 the original root of 17. That is to say, in the above calculation process, there is a set of primitive root relations. This is the earliest Diffie Herman key exchange algorithm.
After solving the problem of why we chose 3 and 17, let's continue to look at how the final RSA came into being:
Remember the euler theorem we mentioned above, where m and n are prime numbers, n is prime number, and d is the modular inverse of e relative to φ n.
What happens when Diffie Herman's key exchange algorithm meets euler theorem?
We get the following inference:
Ok, have we seen the whole encryption and decryption process here?
Where m is plaintext; C is ciphertext; N and e are public keys; D and n are private keys.
The relationship between several groups of numbers must be clear:
1, d is the modular inverse of e relative to φn, φn = n- 1, that is, e * d mod n = 1.
2.m is less than N. When it comes to Diffie Herman's key exchange algorithm, the problem of original root is mentioned above. In RSA encryption algorithm, there is no constraint on M and N, as long as M and N are prime numbers, N is prime number, and M.
Well, that's the principle of RSA encryption algorithm. After the bombing of the above mathematical formula, is it a bit confusing? Give everyone some time to sort it out, and then we will work with you to verify RSA algorithm and why RSA is safe.