Author: Wang Hanjiang
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 named by inventors: Ron Rivest, Adi
Shamir and Leonard Adleman. But RSA's security has not been able to obtain theoretical proof.
The security of RSA depends on the large decomposition. Public key and private key are two large numbers (greater than 100
Function of a decimal position). According to guess, it is difficult to decompose from a key and secret inference.
A large number of buildings.
The generation of the key pair. Select two large numbers, p and q. Calculate:
n = p * q
Then select the encryption key E, require E and (P - 1) * (Q - 1) mutual. Finally, use
Euclid algorithm calculates the decryption key D, meeting
E * D = 1 (MOD (P - 1) * (Q - 1))
Where n and d are also mutual. Number E and
N is the public key, 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), first, divide M, M2, ..., MI, block length S
2 ^ s <= n, and s is as large as possible. The corresponding ciphertext is:
Ci = mi ^ e (MOD N) (a)
Decipse confidence as the following calculation:
Mi = Ci ^ D (MOD N) (B)
RSA can be used for digital signatures, the scheme is to sign (a) signature, (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 atrial decomposition, it has not been able to get theoretical proof.
In order not to prove crack
RSA must be a large number of decompositions. Suppose there is an algorithm that does not have to decompose, it must be modified
For large decomposition algorithms. Currently, RSA
Some variable algorithms have been proven to be equivalent to large numbers. Anyway, decomposition N is the most obvious attack method. Now
In addition, people have decomposed more than 140 large numbers of decimal positions. 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 slow than DES, whether software or hard
Realization. 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. General attackers are camouflage a message (
Blind) let the entity with private key sign. Then, the information it wants can be obtained after calculation. Actually
The attack is the same weakness, that is, there is such a fact: multiplying the input multiplication structure:
(Xm) ^ D = x ^ D * m ^ D mod n
As mentioned earlier, this inherent problem comes from the most useful feature of public key cryptographic systems - everyone can make
Use 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, not knowing what you know.
Signature; another one is never sent to the random document signature sent by strangers, first-way hash when signing.
FUNCTION
Document is used as a Hash process, or simultaneously use different signature algorithms. Several different types of attackers mentioned
law.
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
The 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 recovered without private key. Set P as a clear text, two encryption keys E1 and E2, the public modulus is n, then:
C1 = P ^ E1 MOD N
C2 = P ^ E2 MOD N
Cryptographic analysts know N, E1, E2, C1 and C2, can get P.
Because E1 and E2 are mutual, I can find R and S with the Euclidean algorithm, satisfying:
R * E1 S * E2 = 1
Suppose r is negative, need to calculate C1 ^ (- 1) with the ECLIDEAN algorithm, then
(C1 ^ (- 1)) ^ (- r) * C2 ^ s = p mod n
In addition, there are several other methods that use common analog to attack. In short, if you know a pair of E and D for a given analog number
First, it is conducive to the attacker to decompose analog, one is to contribute to the attacker to calculate other paired E 'and D', without
Decompose the analog number. The solution is only one, that is, do not share analog number n.
The small index attack of RSA. There is an improvement
The RSA speed suggests that the public key E takes 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 research
The most widely public key algorithm has been put forward that it has been in the past two decades, and has experienced the test of various attacks.
People are accepted, and it is generally considered to be one of the best public key schemes. RSA
The security is dependent on the factor decomposition of the large number, but it does not provigures the difficulty of deciphering RSA and the difficulty of decomposition.
The degree equivalent. That is, the major defects of RSA are unable to grasp the concept of confidentiality in theory, and most of the password
People tend to decompose factors that are not NPC issues.
The shortcomings of RSA have: a) generating a key is very troublesome, limited by the number of technologies, so it is difficult to do
One secret. B) The length of the packet is too large, in order to ensure safety, n at least 600 bits
The above, makes the calculation cost, especially slower, slower number of symmetrical cryptographic algorithms;
The development of several decomposition techniques is also increasing, which is not conducive to standardization of data format. Currently, SET
Secure Electronic Transaction
) The protocol is required 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 NIST as DSS (Digital Signature)
Standard). The following parameters are applied in the algorithm:
P: L bits long prime numbers. L is a multiple of 64, and the range is 512 to 1024;
Q: P - 1 of 160BITS is used;
G: g = h ^ ((p-1) / q) MOD P, H satisfying H
1;
x: x Y: Y = g ^ x mod p, (p, q, g, y) is a public key; H (x): One-way hash function. SHA (Secure Hash Algorithm) is selected in DSS. p, q, G can be shared by a group of users, but in practical applications, the use of common analog numbers may bring a certain threat. The signature and verification agreement are as follows: 1. p produces random number K, K 2. P calc calculate r = (g ^ k mod p) mod S = (k ^ (- 1) (h (m) xr)) mod The signature result is (M, R, S). 3. Calculate w = s ^ (- 1) mod U1 = (h (m) * w) mod U2 = (r * w) MOD Q v = ((g ^ u1 * y ^ u2) mod p) mod If V = R, the signature is considered to be valid. DSA is based on integer limited domain discrete logs, and its security is similar to RSA. An important special speculation of DSA The point is the number of two prime numbers, so that when using others' P and Q, even if you don't know the private key, you can confirm them. Is it randomly generated or a hands-on hand? The RSA algorithm does not do.
