GateAI
Network Security

GATE CSE 2017 Set 1 · Q44

NAT2 marksEasy

Time

In a RSA cryptosystem, a participant A uses two prime numbers p=13p = 13 and q=17q = 17 to generate her public and private keys. If the public key of A is 35, then the private key of A is __________.

Your answerNumerical answer

Enter a value to check

Solution

Step-by-step verified solution

Official answer: 11

Network Security

In the RSA cryptosystem:

  1. Calculate the modulus:

    n=p×q=13×17=221n = p \times q = 13 \times 17 = 221
  2. Calculate Euler's totient function ϕ(n)\phi(n):

    ϕ(n)=(p−1)(q−1)=(13−1)(17−1)=12×16=192\phi(n) = (p - 1)(q - 1) = (13 - 1)(17 - 1) = 12 \times 16 = 192
  3. The public key exponent is e=35e = 35.

  4. The private key exponent dd is the multiplicative inverse of ee modulo ϕ(n)\phi(n):

    e⋅d≡1(modϕ(n))e \cdot d \equiv 1 \pmod{\phi(n)}
    35⋅d≡1(mod192)35 \cdot d \equiv 1 \pmod{192}

Using the Extended Euclidean Algorithm:

192=35×5+17192 = 35 \times 5 + 17
35=17×2+135 = 17 \times 2 + 1

Expressing 11 as a linear combination of 3535 and 192192:

1=35−2×171 = 35 - 2 \times 17
1=35−2×(192−5×35)1 = 35 - 2 \times (192 - 5 \times 35)
1=35−2×192+10×351 = 35 - 2 \times 192 + 10 \times 35
1=11×35−2×1921 = 11 \times 35 - 2 \times 192

Thus:

35×11≡1(mod192)35 \times 11 \equiv 1 \pmod{192}

Therefore, the private key d=11d = 11.

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Network Security previous year question is Q44 of the GATE CSE 2017 Set 1 paper. Find more GATE CSE PYQs on Network Security in Computer Networks, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 3 related Network Security PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Network Security in GATE CSE

Network Security has 3 GATE CSE PYQs across 2 papers from 2016 to 2017. This is the only 2-mark NAT question among them, and GATE CSE 2017 Set 1 has 2.

How GATE tests Network Security

More from GATE CSE 2017 Set 1

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2017 Set 1 · Q44 · NAT

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 …

Topic-wise GATE CS PYQs with verified steps

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.