Chapter 1

Build a cipher wheel as illustrated in Figure 1.1, but with an inner wheel that rotates, and use it to complete the following tasks. (For your convenience, there is a cipher wheel that you can print and cut out at www.math.brown.edu/ \(/ \mathrm{jhs} /\) MathCrypto/CipherWheel. pdf.) (a) Encrypt the following plaintext using a rotation of 11 clockwise. "A page of history is worth a volume of logic." (b) Decrypt the following message, which was encrypted with a rotation of 7 clockwise. AOLYLHYLUVZLJYLAZILAALYAOHUAOLZLJYLALZAOHALCLYF IVKFNBLZZLZ (c) Decrypt the following message, which was encrypted by rotating 1 clockwise for the first letter, then 2 clockwise for the second letter, etc. X JHRFTNZHMZGAHIUETXZ JNBWNUTRHEPOMDNBJMAUGORFAOIZOCC

Each of the following messages has been encrypted using a simple substitution cipher. Decrypt them. For your convenience, we have given you a frequency table

Suppose that you have an alphabet of 26 letters. (a) How many possible simple substitution ciphers are there? (b) A letter in the alphabet is said to be fixed if the encryption of the letter is the letter itself. How many simple substitution ciphers are there that leave: (i) no letters fixed? (ii) at least one letter fixed? (iii) exactly one letter fixed? (iv) at least two letters fixed? (Part (b) is quite challenging! You might try doing the problem first with an alphabet of four or five letters to get an idea of what is going on.)

Let \(a, b, c \in \mathbb{Z}\). Use the definition of divisibility to directly prove the following properties of divisibility. (This is Proposition 1.4.) (a) If \(a \mid b\) and \(b \mid c\), then \(a \mid c\). (b) If \(a \mid b\) and \(b \mid a\), then \(a=\pm b\). (c) If \(a \mid b\) and \(a \mid c\), then \(a \mid(b+c)\) and \(a \mid(b-c)\).

Use the Euclidean algorithm to compute the following greatest common divisors. (a) \(\operatorname{gcd}(291,252)\). (b) \(\operatorname{gcd}(16261,85652)\). (c) \(\operatorname{gcd}(139024789,93278890)\). (d) \(\operatorname{gcd}(16534528044,8332745927)\).

Let \(a\) and \(b\) be positive integers. (a) Suppose that there are integers \(u\) and \(v\) satisfying \(a u+b v=1\). Prove that \(\operatorname{gcd}(a, b)=1\). (b) Suppose that there are integers \(u\) and \(v\) satisfying \(a u+b v=6\). Is it necessarily true that \(\operatorname{gcd}(a, b)=6 ?\) If not, give a specific counterexample, and describe in general all of the possible values of \(\operatorname{gcd}(a, b)\) ? (c) Suppose that \(\left(u_{1}, v_{1}\right)\) and \(\left(u_{2}, v_{2}\right)\) are two solutions in integers to the equation \(a u+b v=1\). Prove that \(a\) divides \(v_{2}-v_{1}\) and that \(b\) divides \(u_{2}-u_{1}\). (d) More generally, let \(g=\operatorname{gcd}(a, b)\) and let \(\left(u_{0}, v_{0}\right)\) be a solution in integers to \(a u+b v=g\). Prove that every other solution has the form \(u=u_{0}+k b / g\) and \(v=v_{0}-k a / g\) for some integer \(k\). (This is the second part of Theorem 1.11.)

Let \(a_{1}, a_{2}, \ldots, a_{k}\) be integers with \(\operatorname{gcd}\left(a_{1}, a_{2}, \ldots, a_{k}\right)=1\), i.e., the largest positive integer dividing all of \(a_{1}, \ldots, a_{k}\) is 1 . Prove that the equation $$ a_{1} u_{1}+a_{2} u_{2}+\cdots+a_{k} u_{k}=1 $$ has a solution in integers \(u_{1}, u_{2}, \ldots, u_{k}\). (Hint. Repeatedly apply the extended Euclidean algorithm, Theorem 1.11. You may find it easier to prove a more general statement in which \(\operatorname{gcd}\left(a_{1}, \ldots, a_{k}\right)\) is allowed to be larger than \(\left.1 .\right)\)

Let \(m \geq 1\) be an integer and suppose that $$ a_{1} \equiv a_{2}(\bmod m) \quad \text { and } \quad b_{1} \equiv b_{2}(\bmod m) . $$ Prove that $$ a_{1} \pm b_{1} \equiv a_{2} \pm b_{2}(\bmod m) \quad \text { and } \quad a_{1} \cdot b_{1} \equiv a_{2} \cdot b_{2}(\bmod m) . $$ (This is Proposition 1.13(a).)

Suppose that \(g^{a} \equiv 1(\bmod m)\) and that \(g^{b} \equiv 1(\bmod m)\). Prove that \(g^{\operatorname{gcd}(a, b)} \equiv 1 \quad(\bmod m) .\)

Prove that if \(a_{1}\) and \(a_{2}\) are units modulo \(m\), then \(a_{1} a_{2}\) is a unit modulo \(m\).

Prove that \(m\) is prime if and only if \(\phi(m)=m-1\), where \(\phi\) is Euler's phi function.

Let \(m\) be an odd integer and let \(a\) be any integer. Prove that \(2 m+a^{2}\) can never be a perfect square. (Hint. If a number is a perfect square, what are its possible values modulo \(4 ?\) )

(a) Find a single value \(x\) that simultaneously solves the two congruences $$ x \equiv 3 \quad(\bmod 7) \quad \text { and } \quad x \equiv 4 \quad(\bmod 9) $$ (Hint. Note that every solution of the first congruence looks like \(x=3+7 y\) for some \(y\). Substitute this into the second congruence and solve for \(y\); then use that to get \(x\).) (b) Find a single value \(x\) that simultaneously solves the two congruences $$ x \equiv 13 \quad(\bmod 71) \quad \text { and } \quad x \equiv 41 \quad(\bmod 97) $$ (c) Find a single value \(x\) that simultaneously solves the three congruences $$ x \equiv 4 \quad(\bmod 7), \quad x \equiv 5 \quad(\bmod 8), \quad \text { and } \quad x \equiv 11 \quad(\bmod 15) $$ (d) Prove that if \(\operatorname{gcd}(m, n)=1\), then the pair of congruences $$ x \equiv a \quad(\bmod m) \quad \text { and } \quad x \equiv b \quad(\bmod n) $$ has a solution for any choice of \(a\) and \(b\). Also give an example to show that the condition \(\operatorname{gcd}(m, n)=1\) is necessary.

Let \(\left\\{p_{1}, p_{2}, \ldots, p_{r}\right\\}\) be a set of prime numbers, and let $$ N=p_{1} p_{2} \cdots p_{r}+1 . $$ Prove that \(N\) is divisible by some prime not in the original set. Use this fact to deduce that there must be infinitely many prime numbers. (This proof of the infinitude of primes appears in Euclid's Elements. Prime numbers have been studied for thousands of years.)

Without using the fact that every integer has a unique factorization into primes, prove that if \(\operatorname{gcd}(a, b)=1\) and if \(a \mid b c\), then \(a \mid c\).

For each of the following primes \(p\) and numbers \(a\), compute \(a^{-1} \bmod p\) in two ways: (i) Use the extended Euclidean algorithm. (ii) Use the fast power algorithm and Fermat's little theorem. (See Example 1.28.) (a) \(p=47\) and \(a=11\). (b) \(p=587\) and \(a=345\). (c) \(p=104801\) and \(a=78467\).

Recall that \(g\) is called a primitive root modulo \(p\) if the powers of \(g\) give all nonzero elements of \(\mathbb{F}_{p}\). (a) For which of the following primes is 2 a primitive root modulo \(p\) ? (i) \(p=7\) (ii) \(p=13\) (iii) \(p=19\) (iv) \(p=23\) (b) For which of the following primes is 3 a primitive root modulo \(p\) ? (i) \(p=5\) (ii) \(p=7\) (iii) \(p=11\) (iv) \(p=17\) (c) Find a primitive root for each of the following primes. (i) \(p=23\) (ii) \(p=29\) (iii) \(p=41\) (iv) \(p=43\) (d) Find all primitive roots modulo 11 . Verify that there are exactly \(\phi(10)\) of them, as asserted in Remark 1.33. (e) Write a computer program to check for primitive roots and use it to find all primitive roots modulo 229 . Verify that there are exactly \(\phi(229)\) of them. (f) Use your program from (e) to find all primes less than 100 for which 2 is a primitive root. (g) Repeat the previous exercise to find all primes less than 100 for which 3 is a primitive root. Ditto to find the primes for which 4 is a primitive root.

Let \(p\) be a prime such that \(q=\frac{1}{2}(p-1)\) is also prime. Suppose that \(g\) is an integer satisfying $$ g \not \equiv \pm 1 \quad(\bmod p) \quad \text { and } \quad g^{q} \not \equiv 1 \quad(\bmod p) \text {. } $$ Prove that \(g\) is a primitive root modulo \(p\).

This exercise begins the study of squares and square roots modulo \(p\). (a) Let \(p\) be an odd prime number and let \(b\) be an integer with \(p \nmid b\). Prove that either \(b\) has two square roots modulo \(p\) or else \(b\) has no square roots modulo \(p\). In other words, prove that the congruence $$ X^{2} \equiv b(\bmod p) $$ has either two solutions or no solutions in \(\mathbb{Z} / p \mathbb{Z}\). (What happens for \(p=2\) ? What happens if \(p \mid b ?)\) (b) For each of the following values of \(p\) and \(b\), find all of the square roots of \(b\) modulo \(p\). (i) \((p, b)=(7,2)\) (ii) \((p, b)=(11,5)\) (iii) \((p, b)=(11,7)\) (iv) \((p, b)=(37,3)\) (c) How many square roots does 29 have modulo \(35 ?\) Why doesn't this contradict the assertion in (a)? (d) Let \(p\) be an odd prime and let \(g\) be a primitive root modulo \(p\). Then any number \(a\) is equal to some power of \(g\) modulo \(p\), say \(a \equiv g^{k}(\bmod p)\). Prove that \(a\) has a square root modulo \(p\) if and only if \(k\) is even.

Compute the value of $$ 2^{(p-1) / 2}(\bmod p) $$ for every prime \(3 \leq p<20\). Make a conjecture as to the possible values of \(2^{(p-1) / 2}(\bmod p)\) when \(p\) is prime and prove that your conjecture is correct.

Write a 2 to 5 page paper on one of the following topics, including both cryptographic information and placing events in their historical context: (a) Cryptography in the Arab world to the 15 th century. (b) European cryptography in the 15 th and early 16 th centuries. (c) Cryptography and cryptanalysis in Elizabethan England. (d) Cryptography and cryptanalysis in the 19 th century. (e) Cryptography and cryptanalysis during World War I. (f) Cryptography and cryptanalysis during World War II. (Most of these topics are too broad for a short term paper, so you should choose a particular aspect on which to concentrate.)

Let \(N\) be a large integer and let \(\mathcal{K}=\mathcal{M}=\mathcal{C}=\mathbb{Z} / N \mathbb{Z}\). For each of the functions $$ e: \mathcal{K} \times \mathcal{M} \longrightarrow \mathcal{C} $$ listed in (a), (b), and (c), answer the following questions: \- Is e an encryption function? \- If \(e\) is an encryption function, what is its associated decryption function \(d\) ? \- If \(e\) is not an encryption function, can you make it into an encryption function by using some smaller, yet reasonably large, set of keys? (a) \(e_{k}(m) \equiv k-m(\bmod N)\). (b) \(e_{k}(m) \equiv k \cdot m(\bmod N)\). (c) \(e_{k}(m) \equiv(k+m)^{2}(\bmod N)\).

(a) Convert the 12 bit binary number 110101100101 into a decimal integer between 0 and \(2^{12}-1\). (b) Convert the decimal integer \(m=37853\) into a binary number. (c) Convert the decimal integer \(m=9487428\) into a binary number. (d) Use exclusive or (XOR) to "add" the bit strings \(11001010 \oplus 10011010 .\) (e) Convert the decimal numbers 8734 and 5177 into binary numbers, combine them using XOR, and convert the result back into a decimal number.

Alice and Bob choose a key space \(\mathcal{K}\) containing \(2^{56}\) keys. Eve builds a specialpurpose computer that can check \(10,000,000,000\) keys per second. (a) How many days does it take Eve to check half of the keys in \(\mathcal{K}\) ? (b) Alice and Bob replace their key space with a larger set containing \(2^{B}\) different keys. How large should Alice and Bob choose B in order to force Eve's computer to spend 100 years checking half the keys? (Use the approximation that there are \(365.25\) days in a year.) For many years the United States government recommended a symmetric cipher called DES that used 56 bit keys. During the 1990s, people built special purpose computers demonstrating that 56 bits provided insufficient security. A new symmetric cipher called AES, with 128 bit keys, was developed to replace DES. See Section \(8.10\) for further information about DES and AES.

Explain why the cipher $$ e_{k}(m)=k \oplus m \quad \text { and } \quad d_{k}(c)=k \oplus c $$ defined by XOR of bit strings is not secure against a chosen plaintext attack. Demonstrate your attack by finding the private key used to encrypt the 16 -bit ciphertext \(c=1001010001010111\) if you know that the corresponding plaintext is \(m=0010010000101100\).