Past exam of the mathematics course of the University of Cambridge / 2020 / ia / Paper 2 / 7D / c

Table of contents
- Solution c

Solution

In the RSA cryptosystem, choose distinct large primes

p, q

, put

N = pq

, and choose

e

ϕ (N) = (p - 1) (q - 1) .

The decryption exponent is the modular multiplicative inverse

d \equiv e^{- 1} (mod ϕ (N)) .

Thus

e d = 1 + k ϕ (N)

. For a message with

g cd (m, N) = 1

, the Fermat-Euler theorem gives

c^{d} \equiv m^{e d} = m (m^{ϕ (N)})^{k} \equiv m (mod N) .

For

N = 187 = 11 \cdot 17

,

ϕ (N) = 160

. The extended Euclidean algorithm gives

1 = 37 \cdot 13 - 3 \cdot 160,

so

d = 37 .

 Ancestors (10)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version