GATE 2017 CS – Question 54
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 ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 11
Explanation
The modulus is $n = 13 \times 17 = 221$ and $\phi(n) = 12 \times 16 = 192$. The private key $d$ satisfies $35d \equiv 1 \pmod{192}$. Using the Euclidean algorithm, $192 = 5 \times 35 + 17$ and $35 = 2 \times 17 + 1$, so $1 = 35 - 2(192 - 5 \times 35) = 11 \times 35 - 2 \times 192$. Hence $d = 11$.