[suggested collection] hand to hand with you to explore the mystery of data encryption 😉~ | August more text challenge

Recently, IN the company’s project, I encountered the need to use RSA to encrypt user tokens. At the same time, I also spread out, studied and learned the knowledge of data encryption, and gained a lot, so I decided to sort out and record it

A little history of data encryption

Before we start, let’s talk about the history of data encryption to broaden our horizons

Before 1976, all encryption methods used were symmetric encryption, that is, encryption and decryption of information with the same secret key. Because of this feature, the sender needs to send the secret key to the receiver before transmitting information, so the transmission and management of the secret key is very important. Because there is the behavior of sending the secret key, there is always the risk of leaking the secret key, so the security of this algorithm is relatively low

But as the saying goes: So in 1976, two American computer scientists, Whitfield Diffie and Martin Hellman, came up with a novel idea that could complete the encryption and decrypting process without directly transmitting the key. This is called the Diffie-Hellman key exchange algorithm, and it works like this:

• Party B generates two keys (public key and private key). The public key is public and available to anyone, while the private key is private
• Party A obtains party B’s public key and uses the public key to encrypt the information
• Party B obtains the encrypted information and decrypts it with the private key

This was the inspiration for the now-famous RSA algorithm, which was designed in 1977 by three mathematicians, Rivest, Shamir, and Adleman, and is named after their initials

This algorithm is reliable because it is based on the common understanding that it is easy to find two large primes, but extremely difficult to factor their product. In the main text, I will explain the implementation principle of RSA in detail, now first point to the ~

Let’s start the text

Type of the encryption algorithm

In general, encryption algorithms are divided into three categories:

• Symmetric encryption
• Asymmetric encryption
• Hashing algorithms (strictly speaking, hashing algorithms are data digest algorithms, not encryption algorithms)

Each type is described in detail below

Symmetric encryption

The common types of symmetric encryption algorithms are:

• DES, a symmetric cryptography encryption algorithm developed by IBM in 1972. Plaintext is divided into 64 bits. The key is 64 bits long. The encryption method of forming a ciphertext group by bitwise substitution or exchange of the plaintext group and the 56-bit key. For a 56-bit key, if the exhaustion method is used to crack it, the number of operations is 2 ^ 56. In today’s CPU performance is so strong, it is easy to crack this type of key, so the security of the algorithm is very low
• 3DES, Triple Data Encryption Algorithm (TDEA, Triple Data Encryption Algorithm), it is equivalent to each Data block applied three TIMES DES Encryption Algorithm. Due to the enhancement of computing power, the key of the original DES became vulnerable to brute force cracking, so 3DES was designed to provide a relatively simple way to avoid similar attacks by increasing the key length of DES, rather than designing an entirely new block cipher algorithm
• AES, Advanced Encryption Standard AES, also known as Rijndael encryption in cryptography, is a block encryption standard adopted by the US federal government to replace the former DES, which has been widely analyzed and used around the world. The encryption algorithm adopts the symmetric block cipher system, the key length supports 128 bits, 192 bits, 256 bits, and the block length is 128 bits

The symmetric encryption algorithm is also called the shared key encryption algorithm. In this scenario, both communication parties hold the same key, which is responsible for both encryption and decryption. The advantages and disadvantages of this algorithm are obvious. The advantage is high efficiency of encryption and decryption, while the disadvantage is that once the key is leaked, there is a risk that the information will be cracked. Generally, this algorithm is not used alone, but used together with asymmetric encryption

Asymmetric encryption

The common types of asymmetric encryption algorithms are:

• RSA, which I’ll explain in detail later, but the library I’m using for my project is Jsencrypt
• Elgamal
• Rabin
• Knapsack algorithm
• D-H
• ECC (Elliptic Curve Encryption Algorithm)

Asymmetric encryption algorithm to achieve the basic process of confidential information exchange is: party a to generate a pair of keys and public key open, need to send information to party a’s other characters (party b) use the key on confidential information at party a’s public key to encrypt and then send to party a, party a to use his private key to decrypt the encrypted information. When Party A wants to reply to Party B, the data is encrypted using Party B’s public key. Similarly, Party B uses his private key to decrypt the data. Asymmetric encryption algorithm has complex strength and high security, but it is precisely because of this characteristic that the encryption and decryption speed is not as fast as symmetric encryption algorithm, and in some extreme cases, it can even be 1000 times slower than symmetric encryption

Asymmetric encryption does not require the communication parties to transmit the key in advance or have any agreement to complete the secure communication, and the key management is convenient, can realize the prevention of counterfeiting and repudiation, so it is more suitable for the secure communication requirements in network communication

Hash algorithm

Common types of hashing algorithms are:

• Message Digest (MD) is a Message Digest algorithm. The MD algorithm family includes MD2, MD4, and MD5. The Message Digest generated by them is 128-bit, which is usually expressed as 32 characters in hexadecimal
• Secure Hash Algorithm (SHA) is a family of cryptographic Hash functions. It is a security Hash Algorithm authenticated by FIPS. It is an Algorithm that can calculate the string of fixed length (also called message digest) corresponding to a digital message. The five algorithms of the SHA family, sha-1, SHA-224, SHA-256, SHA-384, and SHA-512, are sometimes collectively called SHA-2. Sha-1 converts a 64-position message of up to two digits into a 160-bit message digest. The last four algorithms generate summaries that are the number after their name, such as the SHA-256 algorithm, which generates 256-bit summaries

Hash algorithm features are as follows:

• No matter how long the input message is, the calculated length of the message digest is always fixed
• The message digest is pseudo-random
• In general, different inputs will produce different outputs, and the same inputs will produce the same outputs
• Only a positive summary of information can be carried out, and no original information can be recovered from the summary, or even anything related to the original information can be found at all

The hash algorithm is usually used for digital signature, user login, and password change scenarios. In this scenario, do not simply md5 the password, but should combine the password with salt (a random string) and then md5 operation (for example: Result = MD5 (password + sault)), this ensures that even if the hacker gets the original information through the message digest, but because of the existence of salt, then it is impossible to know the user’s real password, thus improving the security of the website

Deeply study the PRINCIPLE of RSA algorithm

Next will explain in detail RSA algorithm is how to achieve asymmetric encryption, which will involve some number theory knowledge, but believe that for smart you are all small case ~

A little number theory background

This section starts with a list of the things you need to know about number theory, because only by laying the foundation can you truly grasp the principles

• Co-prime relationship

A prime number is also called a prime number. A natural number greater than 1 is not divisible by any other natural number except 1 and itself. Otherwise it is called a composite number (which states that 1 is neither prime nor composite)

If two positive integers have no common divisor other than 1, then the two numbers are coprime. For example, 4 and 7 have no common divisor, so they are coprime. We can draw the following conclusions:

2. If one number is prime and the other is not a multiple of the former, the two numbers constitute a mutual prime relationship, such as 3 and 10. If two Numbers, the larger the number is prime, the relationship between two constitute co-prime, such as 5 and 4 4. 1 and any relationship is a natural number are co-prime, such as 1 and 10. 5 p is an integer greater than 1, the relationship between p and p - 1 co-prime, such as 4 and 6. 3 p is odd number greater than 1, the relationship between p and p - 2 co-prime, Like 7 and 5. 7. Prime and non-prime numbers can also form a mutual-prime relationshipCopy the code

• The euler function

The purpose of the Euler function is to find the number of numbers that are mutually prime with n in all positive integers less than or equal to the positive integer n, expressed as φ(n)

For example, when n=4, the positive integers that are less than or equal to 4 and are mutually prime with 4 are: 1, 3, so φ(4) = 2

The evaluation process of φ(n) is simple, but we can derive some established conclusions from it, which can better help us understand the principle, listed below

If n=1, then φ(1) =1, because 1 and any number (including itself) constitute a mutual prime relationship 2. If n is prime, then φ(n) is equal to n minus 1, because the prime and every number less than it are mutually prime. For example, 5 and 1, 2, 3, 4 all constitute the mutualprime relationship 3. If n can be decomposed into the product of two mutualprime integers, that is, n = p1 × p2, then φ(n) = φ(p1p2) = φ(p1)φ(p2), that is, the euler function of the product is equal to the product of the euler function of each factorCopy the code

• Euler’s theorem

A ^φ(n) mod n = 1 if n, a is a positive integer and n, a is a mutual prime, then n to the power of a φ(n) mod n = 1. If n, a is a positive integer and n, a is a mutual prime, then n to the power of a φ(n) mod n = 1.

Here we extend the relationship between Euler’s theorem and Fermat’s little theorem. We know from the above that when n is a prime number, φ(n)=n-1, then we can derive the following deformation formula: A ^φ(n) mod n = 1 => a^(n-1) mod n = 1, and that’s what fermat’s little theorem is derived from, and you can see that Fermat’s little theorem is derived from Euler’s theorem when n is prime

Euler’s theorem is at the heart of THE RSA algorithm, so be sure to master it

• Die inverse element

If two positive integers a and b are mutually prime, then we must find an integer C such that ac-1 is divisible by b, or the remainder of ac divided by b is 1, so that ac mod b is equal to 1, then C is said to be the inverse modular element of A

For example, if 3 and 11 are mutually prime, then the modulo inverse of 3 would be 4, because (3 × 4)-1 is divisible by 11. Obviously, there is more than one modular element, and all multiples of 4 plus or minus 11 are modular elements of 3 {… , 18, 7,4,15,26,… }, that is, if c is a modulo inverse element of A, then c+ KB are both modulo inverse elements of A

Related number theory knowledge has been listed out, these theories must be thoroughly understood, we can really to master the principle of RSA algorithm, the next will explain the specific process of RSA algorithm encryption and decryption and principle, I believe you are ready, then start ~

Get into the process and principle of RSA encryption and decryption

This section is divided into two parts:

• Generation of public and private keys
• Encryption and decryption process

Let’s start with the generation of public key and private key. Let’s assume a scenario: Jay Chou wants to encrypt the communication with Jj Lin. In this case, Jay Chou needs to generate the public key and private key.

• In the first step, Chou has to choose two unequal prime numbers, a and B. In this case, Chou chooses 3 and 5 (in practice, the larger the two primes, the harder it is to crack).
• In the second step, calculate the product c of A and B. C = a * b = 3 * 5 = 15. C is the key, which is 1111 when converted into binary and has a length of 4. Therefore, the length of the key is 4
• Third step, calculate the key of the euler function phi c (c), and the derivation process for: from (c) = (ab) = phi phi (a) (b) = (a – 1) (1 b) = (3, 1), (5-1) = 24 = 8, namely the phi (c) = 8
• The fourth step is to randomly select an integer d, provided that 1< d < φ(c)=8, and d and φ(c) are mutually prime, here Jay chooses 3, that is, d = 3
• The fifth step is to calculate d for the inverse module e of φ(c), De mod φ(c) = 1 => (de-1)/φ(c) = k => de-1 = kφ(c) => de + kφ(c) = 1 => 3e + k8 = 1. This equation can be solved using the extended Euclidean algorithm. Anyway, here Jay Chou solves an integer solution of (3, -1), so e = 3
• In this case, c=15,d=3,e=3, so the public key is (15,3), and the private key is (15,3). Of course, in practical application, the public key and private key will not be the same, and the data of public key and private key are expressed in ASN.1 format

Finally, Jay generates the private and public keys he wants, so he can begin the process of encryption and decryption

It can be seen that the RSA key generation process is relatively complicated, in which the variables used are a,b,c,d,e,φ(c), and the public key generation uses C and d, while the other four are not public, so there is a question: Is it possible to derive the private key from C and D, and here’s how to derive it, so what do you do if you want to get the private key

• (c,e)
• (c, kφ(c) + 1)/d)
• (c, kφ(a*b) + 1)/d)
• C, kφ(a)φ(b) + 1)/d.
• (c,(k(a-1)(b-1) + 1) / d)

From the end result can be seen, as long as you can get a and b, then we can deduce the private key, but it must not be so simple, mystery is hidden between the second and the third step, carefully observing the second step can be found on the third step, be broken down into a * b, c or c is factoring, we know for two large prime Numbers is simpler, It is extremely difficult to factor their product, so it is considered impossible to get to the third step, and therefore impossible to break the private key

From the above argument, we can assume that RSA is a secure encryption algorithm, as long as our key length is long enough, it can be considered impossible to break the private key

Through the above, we should have a clear understanding of RSA key generation rules, so next, we will explain the specific encryption and decryption process, go, go, go!

First of all, we need a public key to encrypt information and a private key to decrypt information. After that, let’s take jay again

Suppose that jj Lin needs to send the message m to jay Chou (note that m must be an integer, and the string can be ASCII or unicode, and m must be less than c). At this time, jj Lin needs to encrypt the message m with jay Chou’s public key (c,d)=>(15,3). The encryption algorithm formula is m^d mod c = f, here is actually to find the value of f, if m is 7, other parameters are the value of the above chestnut, can derive 7^3 mod 15 = f, can easily calculate f=13, so Jj Lin will send 13 to Jay Chou

When Jay Chou receives the 13 sent by Jj Lin, he needs to use his private key (15,3) to decrypt it. The decrypting formula is f^e mod c = m, and he can deduce 13^3 mod 15 = m by plugging in the corresponding value, so Jay Chou can easily calculate m=7, and finally get the real data sent by JJ Lin

At this point, the process of data encryption and decrypting is all over, and Jay Chou and Jj Lin can finally begin to communicate happily ~

You might be smart enough to ask the question: The public key (c,d) can only encrypt an integer m that is less than c, so how do you do that if you want to encrypt a message that is larger than C? There are always more ways than difficulties to solve this problem. At present, there are two solutions:

• By dividing the long message into short messages, encrypting each message separately, and finally piecing the decrypted messages together in a certain order, you can finally get the real complete message
• Select a symmetric encryption algorithm (such as DES), use this algorithm to encrypt the information, and then use the RSA public key to encrypt the information encrypted by DES. When decrypting, first use the RSA key to decrypt the information, and then use THE DES to decrypt the information, and finally get the real information. The derivation process is as follows:
  • m
  • DES(m)
  • RSA_public(DES(m))
  • RSA_private(RSA_public(DES(m)))
  • DES(RSA_private(RSA_public(DES(m))))
  • m

Here, all the explanation of the principle of RSA algorithm is over, I believe that you have been able to fully grasp the smart, if there is not quite understand the place, read a few times, I believe that RSA algorithm contains the exquisite thought charm, you will be able to understand the smart ~

conclusion

Network security is closely related to each and every one of us. It is precisely because of the great scientists invented these amazing encryption and decrypting solutions, so we can have such a developed and relatively safe network environment

Before himself to a conceptual understanding of the RSA algorithm, but after detailed study, I was shocked, by which contains the thoughts of design of fine let me repeatedly, a ring by ring, as with reading a novel solve read finally discovered the truth of the matter, but the truth is inseparable from its process of every detail, Even if one detail is slightly off, it can be a long way from the truth

So a lot of things need us to personally dig, so as to truly feel the truth and charm, well, write so much, the end, scatter flowers 🎉 ~

reference

RSA Algorithm Principle (1)

RSA Algorithm Principle (2)

A little request

Now that you have seen here, if you like my article, then please move your finger, help my article point a like or receive a hidden, your support is the biggest motivation for my creation, here thank you all! ~

Recently, I have set up a personal blog, which will be the first to publish the articles I write, I hope that interested partners to visit, if you can comment on the better, hey hey, look forward to your visit oh ~