RSA for Exams: Solving for the Private Exponent

This note focuses on the calculation pattern commonly required in network-security exams. It does not attempt a full treatment of RSA or number theory; the goal is to show a reliable way to solve for the private exponent.

Example

Given:

e = 31
n = 3599
d = ?

1. Recover p and q, then compute φ(n)

RSA uses:

n = p × q

Factor 3599:

3599 = (60 + 1)(60 - 1) = 61 × 59

Therefore:

p = 61
q = 59
φ(n) = (p - 1)(q - 1) = 60 × 58 = 3480

2. Solve ed - kφ(n) = 1

We need d such that:

ed ≡ 1 (mod φ(n))

Write the equation as:

31d + 3480y = 1

where y = -k. Use the Euclidean algorithm until the remainder is 1:

3480 = 31 × 112 + 8
31   = 8 × 3 + 7
8    = 7 × 1 + 1

Rewrite each remainder:

8 = 3480 - 31 × 112        (3)
7 = 31 - 8 × 3             (2)
1 = 8 - 7                  (1)

Substitute equation (2) into equation (1):

1 = 8 - (31 - 8 × 3)
  = 8 × 4 - 31

Now substitute equation (3):

1 = (3480 - 31 × 112) × 4 - 31
  = 3480 × 4 + 31 × (-449)

Comparing this result with 31d + 3480y = 1 gives:

d = -449
y = 4

The private exponent is taken as a positive representative modulo 3480:

d = -449 + 3480 = 3031

So the answer is:

d = 3031

Compact exam solution

n = 3599 = 59 × 61
φ(n) = 58 × 60 = 3480

31d + 3480y = 1

3480 = 31 × 112 + 8
31   = 8 × 3 + 7
8    = 7 × 1 + 1

1 = 8 - 7
  = 8 - (31 - 8 × 3)
  = 8 × 4 - 31
  = (3480 - 31 × 112) × 4 - 31
  = 3480 × 4 + 31 × (-449)

d = -449 ≡ 3031 (mod 3480)

Once this sequence is familiar, practice it with another set of values so the extended-Euclidean back-substitution becomes automatic during the exam.