Question $3-$ RSA $(50$ marks$)$

$($a$)$ In the textbook RSA cryptosystem, suppose Alice has chosen primes $p=13,q=71$

to set up her RSA keys.

$($i$)$ Find $n$ and $(n),$ and explain why $e=19$ is a valid choice for Alice's public key.

$4$ marks

$($ii$)$ Calculate the corresponding private key $d.$

$6$ marks

$($iii$)$ Calculate how many possible key pairs exist.

$8$ marks

$($iv$)$ Assume that Bob wants to send the message $M=2$ to Alice. Calculate the

encrypted message $C,$ and show that Alice would be able to decrypt $C$ to retrieve

the message.