4 Diffie-Hellman key agreement For this question we will be considering the orig

Question

4 Diffie-Hellman key agreement For this question we will be considering the original Diffie-Hellman key agreement algorithm, which is like the authenticated version, but excludes the signatures and verifications. a. For Diffie-Hellman we need to choose a public generator g modulo p (where p is prime). If g is a generator, then for every x with gcd(p,x) = 1, there must exist a k such that gk (mod p). This means that we can take discrete logarithms with base g for any r which is not a multiple of p. We can test if g is a generator by finding its order, which is the smallest k such that g1 (mod p). g is a generator modulo p if and only if the order of g is p-1 Using p = 2027, find all generators between 1 and 10, You can use Wolfram Alpha to find the order of g modulo p by typing, for example, order of 2 modulo 2027, substituting in your value of g for 2. 1 mark. b. Using p 2027 and g the smallest generator that you found in the previous question, suppose that Alice and Bob perform Diffie-Hellman key agreement, where Alice's secret is 424 and Bob's secret is 1746. What messages do Alice and Bob send to each other? 1 mark. c. What is the key that Alice and Bob agree on? 1 mark.

Explanation / Answer

By definition, any integer

g Zp is the generator for... the subgroup generated by g, i.e. the set of gk mod(p) for all integer values k. The order of g is the smallest k1 such that gk=1mod(p)

Alice and Bob end up with the same shared key, putting any value of g will give us the answer.

Now for security, we need the order of g to be a multiple of a large enough prime value, usually denoted q. It is not necessary that g generates the whole of Zp It is not necessary that the order of g is exactly q.

If the targeted security level for Diffie-Hellman is "t bits" (i.e. the system will resist attacks up to at least computational effort 2t), then p must be big enough we need a 1024-bit integer for t=80 roughly and the size of q must be at least 2t bits. Also, the DH private keys (a and b) must be randomly and uniformly generated integers of size at least 2t bits. It is not necessary that a and b are generated uniformly among integers modulo q, only that they are generated among a large enough range (this contradicts from DSA, in which we need a random k which MUST be generated uniformly in the[1,q1] range).

Note that the order of g is the smallest when k1 such that gk=1modp

Let q be the order of the value g . If g is a generator for the entire group, then q=p1, if not, it is some proper divisor of p1.

Now, if q is composite, and has a factor r, Now to determine the value a mod(r) (where a is the private exponent) from the public value A in O(r) steps. One way to do this:

First we need to compute the value Aq/r
Then Determine the value k such that (Aq/r)k=gq/rmodp, which is a discrete log problem over a subgroup of order r

So, if q has small factors, it means we are giving a few bits of the private exponent to the attacker. And, if g is a generator, then q will always be a composite number(because it is even). So instead pick a value of g which has large prime order.

(c) In the Diffie-Hellman protocol for key exchange over an unsecured channel, we choose p and g, where g is a generator of Zp. However assuming Alice and Bob choose a and b as secret keys:

(gb)a(ga)b(modp).

Since Alice knows a and gbshe can compute the rightmost term in that equation, and since Bob knows b and gahe can compute the leftmost term. They then have the same number that they can use as a secret key. Since only ga and gb but not a or b are communicated over an untrusted line.

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.