RSA algorithm is the first algorithm that can be used for both encryption and digital signature, and it is also easy to understand and operate. RSA is the most widely studied public key algorithm. It has been nearly twenty years since it was put forward, and it has been gradually accepted by people after being tested by various attacks. It is generally considered as one of the best public key schemes at present. The security of RSA depends on the factorization of large numbers, but it has not been proved theoretically that the difficulty of deciphering RSA is equal to the difficulty of factorization of large numbers. In other words, one of RSA's major defects is that it can't grasp its security performance in theory, and most people in cryptography tend to think that factorization is not an NPC problem. The main disadvantages of RSA are: a) it is very troublesome to generate keys, and it is difficult to achieve one secret at a time due to the limitation of prime number generation technology. B) The packet length is too large. In order to ensure security, n should be at least 600 bits, which makes the operation cost very high, especially the speed is slow, which is several orders of magnitude slower than that of the symmetric cryptographic algorithm; And with the development of large number decomposition technology, this length is still increasing, which is not conducive to the standardization of data formats. At present, Set protocol requires CA to use 2048-bit key, while other entities use 1024-bit key.
This algorithm appears in 1978, which is the first algorithm that can be used for data encryption and digital signature at the same time. Easy to understand and operate, and very popular. The name of the algorithm is named after the inventors: Ron Rivest, AdiShamir and Leonard Adleman. However, the security of RSA has not been proved theoretically.
The security of RSA depends on the decomposition of large numbers. Both the public key and the private key are functions of two large prime numbers (more than 100 decimal digits). The difficulty of inferring plaintext from a key and ciphertext is equivalent to decomposing the product of two large prime numbers.
Generation of key pairs. Choose two big prime numbers, p and Q. Calculate:
n = p * q
Then the encryption key E is randomly selected, and it is required that E and (p- 1) * (q- 1) are prime numbers. Finally, the decryption key d is calculated by Euclid algorithm, which meets the following requirements.
e * d = 1(mod(p- 1)*(q- 1))
Where n and d are also coprime. Numbers e and n are public keys and d is private key. Two prime numbers, P and Q, are no longer needed and should be discarded so that no one knows.
When encrypting information M (binary representation), firstly, M is divided into equal-length data blocks m 1, m2, ..., mi, block length s, where 2 s.
Ci = mi^e (modern) (a)
When decrypting, the following calculations are performed:
Mi = ci^d (modern) (b)
RSA can be used for digital signature, and the schemes are (a) signature and (b) verification. Considering the factors such as security and the large amount of M information, hash operation is usually done first.
Security of RSA.
The security of RSA depends on the decomposition of large numbers, but whether it is equivalent to the decomposition of large numbers has not been proved theoretically, because it needs to decompose large numbers without proof. Assuming that there is an algorithm that does not need to decompose large numbers, it can definitely be modified into a large number decomposition algorithm. At present, some variant algorithms of RSA have been proved to be equivalent to large number decomposition. In any case, decomposing n is the most obvious attack method. Now, people have been able to decompose more than 140 decimal prime numbers. Therefore, depending on the specific application, the modulus n must be larger.
The speed of RSA.
Because of the calculation of large numbers, the fastest case of RSA is 100 times slower than DES, whether it is implemented by software or hardware. Speed has always been RSA's shortcoming. Generally speaking, it is only used to encrypt a small amount of data.
Selective ciphertext attack of RSA.
RSA is vulnerable to selective ciphertext attacks. Generally, attackers will blindly disguise some information and let entities with private keys sign it. Then, it can get the information it wants through calculation. In fact, all attacks take advantage of the same weakness, that is, there is the fact that the power keeps the multiplication structure of the input:
(XM) d = x d * m d model n
As mentioned earlier, this inherent problem comes from the most useful feature of public key cryptosystem-everyone can use the public key. However, this problem cannot be solved algorithmically, and there are two main measures: one is to adopt a good public key protocol to ensure that entities do not decrypt information generated arbitrarily by other entities or sign information they know nothing about; The other is never to sign a document sent by a stranger casually. When signing, first use one-way hash function to hash the document, or use different signature algorithms at the same time. Several different types of attack methods are mentioned in.
Common mode attack of RSA.
If there are modules in the system, but different people have different E and D, the system will be dangerous. The most common situation is to encrypt the same information with different public keys, and these public keys are modular and prime numbers, so the information can be recovered without private keys. Let p be plaintext, two encryption keys e 1 and e2, and public * * * modulus n, then:
C1= p e1module number
C2 = P^e2 Modern
If the cryptanalyst knows n, e 1, e2, C 1 and C2, he can get p.
Because e 1 and e2 are coprime, R and S can be found by Euclidean algorithm, which satisfies:
r * e 1 + s * e2 = 1
Assuming that R is negative, it is necessary to calculate C 1 (- 1) by Euclid algorithm, then
(c 1^(- 1))^(-r)* c2^s = p modn
In addition, there are several other ways to attack by using common mode. In a word, if we know the e and d of a given module, it is beneficial for the attacker to decompose the module and calculate other pairs of E' and D' without decomposing the module. There is only one solution, and that is not to enjoy the modulus n.
Small exponent attack of RSA. One suggestion to improve the speed of RSA is to make the public key e smaller, which will make encryption easier and faster. But it is not safe to do so, and the way to deal with it is to take larger values for e and d.