RSA

The RSA algorithm is the first algorithm that can be used for both encryption and digital signatures. 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 proposed. It has experienced various attacks and has gradually been accepted by people. It is generally considered to be one of the best public key schemes currently. The security of RSA relies on the factorization of large numbers, but it has not been theoretically proven that the difficulty of deciphering RSA is equivalent to the difficulty of factoring large numbers. That is, the major flaw of RSA is that it is impossible to grasp its confidentiality performance theoretically, and most people in the cryptography community tend to believe that factorization is not an NPC problem. The main disadvantages of RSA are: A) It is troublesome to generate the key. It is limited by the prime number generation technology, so it is difficult to achieve one-time encryption. B) The block length is too large. To ensure security, n must be at least 600 bits, which makes the operation very expensive, especially the speed, which is several orders of magnitude slower than 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 format. Currently, the SET (Secure Electronic Transaction) protocol requires CA to use a 2048-bit key and other entities to use a 1024-bit key.

This algorithm appeared in 1978. It was the first algorithm that could be used for both data encryption and digital signatures. It's easy to understand and operate, and it's popular. Algorithms are named after their inventors: Ron Rivest, AdiShamir and Leonard Adleman. However, the security of RSA has not been theoretically proven.

The security of RSA relies on large number decomposition. Both public and private keys are functions of two large prime numbers (greater than 100 decimal digits). It is speculated that deducing the plaintext from a key and ciphertext is as difficult as factoring the product of two large prime numbers.

Generation of key pair. Choose two large prime numbers, p and q. Calculation:

n = p * q

Then the encryption key e is randomly selected, requiring that e and ( p - 1 ) * ( q - 1 ) are relatively prime. Finally, the Euclid algorithm is used to calculate the decryption key d, satisfying

e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )

where n and d are also Be mutually prime. The numbers e and n are public keys, and d is the private key. The two prime numbers p and q are no longer needed and should be discarded without anyone knowing about them.

When encrypting information m (binary representation), first divide m into equal-length data blocks m1, m2,..., mi, with block length s, where 2^s <= n, s as much as possible big. The corresponding ciphertext is:

ci = mi^e ( mod n ) ( a )

The following calculation is made when decrypting:

mi = ci^d ( mod n ) ( b )

RSA can be used for digital signatures. The solution is to use (a) type signature and (b) type verification. During the specific operation, taking into account factors such as security and the large amount of m information, the HASH operation is generally performed first.

Security of RSA.

The security of RSA relies on large number decomposition, but whether it is equivalent to large number decomposition has not been theoretically proven, because there is no proof that breaking RSA requires large number decomposition. Suppose there is an algorithm that does not require decomposition of large numbers, then it can definitely be modified into an algorithm for decomposition of large numbers. At present, some variant algorithms of RSA have been proven to be equivalent to large number decomposition. Regardless, 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 chosen larger, depending on the specific applicable conditions.

The speed of RSA.

Since all large number calculations are performed, RSA is 100 times slower than DES at its fastest, whether it is software or hardware implementation. Speed ??has always been a drawback of RSA. Generally only used for small amounts of data encryption.

RSA's chosen ciphertext attack.

RSA is vulnerable to chosen ciphertext attacks.

Generally, an attacker disguises a certain piece of information (Blind) and asks an entity with a private key to sign it. Then, after calculation, the information it wants can be obtained. In fact, the attacks exploit the same weakness, which is the fact that exponentiation preserves the multiplicative structure of the input:

( XM )^d = X^d *M^d mod n < /p>

As mentioned earlier, this inherent problem comes from the most useful feature of public key cryptography - everyone can use the public key. However, this problem cannot be solved algorithmically. There are two main measures: one is to use a good public key protocol to ensure that entities do not decrypt information arbitrarily generated by other entities during the work process, and do not sign information that they know nothing about; One is to never sign random documents sent by strangers. When signing, first use the 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 .

RSA’s public *** modulus attack.

If there is a modulus in the system, but different people have different e and d, the system will be dangerous. The most common situation is that the same information is encrypted with different public keys. These public keys are fully modular and mutually prime, so the information can be recovered without the private key. Assume P is the plain text of the message, the two encryption keys are e1 and e2, and the public modulus is n, then:

C1 = P^e1 mod n

C2 = P^e2 mod n

If the cryptanalyst knows n, e1, e2, C1 and C2, he can get P.

Because e1 and e2 are mutually prime, r and s can be found using the Euclidean algorithm, satisfying:

r * e1 + s * e2 = 1

Assumption r is a negative number, and the Euclidean algorithm needs to be used to calculate C1^(-1), then

( C1^(-1) )^(-r) * C2^s = P mod n

In addition, there are several other methods of using public *** modulus attacks. In short, if you know a pair of e and d of a given modulus, one is helpful for the attacker to decompose the modulus, and the other is helpful for the attacker to calculate other pairs of e’ and d’ without decomposing the modulus. There is only one solution, and that is not to share modulus n.

Small exponential attack on RSA. One suggestion to improve the speed of RSA is to make the public key e take a smaller value, which will make encryption easier to implement and increase the speed. But this is unsafe. The solution is to take larger values ??for both e and d.