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

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.

---

11??

---

https://gateoverflow.in/118327/gate2017-1-44

---

n=(p-1)*(q-1)

35*e=1+192*k(k=1,2,3,4......)

for k=2

e=11

---

best approach!

---

Make use of Extended Euclidean algorithm

$35\times d\ mod192=1\ |\ d=?$

---

$192=35\times 5+17$

$35=17\times 2+1$

$17=1\times 17$

---

$1=35-17\times 2$

$1=35-(192-35\times 5)\times 2$

$1=35-2\times 192+10\times 35$

$1=35\times 11-2\times 192$

---

$d=11$

---

That's a blessing in disguise for this question.

---

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

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