The previous article explained in detail the principles of symmetric encryption and algorithms. So is symmetric encryption foolproof? Symmetric encryption has a natural disadvantage, that is, both the encryption party and the decryption party must hold the same key. You may ask a question: Since encryption and decryption are required, of course both parties must hold the key. What's the problem with this? Don't worry, let's continue reading.

Let’s look at an example first. Xiao Ming and Xiao Hong want to communicate, but they don’t want others to know the content of the communication, so the two parties decide to use symmetric encryption. They did the following:

1. Both parties agreed on the encryption and decryption algorithms

2. Both parties determined the key

3. Used during the communication process This key performs encryption and decryption

Is this a seemingly perfect solution? But there is a loophole in one of the steps!

The problem lies in step 2: both parties determine the key!

You will definitely ask, if both parties are not sure of the key, how to perform subsequent encryption and decryption?

The problem is how to make the determined key known to both parties. The key may also be stolen during the delivery process! This leads to a classic problem: the key distribution problem.

Xiao Ming and Xiao Hong will definitely communicate what the key is many times during the process of agreeing on the key. Even if one party decides it once, it must be sent to the other party. Encryption is to ensure the security of information transmission, but the key itself is also information. How to ensure the security of key transmission? Is it possible to encrypt the key transmission again? Wouldn't this lead to an infinite loop?

Are you thinking that even if the key is stolen, isn't there still an encryption algorithm to ensure information security? If you really have this idea, then quickly review the previous article about eliminating hidden security. Any algorithm will eventually be broken, so the complexity of the algorithm cannot be relied upon to ensure security.

Xiao Ming and Xiao Hong are now in a dilemma. If they want to encrypt, they must send each other a key, but sending the key cannot guarantee the security of the key. What should they do?

There are several solutions to the key distribution problem:

Asymmetric encryption is also called public key cryptography. I prefer to use the term asymmetric encryption. Because it can be seen that encryption and decryption use different keys.

In symmetric encryption, we only need one key, which is held by both communicating parties at the same time. Asymmetric encryption requires 4 keys. Each communicating party prepares a pair of public and private keys. The public key is public and is provided by the information recipient to the information sender. The public key is used to encrypt information. The private key is retained by the recipient of the message and is used for decryption. Since the public key is public, there is no confidentiality issue. In other words, there is no key distribution problem in asymmetric encryption! Look, does it perfectly solve the key distribution problem?

Going back to the example just now, Xiao Ming and Xia Hong found after research that asymmetric encryption can solve the security problem of their communication, so they did the following things:

1. Xiao Ming determined Your own private key mPrivateKey, public key mPublicKey. Keep the private key for yourself and send the public key mPublicKey to Xiaohong

2. Xiaohong determined her private key hPrivateKey and public key hPublicKey. Keep the private key yourself and send the public key hPublicKey to Xiao Ming

3. Xiao Ming sends the message "Meet you downstairs at Soho T1 at 10 am on Saturday" and encrypts it with Xiao Hong's public key hPublicKey.

4. After receiving the information, Xiaohong uses her private key hPrivateKey to decrypt it. Then reply "Received, don't be late" and encrypt it with Xiao Ming's public key mPublicKey.

5. After receiving the information, Xiao Ming uses his private key mPrivateKey to decrypt it. After reading the message, I thought to myself: Are you still reminding me not to be late? Is it you who is late every time?

The above process is a complete request and response. Through this example, we sort out the asymmetric encryption and decryption process of an information transmission:

1. The message recipient prepares the public key and private key

2. The private key recipient himself The public key is retained and released to the message sender

3. The message sender uses the receiver's public key to encrypt the message

4. The message receiver uses its own private key to decrypt the message

Public keys can only be used for data encryption. Data encrypted with the public key can only be decrypted with the corresponding private key. This is the core concept of asymmetric encryption.

Below I will use a more vivid example to help everyone understand.

I have a mailbox like the picture below.

Since I only want to receive letters from friends with whom I wish to correspond. So I added a lock to the delivery port. I can make n copies of the key (public key) of this lock and send it to the person I want to receive the letter from. Only these people can use this key to open the mail slot and put the letter in.

I believe that this example can help everyone thoroughly understand the concepts of public keys and private keys.

RSA is the most widely used asymmetric encryption algorithm today. In this section we will briefly introduce the RSA encryption and decryption process.

The RSA encryption and decryption algorithm is actually very simple:

Ciphertext = plaintext ^E mod N

Plaintext = ciphertext ^D mod N

< p> The RSA algorithm does not scramble the original information by playing a Rubik's Cube like symmetric encryption. The same number N is used in RSA encryption and decryption. The public key is public, which means N is also public. So the private key can also be thought of as just D.

Let’s take a look at how N, E, and D are calculated.

1. To find N

First, you need to prepare two very large prime numbers a and b. If it is too small, it will be easy to crack; if it is too large, the calculation cost will be too high. We can use 512-bit numbers, and those with high security requirements can use 1024 or 2048 bits.

N=a*b

2. Find L

L is only a number generated during the key pair generation process and does not participate in encryption and decryption. L is the least common multiple of (a-1) and (b-1)

3. Find E (public key)

E has two restrictions:

1

The greatest common divisor of E and L is 1

The first condition limits the value range of E, and the second condition is to ensure that there is The corresponding D used in decryption.

4. Find D (private key)

D also has two restrictions:

1

E* D mod L = 1

The second condition ensures that the original plaintext can be successfully obtained when decrypting the ciphertext.

Since the principle involves a lot of mathematical knowledge, we will not go into details here. We only need to understand the numbers and formulas used in this process. This is the basis for understanding RSA security.

Since N is public in the public key, you only need to crack D to decrypt and obtain the plaintext.

In actual usage scenarios, prime numbers a and b are generally at least 1024 bits, so the length of N is more than 2048 bits. The length of D is close to N. With the computing power of today's computers, it is very difficult to brute force crack D.

The public key is public, that is to say, E and N are public, so can D be inferred from E and N?

E*D mod L = 1

If you want to calculate D, you need to calculate L first. L is the least common multiple of (a-1) and (b-1). To know L you need to know the prime numbers a and b. The cracker does not know these two prime numbers and can only crack them through brute force. This is the same difficulty as cracking D directly.

Wait, N is public, and N = a*b. So is it possible to perform prime factorization on N to find a and b? Fortunately, humans have not yet discovered a method to efficiently perform prime factorization, so it can be considered that it is very difficult to do prime factorization.

But once an algorithm for fast prime factorization is discovered one day, then RSA will no longer be safe

We can see the importance of large prime numbers a and b in the RSA algorithm . Ensuring the security of a and b also ensures the security of the RSA algorithm. a and b are generated via a pseudo-random generator. Once there is a problem with the algorithm of the pseudo-random number generator, the randomness is poor or can be inferred. Then the security of RSA will be completely destroyed.

A man-in-the-middle attack refers to mixing an attacker into the communication channel. He pretends to be the sender to the receiver, and to the receiver he pretends to be the receiver.

When he monitored the two parties sending public keys, he secretly tampered with the message and sent his own public key to both parties. Then he saves the public keys of both parties.

After doing this, both parties use the attacker's public key for encryption. Then the attacker can decrypt all subsequent communications after intercepting them, tamper with the information content, and then encrypt it with the recipient's public key. . What the recipient gets will be tampered information. In fact, both the sender and the receiver are communicating with the middleman.

To protect against man-in-the-middle, we need to use public key certificates. This part of the content will be introduced in the next article.

Compared with symmetric encryption, asymmetric encryption has the following characteristics:

1. Asymmetric encryption solves the password distribution problem

2. Asymmetric encryption The processing speed is only a few hundredth of that of symmetric encryption. Not suitable for encrypting very long messages.

3. 1024-bit RSA should not be used by new applications. At least 2048 bit RSA is required.

RSA solves the password distribution problem, but is less efficient.

Therefore, sometimes, symmetric and asymmetric encryption may be used together according to needs to form a hybrid cryptosystem, each taking advantage of its strengths.

Finally, I would like to remind everyone that RSA can also be used for signature, but please note that it is a private key signature and a public key signature verification. The sender signs with his own private key, and the recipient uses the other party's public key to verify the signature. Regarding signatures, we will explain them in detail in a later article.