GATE CSE 2017 | Set 1 | Question: 44

Question

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

Comments

$d\times 35 = 1 \text{ mod } 192$

we can write it as:

$d = \frac{1+k\phi}{e} = \frac{1+k\times192}{35}$ , now just put $k's $ value

$d = \frac{1+2\times192}{35} = \frac{385}{35} = 11$

---

how would you solve this question during exam time ?

---

n = ( 13 -1 ) (17 - 1)  = 192

now, 35 * d = 1 mod n = 1 mod 192

thus, d = 11

Answer 1

$\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

Comments

https://stackoverflow.com/questions/16310871/in-rsa-encryption-how-do-i-find-d-given-p-q-e-and-c

---

Stackoverflow solution is not proper . Mathematical rules are broken

---

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 2

Efficient for bigger values

Comments

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

Answer 3

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 = message^E MOD N

  8. Decryption formula (Message):  message = C^D 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)

Answer 4

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.

Comments

Best solution

Answer 5

z = 12*16 = 192

d = 11 satifies

(35*11)%192 is 1

Answer 6

(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

Comments

@skyby

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