§5 public key cryptosystem
§5.1 Annual public key password system
First, public key cryptographic system
Then the public password system has the following characteristics:
(1) The user must be able to effectively calculate the public and secret key pairs, PK, and SK.
(2) If SK is not known, even if the PK, algorithms E and D and Cipomy are known, it is not possible to determine the calculation of the clear text X.
(3) After the encryption is removed, the original plaintext X is restored.
DSK (EPK (x)) = x (*)
The above formula is established to all X of the EPK field.
EPK (DSK (x)) = x (*, *)
The password system has the following features:
(1) The key distribution is simple. Since the encryption key is different from the decryption key, and cannot be enrolled by the encryption key, the encryption key can be sent by the competent authority by the telephone number.
(2) Secret preserved key amount reduction. Members per password communication in the network only need to secretly save their own decryption keys, and n communication members only need N-to-key.
(3) Privacy requirements for private conversations between people who do not meet each other can meet each other.
⑷ You can complete the digital signature. (Explained later)
two. Differences in two cryptographic systems
1. Algorithm: The algorithm of public key cryptosystem is easy to describe precise mathematical terms. It is established on a particular known mathematical issue, and the security dependent on this mathematical problem is not possible. In contrast, the traditional cryptographic system is based on the mathematical equation of complex disorders. Although solving ordinary equations is not difficult, since it is used multiple iterations and disorders, it cannot be solved by parsing.
2. Key: The key generation method of these two cryptographic systems is also different. In the traditional password system, the encryption key and the decryption key can be derived from each other, so they are randomly selected in a simple method. In the public key cryptographic system, the secret key cannot be simply introduced by the public key. The secret key is selected according to a particular requirements, and the public key is effectively calculated by the secret key using the determined step.
5.2 RSA password system and preparatory knowledge
The RSA cryptosystem is invented by the US Rivest. Shamir (Shamir) and Adleman (Edbeman), named their name, the confidentiality of this system is built in a big factor The compliance is made of factor decomposition is a very difficult issue. (For example, two large numbers p, q, p · q = r require the reverse from R Decomposition to find P, Q, very difficult, basically unpasperate.
We introduce some relevant mathematical knowledge before introducing the RSA system.
First, the basic nature of the number:
Definition 1: It can only be unable to be complete with it, and the positive integer of greater than 1 is not subject to other positive integers is called the number (number).
Theorem 1: Sets A and R are two integers, R ≠ 0 must have = integer q and i exist, make A = QR I 0≤i <|R|
Theorem 2: Sets A and B are two integers, and (a, b) = d (D is the maximum common number of A and B), and the integer S and T make D = Sa TB.
(Sui Decomposition Theorem)
Theorem 3: Each integer greater than 1 is exactly a method representing the product of the number of pins (no order in which the prior factor factor appears).
Second, the concept and basic nature of the same are:
Definition 1: If the difference A-B of the two integers A and B can be divided by another integer R, ie R|A-B, referred to as A, B on the mold R, indicated by symbol AUB (MODR). (Ie A and B have the same amount) If R (A-B) is recorded as a b (MODR)
(If AUB (ModR) is A-B = MR. That is, A = B MR is that A, B is the same as the remainder of R.
Obviously the same is an equal relationship, ie
(1) Self-contrary: AUA (MODR)
(2) Symmetrical: If AUB (MODR), B≡A (ModR)
(3) You can pass: if AUB, B≡C (MODR), A≡C (ModR)
Theorem 4: If A1 C≡B1 (ModR), A2≡B2 (ModR), ..., An≡BN (ModR)
Then A1 · A2 ... ANTB1 · B2 ... BN (MODR)
Introduction 1: If AUB (MODR), for arbitrary positive integers n,
An≡BN (MODR)
Introduction 2: If AUB (MODR), for any integer C
A · C≡b · C (MODR)
Proof: When n = 2, ∵A
1A
2-B1B2 = (A1-B1) A2 (A2-B2) B1
And R|a1-B1, R|a2-B2, ∴ R| (A
1A
2-b1b2)
So
1A
2≡B1B2 (MODR)
Proposition 1: If CaTVB (MODR) is (C, R) = 1, AUB (ModR)
Theorem 5: (according to the mode calculation principle)
Sets A1 and A2 as an integer, OP represents binary operators , -, ×
(A1OPA2) mod = [(A1 MODR) OP (A2 MODR)] ModR
Where amoDR represents the remainder after A by R, amoDR = RESR (A)
Theorem 6: If (a, r) = 1, the same solution is the same as the following AX = 1 (MODR).
Proof: ∵ (a, r) = 1
Bamboo
S, T integer makes Sa Tr = 1
∴ 1-as = TR, R|1-As, 1 dowas (ModR)
Third, Euler function
For the convenience of discussions, the following hypothesis R is positive integer
In order to explain the Euler function, some basic words are introduced.
The integer set i is divided into R subsets by mode R, and each subset is called analog R, and any two integers in the same class are the same as the remainder after R. The number in the middle is different by the remainder after R.
Proposition 1: (1) If A and R are mixed, all the numbers in the same class in the same amount of R are each with R.
(2) If a does not with R, the number in the same class in the same category does not match R.
Definition 2: In a fully residual system of R, all of all the Number of R-Mutant is a simplified residual system (with both remaining systems). (Simplify the number of remaining factors)
(r))
Definition 3: r A full residual system in the full residual system is called the Euler function of R, with
(r)
(r) represents the number of simplified remaining systems of R). because
(r) has nothing to do with the complete remaining system used, so it can be described more intuitively.
Definition 2: Euler function
(r) Represents 0, 1, 2, ..., R-1, the number of Number of R, the number of R mutual numbers, referred to as R's Eu Function.
example
(5) = 4.
(10) = 4 {1, 3, 7, 9}
In general, if R is a magpet, then
(r) = r-1, 2 If r is a compliance, then
(r) 3 When R = 1, all integers are mixed with 1, (α, 1) = 1 Since all integers and 1 have the maximum number of conventions, this class is a class with 1 mutual, ∴ (1) = 1 Proposition 3: If (x1, r) = 1, (x2, r) = 1, ..., (xn, r) = 1 (X1 x2 ... xn r) = 1 Proposition 4: If (a, b) = 1, then (ab) = (a) (b) Theorem 7: Set R = ... p (Each of them is the number of pi), then (r) = r (1- )(1- )……(1- ) Theorem 8: (Euler Theorem) If (A, R) = 1, Aφ (R) 1 (ModR) Theorem 9: Setting R = Pq is the product of two prime factors, A is any non-negative integer of less than R (Ie a ∈ {0, 1, 2, ..., r-1}), M is either positive integer, then AMφ (R) 1 dowa (MODR) Certification: (1) When A = 0, the conclusion is obviously established. Fourth, European miles algorithm (1) How to ask for a, b (A, B) = GCD (A, B) (2) How to determine whether A and B are mutual. When the method (1) is obtained, GCD (A, B) is obtained if GCD (A, B) = 1, which is not mutual. (3) Come back to see theorem 6. If (a, r) = 1, what is the solving of the same AXTZ1 (MODR)? It is also using the European miles. • RSA algorithm introduction First, the selection and calculation of the key: 1. Select two prime numbers P and Q at random. 2, calculate R = P • Q 3, calculate the Euler function (r) = (R (1- )(1- )) = (p-1) (Q-1) 4, choose one with (r) Positive integer k of mutual monitone (quality), define K as the public key PK (or define K as a secret key SK) 5. Please confirm the secret key SK (or calculate the public key by the secret key SK) by the public key PK. In summary: 1. Select the number P and Q P = 47 q = 61 secret. 2, calculate r = p • q r = 2867 is disclosed. 3, calculate (r) = (p-1) (Q-1) (r) = 2760 Secret. 4, select the public key PK, make (PK, (r)) = 1 pk = 167 SK = 1223 is disclosed. 5, calculate the secret key SK, make PK • SK ≡1 mod ( (r)) Secret. 6, message (plain text) X secret. 7, ciphertext Y is disclosed. Second, encryption transformation Before encrypted with RSA, first digitize, the plaintext information to be protected is divided into data blocks of a series of decimal numbers, and the value of each data block does not exceed R-1. 2, encrypt each data block, respectively, the corresponding cixed block is generated. The method is to remove the Ming Dynast X; After the PK is passed, the remaining number is taken. Set x = x1 x2 x3 ... XN, the ciphertext block for encrypted the encrypted version, " Then Ciphertext Y = Y1 Y2 ... Yn Each ciphertext block YI is calculated using the following method: Yi = epk (xi) yi≡ (MODR) Requirements 0 ≤ Yi (In fact, the value of yi is not exceeded by R-1). Three, detachment conversion: For each ciphertext block Yi; the corresponding plaintext is reduced, and the method is to remove the delegate YI to the SK, and the remaining number is removed. (0≤ ≤ the remainder If you don't limit it, you can restore a plurality of expressions, making it unrecorded. Xi = DSK (yi) xi≡ (MODR) 0 ≤ xi 4. Precautions for using RSA algorithms 1, R must be a considerable, such as 200-bit decimal. 2. In the RSA, the length of the ulons should be required to be as small as the length of the number P and Q, so that the enemy is difficult to estimate the general range of P, Q. 3, P-1 and Q-1 should contain large prime factors to increase the enemy guesses (r) difficulty.
