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?

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+1 vote

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

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

+2 votes

Best answer

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 =

3. B chooses a secret integer * b* = 15, then sends A

4. A computes * s* = G

5. B computes * s* = H

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$

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?

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?

0

Given the answer to all your queries

https://gateoverflow.in/211671/what-would-be-the-message-sent-by-the-sender-in-rsa-algo#c211702

+3 votes

+1

3^{15*16} mod 619 can be solved without any calculator :-

3^{15*16} mod 619 = 3^{240} mod 619 = (3^{103} * 3^{103} * 3^{34}) mod 619

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

So, (3^{103} * 3^{103} * 3^{34}) mod 619 = [(3^{103 }mod 619)*(3^{103 }mod 619)*(3^{34 }mod 619)] mod 619

Now , let 3^{103 }mod 619 = x

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

So, we get , 3^{6*103} mod 619 = x^{6}

3^{618} mod 619 = x^{6}

Now, apply , **Fermat's Little Theorem here , ie a ^{p-1} ≡ 1 (mod p) **(or) a

So, 3^{618} mod 619 = 1 mod 619 = 1....So, 1 = x^{6 }...So , x =1 ...

Now , [(3^{103 }mod 619)*(3^{103 }mod 619)*(3^{34 }mod 619)] mod 619 = [1*1* (3^{34 }mod 619)] mod 619 = 3^{34} mod 619...

So, whole problem reduces to 3^{34} mod 619..now it can be easily solved

3^{34} mod 619 = (3^{2})^{17} mod 619 = 9^{17}mod 619 = (9^{5*3}9^{2}) mod 619 = (((9^{3})^{5} mod 619) * (81 mod 619)) mod 619 = ((729)^{5}mod 619 *(81 mod 619)) mod 619

here (729 mod 619)^{5 }mod 619 = 110^{5}mod 619 = (110^{2*2} *110) mod 619 = [(110^{2} mod 619)^{2}*110] mod 619

((339^{2} 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 339^{20}...it's out of bound...first break it as

(339^{10}x339^{10})mod 619..but 339^{10} is still out of bound..

(339^{5}x339^{5}x339^{5}x339^{5})mod 619...

417^{4} mod 619

24

i think now u can understand fully :)

0

@Radha , since , we know a^{p-1} mod p = 1..So , if we get a^{618} using any modification in the problem , then it will give remainder 1 then our problem becomes more easier to solve...since here we have a^{240} , now we have to think , how to convert it into a^{618}...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, a^{240} = a^{2*(618/6)}a^{34}

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..

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.5k
- Digital Logic 3k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2.1k
- Databases 4.2k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 584
- Exam Queries 566
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,109 questions

53,222 answers

184,632 comments

70,463 users