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

42 votes
42 votes
$\phi$(n) = (p-1)*(q-1)=192

encryption key (e) =35

we have to choose decryption key(d) such a way that (d*e)%$\phi$(n) =1

(35*11)%192=1

ANS:11
19 votes
19 votes

Efficient for bigger values

10 votes
10 votes

RSA ALGO

 1. Calculate value of N = P x Q, where P and Q are large prime nos.(given)

  2. Calculate Z = (P - 1) x (Q - 1)

  3. Choose a value for E (Public key) such that E & Z has no common factors other than 1 between them.

  4. Calculate value of D (Private key) such that (E*D - 1 ) MOD Z = 0 , OR (E*D MOD Z = 1)

  5. A's Public key becomes a tuple pair of <N,E>

  6. A's Private key becomes a tuple-pair of <N,D>

  7. Encryption formula (Cipher text): C = messageE MOD N

  8. Decryption formula (Message):  message = CD MOD N

So in the prob. we have P,Q. So we can calc. N & Z

Now,

E*D MOD N  = 1

35*D MOD 192 = 1   ....(eqn)

The above eqn can be written as:

35*D  = 1 + 192 * K ( K = some positive int.)

If we analyse the above eqn. it can be seen that D > 5 since we get a remainder of 1 on MODULUS.

Find a int. value for K such that , 192 * K + 1= 35*D.

Take K = 2, 1 + 192*2=385;  

35*11 which implies D = 11 (ANS)

7 votes
7 votes
From given data, we find-

$\Rightarrow$ $35*d \equiv 1 (mod 192)$

Where $d$ is description key.

Also, we have.

From euclidean theorem,

$11*35-192*2=1$

Comparing with $35x + 192y=1$

We get $x = 11.$ as the value of d.
Answer:

Related questions

19 votes
19 votes
4 answers
3
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