1. Introduction to the development of cryptography
Cryptography refers to the study of information encryption, crack the technical science of password. The origins of cryptography date back to 2000 years ago. Today’s cryptography is based on mathematics.
The development history
The history of cryptography can be traced back roughly 2,000 years to the legend that Julius Caesar sent messages in code to prevent enemy interception. What Caesar did was simply to create a table of correspondence for the two dozen Roman letters. In this way, if you do not know the password book, even if the interception of a message can not understand.
For a long time, from the days of Julius Caesar until the 1970s, cryptography evolved very slowly, because designers relied largely on experience. Mathematics is not applied
Before 1976, all encryption methods followed the same pattern: encryption and decryption used the same algorithm. When exchanging data, the two parties communicating with each other must tell each other the rules, otherwise it cannot be decrypted. Then the encryption and decryption rules (referred to as the key), it is particularly important to protect. Passing the key becomes the biggest problem. This type of encryption is called a Symmetric encryption algorithm.
In 1976, two American computer scientists Diffie (W.Diffie), Herman (M. Helman) put forward a new idea, can not directly transfer the key under the situation, complete the key exchange. This is called”Diffie Hermann key exchange“Algorithm. It opened a new direction of cryptography research
In 1977, three M.I.T. mathematicians, Ron Rivest, Adi Shamir and Leonard Adleman, devised an algorithm that could implement asymmetric encryption. The algorithm, named after the three of them, is called THE RSA algorithm.
2. Asymmetric encryption RSA generation process
An encryption algorithm developed in the 1970s. The encryption method is special and requires two keys: public key (publickey) and private keys.privatekey). Public key encryption, private key decryption; Encrypt the private key and decrypt the public key. This encryption algorithm is greatRSA
The algorithm is so reliable that the longer the key, the harder it is to crack. According to the published literature, the longest RSA key ever cracked is 768 bits. That is, a key longer than 768 bits is unbreakable (at least, no one has announced it publicly). Therefore, the 1024-bit RSA key is basically secure, and the 2048-bit RSA key is extremely secure. (Of course, the drawbacks of RSA are easy to think of: relatively low efficiency, limited byte length, etc. So in practice we tend to use symmetric encryption together, using RSA for key content.)
3. Mathematical principle of RSA
3.1 Discrete logarithm problem
3.1.1 the original root
Let’s start with a question: what power of three is 17 equal to 12?
Obviously, for the discrete logarithm problem, it’s easy to compute forward to get 12 on the right-hand side. But when you do it backwards, you don’t know where to start. You have to do everything.
And when the modulus uses the prime number 17, the result is fixed between 1 and 17. When the module 17 is large enough, even if we know the algorithm, we also know the prime number 17 and the answer. If we want to calculate the question mark value in the figure above, we can imagine how difficult it is and how much calculation is required.
The diagram below:
From the figure above we can see that the result of modulo 17 of 3 to the N is any number ranging from 1 to 16. So 3 is called the original root of 17.
So we have a law for encryption, three to the NTH power, which is what we see above
We can use the question mark of N (? As plain text, ciphertext 12 is obtained. So even if a hacker gets hold of the ciphertext 12 that we transmit across the network, even if he knows the formula, he can hardly reverse the calculation of our plaintext N. Especially if we change the modulus 17 to a larger number, such as hundreds of digits, it is basically impossible for hackers to calculate our plaintext through this formula. He had to brute force through trial and error.
The problem of solving N in plain text by using this formula up here is called the discrete logarithm problem
3.2 Euler function φ
Just a few concepts
On mutual relations: if two positive integers have no common factors other than 1, they are said to be coprimes.
If a number N is prime, then anything less than N will be prime of each other. If N=5, then 1, 2, 3, and 4 all form a reciprocal relationship with 5. Then φ (5) = 4 means that there are four numbers that form a reciprocal relationship with 5.
Given any positive integer n, how many positive integers less than or equal to n form a mutual relationship with n? The way to compute this value is calledThe euler function, denoted by φ (n)
For example: calculate the Euler function of 8, and 8 mutually 1, 2, 3, 4, 5, 6, 7, 8, φ (8) = 4
Calculate the Euler function of 7, and 7 mutually 1, 2, 3, 4, 5, 6, 7, φ (7) = 6
Calculate the Euler function of 56, φ (56) = φ (8) * φ (7) = 4 * 6 = 24
Through the above reasoning, it is not difficult to find the characteristics of Euler functions:
Euler function characteristics
If n is prime, φ (n)=n-1.
If n can be decomposed into the product of two mutually essential integers, such as n=AB: Φ (AB) = Φ * Φ (A) (B)
If N is the product of two prime numbers P1 and P2, then φ (N)= φ (P1).Φ (P2) = (P1)(P2-1)
15 * 5 = 3, for example, Φ (5 * 3) = Φ Φ (5) and (3), and Φ (5) = 4, Φ (3) = 2, then Φ (53) = Φ Φ (5) * (3) = 4 * 2 = 8, which is 15 number eight forming co-prime relationship with it.
3.3 Euler’s Theorem
Euler’s theorem: If two positive integers m and n are mutually prime, then m to the φ (n) minus 1 is divisible by n. (m^ φ (n)-1)/n = K(integer)
Fermat’s Little theorem: Special case of Euler’s theorem: if two positive integers M and N are mutually prime, and n is prime! So phi (n) is n minus 1. (m^(n-1)-1)/n = K
3.4 Formula Conversion
Modulo inverse elements: If two positive integers e and x are mutually prime, then the integer D must be found such that Ed -1 is divisible by X. So d is the modulo antielement of e with respect to x.
First of all, according to Euler’s theorem
Since 1 to the k is the same thing as 1, then
And since 1 times m ≡ m, then
With modular inverse element conversion, then the conversion formula is:
Let me switch over
Compare the red boxes in step 5 and step 3. That is, when x is equal to phi (n) :
Note: in the first step of derivation of the formula, the premise of Euler’s theorem is that m and n are mutually prime. However, due to the relation of modular antielements, the above results still hold as long as m < n is satisfied.
If the above formula can be split twice, it can be used for encryption.
We can verify this at the terminal using Python:
M = 4, N = 15, φ(N) = 8, e = 3, d? 3d-1 is equal to 8, and d is equal to 8k plus 1 over 3 -> 3, 11
So you know that m,n doesn’t have to be, just m less than n.
Scientists, however, remained stuck with this formula until the advent of Diffi Hermann key exchange, which was implemented by breaking it down.
3.5 Delphi Hermann key exchange
The actual scene shows the process of Diffi Hermann key exchange as follows:
The client first selects a random number 13, which is known by no one but the client.
The server selects a random number 15, which is unknown to the server.
The numbers 13 and 15 are known only by the client and server and cannot be transmitted over the network.
The client uses 3 as the root, 3 to the 13th power and then takes mod 17 (3^13mod 17 = 12) to get 12, which is sent to the server.
After the server gets 12, it saves 12 first. The server uses the same algorithm as the client (3^15mod17 = 6) to get the number 6 and send it to the client.
This completes the key exchange between the client and server.
Then the client and server do the following operation:
The client gets the number 6 sent from the server, using the same algorithm, (6^13mod17 = 10), the server uses the number 12 from the client, using the same algorithm (12^ 15mod 17 = 10) is also to get 10, this 10 is the client and server exchange secret key.
Thus, the secret key 10 is never transmitted over the network, and the client and server compute the key twice, using the same algorithm.
3.5.1 Mathematical Principles
The mathematics of the Defy Hermann key exchange explained above is shown below:
In fact, both the client and the server are doing this twice,
Two operations on the client side:
The first is done by the server: 3^15mod 17 = 6
The second operation is performed by the client itself with 6 on the server side: 6^13 mod17 = 10
Replace the 6 of the second operation with the 3^15 of the first operation and you actually get 3^15^13 mod17 = 10
Two operations on the server side:
The first operation is done on the client: 3^13mod17 = 12
The second time is to get the client 12 and continue the operation: 12^15mod17 = 10
The 12 of the second operation is actually replaced by 3^13:3^13^15 mod 17 = 10
Then we can sum up the above calculation process as follows:
The above calculation formula is applied as follows: M =3, e=13, n=17, C=12 (3^13mod17 =12) C to the d mod n is equal to m, and since C is equal to m to the e mod n, we get m to the e to the d mod n is equal to m, which is m to the Ed mod n is equal to m, which essentially splits Ed into two operations.
Combine that with what we just did in step 5
The split formula can be used to encrypt, decrypt and restore data:
Where D is the modulo inverse element of e with respect to φ(n), since x = φ(n), then similarly, e and φ(n) are mutually prime
For example: m = 3, n = 15, φ(n) = 8, e = 3, d = 11
Summary:
3.7 Birth of RSA
The formula m ^ (e*d) mod n = m can be obtained from the above Diffi Hermann key exchange and our formula: m ^ (e*d) mod n = m.
Encryption: m ^ e mod n = c, (the result of c encryption, m is plaintext, e and N are public keys, d and N are private keys)
C ^ d mod n = m
The formula conversion is as follows:
N can be very large, typically 1024 bits in length. (The largest integer that humans have decomposed so far, 232 decimal bits, 768 binary bits)
Because we need to find φ(n), so according to the characteristics of the Euclide function, the simplest way n is multiplied by two prime numbers: prime numbers p1, p2. So phi of n is equal to p1-1 times p2-1.
And then we get e and d from φ(n). Six digits are generated: P1, p2, n, φ(n), e, and D where N and e form the public key. N and D form the private key. M is plain text.
Except for the public key which uses n and e, the other four numbers are not public.
3.8 RSA algorithm
So long as d is the modulo antielement of e with respect to phi (n)
M is less than n
Let’s verify this with Python:
M ^ e mod n = c encryption c ^ d mod n = m decryption let’s assume n = 15 then φ(n) = φ(15) = 8, suppose e = 3 suppose d= 19 suppose plaintext m = 7 first calculate encryption: C = 7 ^ 3 mod 15 = 13 then decrypt: 13 ^ 19 mod 15 = 7
Features of RSA algorithm:
Six digits are generated: P1, p2, n, φ(n), e, and D where N and e form the public key. N and D form the private key. M is plain text.
Except for the public key which uses n and e, the other four numbers are not public.
Hackers to crack is actually according to n, to find φ(n), and when n is large, it is difficult to calculate φ(n), φ(n) can only be broken by violence through trial and error (with the factorization method).
Phi (n) the biggest computing to only 232 decimal place, it’s just a matter of operation time, if quantum computers really out, because the computational complexity is infinite quantum computation theory, so can break the phi (n), due to many large companies such as Banks are made of RSA encryption mode, so the appearance of quantum computation Will have a big impact on cryptography.
3.9 Terminal Test the RSA encryption Algorithm
Mac terminals can directly use OpenSSL to run RSA commands.
OpenSSL use RSA
Generate a 1024bit RSA private key. Run the following command:openssl genrsa -out private.pem 1024
Extracting a public key from a private keyopenssl rsa -in private.pem -pubout -out public.pem
The public key and private key files have been generated in the previous two steps respectively
Let’s take a look at the generated public key. What is the private key
Check the public key contents:
In fact, both the public and private keys are base64 encrypted. Let’s convert the private key to plaintext.openssl rsa -in private.pem -text -out private.txt
Let’s look at the plaintext of the private key: terminal type: cat private.txt
3.9.1 Rsa Encryption and decryption implemented by OpenSSL
Open the terminal and create a message.txt file:vi message.txt
Decrypted to dec.txt, we can see that the decrypted plaintext also restores Hello
3.9.2 OpenSSL Extracts the certificate P12 File
Rsa is not suitable for large data encryption due to its low efficiency. It is generally used to encrypt key data, such as exchanging secret keys. Rsa is also used to encrypt hash values, which are called signatures.
We usually do not use pem files directly for encryption in the code. We usually use certificate files in advance
Enter:
openssl req -new -key private.pem -out rsacert.csr
Copy the code
A.csr file will be generated in which you will be prompted to enter some information, such as email address, password, etc
The CSR file actually asks for a certificate file, issuing a certificate to a certificate authority.
So we get the issued certificate rsacert.crt file:
There is a fee for the certificate issued (official certification, certificate structure seal). The institution usually charges 5,000 yuan per year. The validity period we write on the certificate is 10 years, which means 50,000 yuan will be paid, O my GAD.
We will not use this certificate directly, but it needs to be advanced
Terminal input command:
openssl x509 -outform der -in rsacert.crt -out rsacert.der
Copy the code
Extract to the file rsacert.der
This file mainly contains the public key and some necessary information. We will generate a P12 file from this der.
The P12 file actually contains the public and private keys.
