Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 2 / 12H / Solution

In the RSA cryptosystem, choose distinct primes $p,q$, set $N=pq$, and choose $e$ with $\gcd (e,\varphi (N))=1$. The public key is $(N,e)$; the private exponent satisfiesA message $m$ is encrypted and decrypted by

Suppose $\varphi (N)\mid 2^{a}b$, where $b$ is odd. For a unit $x$ modulo $N$, both $O_p(x^b)$ and $O_q(x^b)$ are powers of two dividing $2^a$. If these orders differ, assume without loss of generality thatTaking $t=r<a$ givesand hencea nontrivial factor.

To count successful $x$, write $p-1=2^{r}u$ and $q-1=2^{s}v$ with $u,v$ odd. Raising to the odd power $b$, which is divisible by the odd parts, maps a uniformly chosen element of each cyclic multiplicative group uniformly onto its Sylow two-subgroup. In a cyclic group of order $2^r$, the probability of order $1$ is $2^{-r}$ and that of order $2^j$ is $2^{j-1-r}$ for $1\le j\le r$. If $r\le s$, the probability that the two resulting orders agree isThus at least half of the $\varphi (N)$ units satisfy $O_p(x^b)\ne O_q(x^b)$.

Knowing $d$ reveals the multiple $ed-1$ of $\varphi (N)$. Writing $ed-1=2^{a}b$ with $b$ odd and trying random units therefore yields a factor with probability at least one half per trial; nonunits already reveal a factor by taking their greatest common divisor with $N$. Conversely, factoring $N$ gives $\varphi (N)$ and hence $d=e^{-1}(\mathrm{mod}\varphi (N))$. This proves that recovering the private key is computationally equivalent, up to randomized polynomial-time work, to factoring the RSA modulus, as summarized by RSA private exponent reveals the factorization.

For $N=77$ and $e=43$, $\varphi (N)=60$ andTherefore

Finally, $e$ is odd because it is coprime to the even integer $\varphi (N)$. If $m^e\equiv m(\mathrm{mod}N)$, thenThus fixed points occur in complementary pairs $m,N-m$, which is the Complementary RSA fixed points property.