Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 2 / 12K / b

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.