Shulou(Shulou.com)06/01 Report--

RSA background

Before 1976, the traditional encryption and decryption process was:

1. A uses some means to encrypt the data.

2. The data is transferred to the hands of B.

3. The reverse implementation of B the steps adopted in An encryption.

4. The data is restored.

This is called symmetric encryption.

Decryption and encryption are inverse processes of each other. The person who encrypts must know the means of decryption. The person who decrypts it must also know the means of encryption.

The biggest feature of this encryption and decryption method is symmetry (easy to operate), but this is also its biggest disadvantage. Because of the encryption party, the encryption rules must be informed to the decryption party.

This creates two problems:

1. The encryption and decryption rules are updated periodically. How to tell each other the encryption and decryption rules smoothly.

2. How to save the encryption and decryption rules safely. Because as long as one party leaks the encryption and decryption rules. Then this kind of encryption can be said to have been cracked.

Based on this, in 1976, two American computer scientists put forward a new idea ("Diffie-Hellman key exchange algorithm"), that is, encryption and decryption in the form of public key-private key pairs.

1. The decryption party generates a pair of keys: public key-private key pair. It is not possible for the two to deduce from each other.

2. The public key reaches the encryption side with the ordinary network, while the private key is always kept in the hands of the decryptor.

3. The encryption party uses the public key to convert the file into ciphertext

4. Transmit the ciphertext to the decryption party.

5. The decryptor uses the private key to convert the ciphertext into plaintext to complete the decryption.

Because the public key and the private key cannot logically deduce each other. In this way, as long as the private key is not disclosed, the ciphertext will not be decrypted. Based on this symmetric encryption, the risk of the first problem is solved, and the risk of the second problem is halved.

Inspired by this idea, in 1977, three mathematicians (Rivest, Shamir and Adleman) jointly published the RSA algorithm, whose name comes from the sum of the initials of the three scientists. In the following decades, RSA encryption algorithm, which shines brilliantly in the cryptographic field, has become the representative encryption algorithm of asymmetric encryption. And with the continuous increase of the key length, with the current computer computing level, it is impossible to crack the key violently and break the algorithm in a limited time.

Implementation Logic of RSA encryption algorithm

In the RSA algorithm, there need to be five important numerical elements:

P, Q: these are two unequal prime numbers randomly selected.

N:n=p*q, which is the product of p and Q

φ (n): φ (n) = (pmur1) (qmur1), that is, the product of pmur1 and qmur1

E: randomly select a positive integer coprime with φ (n). And guarantee e < φ (n)

D: according to ed ≡ 1 (mod φ (n)), the modular inverse element d for φ (n) is calculated.

Ed ≡ 1 (mod φ (n)) means that after ed divides φ (n), the remainder is 1.

That is, ed=k* φ (n) + 1

Can be seen as

Finally, ed= φ (n) x ~ (1) can calculate a set of satisfied solutions by using the division method (looking at the deduction logic on the Internet, I think that it is not meaningful to remember purely in the field of pure mathematics).

So (nmeme) is the public key, and (nmeme) is the private key.

Because the derivation of ePerry d depends on φ (n), and the value of φ (n) comes from p and Q. Although p and Q are obtained randomly, they can be decomposed by n-factor. Therefore, the factorization speed of n becomes the bottleneck of the whole decryption. The factorization of n in other words, similar to judging whether n is a prime number, there is no good way to get rid of the constant violent attempts. At present, the order of magnitude of the maximum number of decomposition known is 10 ^ 232, accounting for 768bit bits, so once n breaks through 768 bits, it can be said to be very difficult to crack. (but it is said that quantum computers are very suitable for calculating factorization, but it is still in its infancy.)

I see, after the generation of public and private keys. Let's take a look at how public and private keys are used:

1. Convert the original information into numbers: whether it is ascii code value, or Unicode code, or other base64 transcoding, etc., after the digital sequence is generated. Encrypt in turn as follows:

Public key (nQuery e), original m

M ^ e ≡ c (mod n)

In other words, c equals m ^ e divided by the remainder of n

That is, to calculate the ciphertext c

2. Send the ciphertext to the decryptor, and the decryptor will restore the cipher according to the following

C ^ d ≡ m (mod n) formula

In other words, m equals the remainder of c ^ d divided by n

Finding m in the opposite direction is plaintext.

The process of proof is ignored here. If you are interested, you can take a look at the RSA encrypted blog written by Ruan Yifeng. The mathematical reasoning inside is more rigorous.

In addition, it should be noted that in the process of public key encryption, m is required to be less than n. If an element is found to be larger than the n of the public key in the process of encryption, the original text needs to be cut into smaller elements and then encrypted.

Other

In addition, the recent widespread virus "Eternal Blue" began in Europe and spread half of the world's blackmail virus through the Internet. Its core idea is to spread the RSA public key to the local machine, and then use the RSA public key to encrypt the local file. So that the local files can not be used normally, and then blackmail the machine owner. After the blackmail is successful, just send the private key file to this machine to decrypt the file. The idea is simple, but very effective, difficult to crack, and the private key files of each machine are almost not the same.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.