You are Alice. You have agreed with your friend Bob that you will use the Diffie

Question

You are Alice. You have agreed with your friend Bob that you will use the Diffie-Hellman public-key algorithm to exchange secret keys. You and Bob have agreed to use the public base g = 7 and public modulus p = 1013. You have secretly picked the value SA = 17. You begin the session by sending Bob your calculated value of TA. Bob responds by sending you the value TB = 839. What is the value of your shared secret key? Can you guess Bob’s secret value SB and what it would be? Show each and every step of your calculations (for mod calculation, the following identity may be useful mod( X^n, p) = mod (mod(X,p)*mod(X^n-1, p), p) mod(X*Y,p) = mod(mod(X,p)*mod(Y,p),p)

Explanation / Answer

Let us first under stand what is Diffie Hellman public key algorithm to exchange secret key. On an insecure channel, it is a bad idea to send the key directly as the attacker will know the key and sensitive information send by encrypting with that key later might be stolen by the attacker. But the two persons has to be agreed upan a key, so key must be sent by one person to another by any means.

Toovercome this problem of key exchange between A and B, Diffie Hellman came up with the fiollowing algorithm:

1) A and B both agrees upon a large prime number p and one of the it's generator g, means both p and g are known by A and B, both of these are public

2) Both A and B each chooses a number as their private key. A chooses SA, known by A only and B chooses SB known by B only

3) A generate public key TA = (gSA)mod p and send it to B. B generates public key TB = (gSB)mod q and send it to A

4) A recieves TB and calculate value of share secret key as Key = (TBSA)mod p and B recieves TA and calculate key as Key = (TASB)mod p .

Now, let us move to the above question, we have following data:

p = 1013

g = 7

SA = 17

TB = 839

I am alice, so i will calculate TA and send it to Bob

TA = (gSA)mod p = (717)mod 1013 = (7 * (716mod1013) )mod1013

= (7 * (78mod1013) * (78mod1013))mod1013

= (7*(74mod1013)*(74mod1013)*(74mod1013)*(74mod1013))mod 1013

= (7*375*375*375*375)mod1013 = 904

TA = 904

I will send 904 to Bob

To calculate the key from the public key sent by Bob:

Key = (TBSA)mod p = (83917)mod 1013

= (839 * (8394mod 1013) * (8394mod 1013) * (8394mod 1013) * (8394mod 1013))mod 1013

= (839*840*840*840*840)mod 1013

= 911

Hence Key = 911

To guess the private key of Bob, i need to solve the following equation:

(TASB)mod p = Key

(904SB)mod 1013 = 911

which is discrete logarithm problem. hence it is not feasible to calculate Bob's private key

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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