The Prime Supply Company produces RSA keys. It has a database of ${10}^8$ primes with 200 decimal digits and a database of ${10}^{10}$ primes with 250 decimal digits. Whenever it is asked for an RSA modulus, it randomly chooses a 200-digit prime $p$ and a 250-digit prime $q$ from its databases, and then computes $n=pq$. It advertises that it has ${10}^{18}$ possible moduli to distribute and brags about its great level of security. After the Prime Supply Company has used this method to supply RSA moduli to 20000 customers, Eve tries computing gcd’s of pairs of moduli of these clients (that is, for each pair of clients, with RSA moduli $n^{\prime }$ and $n^{\prime \prime }$, she computes $\text{gcd(}{n}^{\prime }\text{,}{n}^{″}\text{)}$). What is the likely outcome of Eve’s computations? Explain.

The Modulus Supply Company sells RSA moduli. To save money, it has one 300-digit prime $p$ and, for each customer, it randomly chooses another 300-digit prime $q$ (different from $p$ and different from $q$ supplied to other customers). Then it sells $n=pq$, along with encryption and decryption exponents, to unsuspecting customers.

1. Suppose Eve suspects that the company is using this method of providing moduli to customers. How can she read their messages? (As usual, the modulus $n$ and the encryption exponent $e$ for each customer are public information.)

2. Now suppose that the customers complain that Eve is reading their messages. The company computes a set $S$ of ${10}^6$ primes, each with 300 digits. For each customer, it chooses a random prime $p$ from $S$, then randomly chooses a 300-digit prime $q$, as in part (a). The 100 customers who receive moduli $n=pq$ from this update are happy and Eve publicly complains that she no longer can break their systems. As a result, 2000 more customers buy moduli from the company. Explain why the 100 customers probably have distinct primes $p$, but among the 2000 customers there are probably two with the same $p$.

Suppose $p(x)=x^4+x+1$ is used in place of the $p(x)$ used in CRC-32. If $S$ is a binary string, then express it as a polynomial $f(x)$, divide by $p(x)$, and let $r(x)$ be the remainder mod 2. Change this back to a binary string of length 4 and call this string $c(S)$. This produces a check-sum in a manner similar to CRC-32.

1. Compute $c$(1001001) and $c$(1101100).

2. Compute $c$(1001001 ⊕ 1101100) and show that it is the XOR of the two individual XORs obtained in part (a).

You intercept the ciphertext TUCDZARQKERUIZCU, which was encrypted using an Enigma machine. You know the plaintext was either ATTACKONTHURSDAY or ATTACKONSATURDAY. Which is it?

1. You play the CI Game from Chapter 4 with Bob. You give him the plaintexts CAT and DOG. He chooses one of these at random and encrypts it on his Enigma machine, producing the ciphertext DDH. Can you decide which plaintext he encrypted?

2. Suppose you play the CI Game in part (a) using plaintexts of 100 letters (let’s assume that these plaintexts agree in only 10 letters and differ in the other 90 letters). Explain why you should win almost every time. What does this say about ciphertext indistinguishability for Enigma?