Solution 1

1. Probability

1.1. (a)

1.1.1. Solution

We want to compute the conditional probability \[ P(D_2 \mid G), \] where \(G\) denotes the event that the observed output is GREEN.

By Bayes’ theorem, \[ P(D_2 \mid G)=\frac{P(G \mid D_2)\,P(D_2)}{P(G)}. \]

First, compute the numerator: \[ P(G \mid D_2)\,P(D_2)=\frac{1}{2}\cdot\frac{1}{3}=\frac{1}{6}. \]

Next, compute the total probability of observing GREEN: \[ P(G)=P(D_1)P(G \mid D_1)+P(D_2)P(G \mid D_2)+P(D_3)P(G \mid D_3). \]

Substituting the given values, \[ P(G)=\frac{1}{2}\cdot\frac{1}{4}+\frac{1}{3}\cdot\frac{1}{2}+\frac{1}{6}\cdot\frac{3}{4}. \]

Now simplify: \[ P(G)=\frac{1}{8}+\frac{1}{6}+\frac{1}{8} =\frac{1}{4}+\frac{1}{6} =\frac{5}{12}. \]

Therefore, \[ P(D_2 \mid G)=\frac{1/6}{5/12} =\frac{1}{6}\cdot\frac{12}{5} =\frac{2}{5}. \]

Hence, the probability that the chosen device was \(D_2\), given that the output is GREEN, is \[ \boxed{\frac{2}{5}}. \]

1.2. (b)

1.2.1. Solution

Let the algorithm BiasedCoin_p output \(1\) with probability \(p\) and \(0\) with probability \(1-p\), where \(0 < p < 1\). Different calls are independent.

The goal is to construct an algorithm that outputs a uniform random bit, i.e., \[ P(\text{output }0)=P(\text{output }1)=\frac12. \]

Algorithm
Use the following procedure:
1. Call BiasedCoin_p twice independently.
2. If the two outputs are:
  - \(0,1\), then output \(0\);
  - \(1,0\), then output \(1\);
  - \(0,0\) or \(1,1\), discard both results and repeat the procedure.
Equivalently, in pseudocode:

\[ \textbf{repeat} \] \[ \qquad x \leftarrow \text{BiasedCoin}_p \] \[ \qquad y \leftarrow \text{BiasedCoin}_p \] \[ \textbf{until } x \neq y \] \[ \textbf{if } (x,y)=(0,1) \textbf{ then output } 0 \] \[ \textbf{else output } 1 \]
Correctness proof

We show that the output is uniformly random.

Since the two invocations are independent, we have \[ P((x,y)=(0,1))=(1-p)p \] and \[ P((x,y)=(1,0))=p(1-p). \]

These two probabilities are equal: \[ (1-p)p=p(1-p). \]

The algorithm only outputs when the pair is either \(01\) or \(10\). Therefore,

\[ P(\text{output }0)=P((x,y)=(0,1)\mid x\neq y) \] and \[ P(\text{output }1)=P((x,y)=(1,0)\mid x\neq y). \]

Now \[ P(x\neq y)=P(01)+P(10)=(1-p)p+p(1-p)=2p(1-p). \]

Hence \[ P(\text{output }0) =\frac{P(01)}{P(x\neq y)} =\frac{p(1-p)}{2p(1-p)} =\frac12, \] and similarly, \[ P(\text{output }1) =\frac{P(10)}{P(x\neq y)} =\frac{p(1-p)}{2p(1-p)} =\frac12. \]

Thus the algorithm outputs a uniform random bit.
Expected number of calls to BiasedCoin_p

A single round consists of two calls to BiasedCoin_p.

A round succeeds exactly when the two outputs are different, i.e., when we get \(01\) or \(10\). Therefore the success probability of one round is \[ P(\text{success})=P(01)+P(10)=2p(1-p). \]

So the number of rounds until success follows a geometric distribution with parameter \[ 2p(1-p). \]

Thus the expected number of rounds is \[ \frac{1}{2p(1-p)}. \]

Since each round uses exactly two calls, the expected number of calls is \[ 2 \cdot \frac{1}{2p(1-p)}=\frac{1}{p(1-p)}. \]

2. Historic Ciphers

2.1. (a) Enigma Elimination

2.1.1. Solution

We use the well-known property of the Enigma machine that no letter can ever be encrypted to itself. In other words, for every position \(i\), the plaintext letter and the ciphertext letter at position \(i\) must be different.

The ciphertext is \[ \texttt{QAXROQ} \] and the candidate plaintexts are:

\(\texttt{BERLIN}\)
\(\texttt{MADRID}\)
\(\texttt{LISBON}\)

We compare each candidate letter by letter with the ciphertext.

Candidate 1: BERLIN

\begin{align*} B &\to Q \\ E &\to A \\ R &\to X \\ L &\to R \\ I &\to O \\ N &\to Q \end{align*}
No letter is mapped to itself, so this plaintext is possible.
Candidate 2: MADRID

\begin{align*} M &\to Q \\ A &\to A \\ D &\to X \\ R &\to R \\ I &\to O \\ D &\to Q \end{align*}
Here, at least one letter is mapped to itself: \[ A \to A \] and also \[ R \to R. \]

This is impossible for Enigma, so MADRID cannot be the plaintext.
Candidate 3: LISBON

\begin{align*} L &\to Q \\ I &\to A \\ S &\to X \\ B &\to R \\ O &\to O \\ N &\to Q \end{align*}
Here we have \[ O \to O, \] which is impossible for Enigma.

So LISBON cannot be the plaintext.
Conclusion

The only possible message is \[ \boxed{\texttt{BERLIN}}. \]

2.2. (b) Affine Cipher

2.2.1. i

The affine cipher is defined by \[ \mathrm{Enc}(x)=ax+b \pmod{26}, \] with the condition \[ \gcd(a,26)=1. \]

We are told that the plaintext \(\texttt{AT}\) encrypts to the ciphertext \(\texttt{EF}\). Using the identification \[ A=0,\; B=1,\; \dots,\; Z=25, \] this gives \[ A=0,\quad T=19,\quad E=4,\quad F=5. \]

Hence we obtain the two congruences \[ a\cdot 0+b \equiv 4 \pmod{26}, \] and \[ a\cdot 19+b \equiv 5 \pmod{26}. \]

From the first congruence, we immediately get \[ b \equiv 4 \pmod{26}. \]

Substituting this into the second congruence yields \[ 19a+4 \equiv 5 \pmod{26}, \] so \[ 19a \equiv 1 \pmod{26}. \]

Thus, we need to compute the inverse of \(19\) modulo \(26\).

Using the extended Euclidean algorithm

We apply the Euclidean algorithm to \(26\) and \(19\):

\[ 26 = 1\cdot 19 + 7, \] \[ 19 = 2\cdot 7 + 5, \] \[ 7 = 1\cdot 5 + 2, \] \[ 5 = 2\cdot 2 + 1, \] \[ 2 = 2\cdot 1 + 0. \]

Therefore, \[ \gcd(19,26)=1. \]

Now we express \(1\) as a linear combination of \(19\) and \(26\).

Starting from \[ 1 = 5 - 2\cdot 2, \] and using \[ 2 = 7 - 1\cdot 5, \] we get \[ 1 = 5 - 2(7-5) = 3\cdot 5 - 2\cdot 7. \]

Next, since \[ 5 = 19 - 2\cdot 7, \] we substitute again: \[ 1 = 3(19-2\cdot 7)-2\cdot 7 = 3\cdot 19 - 8\cdot 7. \]

Finally, using \[ 7 = 26 - 1\cdot 19, \] we obtain \[ 1 = 3\cdot 19 - 8(26-19) = 11\cdot 19 - 8\cdot 26. \]

Thus, \[ 11\cdot 19 - 8\cdot 26 = 1. \]

Reducing this equation modulo \(26\), we get \[ 11\cdot 19 \equiv 1 \pmod{26}. \]

Hence, \[ 19^{-1} \equiv 11 \pmod{26}, \] and therefore \[ a \equiv 11 \pmod{26}. \]

Together with \[ b \equiv 4 \pmod{26}, \] we conclude that the key is \[ \boxed{(a,b)=(11,4)}. \]

2.2.2. iii

The affine cipher is defined by \[ \mathrm{Enc}(x)=ax+b \pmod{26}. \]

For this cipher to be valid, the encryption function must be invertible. That is, every ciphertext must correspond to exactly one plaintext, so that decryption is possible.

The crucial part is the multiplication by \(a\) modulo \(26\). In order to recover \(x\) from \[ y \equiv ax+b \pmod{26}, \] we first subtract \(b\): \[ y-b \equiv ax \pmod{26}. \]

To solve for \(x\), we need to multiply both sides by the inverse of \(a\) modulo \(26\). This requires that there exists some integer \(a^{-1}\) such that \[ aa^{-1}\equiv 1 \pmod{26}. \]

Such an inverse exists if and only if \[ \gcd(a,26)=1. \]

Hence, the condition \[ \gcd(a,26)=1 \] is necessary in order for decryption to work.

What goes wrong if \(\gcd(a,26)\neq 1\)?

If \(\gcd(a,26)\neq 1\), then \(a\) has no inverse modulo \(26\). In that case, the map \[ x \mapsto ax \pmod{26} \] is not one-to-one, so different plaintext letters may be mapped to the same ciphertext letter.

For example, let \(a=2\). Then \[ 2\cdot 0 \equiv 0 \pmod{26} \] and \[ 2\cdot 13 \equiv 26 \equiv 0 \pmod{26}. \]

Thus two different inputs, \(0\) and \(13\), produce the same value modulo \(26\). After adding the same \(b\), they still remain equal modulo \(26\). Therefore the encryption is not injective, and the ciphertext cannot be uniquely decrypted.
Conclusion

The condition \[ \boxed{\gcd(a,26)=1} \] is required because it guarantees that \(a\) has a multiplicative inverse modulo \(26\). Therefore the affine encryption function is invertible, and each ciphertext corresponds to exactly one plaintext.