edited by
23,659 views
39 votes
39 votes
In a RSA cryptosystem, a participant $A$ uses two prime numbers $p = 13$ and $q = 17$ to generate her public and private keys. If the public key of $A$ is $35$, then the private key of $A$ is __________ .
edited by

12 Answers

6 votes
6 votes
(what i did), first i calculated n i.e. 13*17,

then z = (p-1)*(q-1) = 12*16= 192.

to find private key from given public key i.e. e=35 we need to find d which satisfy the equation

                                                                                            e*d = 1(mod z)  or   e*d mod z =1

i focused on z = 192, and try to find which multiple of 192 can give remainder 1 when divided by 35 , luckily i got 192*2= 385

which satisfy 35*11 mod 192 =1.

mp point here is instead of doing a lengthy work, try the simple one GATE will not try to test your calculation skill
6 votes
6 votes

Approach

Find first number bigger than 192 which is divided by 35 = 210

210%192 = 18

taking twice of 210*2 = 420

420%192 = 36

Clearly, visible 36 is 1 more than 35

That means Subtract 35 from 420 = 385 so that remainder can be reduced to 1(Required condition of RSA (d*e) mod ϕ(n) =1)

So, e*d = 385  => 35*d = 385

d = 11

4 votes
4 votes
35d = 1 mod 192
We will get remainder as 1 if
35d = (Multiple of 192) + 1
Trail 1:
35d = (192*1) + 1
35d = 193
d = 5.514 but D should be an integer
Trail 2:
35d = (192*2) + 1
35d = 385
d = 11 here we got an integer so 11 is the answer
Answer:

Related questions

19 votes
19 votes
4 answers
3
go_editor asked Sep 26, 2014
6,954 views
Which of the following are used to generate a message digest by the network security protocols?RSASHA-$1$DESMD5I and III onlyII and III onlyII and IV onlyIII and IV only