4.6k 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 | 4.6k views
0

This one ...

Efficient for bigger values

selected by
+1
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).
$\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
+11

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
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.

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)

z = 12*16 = 192

d = 11 satifies

(35*11)%192 is 1

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

(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
What I did:

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

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