Describe the RSA encryption scheme with public key $(N, e)$ and private key $d$.

Suppose $N=p q$ with $p$ and $q$ distinct odd primes and $1 \leqslant x \leqslant N$ with $x$ and $N$ coprime. Denote the order of $x$ in $\mathbb{F}_{p}^{*}$ by $\mathrm{O}_{p}(x)$. Further suppose $\Phi(N)$ divides $2^{a} b$ where $b$ is odd. If $\mathrm{O}_{p}\left(x^{b}\right) \neq \mathrm{O}_{q}\left(x^{b}\right)$ prove that there exists $0 \leqslant t<a$ such that the greatest common divisor of $x^{2^{t} b}-1$ and $N$ is a nontrivial factor of $N$. Further, prove that the number of $x$ satisfying $\mathrm{O}_{p}\left(x^{b}\right) \neq \mathrm{O}_{q}\left(x^{b}\right)$ is $\geqslant \Phi(N) / 2$.

Hence, or otherwise, prove that finding the private key $d$ from the public key $(N, e)$ is essentially as difficult as factoring $N$.

Suppose a message $m$ is sent using the $\mathrm{RSA}$ scheme with $e=43$ and $N=77$, and $c=5$ is the received text. What is $m$ ?

An integer $m$ satisfying $1 \leqslant m \leqslant N-1$ is called a fixed point if it is encrypted to itself. Prove that if $m$ is a fixed point then so is $N-m$.