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.)

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.

Choose two 30-digit primes $p$ and $q$ and an encryption exponent $e$. Encrypt each of the plaintexts cat, bat, hat, encyclopedia, antidisestablishmentarianism. Can you tell from looking at the ciphertexts that the first three plaintexts differ in only one letter or that the last two plaintexts are much longer than the first three?

Factor 618240007109027021 by the $p-1$ method.

Factor 8834884587090814646372459890377418962766907 by the $p-1$ method. (The number is stored in the downloadable computer files ( bit.ly/2JbcS6p) as n1.)

Let $n=537069139875071$. Suppose you know that

Factor $n$.

Let $n=985739879\cdot 1388749507$. Find $x$ and $y$ with $x^2\equiv y^2(\text{mod}n)$ but $x\cancel{\equiv }\pm y(\text{mod}n)$.

1. Suppose you know that

   $$\begin{array}{cc}{33335}^2\equiv {670705093}^2& (\text{mod}670726081)\text{.}\end{array}$$

   Use this information to factor 670726081.

2. Suppose you know that $3^2\equiv {670726078}^2(\text{mod}670726081)$. Why won’t this information help you to factor 670726081?

Suppose you know that

How would you use this information to factor 3837523? Note that the exponent 1916460 is twice the exponent 958230.

Alice and Bob have the same RSA modulus $n$, given to them by some central authority (who does not tell them the factorization of $n$). Alice has encryption and decryption exponents $e_A$ and $d_A$, and Bob has $e_B$ and $d_B$. As usual, $e_A$ and $e_B$ are public and $d_A$ and $d_B$ are private.

1. Suppose the primes $p$ and $q$ used in the RSA algorithm are consecutive primes. How would you factor $n=pq$?

2. The ciphertext 10787770728 was encrypted using $e=113$ and $n=10993522499$. The factors $p$ and $q$ of $n$ were chosen so that $q-p=2$. Decrypt the message.

3. The following ciphertext $c$ was encrypted mod $n$ using the exponent $e$:

   $$\begin{array}{c}n=152415787501905985701881832150835089037858868621211004433\\ e=9007\\ c=141077461765569500241199505617854673388398574333341423525.\end{array}$$

   The prime factors $p$ and $q$ of $n$ are consecutive primes. Decrypt the message. (The number $n$ is stored in the downloadable computer files (bit.ly/2JbcS6p) as naive, and $c$ is stored as cnaive.) Note: In Mathematica^®, the command Round[N[Sqrt[n],50]] evaluates the square root of $n$ to 50 decimal places and then rounds to the nearest integer. In Maple, first use the command Digits:=50 to obtain 50-digit accuracy, then use the command round(sqrt(n*1.)) to change $n$ to a decimal number, take its square root, and round to the nearest integer. In MATLAB, use the command digits(50);round(vpa(sqrt(ʼn’))).

Let $p=123456791$, $q=987654323$, and $e=127$. Let the message be $m=14152019010605$.

1. Compute $m^e(\text{mod}p)$ and $m^e(\text{mod}q)$; then use the Chinese remainder theorem to combine these to get $c\equiv m^e(\text{mod}pq)$.

2. Change one digit of $m^e(\text{mod}p)$ (for example, this could be caused by some radiation). Now combine this with $m^e(\text{mod}q)$ to get an incorrect value $f$ for $m^e(\text{mod}pq)$. Compute $\text{gcd}\left(c-f,pq\right)$. Why does this factor $pq$?

The method of (a) for computing $m^e(\text{mod}pq)$ is attractive since it does not require as large multiprecision arithmetic as working directly mod $pq$. However, as part (b) shows, if an attacker can cause an occasional bit to fail, then $pq$ can be factored.

Suppose that $p=76543692179$, $q=343434343453$, and $e=457$. The ciphertext $c\equiv m^e(\text{mod}pq)$ is transmitted, but an error occurs during transmission. The received ciphertext is 2304329328016936947195. The receiver is able to determine that the digits received are correct but that last digit is missing. Determine the missing digit and decrypt the message.

Test 38200901201 for primality using the Miller-Rabin test with $a=2$. Then test using $a=3$. Note that the first test says that 38200901201 is probably prime, while the second test says that it is composite. A composite number such as 38200901201 that passes the Miller-Rabin test for a number $a$ is called a strong $a$-pseudoprime.

There are three users with pairwise relatively prime moduli $n_1\text{,}{n}_2\text{,}{n}_3$. Suppose that their encryption exponents are all $e=3$. The same message $m$ is sent to each of them and you intercept the ciphertexts $c_i\equiv m^3(\text{mod}{n}_i)$ for $i=1\text{,}2\text{,}3$.

1. Show that $0\le m^3<n_1{n}_2{n}_3$.

2. Show how to use the Chinese remainder theorem to find $m^3$ (as an exact integer, not only as $m^3(\text{mod}{n}_1{n}_2{n}_3)$) and therefore $m$. Do this without factoring.

3. Suppose that

   $$\begin{array}{c}{n}_1=2469247531693\text{,}{n}_2=11111502225583\text{,}\\ n_3=44444222221411\end{array}$$

   and the corresponding ciphertexts are

   $$359335245251\text{,}10436363975495\text{,}5135984059593.$$

   These were all encrypted using $e=3$. Find the message.

1. Choose a 10-digit prime $p$ and and 11-digit prime $q$. Form $n=pq$.

2. Let the encryption exponent be $e=65537$. Write a program that computes the RSA encryptions of all plaintexts $m$ with $1\le m<{10}^4$. (Do not store or display the results.) The computer probably did this almost instantaneously.

3. Modify your program in (b) so that it computes the encryptions of all $m$ with $1\le m<{10}^8$ and time how long this takes (if this takes too long, use ${10}^7$; if it’s too fast to time, use ${10}^9$).

4. Using your timing from (c), estimate how long it will take to encrypt all $m$ with $1\le m<n$ (a year is approximately $3\times {10}^7$ seconds).

Even this small example shows that it is impractical to make a database of all encryptions in order to attack RSA.