+1 vote
90 views
Suppose 2 parties A and B wish to setup a common secret key among themselves using DH key exchange technique .
They agree on 619 as the modulus and 3 as primitive root . Party A chooses 16 and party B chooses 15 as their respective
secrets . what is DH key ?

A)  21

B) 24

C)  242

D) 223

The Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure channel. This key can then be used to encrypt subsequent communications using a symmetric key cipher.

1. A and B agree to use a modulus p = 619 and base g = 3(primitive root)

2. A chooses a secret integer a = 16, then sends B  H = ga mod p = $3^{16}$ mod $619$ = $223$

3. B chooses a secret integer b = 15, then sends A Ggb mod p = $3^{15}$ mod $619$ = $487$

4. A computes s = Ga mod p = $487^{16}$ mod $619$ = $24$

5. B computes s = Hb mod p = $223^{15}$ mod $619$ = $24$

6. A and B now share a secret i.e $24$

$OR$

simply The D-H key is $g^{ab}$ mod $p$ = $3^{16*15}$ mod $619$ = $24$

selected
0
Can u plz explain how to calculate 3^240 ?

Here there must be some rule with which we actually break 240 as (20)12 , since if I evaluate 3^12 mod 619 =339 and then 339 ^20 mod 619 =553 so answer is varying , so which way to go?

Hope it helps.

+1

315*16 mod 619 can be solved without any calculator :-

315*16 mod 619 = 3240 mod 619 = (3103 * 3103 * 334) mod 619

Since , (a*b) mod n = ((a mod n )*(b mod n) ) mod n

So, (3103 * 3103 * 334) mod 619  = [(3103 mod 619)*(3103 mod 619)*(334 mod 619)] mod 619

Now , let 3103 mod 619 = x

Now , take power of 6 both sides or write x , 6 times and multiply them ,

So, we get , 36*103 mod 619 = x6

3618 mod 619 = x6

Now, apply , Fermat's Little Theorem here , ie ap-1 ≡ 1 (mod p) (or)  ap-1 mod p = 1 mod p

So, 3618 mod 619 = 1 mod 619 = 1....So, 1 = x6 ...So , x =1 ...

Now , [(3103 mod 619)*(3103 mod 619)*(334 mod 619)] mod 619  = [1*1* (334 mod 619)] mod 619 = 334 mod 619...

So, whole problem reduces to 334 mod 619..now it can be easily solved

334 mod 619 = (32)17 mod 619 = 917mod 619 = (95*392) mod 619 = (((93)5 mod 619) * (81 mod 619)) mod 619 = ((729)5mod 619 *(81 mod 619)) mod 619

here (729 mod 619)5 mod 619 = 1105mod 619 = (1102*2 *110) mod 619 = [(1102 mod 619)2*110] mod 619

((3392 mod 619)*110 ) mod 619 = 406*110 mod 619 = 92...

So, overall , we get ,92*81 mod 619 = 24..

0
@Ankit , I appreciate your approach but I could not get how did you realise that 3^240 should be broken in terms of 3^103 and then you multiplied 6 on both sides , It's something very high level for me and a bit tricky as well .
0
@Garl , even here there must be some rule with which we actually break 240 as (20)12 , since if I evaluate 3^12 mod 619 =339 and then 339 ^20 mod 619 =553 so answer is varying , so which way to go?
+1

radha gogia ..the process should be repeated... how can u do 33920...it's out of bound...first break it as

(33910x33910)mod 619..but 33910 is still out of bound..

(3395x3395x3395x3395)mod 619...

4174 mod 619

24

i think now u can understand fully :)

0

0

@Radha , since , we know ap-1 mod p = 1..So , if we get a618 using any modification in the problem , then it will give remainder 1 then our problem becomes more easier to solve...since here we have a240 , now we have to think , how to convert it into a618...So , we have to write 240 in the form of 618..now since 618 is not a prime number ..so break it and relate it to 240.. now if we check, is there something common in both 240 and 618 so that we can relate it..

240 = 2*103 + 34 and 618 = 6*103...so we get something common ie 103 in both ..so we can relate these 2 numbers..

So, I have written 240 = 2*103 + 34 = 2*(618/6) + 34

So, a240 = a2*(618/6)a34

So , I converted 240 into 618 based on a number 103..and I took power as 6 both sides to make it as 618 because 103*6 =618  and since I know remainder will be 1 so in the end I will get x =1 ..So, based on above things , I calculated it..

0

radha gogia E in the no shows that it cannot be represented fully .