Introduction

Next: Discrete Logarithms and Diffie-Hellman

Exercises

Section 1.1: Simple Substitution Ciphers

1.1. Build a cipher wheel as illustrated in Fig. 1.1, but with an inner wheel that rotates, and use it to complete the following tasks.

(a) Encrypt the following plaintext using a rotation of 11 clockwise.

“A page of history is worth a volume of logic.”

In ROT11: L alrp zq stedzcj td hzces l gzwfxp zq wzrtn

(b) Decrypt the following message, which was encrypted with a rotation of 7 clockwise.

AOLYLHYLUVZLJYLAZILAALYAOHUAOLZLJYLAZAOHALCLYFIVKFNBLZZLZ

Apply ROT(-7): THEREARENOSECRETSBETTERTHANTHESECRETSTHATEVERYBODYGUESSES

(c) Decrypt the following message, which was encrypted by rotating 1 clockwise for the first letter, then 2 clockwise for the second letter, etc.

XJHRFTMZHMZGAHIUETXZJNBWNUTRHEPOMDNBJMAUGORFAOIZOCC

1.2. Decrypt each of the following Caesar encryptions by trying the various possible shifts until you obtain readable text.

(a) LWKLQNWKDWLVKDOOQHYHUVKHDELOOERDUGORYHOBDVDWHH

(b) UXENRBWXCUXENFQRLQJUCNABFQNWRCJUCNAJCRXWORWMB

(c) BGUTBMBGZTFHNLXMKTIPBMAVAXXLXTEPTRLEXTOXKHHFYHKMAXFHNLX

1.3. For this exercise, use the simple substitution table given in Table 1.11.

a	b	c	d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	z
S	C	J	A	X	U	F	B	Q	K	T	P	R	W	E	Z	H	V	L	I	G	Y	D	N	M	O

(a) Encrypt the plaintext message:

The gold is hidden in the garden.

(b) Make a decryption table, that is, a table in which the ciphertext alphabet is in order from A to Z and the plaintext alphabet is mixed up.

(c) Use your decryption table from (b) to decrypt the following message.

IBXLX JVXIZ SLLDE VAQLL DEVAU QLB

1.4. 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 and a list of the most common bigrams that appear in the ciphertext. (If you do not want to recopy the ciphertexts by hand, they can be downloaded or printed from the web site listed in the preface.)

(a) “A Piratical Treasure” (316 letters):

JNRZR BNIGI BJRGZ IZLQR OTDNJ GRIHT USDKR ZZWLG OIBTM NRGJN
IJTZJ LZISJ MRSBL QVRSI ORIQT QDEKJ JNRQW GLOFN IJTZX QLFQL
WBJMJ ITQXT ZJHTB LKUHQL JZKMM LZRNT OBIMIEURLW BLQZJ GKBJT
QDIQSL WJNRO LGRIE ZJGKZ RBGSM JLDGI MNZTQ IHRKM OSOQH IJL
QJBRNJVQAYCIAAWNVWQPVSNSXVJQSWCNODIXGJQAEVOOXCSXXCG
MRIGJLJNRBGKHRTQJRUURBLJWJNRZIUZTULGIENZLUKJRUSTQZLUK
EURFT JNLKJ JNRXRS

Frequency table:

Letter	R	J	I	L	Z	T	N	Q	B	G	K	U	M	O	S	H	W	F	E	D	X	V
Freq	33	30	27	25	24	20	19	16	15	15	13	12	12	10	9	8	7	6	5	5	3	2

Most frequent bigrams: JN (11 times), NR (8 times), TQ (6 times), and LW, RB, RZ, JL (5 times each).

(b) “A Botanical Code” (253 letters):

KZRNK GJKIP ZBOOB XLCRG BXFAU GJBNG RIXRU XAFGJ BXRME MNKNG
BURIX KJRXR SBUER ISATB UIBNN RTBUM NBIGK EBIGR OCUBR GLUBN
JBGRL SJGLN GJBOR ISLRS BAFFO AZBUN RFAUS AGGBI NGLXM IAZRX
RMNVL GBNAS GJRUE KISRM BOAAZ GLOKW FAUKI NGRIC BEBRI NJAWB
OBNNO ATBZJ KOBRC JKIRR NGBUE BRINK XKBAF QBROA LNMRG MALUF
BBG

Frequency table:

Letter	B	R	G	N	A	I	U	K	O	J	L	X	M	F	S	E	Z	C	T	W	P	V	Q
Freq	32	28	22	20	16	16	14	13	12	11	10	10	8	8	7	7	6	5	3	2	1	1	1

Most frequent bigrams: NG and RI (7 times each), BU (6 times), and BR (5 times).

(c) “A Brilliant Detective” (313 letters; all occurrences of the word “the” have been removed from the plaintext):

GS2ES GNUBE SZGUG SNKGX CSUUE QNZOQ EOVJN VKNGX GAHSA WSZZ
BOVUE SIXCQ NQESX NGEUG AHZQA QHNSP CIPQA OIDLV JXGAK CGJCG
SASUB FVQAV CIAWN VWQPV SNSXV JGPCV NODIX GJQAE VOOXC SXXCG
OGOVA XGNVU BAVKX QZVQD LVJXQ EXCQO VKCQG AMVAX VWXCG OOBOX
VZCSO SPPSN VAXUB DVVAX QJQAJ VSUXC SXXCV OVJCS NSJXV NOJQA
MVBSZ VOOSH VSAWX QHGMV GWVSX CSXXC VBSNV ZVNVN SAWQZ ORVXJ
CVOQE JCGUW NVA

Frequency table:

Letter	V	S	X	G	A	O	Q	C	N	J	U	Z	E	W	B	P	I	H	K	D	M	L	R	F
Freq	39	29	22	29	21	20	20	19	13	10	11	10	8	6	5	5	5	4	3	2	1	1	1	1

Most frequent bigrams: XC (10 times), NV (7 times), and CS, DV, QA, SX (6 times each).

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

---

Section 1.2: Divisibility and Greatest Common Divisors

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

1.7. Use a calculator and the method described in Remark 1.9 to compute the following quotients and remainders.

(a) 34787 divided by 353.

(b) 238792 divided by 7843.

(c) 9829387493 divided by 873485.

(d) 1498387487 divided by 76348.

1.8. Use a calculator and the method described in Remark 1.9 to compute the following remainders, without bothering to compute the associated quotients.

(a) The remainder of 78745 divided by 127.

(b) The remainder of 2837647 divided by 4387.

(c) The remainder of 8739287463 divided by 18754.

(d) The remainder of 4536782793 divided by 9784537.

1.9. Use the Euclidean algorithm to compute the following greatest common divisors.

(a) $\gcd (291,252)$.

(b) $\gcd (16261,85652)$.

(c) $\gcd (139024789,93278890)$.

(d) $\gcd (16534528044,8332745927)$.

1.10. For each of the $\gcd (a,b)$ values in Exercise 1.9, use the extended Euclidean algorithm (Theorem 1.11) to find integers $u$ and $v$ such that $au+bv=\gcd (a,b)$.

1.11. Let $a$ and $b$ be positive integers.

(a) Suppose that there are integers $u$ and $v$ satisfying $au+bv=1$. Prove that $\gcd (a,b)=1$.

(b) Suppose that there are integers $u$ and $v$ satisfying $au+bv=6$. Is it necessarily true that $\gcd (a,b)=6$? If not, give a specific counterexample, and describe in general all of the possible values of $\gcd (a,b)$.

(c) Suppose that $(u_1,v_1)$ and $(u_2,v_2)$ are two solutions in integers to the equation $au+bv=1$. Prove that $a$ divides $v_2-v_1$ and that $b$ divides $u_2-u_1$.

(d) More generally, let $g=\gcd (a,b)$ and let $(u_0,v_0)$ be a solution in integers to $au+bv=g$. Prove that every other solution has the form $u=u_0+kb/g$ and $v=v_0-ka/g$ for some integer $k$. (This is the second part of Theorem 1.11.)

1.12. The method for solving $au+bv=\gcd (a,b)$ described in Sect. 1.2 is somewhat inefficient. This exercise describes a method to compute $u$ and $v$ that is well suited for computer implementation. In particular, it uses very little storage.

(a) Show that the following algorithm computes the greatest common divisor $g$ of the positive integers $a$ and $b$, together with a solution $(u,v)$ in integers to the equation $au+bv=\gcd (a,b)$.

1. Set u = 1, g = a, x = 0, and y = b
2. If y = 0, set v = (g - au)/b and return the values (g, u, v)
3. Divide g by y with remainder, g = qy + t, with 0 ≤ t < y
4. Set s = u - qx
5. Set u = x and g = y
6. Set x = s and y = t
7. Go To Step (2)

(b) Implement the above algorithm on a computer using the computer language of your choice.

(c) Use your program to compute $g=\gcd (a,b)$ and integer solutions to the equation $au+bv=g$ for the following pairs $(a,b)$:

• (i) $(527,1258)$
• (ii) $(228,1056)$
• (iii) $(163961,167181)$
• (iv) $(3892394,239847)$

(d) What happens to your program if $b=0$? Fix the program so that it deals with this case correctly.

(e) It is often useful to have a solution with $u>0$. Modify your program so that it returns a solution with $u>0$ and $u$ as small as possible. [Hint. If $(u,v)$ is a solution, then so is $(u+b/g,v-a/g)$.] Redo (c) using your modified program.

1.13. Let $a_1,a_2,\dots ,a_k$ be integers with $\gcd (a_1,a_2,\dots ,a_k)=1$, i.e., the largest positive integer dividing all of $a_1,\dots ,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,\dots ,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 $\gcd (a_1,\dots ,a_k)$ is allowed to be larger than 1.)

1.14. Let $a$ and $b$ be integers with $b>0$. We’ve been using the “obvious fact” that $a$ divided by $b$ has a unique quotient and remainder. In this exercise you will give a proof.

(a) Prove that the set $\{a-bq:q\in \mathbb{Z}\}$ contains at least one non-negative integer.

(b) Let $r$ be the smallest non-negative integer in the set described in (a). Prove that $0\le r<b$.

(c) Prove that there are integers $q$ and $r$ satisfying $a=bq+r$ and $0\le r<b$.

(d) Suppose that $a=b{q}_1+r_1=b{q}_2+r_2$ with $0\le r_1<b$ and $0\le r_2<b$. Prove that $q_1=q_2$ and $r_1=r_2$.

---

Section 1.3: Modular Arithmetic

1.15. Let $m\ge 1$ be an integer and suppose that

$a_1\equiv a_2(\mathrm{mod}m)\text{and}{b}_1\equiv b_2(\mathrm{mod}m).$

Prove that

$a_1\pm b_1\equiv a_2\pm b_2(\mathrm{mod}m)\text{and}{a}_1\cdot b_1\equiv a_2\cdot b_2(\mathrm{mod}m).$

(This is Proposition 1.13(a).)

1.16. Write out the following tables for $\mathbb{Z}/m\mathbb{Z}$ and $(\mathbb{Z}/m\mathbb{Z}{)}^{\ast }$, as we did in Figs. 1.4 and 1.5.

(a) Make addition and multiplication tables for $\mathbb{Z}/3\mathbb{Z}$.

(b) Make addition and multiplication tables for $\mathbb{Z}/6\mathbb{Z}$.

(c) Make a multiplication table for the unit group $(\mathbb{Z}/9\mathbb{Z}{)}^{\ast }$.

(d) Make a multiplication table for the unit group $(\mathbb{Z}/16\mathbb{Z}{)}^{\ast }$.

1.17. Do the following modular computations. In each case, fill in the box with an integer between $0$ and $m-1$, where $m$ is the modulus.

(a) $347+513\equiv \square (\mathrm{mod}763)$

(b) $3274+1238+7231+6437\equiv \square (\mathrm{mod}9254)$

(c) $153\cdot 287\equiv \square (\mathrm{mod}353)$

(d) $357\cdot 862\cdot 193\equiv \square (\mathrm{mod}943)$

(e) $5327\cdot 6135\cdot 7139\cdot 2187\cdot 5219\cdot 1873\equiv \square (\mathrm{mod}8157)$

(Hint. After each multiplication, reduce modulo 8157 before doing the next multiplication.)

(f) $137^2\equiv \square (\mathrm{mod}327)$

(g) $373^6\equiv \square (\mathrm{mod}581)$

(h) $23^3\cdot 19^5\cdot 11^4\equiv \square (\mathrm{mod}97)$

1.18. Find all values of $x$ between $0$ and $m-1$ that are solutions of the following congruences. (Hint. If you can’t figure out a clever way to find the solution(s), you can just substitute each value $x=1,x=2,\dots ,x=m-1$ and see which ones work.)

(a) $x+17\equiv 23(\mathrm{mod}37)$

(b) $x+42\equiv 19(\mathrm{mod}51)$

(c) $x^2\equiv 3(\mathrm{mod}11)$

(d) $x^2\equiv 2(\mathrm{mod}13)$

(e) $x^2\equiv 1(\mathrm{mod}8)$

(f) $x^3-x^2+2x-2\equiv 0(\mathrm{mod}11)$

(g) $x\equiv 1(\mathrm{mod}5)$ and also $x\equiv 2(\mathrm{mod}7)$. (Find all solutions modulo 35, that is, find the solutions satisfying $0\le x\le 34$.)

1.19. Suppose that $g^a\equiv 1(\mathrm{mod}m)$ and that $g^b\equiv 1(\mathrm{mod}m)$. Prove that

$g^{\gcd (a,b)}\equiv 1(\mathrm{mod}m).$

1.20. Prove that if $a_1$ and $a_2$ are units modulo $m$, then $a_1{a}_2$ is a unit modulo $m$.

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

1.22. Let $m\in \mathbb{Z}$.

(a) Suppose that $m$ is odd. What integer between $1$ and $m-1$ equals $2^{-1}\mathrm{mod}m$?

(b) More generally, suppose that $m\equiv 1(\mathrm{mod}b)$. What integer between $1$ and $m-1$ is equal to $b^{-1}\mathrm{mod}m$?

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

1.24.

(a) Find a single value $x$ that simultaneously solves the two congruences

$x\equiv 3(\mathrm{mod}7)\text{and}x\equiv 4(\mathrm{mod}9).$

(Hint. Note that every solution of the first congruence looks like $x=3+7y$ 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(\mathrm{mod}71)\text{and}x\equiv 41(\mathrm{mod}97).$

(c) Find a single value $x$ that simultaneously solves the three congruences

$x\equiv 4(\mathrm{mod}7),x\equiv 5(\mathrm{mod}8),\text{and}x\equiv 11(\mathrm{mod}15).$

(d) Prove that if $\gcd (m,n)=1$, then the pair of congruences

$x\equiv a(\mathrm{mod}m)\text{and}x\equiv b(\mathrm{mod}n)$

has a solution for any choice of $a$ and $b$. Also give an example to show that the condition $\gcd (m,n)=1$ is necessary.

1.25. Let $N$, $g$, and $A$ be positive integers (note that $N$ need not be prime). Prove that the following algorithm, which is a low-storage variant of the square-and-multiply algorithm described in Sect. 1.3.2, returns the value $g^A(\mathrm{mod}N)$. (In Step 4 we use the notation $\lfloor x\rfloor$ to denote the greatest integer function, i.e., round $x$ down to the nearest integer.)

Input. Positive integers $N$, $g$, and $A$.

1. Set $a=g$ and $b=1$.
2. Loop while $A>0$.
3.  If $A\equiv 1(\mathrm{mod}2)$, set $b=b\cdot a(\mathrm{mod}N)$.
4.  Set $a=a^2(\mathrm{mod}N)$ and $A=\lfloor A/2\rfloor$.
5.  If $A>0$, continue with loop at Step 2.
6. Return the number $b$, which equals $g^A(\mathrm{mod}N)$.

1.26. Use the square-and-multiply algorithm described in Sect. 1.3.2, or the more efficient version in Exercise 1.25, to compute the following powers.

(a) $17^{183}(\mathrm{mod}256)$

(b) $2^{477}(\mathrm{mod}1000)$

(c) $11^{507}(\mathrm{mod}1237)$

1.27. Consider the congruence $ax\equiv c(\mathrm{mod}m)$.

(a) Prove that there is a solution if and only if $\gcd (a,m)$ divides $c$.

(b) If there is a solution, prove that there are exactly $\gcd (a,m)$ distinct solutions modulo $m$.

(Hint. Use the extended Euclidean algorithm (Theorem 1.11).)

---

Section 1.4: Prime Numbers, Unique Factorization, and Finite Fields

1.28. Let $\{p_1,p_2,\dots ,p_r\}$ 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.)

1.29. Without using the fact that every integer has a unique factorization into primes, prove that if $\gcd (a,b)=1$ and $a\mid bc$, then $a\mid c$. (Hint. Use the fact that it is possible to find a solution to $au+bv=1$.)

1.30. Compute the following ${\text{ord}}_p$ values:

(a) ${\text{ord}}_2(2816)$

(b) ${\text{ord}}_7(2222574487)$

(c) ${\text{ord}}_p(46375)$ for each $p=3,5,7,$ and $11$

1.31. Let $p$ be a prime number. Prove that ${\text{ord}}_p$ has the following properties.

(a) ${\text{ord}}_p(ab)={\text{ord}}_p(a)+{\text{ord}}_p(b)$. (Thus ${\text{ord}}_p$ resembles the logarithm function, since it converts multiplication into addition!)

(b) ${\text{ord}}_p(a+b)\ge \min \{{\text{ord}}_p(a),{\text{ord}}_p(b)\}$.

(c) If ${\text{ord}}_p(a)\ne {\text{ord}}_p(b)$, then ${\text{ord}}_p(a+b)=\min \{{\text{ord}}_p(a),{\text{ord}}_p(b)\}$.

A function satisfying properties (a) and (b) is called a valuation.

---

Section 1.5: Powers and Primitive Roots in Finite Fields

1.32. For each of the following primes $p$ and numbers $a$, compute $a^{-1}\mathrm{mod}p$ in two ways: (i) Use the extended Euclidean algorithm. (ii) Use the fast power algorithm and Fermat’s little theorem. (See Example 1.27.)

(a) $p=47$ and $a=11$.

(b) $p=587$ and $a=345$.

(c) $p=104801$ and $a=78467$.

1.33. Let $p$ be a prime and let $q$ be a prime that divides $p-1$.

(a) Let $a\in {\mathbb{F}}_p^{\ast }$ and let $b=a^{(p-1)/q}$. Prove that either $b=1$ or else $b$ has order $q$. (Recall that the order of $b$ is the smallest $k\ge 1$ such that $b^k=1$ in ${\mathbb{F}}_p^{\ast }$. Hint. Use Proposition 1.29.)

(b) Suppose that we want to find an element of ${\mathbb{F}}_p^{\ast }$ of order $q$. Using (a), we can randomly choose a value of $a\in {\mathbb{F}}_p^{\ast }$ and check whether $b=a^{(p-1)/q}$ satisfies $b\ne 1$. How likely are we to succeed? In other words, compute the value of the ratio

$\frac{\#\{a\in {\mathbb{F}}_p^{\ast }:a^{(p-1)/q}\ne 1\}}{\#{\mathbb{F}}_p^{\ast }}.$

(Hint. Use Theorem 1.30.)

1.34. 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 $\varphi (10)$ of them, as asserted in Remark 1.32.

(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 $\varphi (228)$ 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.

1.35. 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 0(\mathrm{mod}p)\text{and}g\not\equiv \pm 1(\mathrm{mod}p)\text{and}{g}^q\not\equiv 1(\mathrm{mod}p).$

Prove that $g$ is a primitive root modulo $p$.

1.36. 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(\mathrm{mod}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(\mathrm{mod}p)$. Prove that $a$ has a square root modulo $p$ if and only if $k$ is even.

1.37. Let $p\ge 3$ be a prime and suppose that the congruence $X^2\equiv b(\mathrm{mod}p)$ has a solution.

(a) Prove that for every exponent $e\ge 1$ the congruence

X^2 \equiv b \pmod{p^e} \tag{1.14}

has a solution. (Hint. Use induction on $e$. Build a solution modulo $p^{e+1}$ by suitably modifying a solution modulo $p^e$.)

(b) Let $X=\alpha$ be a solution to $X^2\equiv b(\mathrm{mod}p)$. Prove that in (a), we can find a solution $X=\beta$ to $X^2\equiv b(\mathrm{mod}{p}^e)$ that also satisfies $\beta \equiv \alpha (\mathrm{mod}p)$.

(c) Let $\beta$ and ${\beta }^{\prime }$ be two solutions as in (b). Prove that $\beta \equiv {\beta }^{\prime }(\mathrm{mod}{p}^e)$.

(d) Use Exercise 1.36 to deduce that the congruence (1.14) has either two solutions or no solutions modulo $p^e$.

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

---

Section 1.6: Cryptography by Hand

1.39. Write a 2–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 fifteenth century.

(b) European cryptography in the fifteenth and early sixteenth centuries.

(c) Cryptography and cryptanalysis in Elizabethan England.

(d) Cryptography and cryptanalysis in the nineteenth 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.)

1.40. A homophonic cipher is a substitution cipher in which there may be more than one ciphertext symbol for each plaintext letter. Here is an example of a homophonic cipher, where the more common letters have several possible replacements (see Table in textbook for full cipher alphabet).

Decrypt the following message: $\text{( \% }\Delta \text{ ♣ }\Rightarrow \text{ ‡ \# 4 }\infty \text{ : }◊\text{ 6 }\nearrow \odot \text{ [ }\aleph \text{ 8 \% 2 [ 7 }\Downarrow \text{ ♣ }\searrow ♡\text{ 5 }\odot ▽$

1.41. A transposition cipher is a cipher in which the letters of the plaintext remain the same, but their order is rearranged. Here is a simple example in which the message is encrypted in blocks of 25 letters at a time. Take the given 25 letters and arrange them in a 5-by-5 block by writing the message horizontally on the lines. For example, the first 25 letters of the message

Now is the time for all good men to come to the aid…

is written as

$\begin{array}{ccccc}N& O& W& I& S\\ T& H& E& T& I\\ M& E& F& O& R\\ A& L& L& G& O\\ O& D& M& E& N\end{array}$

Now the ciphertext is formed by reading the letters down the columns, which gives the ciphertext NTMAO OHELD WEFLM ITOGE SIRON.

(a) Use this transposition cipher to encrypt the first 25 letters of the message:

Four score and seven years ago our fathers…

(b) The following message was encrypted using this transposition cipher. Decrypt it.

WNOOA HTUFN EHRHE NESUV ICEME

(c) There are many variations on this type of cipher. We can form the letters into a rectangle instead of a square, and we can use various patterns to place the letters into the rectangle and to read them back out. Try to decrypt the following ciphertext, in which the letters were placed horizontally into a rectangle of some size and then read off vertically by columns.

WHNCE STRHT TEOOH ALBAT DETET SADHE
LEELL QSFMU EEEAT VNLRI ATUDR HTEEA

(For convenience, we’ve written the ciphertext in 5-letter blocks, but that doesn’t necessarily mean that the rectangle has a side of length 5.)

---

Section 1.7: Symmetric Ciphers and Asymmetric Ciphers

1.42. Encode the following phrase (including capitalization, spacing and punctuation) into a string of bits using the ASCII encoding scheme given in Table 1.10.

Bad day, Dad.

1.43. Consider the affine cipher with key $k=(k_1,k_2)$ whose encryption and decryption functions are given by

$e_k(m)\equiv k_1\cdot m+k_2(\mathrm{mod}p),d_k(c)\equiv k_1^{\prime }\cdot (c-k_2)(\mathrm{mod}p),$

where $k_1^{\prime }$ is the inverse of $k_1$ modulo $p$.

(a) Let $p=541$ and let the key be $k=(34,71)$. Encrypt the message $m=204$. Decrypt the ciphertext $c=431$.

(b) Assuming that $p$ is public knowledge, explain why the affine cipher is vulnerable to a known plaintext attack. (See Property 4 on page 38.) How many plaintext/ciphertext pairs are likely to be needed in order to recover the private key?

(c) Alice and Bob decide to use the prime $p=601$ for their affine cipher. The value of $p$ is public knowledge, and Eve intercepts the ciphertexts $c_1=324$ and $c_2=381$ and also manages to find out that the corresponding plaintexts are $m_1=387$ and $m_2=491$. Determine the private key and then use it to encrypt the message $m_3=173$.

(d) Suppose now that $p$ is not public knowledge. Is the affine cipher still vulnerable to a known plaintext attack? If so, how many plaintext/ciphertext pairs are likely to be needed in order to recover the private key?

1.44. Consider the Hill cipher defined by (1.11),

$e_k(m)\equiv k_1\cdot m+k_2(\mathrm{mod}p)\text{and}{d}_k(c)\equiv k_1^{-1}\cdot (c-k_2)(\mathrm{mod}p),$

where $m$, $c$, and $k_2$ are column vectors of dimension $n$, and $k_1$ is an $n$-by-$n$ matrix.

(a) We use the vector Hill cipher with $p=7$ and the key

$k_1=\left(\begin{array}{cc}1& 3\\ 2& 2\end{array}\right)\text{and}{k}_2=\left(\begin{array}{c}5\\ 4\end{array}\right).$

• (i) Encrypt the message $m=\left(\begin{array}{c}7\\ 3\end{array}\right)$.
• (ii) What is the matrix $k_1^{-1}$ used for decryption?
• (iii) Decrypt the message $c=\left(\begin{array}{c}5\\ 3\end{array}\right)$.

(b) Explain why the Hill cipher is vulnerable to a known plaintext attack.

(c) The following plaintext/ciphertext pairs were generated using a Hill cipher with the prime $p=11$. Find the keys $k_1$ and $k_2$.

$m_1=\left(\begin{array}{c}5\\ 4\end{array}\right),c_1=\left(\begin{array}{c}8\\ 1\end{array}\right),m_2=\left(\begin{array}{c}0\\ 10\end{array}\right),c_2=\left(\begin{array}{c}8\\ 5\end{array}\right),m_3=\left(\begin{array}{c}8\\ 1\end{array}\right),c_3=\left(\begin{array}{c}7\\ 8\end{array}\right).$

(d) Explain how any simple substitution cipher of the alphabet can be thought of as a special case of a Hill cipher.

1.45. 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}\to \mathcal{C}$ listed in (a)–(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(\mathrm{mod}N)$

(b) $e_k(m)\equiv k\cdot m(\mathrm{mod}N)$

(c) $e_k(m)\equiv (k+m{)}^2(\mathrm{mod}N)$

1.46.

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

1.47. Alice and Bob choose a key space $\mathcal{K}$ containing $2^{56}$ keys. Eve builds a special-purpose 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.)

1.48. Explain why the cipher

$e_k(m)=k\oplus m\text{and}{d}_k(c)=k\oplus c$

defined by XOR of bit strings is not secure against a known 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=0010010001101100.$

1.49. Alice and Bob create a symmetric cipher as follows. Their private key $k$ is a large integer and their messages (plaintexts) are $d$-digit integers $\mathcal{M}=\{m\in \mathbb{Z}:0\le m<10^d\}$.

To encrypt a message, Alice computes $\sqrt{k}$ to $d$ decimal places, throws away the part to the left of the decimal point, and keeps the remaining $d$ digits. Let $\alpha$ be this $d$-digit number. (For example, if $k=87$ and $d=6$, then $\sqrt{87}=9.32737905\dots$ and $\alpha =327379$.)

Alice encrypts a message $m$ as $c\equiv m+\alpha (\mathrm{mod}10^d)$.

Since Bob knows $k$, he can also find $\alpha$, and then he decrypts $c$ by computing $m\equiv c-\alpha (\mathrm{mod}10^d)$.

(a) Alice and Bob choose the secret key $k=11$ and use it to encrypt 6-digit integers (i.e., $d=6$). Bob wants to send Alice the message $m=328973$. What is the ciphertext that he sends?

(b) Alice and Bob use the secret key $k=23$ and use it to encrypt 8-digit integers. Alice receives the ciphertext $c=78183903$. What is the plaintext $m$?

(c) Show that the number $\alpha$ used for encryption and decryption is given by the formula

$\alpha =\lfloor 10^d\left(\sqrt{k}-\lfloor \sqrt{k}\rfloor \right)\rfloor ,$

where $\lfloor t\rfloor$ denotes the greatest integer that is less than or equal to $t$.

(d) (Challenge Problem) If Eve steals a plaintext/ciphertext pair $(m,c)$, then it is clear that she can recover the number $\alpha$ since $\alpha \equiv c-m(\mathrm{mod}10^d)$. If $10^d$ is large compared to $k$, can she also recover the number $k$? This might be useful, for example, if Alice and Bob use some of the other digits of $\sqrt{k}$ to encrypt subsequent messages.

1.50. Bob and Alice use a cryptosystem in which their private key is a (large) prime $k$ and their plaintexts and ciphertexts are integers. Bob encrypts a message $m$ by computing the product $c=km$. Eve intercepts the following two ciphertexts:

$c_1=12849217045006222,c_2=6485880443666222.$

Use the $\gcd$ method described in Sect. 1.7.4 to find Bob and Alice’s private key.