GATE CS 2017 Set 1 Q.44 (CS Q.44): Application Layer: DNS, HTTP, SMTP, FTP

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

Your answer

Official answer and solution

Official answer: 11
From: Official GATE 2017 answer key

Solution

Apply the RSA key generation algorithm using Euler's totient function and the Extended Euclidean Algorithm to find the modular multiplicative inverse.

Given prime numbers $p = 13$ and $q = 17$ , the modulus is:

n = p \times q = 13 \times 17 = 221

Euler's totient function $\phi(n)$ is:

\phi(n) = (p - 1)(q - 1) = (13 - 1)(17 - 1) = 12 \times 16 = 192

The public key is $e = 35$ . The private key $d$ is the modular inverse of $e$ modulo $\phi(n)$ :

e \cdot d \equiv 1 \pmod{\phi(n)} \implies 35 \cdot d \equiv 1 \pmod{192}

Apply the Extended Euclidean Algorithm to solve $35d + 192k = 1$ :

192 = 5 \times 35 + 17

35 = 2 \times 17 + 1

Expressing 1 as a linear combination:

1 = 35 - 2 \times 17 = 35 - 2 \times (192 - 5 \times 35) = 11 \times 35 - 2 \times 192

Thus:

11 \times 35 \equiv 1 \pmod{192}

Checking: $35 \times 11 = 385 = 2 \times 192 + 1$ . Hence, the private key is $d = 11$ .

Final answer

11.0

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2017 Computer Science and Information Technology (CS) Session 1
Question: 44 of 65, printed as CS Q.44
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source