Introduction to RSA Algorithm
Wang Hanqiang
This algorithm has occurred in 1978. It is the first algorithm that can be used for data encryption and digital signatures. It is easy to understand and operate, and it is also very popular. The name of the algorithm is naming in the name of the inventor: Ron Rivest, Adishamir and Leonard Adleman. But RSA's security has not been able to obtain theoretical proof. The security of RSA depends on the large decomposition. The public key and private key are two functions of two bulk (more than 100 decocation). It is speculated that the difficulty of clearing the plain text from a key and ciphertext is equivalent to decomposing two largest accumulation. The generation of the key pair. Select two large numbers, p and q. Calculate: n = p * q then randomly select the encryption key E, require E and (P - 1) * (Q - 1) mutual. Finally, the decryption key D is calculated using the Euclid algorithm to satisfy E * D = 1 (MOD (P - 1) * (Q - 1)) where n and d are also mutual. The number E and N are the public key, and D is the private key. The two prime numbers p and q are no longer needed, should be discarded, don't let anyone know. When encrypting information m (binary representation), the m is first divided into a equal length data block M1, M2, ..., Mi, block length S, where 2 ^ s <= n, and s is as large as possible. The corresponding ciphertext is: Ci = Mi ^ e (MOD N) (a) decrypts as follows: Mi = Ci ^ D (MOD N) (B) RSA can be used for digital signatures, the scheme is to sign the signature (A) , (B) verification. Considering the factors such as safety and M information when considering the factors of safety and M information, they are generally ash as a HASH operation. RSA security. The security of RSA depends on the large number of decomposition, but whether it is equivalent to the theoretical proof, because there is no proven to crack the RSA, there must be a large number of decomposition. Assume that there is an algorithm that does not have to decompose, it must be modified to become a large number of decomposition algorithms. At present, some of RSA's variety algorithms have been proven to be equivalent to large decomposition. Anyway, decomposition N is the most obvious attack method. Nowadays, people have decomposed more than 140 decimalities. Therefore, the modulus n must be selected, depending on the specific applicability. RSA speed. Since all of them are calculated, the fastest cases of RSA are more slower than DES, whether software or hardware implementation. The speed has always been the defect of RSA. Generally, only a small amount of data encryption. The selection ciphertext attack of RSA. RSA is very fragile in front of the selection of ciphertext attacks. The general attacker is to make a piece of information, and sign the entity owned by the private key. Then, the information it wants can be obtained after calculation. In fact, the attack is the same weakness, that is, there is a fact that the power retains the input multiplication structure: (XM) ^ D = x ^ D * m ^ D mod N has been mentioned before, this inherent The problem comes from the most useful feature of the public key cryptographic system - each person can use the public key. However, from the algorithm to solve this problem, there are two main measures: one is a good public key protocol to ensure that the entity does not decrypt the information generated by other entities during the work, and is not known for the information you know nothing. One is never sent to the random document signature sent by the stranger, first use One-Way HashFunction to process the document as Hash, or use different signature algorithms simultaneously. Several different types of attack methods are mentioned in China. RSA's public analog number attack. If there is a modulus in the system, only different people have different E and D, and the system will be dangerous. The most common situation is that the same information is encrypted with different public keys, and these public keys are common mode and mutually matched, then the information can be restored without private key.
Set P as clear text, two encryption keys E1 and E2, the public analog number is n, then: C1 = P ^ E1 mod nc2 = P ^ E2 MOD N cryptographic analyst knows N, E1, E2, C1 and C2 You can get P. Because E1 and E2 are mutual, it can be found with the Euclidean algorithm to find R and S, satisfying: r * e1 s * e2 = 1 assumes that R is negative, need to calculate C1 ^ (- 1) with the Euclidean algorithm, then (C1 ^ (-1)) ^ (- r) * C2 ^ S = P MOD N In addition, there are several other methods that utilize common analog to attack. In summary, if you know a pair of E and D for a given analog number, one is conducive to the attacker to decompose analog, one is to contribute to the attacker to calculate other paired E 'and D' without having to decompose anode. The solution is only one, that is, do not share analog number n. The small index attack of RSA. There is a suggestion for increasing the RSA speed to make the public key E take a smaller value, which makes the encryption easy to achieve, and the speed is improved. But this is unsafe, and the method of dealing with E and D take a large value. The RSA algorithm is the first algorithm that can be used for encryption and digital signatures, and is also easy to understand and operate. RSA is the most widely studied public key algorithm. From now on, it has been in the past two decades. It has experienced various attacks, and gradually accepts people, and is generally one of the best public key schemes. The security of RSA depends on the factor decomposition of the large number, but does not in theory to prove the difficulty of deciphering RSA and the equivalent of the large number of decomposition. That is, the significant defects of RSA are unable to grasp its confidentiality performance in theory, and most people who pass codenic programs tend to decompose factor is not NPC issues. The shortcomings of RSA have mainly: a) It is very troublesome to generate a key, which is limited by the number of techniques, so it is difficult to achieve a secret. B) Packet length is too large, in order to ensure safety, n at least 600 bits or more, make the calculation cost, especially slower, more symmetric cryptographic algorithms, slowly, and with the development of large decomposition technology This length is also increasing, which is not conducive to standardization of data format. Currently, CAs are required in the SET (Secure Electronic Transaction) protocol to use a 2048-bit key, and other entities use 1024 bits of keys. DSS / DSA Algorithm DIGITAL SIGNATURE Algorithm (DSA) is a variant of Schnorr and Elgamal signature algorithms, which is used as DSS (DIGITAL SIGNATURESTANDARD). The following parameters are applied in the algorithm: p: L bits long prime numbers. L is a multiple of 64, the range is 512 to 1024; Q: P - 1 160BITS presence; g: g = h ^ ((p-1) / q) MOD P, H satisfying H
1; x: x
