Online toolbox

What is the RSA encryption algorithm?

RSA was proposed in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman. All three of them were working at the Massachusetts Institute of Technology at the time. RSA is composed of the initials of their surnames spelled together. The RSA algorithm is an asymmetric encryption algorithm. Unlike the symmetric encryption algorithm, the RSA algorithm has two different keys, one is a public key and the other is a private key. The RSA public key cryptosystem is a cryptosystem that uses different encryption keys and decryption keys, and it is "computationally infeasible to derive the decryption key from the known encryption key." In the public key cryptosystem, the encryption key (i.e., public key) PK is public information, while the decryption key (i.e., secret key) SK needs to be kept secret. Encryption algorithm E and decryption algorithm D are also public. Although the decryption key SK is determined by the public key PK, SK cannot be calculated based on PK. It is based on this theory that the famous RSA algorithm appeared in 1978. It usually generates a pair of RSA keys first, one of which is a secret key and is saved by the user; the other is a public key, which can be disclosed to the public, or even registered in the network server. To improve confidentiality, RSA keys are at least 500 bits long. This makes encryption computationally intensive. In order to reduce the amount of calculation, when transmitting information, a combination of traditional encryption methods and public key encryption methods is often used, that is, the information is encrypted with an improved DES or IDEA session key, and then the session key and information digest are encrypted with the RSA key. After receiving the information, the other party decrypts it with a different key and can check the summary of the information. RSA is the most widely studied public key algorithm. Since it was proposed, it has experienced various attacks and has gradually become accepted by people. It is generally considered to be one of the best public key schemes at present. In 1983, MIT applied for a patent for the RSA algorithm in the United States. RSA allows you to choose the size of the public key. A 512-bit key is considered unsafe; a 768-bit key does not have to worry about being compromised by anything other than the National Security Administration (NSA); and RSA is embedded within major products such as Windows, Netscape Navigator, Quicken and Lotus Notes. As the 1024-bit key of the RSA algorithm faces serious security threats, in order to ensure the safe application of electronic authentication services, on December 5, 2016, the Shanghai City Cryptography Administration issued an announcement on its official website, stating that starting from January 1, 2017, we will stop providing the 1024-bit key pair service of the RSA algorithm, and cooperate with electronic authentication service organizations and application units to take countermeasures to ensure a smooth transition.

Security of RSA Encryption Algorithm

The security of RSA relies on the decomposition of large numbers, but whether it is equivalent to the decomposition of large numbers has not been theoretically proved, nor has it been theoretically proved and deciphered. The difficulty of RSA is equivalent to the difficulty of decomposing large numbers. Because there is no proof that cracking RSA requires large number decomposition. Assuming there is an algorithm that does not need to decompose large numbers, it can definitely be modified to become a large number decomposition algorithm. That is, the major flaw of RSA is that it cannot theoretically grasp its security performance, and most people in the cryptographic community tend to prefer factorization not to be NPC problem. Currently, some variants of RSA algorithms have been proven to be equivalent to large number factorization. Anyway, decomposing n is the most obvious attack method. Now, people can decompose large prime numbers with more than 140 decimal digits. Therefore, the modulus n must be selected larger, depending on the specific application. The security strength of the RSA algorithm increases as the length of its key increases. However, the longer the key, the longer the time it takes to encrypt and decrypt it. Therefore, it should be considered based on the sensitivity of the protected information, the unworthiness of the attacker to crack it, and the response time required by the system, especially in the field of commercial information.