Introduction to Cryptography with Coding Theory, 3rd Edition

9.9 Computer Problems

1. 1. Paul Revere’s friend in a tower at MIT says he’ll send the message one if (the British are coming) by land and two if by sea. Since they know that RSA will be invented in the Boston area, they decide that the message should be encrypted using RSA with $n=712446816787$ and $e=6551$. Paul Revere receives the ciphertext 273095689186. What was the plaintext? Answer this without factoring $n$.

   2. What could Paul Revere’s friend have done so that we couldn’t guess which message was encrypted? (See the end of Subsection 9.2.2.)

2. In an RSA cryptosystem, suppose you know $n=718548065973745507$, $e=3449$, and $d=543546506135745129$. Factor $n$ using the $a^r\equiv 1$ method of Subsection 9.4.2.

3. Choose two 30-digit primes $p$ and $q$ and an encryption exponent ...