1. Among the shifts of EVIRE, there are two words: arena and river. Therefore, Anthony cannot determine where to meet Caesar.

3. The decrypted message is ’cat’.

5. The ciphertext is QZNHOBXZD. The decryption function is $21x+9$.

7. The encryption function is therefore $11x+14$.

9. The plaintext is happy.

11. Successively encrypting with two affine functions is the same as encrypting with a single affine function. There is therefore no advantage of doing double encryption in this case.

13. Mod 27, there are 486 keys. Mod 29, there are 812 keys.

15.

1. The possible values for $\alpha$ are 1,7,11,13,17,19,23,29.

2. There are many such possible answers, for example $x=1$ and $x=4$ will work. These correspond to the letters ’b’ and ’e’.

19.

2. The key is AB. The original plaintext is BBBBBBABBB.

21. The key is probably AB.

27. EK IO IR NO AN HF YG BZ YB LF GM ZN AG ND OD VC MK

29. AAXFFGDGAFAX

1.

1. 0.

2. $P(M=cat|C=mxp)\ne P(M=cat)$.

3. The conditional probability is 0. Affine ciphers do not have perfect secrecy.

5.

1. 1/2.

2. $m_0=HI\text{,}{m}_1=BE$ is a possibility.

11.

1. Possible.

2. Possible.

3. Impossible.

13. $X$

1. ] The next four terms of the sequence are 1, 0, 0, 1.

3. $c_0=1\text{,}{c}_1=0\text{,}{c}_2=0\text{,}{c}_3=1$.

5. $c_0=2$ and $c_1=1$.

7. $k_{n+2}\equiv k_n$.

9. $c_0=4$ and $c_1=4$.

1. eureka.

3. $\left(\begin{array}{cc}12& 3\\ 11& 2\end{array}\right)$.

5. $\left(\begin{array}{cc}7& 2\\ 13& 5\end{array}\right)$.

7.

1. $\left(\begin{array}{cc}10& 9\\ 13& 23\end{array}\right)$.

2. $\left(\begin{array}{cc}10& 19\\ 13& 19\end{array}\right)$.

9. Use aabaab.

13.

1. Alice’s method is more secure.

2. Compatibility with single encryption.

19. The $j$th and the $(j+1)\text{st blocks}$.

1.

1. Switch left and right halves and use the same procedure as encryption. Then switch the left and right of the final output.

2. After two rounds, the ciphertext alone lets you determine $M_0$ and therefore $M_1\oplus K$, but not $M_1$ or $K$ individually. If you also know the plaintext, you know $M_1$ are therefore can deduce $K$.

3. Three rounds is very insecure.

3. The ciphertext from the second message can be decrypted to yield the password.

5.

1. The keys for each round are all 1s, so using them in reverse order doesn’t change anything.

2. All 0s.

7. Show that when $\bar{P}$ and $\bar{K}$ are used, the input to the S-boxes is the same as when $P$ and $K$ are used.

1.

1. We have $W(4)=W(0)\oplus T(W(0))=T(W(0))$. In the notation in Subsection 8.2.5, $a=b=c=d=0$. The $S\text{-box}$ yields $e=f=g=h=99(\text{base 10})=\text{01100011}(\text{binary})$. The round constant is $r(4)={00000010}^0=00000001$. We have $e\oplus r(4)=01100100$. Therefore,

   $$W(4)=T(W(0))=\left(\begin{array}{c}01100100\\ 01100011\\ 01100011\\ 01100011\end{array}\right)\text{.}$$

3.

1. Since addition in $GF(2^8)$ is the same as $\oplus$, we have $f(x_1)\oplus f(x_2)=\alpha (x_1+x_2)=\alpha (x_3+x_4)=f(x_3)\oplus f(x_4)$.

1. The plaintext is $1415=no$.

3.

1. $d=27$.

2. Imitate the proof that RSA decryption works.

5. The correct plaintext is $9$.

7. Use $d=67$.

9. Solve $de\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p-1)$.

11. Bob computes $b_1$ with $b{b}_1\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}\varphi (n))$ and raises $e$ to the power $b_1$.

13. Divide the decryption by 2.

15. It does not increase security.

17. $e=1$ sends plaintext, and $e=2$ doesn’t satisfy $gcd(e\text{,}(p-1)(q-1))=1$.

21. Compute a gcd.

23. We have $(516107\cdot 187722{)}^2\equiv (2\cdot 7{)}^2(\mathrm{m}\mathrm{o}\mathrm{d}n)$.

25. Combine the first three congruences. Ignore the fourth congruence.

27. Use the Chinese Remainder Theorem to find $x$ with $x\equiv 7(\mathrm{m}\mathrm{o}\mathrm{d}p)$ and $x\equiv -7(\mathrm{m}\mathrm{o}\mathrm{d}q)$.

31. There are integers $x$ and $y$ such that $x{e}_A+y{e}_B=1$.

33. HELLO

41. 12345.

45. Find $d^{\prime }$ with $d^{\prime }e\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}12345)$.

47.

2. 1000000 messages.

1.

1. $L_2(3)=4$.

2. $2^7\equiv 11(\mathrm{m}\mathrm{o}\mathrm{d}13)$.

3.

1. $6^5\equiv 10$.

2. $x$ is odd.

5. $x$ is even.

7. (a), (b) $L_2(24)=72$.

9. $x=122$.

13. Alice sends $10$ to Bob and Bob sends $5$ to Alice. Their shared secret is 6.

15. Eve computes $b_1$ with $b{b}_1\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p-1)$.

1. It is easy to construct collisions: $h(x)=h(x+p-1)$, for example. (However, it is fairly quickly computed (though not fast enough for real use), and it is preimage resistant.)

3.

1. Finding square roots $\text{mod }pq$ is computationally equivalent to factoring.

2. $h(x)\equiv h(n-x)$ for all $x$

5. It satisfies (1), but not (2) and (3).

9. (a) and (b) Let $h$ be either of the hash functions. Given $y$ of length $n$, we have $h(y\parallel 000\cdots )=y$.

11. Collision resistance.

1. ${\displaystyle \frac{165}{288}}\approx .573$

5. $1-e^{-7.3\times {10}^{-47}}\approx 0$.

7. It is very likely that two choose the same prime.

9. The probability is approximately $1-e^{-500}\approx 0$ (or $1-e^{-450}\approx 0$ if you take numbers of exactly 15 digits).

1. Use the congruence defining $s$ to solve for $a$.

3. See Section 13.4.

7.

1. Let $m_1\equiv m{r}_1{r}^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}p-1)$.

9. Imitate the proof for the usual ElGamal signatures.

13. Eve notices that $\beta =r$.

1. Use the Birthday attack. Eve will probably factor some moduli.

3.

1. 0101 and 0110.

5.

1. Enigma does not encrypt a letter to itself, so DOG is impossible.

2. If the first of two long plaintexts is encrypted with Enigma, it is very likely that at least one letter of the second plaintext will match a letter of the ciphertext. More precisely, each individual letter of the second plaintext that doesn’t match the first plaintext has probability around 1/26 of matching, so the probability is $1-(25/26{)}^{90}\approx 0.97$ that there is a match between the second plaintext and the ciphertext. Therefore, Enigma does not have ciphertext indistinguishability.

1. $K_{AB}=g_A(r_B)=21$, $K_{AC}=g_A(r_C)=7$ and $K_{BC}=g_B(r_C)=29$.

3. $a=8$, $b=8$, $c=23$.

1.

1. We have $r\equiv {\alpha }_1(cx+w)+{\alpha }_2\equiv Hx+{\alpha }_{1}w+{\alpha }_2(\mathrm{m}\mathrm{o}\mathrm{d}q)$. Therefore

   $$g^r\equiv g^{w{\alpha }_1}{g}^{{\alpha }_2}{g}^{xH}\equiv g_w^{{\alpha }_1}{g}^{{\alpha }_2}{g}^{xH}\equiv a{h}^H(\mathrm{m}\mathrm{o}\mathrm{d}p)\text{.}$$

2. Since $c_1\equiv w+xc(\mathrm{m}\mathrm{o}\mathrm{d}q)$, we have ${\alpha }_1{c}_1\equiv w{\alpha }_1+xH(\mathrm{m}\mathrm{o}\mathrm{d}q)$. Therefore,

   $$r\equiv {\alpha }_1{c}_1+{\alpha }_2\equiv xH+w{\alpha }_1+{\alpha }_2(\mathrm{m}\mathrm{o}\mathrm{d}q)\text{.}$$

   Multiply by $s$ and raise $I{g}_2$ to these exponents to obtain

   $$(I{g}_2{)}^{r}s\equiv (I{g}_2{)}^{xsH}(I{g}_2{)}^{ws{\alpha }_1}(I{g}_2{)}^{s{\alpha }_2}(\mathrm{m}\mathrm{o}\mathrm{d}p)\text{.}$$

   This may be rewritten as

   $$A^r\equiv z^{H}b(\mathrm{m}\mathrm{o}\mathrm{d}p)\text{.}$$

3. Since $r_1\equiv usd+x_1$ and $r_2\equiv sd+x_2(\mathrm{m}\mathrm{o}\mathrm{d}q)$, we have

   $$g_1^{r_1}{g}_2^{r_2}\equiv (g_1^u{g}_2{)}^{sd}{g}_1^{x_1}{g}_2^{x_2}\equiv (I{g}_2^{sd}{g}_1^{x_1}{g}_2^{x_2}\equiv \equiv A^{d}B(\mathrm{m}\mathrm{o}\mathrm{d}p)\text{.}$$

3.

1. The only place $r_1$ and $r_2$ are used in the verification procedure is in checking that $g_1^{r_1}{g}_2^{r_2}\equiv A^{d}B$.

2. The Spender spends the coin correctly once, using $r_1\text{,}{r}_2$. The Spender then chooses any two random numbers $r_1^{\prime }\text{,}{r}_2^{\prime }$ with $r_1^{\prime }+r_2^{\prime }=r_1+r_2$ and uses the coin with the Vendor, with $r_1^{\prime }\text{,}{r}_2^{\prime }$ in place of $r_1\text{,}{r}_2$. All the verification equations work.

5. $r_2$ and $r_2^{\prime }$ are essentially random numbers (depending on hash values involving the clock), the probability is around $1/q$ that $r_2\equiv r_2^{\prime }(\mathrm{m}\mathrm{o}\mathrm{d}q)$. Since $q$ is large, $1/q$ is small.

7. Fred only needs to keep the hash of the file on his own computer.

1. One possibility is to take $p=7$ and choose the polynomial $s(x)=5+x(\mathrm{m}\mathrm{o}\mathrm{d}7)$ (where 5 is chosen randomly). Then the secret value is $s(0)=5$, and we may choose the shares (1,6), (2,0), (3,1), and (4,2).

3. *=63

5. The polynomial is

The secret is $13(\mathrm{m}\mathrm{o}\mathrm{d}17)$.

7. $M=77\text{,}57\text{,}37\text{,}17$.

9. Take a (10, 30) scheme and give the general 10 shares, the colonels five shares each, and the clerks two each.

11. Start by splitting the launch code into three equal components using a three-party secret splitting scheme.

3.

1. Nelson computes a square root of $y\text{ mod }p$ and $\text{mod }q$, then combines them to obtain a square root of $y\text{ mod }n$.

2. Use the $x^2\equiv y^2$ factorization method.

3. No.

5.

Step 4: Victor randomly chooses $i=1$ or 2 and asks Peggy for $r_i$.

Step 5: Victor checks that $x_i\equiv r_i^e(\mathrm{m}\mathrm{o}\mathrm{d}n)$.

They repeat steps 1 through 5 at least 7 times (since $(1/2{)}^7<.01$).

7.

1. One way: Step 4: Victor chooses $i\ne j$ at random and asks for $r_i$ and $r_j$. Then five repetitions are enough. Another way: Victor asks for only one of the $r_k\text{’s}$. Then twelve repetitions suffice.

2. Choose $r_1\text{,}{r}_2$. Then solve for $r_3$.

1. $H(X_1)=H(X_2)=1$, and $H(X_1\text{,}{X}_2)=2$.

3. $H(X)=2$.

5. $H(Y)\le H(X)$.

7.

1. 2.9710

2. $2.9517$

9.

1. $H(P)=-\left({\displaystyle \frac{1}{3}}{log}_2{\displaystyle \frac{1}{3}}+{\displaystyle \frac{2}{3}}{log}_2{\displaystyle \frac{2}{3}}\right)$.

2. This system matches up with the one-time pad, and hence $H(P|C)=H(P)$.

13.

1. $H(X)={log}_{2}36$.

2. Use Fermat’s Theorem to obtain $H(Y)=0$.

3.

1. $(3\text{,}2)\text{,}(3\text{,}5)\text{,}(5\text{,}2)\text{,}(5\text{,}5)\text{,}(6\text{,}2)\text{,}(6\text{,}5)\text{,}\mathrm{\infty }$.

2. $(3\text{,}5)$.

3. $(5\text{,}2)$.

5.

1. $(2\text{,}2)$.

2. She factors 35.

7. One example: $y^2\equiv x^3+17$.

9.

1. $3Q=(-1\text{,}0)$.

15. $y\equiv \pm 4\text{,}\pm 11(\mathrm{m}\mathrm{o}\mathrm{d}35)$

3. Compute $\tilde{e}(aA\text{,}B)$ and $\tilde{e}(A\text{,}bB)$.

7.

1. Eve knows $r{P}_0\text{,}{P}_1\text{,}k$. She computes

   $$\tilde{e}(r{P}_0\text{,}{P}_1{)}^k=\widetilde{(}k{P}_0\text{,}{P}_1{)}^r=\tilde{e}(H_1(\text{bob}@\text{computer}\text{.}\text{com})\text{,}{P}_1{)}^r=g^r\text{.}$$

   Eve now computes $H_2(g^r)$ and XORs it with $t$ to get $m$.

9. See Claim 2 in Section 9.1.

1. The basis $(0\text{,}1)\text{,}(-2\text{,}0)$ is reduced. The vector $(0\text{,}1)$ is a shortest vector.

1.

1. The original message is 0,1,0,0.

2. The original message is 0,1,0,1.

3.

1. $n=5$ and $k=2$.

2. $$G=\left(\begin{array}{ccccc}1& 1& 0& 1& 0\\ 1& 0& 1& 0& 1\end{array}\right)\text{.}$$

3. $(0\text{,}0\text{,}0\text{,}0\text{,}0)\text{,}(1\text{,}1\text{,}0\text{,}1\text{,}0)\text{,}(1\text{,}0\text{,}1\text{,}0\text{,}1)\text{,}(0\text{,}1\text{,}1\text{,}1\text{,}1)$.

4. $R={\displaystyle \frac{{log}_2(4)}{5}}=0.4$.

5.

2. $d(C)=2$.

13. $1+X+X^2+X^3$ is in $C$ and the other two polynomials are not in $C$.

19. The error is in the 3rd position. The corrected vector is (1,0,0,1,0,1,1).

1.

1. The period is 4.

2. $m=8$.

3. $r=4$.