Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 2 / 12K (Coding and Cryptography)

In the Rabin cryptosystem, the public key is $N=pq$, usually with distinct secret primes $p,q\equiv 3(\mathrm{mod}4)$. A message $m$ is encrypted asKnowing $p$ and $q$, the receiver finds the two square roots of $c$ modulo each prime and combines them by the Chinese remainder theorem, obtaining the four square roots modulo $N$; redundancy identifies the intended message.

Factoring $N$ plainly enables this decryption. Conversely, suppose an algorithm returns a square root of a chosen quadratic residue. Choose random invertible $x$, submit $x^2\mathrm{mod}N$, and receive a root $y$. With probability at least $1/2$, $y\not\equiv \pm x(\mathrm{mod}N)$; thenis a nontrivial factor. Thus decryption and factoring are equivalent up to a randomized polynomial-time reduction.

For the RSA cryptosystem, choose $N=pq$ and a public exponent $e$ coprime to $\varphi (N)$. The public key is $(N,e)$, while the private exponent satisfiesEncryption sends $m$ to $c\equiv m^e(\mathrm{mod}N)$, and decryption computes $c^d\equiv m(\mathrm{mod}N)$.

Let the intercepted ciphertexts beSince $\gcd (e_i,e_j)=1$, the extended Euclidean algorithm gives integers $a,b$ with $a{e}_i+b{e}_j=1$. The common-modulus RSA attack recoversNegative powers are evaluated using modular inverses. If an inverse does not exist, its greatest common divisor with $N$ already factors the modulus.

Yes. Your public and private exponents reveal $ed-1$, a nonzero multiple of $\lambda (N)$. The standard RSA private exponent reveals the factorization algorithm uses repeated squaring of random residues to obtain a nontrivial square root of one and hence factors $N$ with a greatest common divisor. Once $p$ and $q$ are known, compute $\varphi (N)$ and invert every other customer's public exponent to obtain that customer's private exponent.