6.9k views
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 __________ .
edited | 6.9k views
+10

so the answer depends on the solution of 35*d= 1 mod 192.

now the best approach to find d would be multiple of 192= 192x+1 (where x is natural no.)

try to divide (192x+1) by 35 if it is divisible then it would be answer

lets say x=1.....    192*1+1=193mod35  remainder not 0

now      x=2......    192*2+1=385mod35 remainder equal to 0        (35*11=385)

so found d=11 within 2 calculation...

i found this approach by one of my mathematic genius friend.

0
best approach!

Efficient for bigger values

selected by
+2
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.
0
@ yashgupta1992
what is the procedure?
can u tell me in detail
+2
@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.
0
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).
+1

refer this

$\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
0
(35*203)%192=1
+20

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

0
how to solve (d x 35)mod( 192)=1 ???   i mean this i also got .. but further ? how to solve?
+3
$(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)$
0
@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
0

@   Nice observation !

0
0
Stackoverflow solution is not proper . Mathematical rules are broken

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)

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.
0
Best solution

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

+1
Rachit can you please explain a bit.
0
@Rachit Agarwal

please explain a bit more. Things not clear like why finding number bigger than 192 then why you double it and the whole procedure ahead.
z = 12*16 = 192

d = 11 satifies

(35*11)%192 is 1
(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
0
@skyby

why you find here 192*2=385. what is purpose of that?
What I did:

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

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

0
Why are we checking divisibility by 35?
+1
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
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
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

edited

1
+1 vote