Exercise 5.5 (Entropies in the affine cipher) Compute H(K|C) and H(K|P,C) for the Affine cipher when used to encrypt a single letter from the English alphabet. Assume that keys and plaintexts are uniformly chosen.

To compute \( H(K|C) \) and \( H(K|P, C) \) for the Affine cipher, we need to review the concepts of conditional entropy in the context of cryptography, particularly for the Affine cipher. The Affine cipher encryption function is given by:

\[
C = (aP + b) \mod 26
\]

where:
- \( P \) is the plaintext (a letter from the alphabet).
- \( C \) is the ciphertext (also a letter from the alphabet).
- \( a \) and \( b \) are the components of the key \( K \).
- \( a \) must be coprime with 26 (the number of letters in the alphabet).

### Entropy Definitions
1. **Entropy of a random variable**: For a random variable \( X \), the entropy \( H(X) \) is given by:
   \[
   H(X) = - \sum_{x} P(X=x) \log_2 P(X=x)
   \]
   where \( P(X=x) \) is the probability that \( X \) takes the value \( x \).

2. **Conditional entropy**: The conditional entropy \( H(X|Y) \) is the entropy of \( X \) given \( Y \) and represents the remaining uncertainty about \( X \) after \( Y \) is known. It is given by:
   \[
   H(X|Y) = - \sum_{x,y} P(X=x, Y=y) \log_2 P(X=x | Y=y)
   \]

### Step-by-Step Computation

#### 1. **Computing \( H(K|C) \) (Conditional Entropy of the Key Given the Ciphertext)**

- Let \( K = (a, b) \) be the key, where \( a \) is chosen from the set of integers coprime with 26, and \( b \) is chosen from the set \( \{0, 1, \dots, 25\} \).
- There are 12 possible values for \( a \) (as only 12 integers between 1 and 25 are coprime with 26) and 26 possible values for \( b \), giving a total of \( 12 \times 26 = 312 \) possible keys.

When a ciphertext \( C \) is known, the key \( K \) is not fully determined, as multiple keys can map different plaintexts to the same ciphertext. This is because the Affine cipher is not a one-to-one function for keys and ciphertexts. Specifically, for each ciphertext, there are multiple possible key combinations that could have produced it. 

Thus, the uncertainty about the key remains even when the ciphertext is known, and this conditional entropy is non-zero.

Given that keys are uniformly distributed, and because there are 312 possible keys and 26 ciphertexts, we can approximate:

\[
H(K|C) = \log_2 12 = 3.585 \text{ bits}
\]

This accounts for the uncertainty about the multiplier \( a \) in the key when the ciphertext is known.

#### 2. **Computing \( H(K|P, C) \) (Conditional Entropy of the Key Given the Plaintext and Ciphertext)**

If both the plaintext \( P \) and ciphertext \( C \) are known, the key \( K \) becomes fully determined. Specifically, given both \( P \) and \( C \), we can solve the Affine cipher equation to uniquely determine \( a \) and \( b \), the components of the key \( K \). Therefore, knowing both the plaintext and the ciphertext eliminates all uncertainty about the key.

Thus:

\[
H(K|P, C) = 0 \text{ bits}
\]

### Summary

- \( H(K|C) = \log_2 12 = 3.585 \text{ bits} \)
- \( H(K|P, C) = 0 \text{ bits} \)

Would you like more details or have any questions?

Here are 5 related questions for further exploration:
1. How does the structure of the Affine cipher compare to other classical ciphers like the Caesar cipher?
2. How would the entropies change if the size of the alphabet was different (e.g., a larger or smaller set)?
3. What is the role of coprimality in ensuring the Affine cipher’s reversibility?
4. How would you compute \( H(K|P) \), the entropy of the key given only the plaintext?
5. How does the uniform distribution assumption affect the entropies in the Affine cipher?

**Tip:** In cryptography, understanding the relationship between plaintext, ciphertext, and the key is essential for assessing the security of the cipher. The more information a cipher leaks, the less secure it is.

Learn how to compute the conditional entropy H(K|C) and H(K|P,C) in the context of the Affine cipher. This problem explores key concepts in cryptography and information theory, involving the uniform distribution of keys and plaintexts. Suitable for students in cryptography and information theory courses.

Math Problem Statement

Solution

Ask a new question for Free

By Image

Math Problem Analysis

Mathematical Concepts

Formulas

Theorems

Suitable Grade Level

Related Recommendation