Past exam of the computer science course of the University of Oxford / 2015 / Computer security / 1 / b

For distinct prime numbers $p,q$, compute the Euler totient functionThe RSA cryptosystem private exponent is a modular multiplicative inverse of the public exponent:Use the extended Euclidean algorithm on $3$ and $\phi (n)$. It produces integers $u,v$ with $3u+\phi (n)v=1$, and reducing $u$ modulo $\phi (n)$ gives a suitable positive $d$. Searching through possible exponents is unnecessary.

To see correctness even for a plaintext sharing a factor with $n$, write $3d=1+t\phi (n)$. Modulo $p$, either $m=0$ or Fermat's little theorem gives $m^{3d}=m$; the same holds modulo $q$. The Chinese remainder theorem then gives $c^d=m(\mathrm{mod}n)$. One may alternatively invert $3$ modulo $\mathrm{lcm}(p-1,q-1)$, but inversion modulo $\phi (n)$ is sufficient for this paper.

The essential exponent condition isOtherwise the modular multiplicative inverse defining $d$ does not exist. For large prime numbers greater than three, this is equivalent toIf, for example, $p\equiv 1(\mathrm{mod}3)$, the multiplicative group modulo $p$ has order divisible by three, and cubing is not a bijection; distinct plaintexts can have the same ciphertext. Unique decryption of all messages would then be impossible.

The prime numbers must also be distinct for the displayed totient formula, and selected sufficiently large and independently that integer factorization of $n=pq$ is infeasible. A small factor, equal factors, or an exceptionally small difference between $p$ and $q$ gives an avoidable factorisation weakness. These size and generation conditions address security; the congruence condition addresses invertibility of cubing.