The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+22 votes
In a RSA cryptosystem, a participant $A$ uses two prime numbers $p = 13$ and $q = 17$ to generate here public and private keys. If the public key of $A$ is $35$, then the private key of $A$ is __________ .
asked in Computer Networks by Veteran (370k points)
edited by | 5.5k views

8 Answers

+17 votes
Best answer

Efficient for bigger values

answered by Loyal (6.9k points)
selected by
Not sure if its right methodology or not but usually the co-prime number is a prime number. So I checked only for prime numbers - 3, 5, 7, 11. And got ans in less than 2 minutes.
@ yashgupta1992
what is the procedure?
can u tell me in detail
@Srestha I dont recall the procedure, but due to rigrous practice intutively I knew the other number will be only a prime and hence did not waste time for looking at every other number. Though I will research out if there is a mathematical logic behind it.
Apart from given condition or rules; is there any other rules for applying this formulae . Or we can apply this step any time at any set of input(s).
+26 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


answered by Active (1.4k points)

attempting such questions with an on-screen calculator could be a tough task, (in this case) you check for d=5,6,7,8,.... and hope you get answer before 19 otherwise your 1.5 minutes are wasted. Speaking for myself in examination I felt, relying on repetitive calculations increases the panic level. A better approach would be

We know

ϕ(n)=192 and e=35, so

(35*d)%192=1 OR 35*d=192k+1 for some k

now look at RHS, last digit of 192k (be it any k) will be {2,4,6,8,0}, add 1 to them and you'll see last digit of RHS will always be {3,5,7,9,1}

as you can see on LHS the last digit is 5, there is no way you can get {3,7,9,1} on the last digit of 35*d, be it any d you pick. Now you can conclude that last digit of 35*d is definitely 5. Therefore you need to check for odd values only. Check for d=5,7,9,11,... time halved

@happy singh: in RSA crypto, they settle for smallest d found. Chalo by chance you got 203, what you should have done is check for any smaller than 203 (which is relatively easy)

subtract a number (say A) from 35*203 such that it is a multiple of both 35 and 192, not necessarily LCM.

As 35*203 > product of (35,192), go for 35*192

35*203 - 35*192 = 35*11

you could have got 11

how to solve (d x 35)mod( 192)=1 ???   i mean this i also got .. but further ? how to solve?
$(a*b)mod\,c = (a\,mod\,c*b\,mod\,c)mod\,c$

Thereby, getting $203$ which is greater than $192$ you can easily see that $11$ is $(b\,mod\,c)$
@shweta to be honest
you have to try every possible number for 'd' and check it

there are some tricks to reduce the possible answers and speed up your calculations, but the reality is you have to check manually

@   Nice observation !

+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,


Comparing with $35x + 192y=1$

We get $x = 11.$ as the value of d.
answered by Loyal (6.3k points)
Best solution
+6 votes


 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


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)

answered by Loyal (8.5k points)
+6 votes


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

answered by Junior (573 points)
Rachit can you please explain a bit.
+5 votes
z = 12*16 = 192

d = 11 satifies

(35*11)%192 is 1
answered by Active (2k points)
+5 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
answered by Junior (837 points)
+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
answered by (257 points)
Why are we checking divisibility by 35?
d*35 mod192=1

by seeing the  equation we can easily depict that d>5

just the  write mutiples of 35 (210,245,280,315,350,385,420)

now write the multiples of 192 (192,384,576)

by just intutively dividing the mutiples of 192 with multiples of  35

we see that only 384%385=1 means multiples smaller than 384 will also give same remainder so 192%385=1(because they are the multiple of same number).u can check with other number also

hence we can easily find the d i.e 11

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,474 questions
49,930 answers
65,900 users