The world's most mainstream encryption algorithm

An epoch-making algorithm, earth-shattering; an encryption algorithm that can only be cracked with computing power

##RSA algorithm Stepping out of the historical stage (recommended learning: webfront-end video tutorial)

The time came to 1976, two American computer scientists Whitfield Diffie and Martin Herbert Martin Hellman, for the first time proved that decryption can be completed without directly transmitting the key. This is called the "Diffie-Hellman Key Exchange Algorithm".

The emergence of the DH algorithm has epoch-making significance: from this moment on, it enlightens people that different rules can be used for encryption and decryption, as long as there is a certain correspondence between the rules.

This new mode is also called "asymmetric encryption algorithm":

(1) Party B generates two keys, a public key and a private key. The public key is public and can be obtained by anyone, while the private key is kept secret.

(2) Party A obtains Party B’s public key and uses it to encrypt the information.

(3) Party B obtains the encrypted information and decrypts it with the private key.

The information encrypted by the public key can only be decrypted by the private key. As long as the private key is not leaked, the communication is safe.

Just one year after the invention of the DH algorithm, in 1977, Ron Rivest, Adi Shamir and Leonard Adleman They proposed the RSA algorithm together at MIT. RSA is composed of the initial letters of their last names spelled together.

The newly born RSA algorithm has more powerful characteristics than the DH algorithm, because the DH algorithm is only used for key distribution, while the RSA algorithm can be used for information encryption and digital signatures. In addition, the longer the key of the RSA algorithm, the difficulty of cracking increases exponentially.

Because of its powerful performance, it is no exaggeration to say that wherever there is a computer network, there is the RSA algorithm.

This is how the RSA algorithm works

The RSA algorithm is famous all over the world, so how does it work?

The first step , randomly select two unequal prime numbers p and q.

The second step is to calculate the product n of p and q. The length of n is the key length, generally expressed in binary, and the general length is 2048 bits. The longer the number of digits, the harder it is to crack.

The third step is to calculate the Euler function φ(n) of n.

The fourth step is to randomly select an integer e, where 1< e < φ(n), and e and φ(n) are relatively prime.

The fifth step is to calculate the modular inverse element d of e with respect to φ(n). The so-called "modular inverse element" means that there is an integer d that can make the remainder of ed divided by φ(n) 1.

The sixth step is to encapsulate n and e into public key (n,e), and encapsulate n and d into private key (n,d).

Suppose user A wants to send encrypted information m to user B, and he wants to encrypt m with the public key (n,e). The encryption process is actually a formula:

After user B receives the information c, he uses the private key (n, d) to decrypt it. The decryption process is also a formula:

In this way, user B knows that the message sent by user A is m.

As long as user B keeps the number d secret, others will not be able to obtain the encrypted information m based on the transmitted information c.

The RSA algorithm uses (n, e) as the public key. Is it possible to deduce d when n and e are known?

(1)ed≡1 (mod φ(n)). Only by knowing e and φ(n) can we calculate d.

(2)φ(n)=(p-1)(q-1). Only by knowing p and q can we calculate φ(n).

(3)n=pq. Only by factoring n can we calculate p and q.

So, if n can be decomposed very simply, it is easy to calculate d, which means the information is cracked.

But currently the factorization of large integers is a very difficult thing. At present, apart from brute force cracking, no other effective method has been found. In other words, as long as the key length is long enough, information encrypted with RSA cannot actually be decrypted.

RSA algorithm is gradually being applied to all aspects of human beings

Due to the reliability of the RSA algorithm, this technology is now applied in many places.

The most important application is the protection of information transmission on the Internet. Using the RSA algorithm, even if it is intercepted during the transmission process, it will be difficult to decrypt, ensuring the security of information transmission. Only those with the private key can interpret the information.

The U-Shield for bank transactions is the only proof of user identity. When the USB shield is used for the first time, the RSA algorithm is used to generate the private key and save it in the USB shield. In future use, the private key is used to decrypt the transaction information to perform subsequent transaction operations and protect the interests of the user.

Nowadays, there are many fake and shoddy products, and companies need to use some anti-counterfeiting methods. At present, the most common one is QR code anti-counterfeiting, which facilitates consumers to verify products through a simple scanning operation. However, if the QR code is displayed in plain text, it will be easily used by criminals. Currently, some people have used the RSA algorithm to encrypt the plain text of the QR code to protect the interests of consumers.

The above is the detailed content of The world's most mainstream encryption algorithm. For more information, please follow other related articles on the PHP Chinese website!