Student ID: 151828815
Reference: /item/Diffie-Hellman/9827194? Fr = Aladdin
/fw124/article/details/8462373
Embedded cattle guide: With the rapid development of Internet and the improvement of computer computing power, there is a further requirement for information confidentiality-not only information but also keys. DH(Diffie-Hellman) algorithm provides a way to make the key pass through the insecure network safely.
embedded bull nose: DH algorithm, key and network information security
embedded bull question: what is DH algorithm used to protect the communication security in the network? What is the basic principle of DH key exchange?
embedded text: (1) description of algorithm
concept of discrete logarithm:
primitive root: if a is a primitive root of prime number p, then the numerical values:
a mod p, a 2mod p, …, a (p-1) mod p
are different integers, and are in a certain way.
discrete logarithm: if a unique exponent I can be found for an integer B and a primitive root A of prime number P, so that:
B = (I power of A) mod p where ≦ i ≦ p-1
, then the exponent I is called the discrete logarithm of the modulus P of B based on A..
the effectiveness of diffie-hellman algorithm depends on the difficulty of calculating discrete logarithm, which means that it is considered difficult to calculate I for a given prime number P and its original root A, but it is relatively easy to calculate B for a given I..
Diffie-Hellman algorithm:
suppose user a and user b want to exchange a key.
take a prime number p and an integer a, where a is an original root of p, and disclose a and p.
A select the random number xa <: P, and calculate ya = a xa mod p.
B select random number XB <; P, and calculate Yb = a xbmod p.
each party keeps X secret and makes Y public for the other party.
A the way to calculate the key is: k = (Yb) xa mod p
b the way to calculate the key is: k = (ya) xbmod p
proof:
(Yb) xa mod p = (a XB mod p) xa mod p
= (a XB -the key is a (XA * XB) mod p)
= (a xa mod p) XB mod p = (YA) XB mod p
Since XA and XB are confidential and only P, A, YB and Ya are available to the third party, the key can only be determined by taking the discrete logarithm, but for a large prime number P, the discrete logarithm is calculated.
Example:
Suppose user Alice and user Bob want to exchange a key.
take a prime number p =97 and a primitive root a =5 of 97.
Alice and Bob choose secret keys XA=36 and XB=58 respectively, and calculate their respective public keys:
Ya = A XA MOD P = 5 36 MOD 97 = 5
Yb = A XB MOD P = 5 58 MOD 97 = 44
After Alice and Bob exchange public keys, The calculation of * * * sharing key is as follows:
Alice: k = (Yb) Xamod p = 44 36mod97 = 75
Bob: k = (Ya) XBmod p = 5 58mod97 = 75
(2), security
Of course. XB and p, otherwise you can experiment with all possible values. (There are at most 97 such values in total * * *, even if XA and XB are large, it won't help).
if p is a prime number with at least 3 bits, and XA and XB are at least 1 bits long, it is impossible to calculate XA*XB from a, p and a (xa * XB) mod p even with all the computing resources of mankind and the best algorithm today.
this problem is the famous discrete logarithm problem. Note that g does not need to be very large, and it is usually 2 or 5 in general practice.
In the initial description, the Diffie-Herman key exchange itself does not provide authentication services for both parties, so it is vulnerable to man-in-the-middle attacks.
A middleman can successfully pretend to be Bob to Alice by exchanging Diffie-Herman keys twice in the center of the channel, once with Alice and once with Bob, and vice versa.
an attacker can decrypt (read and store) anyone's information and re-encrypt it, and then pass it on to another person. Therefore, a mechanism that can verify the identities of both parties is usually needed to prevent such attacks.
There are many security authentication solutions that use Diffie-Herman key exchange. For example, when Alice and Bob*** have a public key infrastructure, they can sign their return keys.