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

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.