W.Diffie and M.E.Hellman, new directions of cryptography, IEEE transactions on information theory, IT-22. No.6, 1 1 month 1976, pp. 644-654.
The one-way trapdoor function is a function f that satisfies the following conditions:
(1) Given x, it is easy to calculate y = f (x);
(2) Given y, it is difficult to calculate x so that y=f(x).
(The so-called calculation difficulty x=f- 1(Y) means that the calculation is quite complicated and has no practical significance. )
(3) When δ exists, it is easy to calculate X so that y=f(x) For any given y, if the corresponding x exists.
Note: 1*. Only (1) and (2) are called one-way functions; Article (3) is called trap property, and δ is called trap information.
2*. When the trapdoor function f is used as an encryption function, it can be made public, which is equivalent to making public the encryption key. At this time, the encryption key is called the public key and recorded as Pk. The designer of F function keeps δ secret and uses it as the decryption key. At this time, Δ is called the key and recorded as Sk. Because the encryption function is public, anyone can encrypt the information X into y=f(x) and send it to the designer of the function (of course, it can also be transmitted through insecure channels); Since the designer owns Sk, he can naturally solve x=f- 1(y).
3*. The property of one-way trapdoor function (2) shows that it is not feasible for eavesdroppers to infer X from the intercepted ciphertext y=f(x).
Diffie and Hellman gave the idea of cryptography in their landmark articles, but they did not give a real example of public key cryptography, nor did they find a real one-way function with trapdoor. But they gave an example of one-way function, and based on this, they proposed the Diffie-Hellman key exchange algorithm. This algorithm is based on the difficulty of computing discrete logarithm over finite fields: let f be a finite field and g∈ F be f * = f \ {0} =
Description of Diffie-Hellman key exchange protocol: Alice and Bob negotiate a big prime number P and a big integer G, 1
When Alice and Bob want to communicate privately, they can do so as follows:
(1)Alice sends a large random number x and calculates it.
X=gx (modulo p)
(2)Bob chooses a big random number x? , and calculate x? = gx？ (Ministry of Defence)
(3) Alice sends X to Bob; ; Bob can x? Send it to Alice.
(4) Alice calculates K=(X? )X(mod P)； Bob is k? =(X) X？ (mod P), it is easy to see that K=K? =g xx？ (Ministry of Defence).
According to (4), Alice and Bob obtained the same secret value k, and both parties used k as the encryption and decryption key, and used the traditional symmetric key algorithm for secure communication.
Note: Diffie-Hellman key exchange algorithm is patented in the United States and Canada.
3 RSA public key algorithm
RSA public key algorithm was proposed by Rivest, Shamir and Adleman in 1978 (see ACM communication. Volume 265438 +0. Number two. February 1978, page 120- 126).
Z/(n) is expressed as Zn, where n = pqp and q are prime numbers and are different. if
Z*n？ {g∈ Zn|(g, n)= 1}, it is easy to see that Z*n is? Multiplication group of order (n) with g? (n)？ 1(mod n), and? (n)=(p- 1)(q- 1)。
RSA cryptosystem is described as follows:
First, plaintext space p = ciphertext space C=Zn. (see P 175).
A. Generation of key
Choose p, q, p and q as different prime numbers, and calculate n=p*q,? (n)=(p- 1)(q- 1), choose the integer e to make (? (n)，e)= 1， 1 & lt； e & lt？ (n)), calculate d so that d=e- 1(mod? (n)), public key Pk={e, n }；; Private key Sk={d, p, q}.
Note that when 0
MK？ (n)+ 1？ M(mod n), and ed? 1 (mod？ (n)), easy to see (Me)d M(mod n)
B. Encrypt (e, n) plaintext: m
C. Decryption (with d, p, q)
Ciphertext: c plaintext: M=Cd(mod n)
Note: 1* is a pair of inverse operations in encryption and decryption.
2*, for 0 < m < n, if (m, n) ≠ 1, then m is an integer multiple of p or q, assuming that M=cp, from (cp, q)= 1, then there is m? (q)？ 1(mod q) M？ (q)？ (p)？ 1(item q)
Do you have an m? (q)= 1+kq； M=cp Multiplication is the same on both sides.
Do you have an m? (q)+ 1 = m+kcpq = m+kcn then
Do you have an m? (q)+ 1？ M (modern)
Example: if Bob chooses p= 10 1 and Q = 1 13, then n =113. (n)= 100× 1 12 = 1 1200； However, 1 1200 = 26× 52× 7, and a positive integer e can be used as an encryption index if and only if e is not divisible by 2,5,7 (in fact, Bob will not decompose φ(n), and he will use the division method (European algorithm) to find e so that (e, φ (n) = Suppose Bob chooses E.
d=e - 1？ 6597(mod 1 1200), so Bob's decryption key d=6597.
Bob publishes n= 1 14 13 and e=3533 in a directory. Now suppose Alice wants to send plain text 9726 to Bob, and she calculates:
97263533(mod 1 14 13)= 576 1
And send ciphertext 576 1 on one channel. When Bob received the ciphertext 576 1, he decrypted it with his secret decryption index (private key) D = 6597: 57616597 (mod113) = 9726.
Note: The security of RSA is based on the fact that the encryption function ek(x)=xe(mod n) is a one-way function, so it is not feasible for people to get the inverse. And the trap that Bob can decrypt is to decompose n=pq, okay? (n)=(p- 1)(q- 1). Therefore, the decryption private key d is solved by Euclidean algorithm.
Implementation of RSA Cryptosystem
The implementation steps are as follows: Bob is the implementer.
(1) Bob found two big prime numbers, p and q.
(2)Bob calculates n=pq and? (n)=(p- 1)(q- 1)。
(3) Bob chooses a random number e (0
(4)Bob calculates d=e- 1(mod? (n))
(5)Bob exposes N and E as her public keys in the directory.
The key for cryptanalysts to attack RSA system is how to decompose n. Ruofen.
If the solution succeeds in making n=pq, then φ (n) = (P- 1) (Q- 1) can be calculated, and then it can be calculated by the public.
Open e, decrypt D. (guess: crack RSA, decompose n is a polynomial.
Equivalent to. However, this conjecture has not given a credible proof so far! ! ! )
Therefore, RSA is required to be secure, and P and Q must be large enough prime numbers to make.
Analysts can't decompose n in polynomial time. Suggested choice
P and q are approximately decimal prime numbers of 100. The length of module n is required to be at least
5 12. The RSA algorithm used by EDI attack standard stipulates that the length of n is
5 12 to 1024, but it must be a multiple of 128. International figures
The signature standard ISO/IEC 9796 stipulates that the length of n is 5 12 bits.
In order to resist the existing integer decomposition algorithm, the prime factor of RSA module n is analyzed
P and q also have the following requirements:
(1)|p-q| is very large, usually the length of p and q is the same;
(2)p- 1 and q- 1 contain macro factors p 1 and q 1 respectively.
(3)P 1- 1 and q 1- 1 contain macro factor p2 and q2, respectively.
(4)p+ 1 and q+ 1 contain macro-element p3 and q3, respectively.
In order to improve the encryption speed, e is usually taken as a specific small integer, such as e = 2 16+ 1 in EDI international standard, and even e = 3 in ISO/IEC9796. At this time, the encryption speed is generally 10 times faster than the decryption speed. Next, the encryption and decryption arithmetic operations, mainly exponentiation of modulo n, are studied. The famous "square sum multiplication" method reduces the number of modular multiplications of xc(mod n) to at most 2l, where L is the number of digits representing the exponent c in binary. Let n represent k bits in binary form, that is, k=[log2n]+ 1. L≤ k, so that xc(mod n) can be completed in o(k3) time. (Note that it is not difficult to see that multiplication can be completed in o(k2) time. )
Square sum multiplication algorithm;
The exponent c is expressed in binary form as:
c=
xc = xc0×(x2)c 1×…×(x2t- 1)CT- 1
Pre-calculation: x2=xx
x4=x22=x2x2
.
.
.
x2t- 1 =x2t-2*x2t-2
Xc calculation: multiply all x2i corresponding to ci= 1 to get xc. Until/very
T- 1 multiplication is used more. Please refer to the reference book 177 and give the calculation.
Xc(mod n) algorithm program:
A=xc c=c0+c 12+..+CT- 12t- 1 =[CT- 1，....，c 1，c0]2
5 RSA signature scheme
The basic concept of signature
Characteristics of traditional signature (handwritten signature):
(1) signature is the physical part of the signed document;
(2) Verify the physical parts and compare them to achieve the purpose of confirmation. (easy to forge)
(3) It is not easy to faithfully "copy"! ! !
Definition: (Digital signature scheme) A signature scheme is a signature algorithm and verification.
The proof algorithm consists of two parts. Can be carved through the five-element relationship group (P, A, K, S, V):
(1)P is a finite set of all possible messages;
(2)A is a finite set of all possible signatures;
(3)k is a finite key space, which is a finite set of some possible keys;
(4) For any k ∈K, there is a signature algorithm Sigk ∈ S and a corresponding verification algorithm VERK ∈ V. For each one,
Sigk:p A and Verk:P×A {true, false} Meet the conditions: any x ∈ p, y ∈ a. Signature with signature scheme: ver (x, y) = {
Note: 1*. Any k∈K, functions Sigk and Verk are polynomial time functions.
2*.Verk is a public function, while Sigk is a secret function.
3*. If the bad guys (such as Oscar) want to forge Bob's signature on X, it is computationally impossible. That is, given x, only Bob can calculate the signature y so that verk (x, y) = true.
4*. A signature scheme cannot be unconditionally secure. As long as there is enough time, Oscar can always forge Bob's signature.
RSA signature: n=pq, P=A=Zn, define key set K={(n, e, p, q, d)}|n=pq, d*e? 1(mod？ (n))}
Note: n and e are public keys; P, Q, d q and D are secret (private keys). For x∈P, Bob should sign x, and take K ∈ K. Sigk(x)? xd(mod n)？ Y (module n)
therefore
Verk(x, y)= true x? Ye (modern)
(note: e, n is on; You can publicly verify whether the signature (x, y) is right or wrong! ! That is, whether it is Bob's signature)
Note: 1*. Anyone can calculate x=ek(y) for a signature y to forge Bob's signature on random message X.
2*. Encrypted transmission of signature message: suppose Alice wants to encrypt the signature message for Bob, and she does this: For plaintext X, Alice calculates the signature of X, y=SigAlice(x), and then uses Bob's public encryption function eBob to calculate it.
Z=eBob(x, y). Alice sends Z to Bob. After Bob receives Z, the first step is to decrypt it.
dBob(Z)=dBobeBob(x，y)=(x，y)
Then check
VeraAlice (x，y) = true
Q: If Alice encrypts message X first and then signs it, the result will be
How's it going? Y=SigAlice(eBob(x))
Alice sends (z, y) to Bob, who first decrypts z to get x; Then use
VerAlice checks the encrypted signature y about X. The potential problems of this method
The problem is that if Oscar gets this pair of (z, y), he can use his signature.
Replace Alice's signature
y？ =SigOscar(eBob(x))
(Note: Oscar can sign the ciphertext eBob(x), even if he doesn't know the plaintext X. Oscar Telemorphism (z, y? ) Bob, Bob, he may infer that plaintext X is from Oscar. Therefore, it is recommended that you sign first and then encrypt. )
6. EIGMAL plan
EIGamal public key cryptosystem is based on discrete logarithm problem. Jean p
At least 150 decimal prime, p- 1 has a big prime factor. Zp is a finite field,
If α is the primitive in Zp, then there is ZP * =
How to calculate the unique integer A (required, 0≤a≤ p-2), satisfying
αa=β (modulus p)
Write a as a=logαβ.
Generally speaking, solving a is computationally difficult.
Description of Egamal public key system in Zp*: Let the plaintext space be P=Zp* and the ciphertext be empty.
C=Zp*×Zp*, and define the key space K={(p, α, a, β )|β=αa(mod p)}
The public key is: p, α, β.
Key (private key): a
Alice takes a secret random number k∈ Zp- 1 and encrypts plaintext X.
ek(x，k)=(y 1，y2)
Where y 1 = α k (mod p) and y2 = x β k (mod p).
Bob decrypted it,
dk(y 1，y2)=y2(y 1α)- 1(mod p)
Note: 1*. It is easy to verify Y2 (y1α)-1= x (α a) k (α ka)-1= x! !
2*. Using EIGamal encryption algorithm, we can give a signature scheme based on this:
Alice wants to sign plaintext X. First, she takes a secret random number K as her signature.
sign
Sigk(x，k)=(？ , ? )
Among them? =αk(mod p)，？ =(x-a？ ) k- 1 (model p- 1)
Right, x? ∈Zp* and ∈ Zp- 1, define Verk(x,,? ) = True equivalent to
β? α? =αx (modulo p)
It should be noted that if the signature is correctly constructed, the verification will
Is successful, because
β? α? = αa？ αk？ (mod p)= αa？ +k？ (Ministry of Defence)
Know from above? =(x- a？ ) k- 1(mod p- 1) can be introduced.
k？ =x- a？ (mod p- 1) has an a? +kx(mod p)
So beta? = αx (modulo p)
This signature scheme has been determined as the signature standard by NIST (National Institute of Standards and Technology) (1985).
For RSA, please visit the website:
www.RSAsecurity.com