RSA encryption algorithm
· Foreword
This paper introduces the concept, principles, proof and realization of the RSA algorithm. I have reviewed the relevant information online before writing this article, but these information is not ambiguous. So I strive to use popular text to penetrate the algorithm in depth, with the most rigorous steps to the relevant algorithms to reduce the difficulty of reading the article. Readers can understand the full text as long as they have learned the number of junior high schools, I sincerely hope that more readers can recognize that the encryption algorithm is not difficult.
The algorithms in the article are pseudo-codes. Due to the pseudo code, there is no way to test, plus my personal mathematical skill is relatively weak, so the wrong leakage is inevitable, please ask the teachers to give advice. Question or refer to the email to fireseed1949@hotmail.com, I will read and reply carefully!
Thanks to Beihang Mathematics (graduation) Li Wei teacher, Xigong University Computer Department (graduation) Zhang Xiaoning teaches me guidance on me.
Another note: The MOD in the article is the symbol of the surplus, and the x mod y represents X divided by Y.
· Overview
The RSA algorithm is a non-symmetrical encryption algorithm in the world that can be used for data encryption and digital signatures. It is easy to understand and operate, so popular is very popular. The name of the algorithm is named by inventors, they are: Ron Rivest, Adi Shamir and Leonard Adleman. While the security of RSA has not been theoretically confirmed, it has experienced various attacks and has not been completely broken. In order to make readers easier to understand RSA encryption, first explain the concepts and principles of information encryption technology.
Our method for encrypting data exchanged on digital media is called information exchange encryption technology, which is divided into two categories, namely, symmetric encryption, and asymmetric encryption.
In symmetric encryption technology, the same key is used to encrypt and decrypt information, that is, a key is opened. This encryption method simplifies the encryption process, and both parties of information exchange do not have to study and exchange dedicated encryption algorithms. If the private key in the switched phase has not been disclosed, the confidentiality and packet integrity can be guaranteed. Symmetric encryption technology has some shortcomings. If you have N exchange objects, then he will maintain N private keys, another problem with symmetrical encryption is to share a private key, and exchange any information on both sides. It is transmitted to each other after encrypting the key. For example, triple DES is a deformation of the DES (Data Encryption Standard), this method uses two independent 56 for the key to encrypt information, thereby enabling the valid key length to 112 bits.
In an asymmetric encryption (or disclosed key encryption) system, the key is decomposed into pair, that is, the public key (public key), and a private key (private key). This can be publicly disclosed as a public key in the key, and another as a private key is properly saved by a non-confidential manner. The public key is used to encrypt, and the private key is used to decrypt, and the private key can only be mastered by the switching party generated by the generated key, and the public key can be widely announced, but it only corresponds to the switching party generating the key. Asymmetric encryption methods can establish secure communication without prior exchange keys, which are widely used in information exchanges such as identity authentication, digital signatures. The asymmetric encryption system is generally based on certain known mathematical problems, which is an inevitable result of the development of computed complexity. The most representative is the RSA public key cryptographic system.
In the RSA algorithm, we must first get two different prime numbers p and q as algorithm factors, find a positive integer E, make E and (P - 1) * (q - 1) of each other, this E is a private key. Found an integer D such that (E * D) MOD ((p - 1) * (q - 1)) = 1 is established, D is the public key 1. The product of N is N is P and Q, N is the public key 2. When encrypts, it will be converted into one or a set of integer I of one or a set of integer i, and calculate the value of the ID MOD N, M. When decrypting the ciphertext Me Mod n, that is, the remainder of M's E-by, and the remainder obtained by N is clear. Because of the private key E and (P - 1) * (Q - 1), the public key D is established ((p - 1) * (Q - 1)) = 1. Cracks can get D and N, if e, (p - 1) * (q - 1) must be derived, thus must first decompose the N. If N is big, it will be very difficult to decompose, so it is necessary to increase the size of the encryption strength P and Q plays a decisive factor. Generally speaking, when P and Q are greater than 2128, it is basically unlikely to crack the current machine computer processing speed.
·prove
The following will begin discussing the principle of the RSA algorithm and its algorithm proven. If you only care about the implementation of the RSA algorithm, you can skip this step. I use each useful theorem to mark the coarse label. For friends who are not in the row, I can only understand the relevant theorem instead of the verification process.
First, the transformation of the Ma Xiaoli [1]
Gemadoming: Hes are any positive integer, P is the number of prime, and N cannot be divided by P, then:
Np MOD P = N
GM Line can be deformable:
Np - n mod p = 0
(N (Np - 1 - 1)) MOD P = 0
because
(N (Np - 1 - 1)) MOD N = 0
So the multiple of N and P is:
N (Np - 1 - 1) (1)
Also because N and P are mixed, and the least common multiple of mutual numbers is their product, there is a positive integer M so that: n (Np - 1 - 1) = MNP is established. Standardization is concurrent:
NP - 1 - 1 = MP
(Np - 1 - 1) MOD P = 0
Can be deformable:
Np - 1 mod p = 1 (2)
(2) is the conversion theorem of the Ma Xiaoli, which is convenient to describe, hereinafter referred to as the theorem. Tips, many people may think that Ma Xiaoxi is original (2), it is actually not the case, because the conversion of the Ma Xiaoming is very easy, and the conversion theorem is also very common in mathematics or computer procedures. The formula, so people generally believe that (2) is the Ma Xiaoxi.
Second, the intensification decomposition formula
There are three positive integers x, y, and z, and x * y is greater than z, there is:
(X * y) mod z = (x mod z) * (y mod z)) MOD Z
Proof as follows
When X and Y are larger than Z, X and Y can be represented as:
X = zi a (1)
Y = zj b (2)
Distribute (1) and (2) into (x * y) mod z to: ((zi a) (zj b)) MOD Z
(Z (Zij Ia IB) AB) MOD Z (3)
Because Z (Zij Ia IB) is an integer multiple of Z, (3) can be customized:
AB MOD Z
Since A and B are actually X and Y divide the remainder of Z, it is:
(X * Y) MOD Z = (x MOD Z) * (Y Mod Z)) Mod Z is established.
When x ratio z is large and Y rattan
X = zi a
Substance (x * y) mod z to:
(Ziy ay) MOD Z
AY MOD Z
Because A = x mod z, because y mod z = y, it is:
(X * Y) MOD Z = (x MOD Z) * (Y Mod Z)) Mod Z is established.
Similarly, when the X ratio Z is small and Y ratio Z is large, the above formula is also established.
As X and Y are ratio Z hours, x = x mod z, y = y mod z So:
(X * Y) MOD Z = (x MOD Z) * (Y Mod Z)) Mod Z is established.
The intensive decomposition formula is established.
Third, theorem
There are two mutual numbers of P and Q, if there is x mod p = 0, X mod = 0, then: x mod pq = 0
prove:
Because of P and Q, the number of mats is KPQ (k is an integer), the least common multiple is PQ. Only because x is the common multiple of P and Q, X / PQ = K, so X MOD PQ = 0.
Fourth, theorem three
There are two mutual numbers of p and q, with integer X and Y satisfy Y mod p = x, y mod = x, then: y mod pq = x
prove:
X = y mod p
It can be expressed as:
Y = x kp
Y - x = kp
That is, Y-X can be divided by P, which can be used by q. Also because P, q is, depending on theorem.
(Y - X) MOD PQ = 0
which is
Y mod pq = x
V. Theorem three inverse nature
There are P and Q two mutual numbers, and the integer X and Y satisfy Y mod pq = x, then: y mod p = x, y mod = x
prove:
Y mod pq = x
It can be expressed as:
(Y - X) MOD PQ = 0
Obvious
(Y - X) MOD P = 0
(Y - x) MOD Q = 0
So the original question was established.
Sixth, RSA theorem
If P and Q are two phases, the integer R and M are positive and integer R and M, where the value of M and (p - 1) (q - 1) are mutually matched, and (rm) mod (P - 1 (Q - 1) = 1. There is a positive integer A, and a Give C = Ar MOD PQ to B = CM MOD PQ: B = ((AR MOD PQ) M) MOD PQ According to the formula of the intensive decomposition, it can be deformable: B = (ar) m mod pq B = ARM MOD PQ (1) Because there are (rm) mod (p - 1) (q - 1) = 1, there is: Rm = k (p - 1) (Q - 1) 1, K is positive integer. Substation (1): B = AK (P - 1) (Q - 1) 1 mod pq (2) If ARM If ARM> PQ, and a multiple of P is not a multiple of Q, (2) can be deformable: B = (AAK (P - 1) (Q - 1)) MOD PQ Defillation according to the intensive decomposition formula: B = ((A MOD PQ) (AK (P - 1) (Q - 1) MOD PQ) MOD PQ (3) According to the inverse of the theorem three: AK (P - 1) (Q - 1) MOD PQ = (AK (P - 1)) (Q - 1) MOD Q Depending on the Maima, you can: (AK (P - 1)) (Q - 1) MOD Q = 1, then AK (P - 1) (q - 1) MOD PQ = 1 Therefore (3) can be converted to: B = (a MOD PQ) MOD PQ Because of A Summary by the proof process: When P is the number of prime and A and P, then when N is an AN (P - 1) MOD P = 1 when N is any natural number, this theorem is used below, and we call it the americ. If ARM> PQ, a multiple of the PQ but the multiple of Q, a may be represented as a = NQ, n is an integer smaller than A. Then (2) can be deformable: B = (NQ) K (P - 1) (q - 1) 1 mod pq B = (Nk (p - 1) 1) (QK (P - 1) (q - 1) 1) MOD PQ Propose Q as a common factor, obtained: B = ((NNK (p - 1)) (QK (p - 1) (q - 1) MOD P) q Decompose using the formula of the MDF decomposition. B = ((NNK (p - 1) (Q - 1) MOD P) (Qk (p - 1) (q - 1) MOD P) MOD P) q with according to four, NK (P - 1) (Q - 1) and Qk (p - 1) (Q - 1) of the value is 1, so it is: B = (((N mod p) mod p) mod p) q B = NQ MOD PQ MOD PQ MOD PQ B = a mod pq mod pq mod pq Because of A Similarly, when A is a multiple of P instead of Q, B = a is also established. Also because A is less than PQ, and P and q are all rigmeous, the A is both a multiplication of P and Q's multiple. The RSA theorem is established. · Big integer storage operation Due to safety needs, current mainstream RSA encryption algorithms are binding 512-bit or 1024-bit large integers, and the current mainstream high-level language compiler can only support 2 credit 64-bit integers, so large integers Storage and operations are critical to the implementation of the RSA algorithm. One of the most easily understood is to use a decimal representation and perform each bit (0 - 9) as a separate number of arrays. When making operations such as adding and subtraction, manually use it. However, the computer for the 10-based number is not in line, and it means that the number of non-2N-based numbers is wasteful, so 8-based, 16-based, 32-based, 64-based representations should be used, so that each One digit can occupy a complete memory space. At present, most PC machines are based on 32-bit operations, so 232 credits indicate that the large number will greatly improve the processing efficiency of the computer. In reality, the storage of each digit using a 32-bit integer array is used, and a Boolean value indicates that the positive and negative. When calculating, it is often encountered in the borrowing position, and it will often exceed 232 times. Fortunately, all current compilers support 64-bit integers, which can be satisfied (232 - 1) * (232 - 1) operation, so use 64-bit integers will be a good choice as an intermediate amount. In addition to the basic operations such as addition and reduction, there are some assignment, comparison, left and right shifts, or, and, etc., we can use the object-oriented way to package large numbers and use C characteristics. The operator is overloaded to make it an overall object to operate. This way we can use it like Int. Of course, the realization of large numbers is not an article, and there are currently some mature and open source larger type libraries, such as GTK, HugeCalc, etc., I will not further explain the specific algorithms here. . · Power model operation The power mode is the key in the RSA algorithm, whether it is a prime test or encrypted decryption, a power model operation is used. Simply put, the power mode is calculated to calculate the value of NR MOD D. However, for a computer, it will be very wasted when the value of R large NR is calculated, and the storage is very slow and difficult to implement. However, we can find that NR MOD D can be converted by the formula discussed above. NR MOD D = ((N mod D) R) MOD D (1) In this way, in the process of the operation ((N mod D) R) MOD D, in the worst case, the maximum value that may occur is (D - 1) R, and D <= n, thereby reducing The amount of data is improved. By observing findings, (1) can still decompose to reduce the arithmetic steps. When calculating A13, if you let A directly multiply, you need 12 operations. But if we save the value of A * a, we only need to carry out B = A * a and b * b * b * b * b * b * a, a total of seven computments, if we will put B * B value Save, then we only need to perform B = a * a, c = b * b, d = c * c, d * c * a, a total of five operations. Summary This rule can find that if the power is odd during the operation, it is necessary to multiply the product reserved by the multiplication. According to this law, we divide the calculation into two parts of the product, below is pseudo code. Algorithm 1: Calculate the N of the N, order R is the calculation result. R: = n; r is used to store 2N K: = 1; K is used to store the product of another part M: = 0; M represents the power of the power per fouled While E> 1 E: = E / 2, the remainder is stored in M IF m = 1 K: = r * K END IF R: = r * r NEXT R: = r * K Go back to the power model operation we just discussed. In fact, in the (1), we need to see the value of (N mod D) R, then as long as the value of the parameter N in the upper pseudo code is N mod D, and the result r is required to R mode. The following is a pseudo code based on the power mode calculation based on the multiplication algorithm. Algorithm 2: Calculate the N of the e times to take D. The order R is the calculation result. R: = n mod d R: = R ^ E; call algorithm R: = R% D If it is further optimized to the algorithm in the process of referring to the algorithm, it has become a famous Mongerley's fast power mode algorithm, and the pseudo code is as follows. Algorithm 3: The MONGMLL calculates the mode of e-Dimetown to D. The order R is the calculation result. R: = 1 A: = N B: = E While Z! = 0 IF B & 1; Judgment is odd B: = B - 1 R: = r * a X: = x% d Else B: = B / 2 A: = a * a A: = a% D END IF NEXT MONGMARLE is currently an operation of the world's highest efficiency, and many of the methods used in processing similar algorithms. · Looking for a big number In order to effectively prevent cracking, it is necessary to find two large numbers as an algorithm factor. And find a big amount, is a eternal topic of mathematicians. The definition of the number is only the natural number of herself and 1, according to a routine understanding, use a computer to perform a large number of numbers to test a large number, need to traverse all natural numbers smaller than it and greater than 1, and determine if it can be used one by one Number. This process is very slow in very large numbers. However, according to the Maima's aimer, we can design an algorithm to rapid test prime. When A and Q are mutual, there is: AQ - 1 mod = 1, then we can determine whether the value of AQ - 1 MOD Q is equal to 1 pairs of Q in Q. If you take a lot of A, Q is still not tested, then Q is the number of prime. Of course, the more accurate testing times, but it is enough to talk about 50 times. In addition, the normal algorithm is prepared in advance, an array comprising 500 packages, first removing Q, will greatly improve the pass rate, the method is as follows: Algorithm 4: Maima positive test may be P C: = 500; Vulnese Table Size S [0 to c]; prime table B: = P - 1 T: = 50; indicates the number of times for testing A: = 0 For i: = 0 to C; Performing the prime number table preliminary test IF P MOD S [I] = 0 Return Faile END IF IF P Break END IF Next i For i: = 0 to t A: = S [ Rand () MOD C] IF a ^ (p - 1) MOD P <> 1 Return Faile END IF Next i Return PASS This algorithm looks perfect, but in fact, it has made a big mistake from the beginning, that is, there is AQ - 1 mod = 1 for any and q - 1 mod = 1, this is the nature of the number, it is A necessary condition for the number of prime numbers, but not sufficient conditions! Let's take a look at the number of 29341, it is equal to 13 * 37 * 61, but any A29341 - 1 MOD 29341 = 1 is established with the A29341 - 1 MOD 29341 = 1. There are still many other numbers, and they call them as the number of carmai. Now mathematicians have found all 1016 The number of Carmai, the maximum number of Karma, 9585921133193329. We must find a more effective test method. The mathematicians have summed up a variety of rapid and effective prime test methods through the study of Ma Xiaoli, and the current fastest algorithm is the Robin Miller test algorithm. The process is as follows: First determine if n is odd, not an odd judgment failed.
