edited by
23,641 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

2 votes
2 votes
What I did:

take 192 + 1 = 193 - divisible by 35? - No

take 192 * 2 + 1 = 385 - divisible by 35? - Yes - Quotient 11.

11 is the answer! :P
0 votes
0 votes
step 1 --> First we take two distinct prime no. (p ,q)

                 here given p=13,q=17

step 2 --> compute n = p*q

                here  n= 13*17 =221

step 3 -->  compute  Ø(n) =  Ø(p*q) =  Ø(p)  Ø(q) = (p-1) (q-1)

                   here  Ø(13*17) = 12*16 = 192

step 4 --> choose an integer 'e' such that 1<=e< Ø(n), which is co-prime to  Ø(n)

                  (e,n) is public key (35,221)

                  so , e = 35 (since public key given in question is 35)

step 5 --> Determine d

               ed  = 1 mod  Ø(n)

               35*d = 1 mod 192

               d*35 mod 192 = 1

            so d=11 (answer)
edited by
0 votes
0 votes
There are some basic formulas in the RSA Algorithm:

public keys are:  e, n

private keys are: d,n

let us consider two relatively large co-prime numbers p and q then

1. $n = p*q$

2. $\phi(n)= (p-1)*(q-1)$

3. $ed= 1 mod \phi (n)$

In the question they have mentioned that:

$p=13, q=17 ,e=35$

So  $\phi(n)= (13-1)(17-1)=12*16=192$

$ed=1 mod \phi(n)$

$35*d=1 mod 192$; here the tricky part comes in the role,

In 192 the last digit is 2 and in 35 the last digit is 5. Now d's last digit must be that digit which after multiplying with 5 gives 1 as the remainder when the mod 2 is applied on the product.

So the last digit of 'd' contains 1, 3, 5, 7, 9 and the most important thing both e and d are always co-prime. Now you can take some values and check the condition.

11 is the smallest value of 'd' satisfying all the properties.

Answer : d=11
0 votes
0 votes

We can use extended euclidean algorithm to find the inverse.

$e * d = 1 mod 192$

here, we initialize $t1=0 , t2= 1, r1=192, r2= 35$ where $t=t1-q*t2$

And, proceed as follows:

Shift the values at each step as shown:

q r1 r2 r t1 t2 t
5 192 35 17 0 1 -5
2 35 17 1 1 -5 11
17 17 1 0 -5 11 -192
  1 0   11 -192  

Stop the procedure when you get $r2=0$. The value of t1 will give you inverse i.e value of $d=11$

Finally you get Private key of A =11.

Answer:

Related questions

19 votes
19 votes
4 answers
11
go_editor asked Sep 26, 2014
6,947 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