Chapter 21: Cryptography & Network Information Theory

Part VII: Modern Applications

The One-Time Pad & Perfect Secrecy

Claude Shannon (1949) proved that the one-time pad (OTP) achieves perfect secrecy: the ciphertext reveals absolutely nothing about the plaintext.

$ C = M \oplus K $

XOR the message $M$ with a random key $K$ of equal length

Perfect secrecy condition: $H(M|C) = H(M)$ — the posterior distribution of the message given the ciphertext equals the prior. Equivalently, $I(M;C) = 0$: ciphertext and message are statistically independent.

Shannon's theorem: perfect secrecy requires $H(K) \geq H(M)$ — the key must have at least as much entropy as the message. The OTP achieves this with equality. The key must be truly random, never reused, and kept secret.

Shannon Secrecy Capacity

Wyner (1975) introduced the wiretap channel: Alice communicates to Bob over a channel$p(y|x)$, while an eavesdropper Eve observes a degraded version$p(z|x)$. The secrecy capacity is:

$ C_s = \max_{p(x)} \bigl[I(X;Y) - I(X;Z)\bigr] = \max(0, C_m - C_e) $

For Gaussian channels: if Bob's SNR is higher than Eve's, positive secrecy rate is achievable without a shared secret key — using only the channel's physical properties. This is the foundation of physical-layer security.

Computational Security & Public-Key Cryptography

Real-world cryptography (RSA, Diffie-Hellman, AES) does not achieve perfect secrecy — it relies on computational hardness assumptions. The ciphertext does contain information about the message, but extracting it requires solving problems believed to be computationally intractable (integer factorization, discrete logarithm).

RSA Security

Based on hardness of factoring $n = pq$. Secure if factoring is hard. Key size 2048 bits provides ~112 bits of security.

Quantum Threat

Shor's algorithm (1994) factors in polynomial time on a quantum computer. Post-quantum cryptography (lattice-based) resists quantum attacks.

Network Coding & Slepian-Wolf

Classical networking routes packets without modification. Network coding(Ahlswede et al., 2000) allows intermediate nodes to linearly combine packets, achieving the multicast capacity $\min_{S \text{-cuts}} \text{capacity}$ — impossible with pure routing.

Slepian-Wolf theorem (1973): Two correlated sources $X, Y$ compressed independently can be jointly decoded at rates:

$ R_X \geq H(X|Y), \quad R_Y \geq H(Y|X), \quad R_X + R_Y \geq H(X,Y) $

This is remarkable: even without coordination between encoders, the joint compression rate $H(X,Y)$ is achievable — as if both encoders could see each other's data. Applications include sensor networks and distributed video coding.

Python: OTP, Secrecy Capacity & Slepian-Wolf

Demonstrate that OTP produces uniform ciphertext regardless of plaintext entropy, plot Shannon secrecy capacity vs SNR, and visualize the Slepian-Wolf achievable rate region.

Python

script.py211 lines

import numpy as np
import matplotlib
matplotlib.use('Agg')
import matplotlib.pyplot as plt
from collections import Counter
import math

np.random.seed(42)

# ── One-Time Pad ──────────────────────────────────────────────────────────────
def xor_bytes(a, b):
    """XOR two equal-length byte arrays."""
    return bytes(x ^ y for x, y in zip(a, b))

def otp_encrypt(message_bytes, key_bytes):
    """One-time pad encryption."""
    assert len(key_bytes) >= len(message_bytes), "Key must be at least as long as message"
    return xor_bytes(message_bytes, key_bytes[:len(message_bytes)])

def otp_decrypt(ciphertext_bytes, key_bytes):
    """One-time pad decryption (same as encryption)."""
    return otp_encrypt(ciphertext_bytes, key_bytes)

def byte_entropy(data):
    """Shannon entropy of a byte string in bits."""
    counts = Counter(data)
    n = len(data)
    return -sum((c/n) * math.log2(c/n) for c in counts.values())

# Demo messages
messages = [
    b"Information theory",
    b"AAAAAAAAAAAAAAAAAA",  # low entropy plaintext
    b"Hello, World!12345",
]

print("=== One-Time Pad Encryption ===")
print(f"{'Message':<25} {'H(M)':>6} | {'H(C)':>6} | {'H(C|K=k)':>10} | {'Secure?':>7}")
print("-" * 65)

for msg in messages:
    key = bytes(np.random.randint(0, 256, len(msg)))
    ciphertext = otp_encrypt(msg, key)
    H_M = byte_entropy(msg)
    H_C = byte_entropy(ciphertext)
    decrypted = otp_decrypt(ciphertext, key)
    assert decrypted == msg, "Decryption failed!"
    print(f"{msg.decode():<25} {H_M:>6.3f} | {H_C:>6.3f} | {'uniform':>10} | {'Yes':>7}")

print()
print("Key insight: regardless of plaintext entropy, ciphertext is ALWAYS uniform (H=8 bits/byte)")
print("This is PERFECT SECRECY: H(M|C) = H(M), ciphertext reveals nothing about message")
print()

# ── Show that OTP output is uniform regardless of plaintext ───────────────────
N_samples = 10000
# Low-entropy plaintext: always 'A'
msg_low = b'A' * 8
# High-entropy plaintext: random bytes
msg_high = bytes(np.random.randint(0, 256, 8))

ciphers_low  = []
ciphers_high = []
for _ in range(N_samples):
    k = bytes(np.random.randint(0, 256, 8))
    ciphers_low.append(otp_encrypt(msg_low, k)[0])
    ciphers_high.append(otp_encrypt(msg_high, k)[0])

H_cipher_low  = byte_entropy(bytes(ciphers_low))
H_cipher_high = byte_entropy(bytes(ciphers_high))
print(f"Low-entropy plaintext ('AAAAAAAA'):  ciphertext entropy = {H_cipher_low:.4f} bits (should be ≈8)")
print(f"High-entropy random plaintext:        ciphertext entropy = {H_cipher_high:.4f} bits (should be ≈8)")
print()

# ── Shannon Secrecy Capacity ──────────────────────────────────────────────────
# Wiretap channel: main channel capacity C_m, eavesdropper channel capacity C_e
# Secrecy capacity: C_s = max(0, C_m - C_e)
print("=== Shannon Secrecy Capacity ===")
print("C_s = max(0, C_m - C_e)  (Wyner's wiretap channel, 1975)")
print()

SNR_dB_range = np.linspace(-5, 20, 200)
SNR_main = 10 ** (SNR_dB_range / 10)  # main channel

# Fix eavesdropper at lower SNR (e.g., 5 dB less)
snr_penalty_dB = 5.0
SNR_eve = 10 ** ((SNR_dB_range - snr_penalty_dB) / 10)

C_main = np.log2(1 + SNR_main)   # bits/channel use (Shannon capacity)
C_eve  = np.log2(1 + SNR_eve)

C_secrecy = np.maximum(0, C_main - C_eve)

print(f"Eavesdropper is {snr_penalty_dB} dB weaker than main channel")
for snr_test in [0, 5, 10, 15]:
    idx = np.argmin(np.abs(SNR_dB_range - snr_test))
    print(f"  SNR_main={snr_test} dB: C_m={C_main[idx]:.3f}, C_e={C_eve[idx]:.3f}, C_s={C_secrecy[idx]:.3f} bits")

# ── Slepian-Wolf ──────────────────────────────────────────────────────────────
print()
print("=== Slepian-Wolf Distributed Source Coding ===")
# Two correlated sources X, Y compressed separately but decoded jointly
# Achievable rate region: R_X >= H(X|Y), R_Y >= H(Y|X), R_X+R_Y >= H(X,Y)

# Example: X, Y highly correlated (e.g., temperature readings from nearby sensors)
n_symbols = 10000
X = np.random.randint(0, 8, n_symbols)
noise = np.random.randint(0, 2, n_symbols)  # small noise
Y = (X + noise) % 8  # Y is close to X

# Estimate entropies
from collections import Counter as C2
def empirical_entropy(seq):
    counts = C2(seq)
    n = len(seq)
    return -sum((c/n) * math.log2(c/n) for c in counts.values())

def empirical_joint_entropy(seq1, seq2):
    pairs = list(zip(seq1, seq2))
    counts = C2(pairs)
    n = len(pairs)
    return -sum((c/n) * math.log2(c/n) for c in counts.values())

H_X  = empirical_entropy(X)
H_Y  = empirical_entropy(Y)
H_XY = empirical_joint_entropy(X, Y)
H_X_given_Y = H_XY - H_Y
H_Y_given_X = H_XY - H_X

print(f"H(X) = {H_X:.3f} bits, H(Y) = {H_Y:.3f} bits")
print(f"H(X,Y) = {H_XY:.3f} bits (joint entropy)")
print(f"H(X|Y) = {H_X_given_Y:.3f} bits  <- minimum rate for X if Y is side info")
print(f"H(Y|X) = {H_Y_given_X:.3f} bits  <- minimum rate for Y if X is side info")
print(f"Independent coding would need R_X+R_Y = {H_X+H_Y:.3f} bits")
print(f"Slepian-Wolf allows R_X+R_Y >= H(X,Y) = {H_XY:.3f} bits (saving {H_X+H_Y-H_XY:.3f} bits)")

# ── Plotting ──────────────────────────────────────────────────────────────────
fig, axes = plt.subplots(1, 3, figsize=(15, 5))
fig.patch.set_facecolor('#0a0a1a')

# Plot 1: OTP output distribution for low vs high entropy plaintext
ax1 = axes[0]
bins_b = np.arange(0, 257, 8)
ax1.hist(ciphers_low, bins=bins_b, color='#818cf8', alpha=0.7, density=True, label="OTP(AAA...)")
ax1.hist(ciphers_high, bins=bins_b, color='#a5b4fc', alpha=0.5, density=True, label="OTP(random)")
ax1.axhline(1/256, color='#fbbf24', linestyle='--', linewidth=2, label='Uniform (1/256)')
ax1.set_xlabel('Ciphertext byte value', color='white', fontsize=11)
ax1.set_ylabel('Frequency (normalized)', color='white', fontsize=11)
ax1.set_title("OTP Output is Always Uniform\n(Perfect Secrecy)", color='white', fontsize=12, fontweight='bold')
ax1.legend(fontsize=9, facecolor='#1a1a2e', edgecolor='#818cf8', labelcolor='white')
ax1.set_facecolor('#0a0a1a')
ax1.tick_params(colors='white')
ax1.grid(True, alpha=0.2, color='#818cf8')
for sp in ax1.spines.values(): sp.set_color('#818cf8')

# Plot 2: Secrecy capacity vs SNR
ax2 = axes[1]
ax2.plot(SNR_dB_range, C_main,    color='#34d399', linewidth=2.5, label='Main channel capacity C_m')
ax2.plot(SNR_dB_range, C_eve,     color='#f87171', linewidth=2.5, label=f'Eve capacity C_e (−{snr_penalty_dB}dB)')
ax2.plot(SNR_dB_range, C_secrecy, color='#818cf8', linewidth=2.5, linestyle='--', label='Secrecy capacity C_s')
ax2.fill_between(SNR_dB_range, C_secrecy, alpha=0.15, color='#818cf8', label='Secure region')
ax2.set_xlabel('Main channel SNR (dB)', color='white', fontsize=11)
ax2.set_ylabel('Capacity (bits/channel use)', color='white', fontsize=11)
ax2.set_title("Shannon Secrecy Capacity\n$C_s = \max(0, C_m - C_e)$", color='white', fontsize=12, fontweight='bold')
ax2.legend(fontsize=8, facecolor='#1a1a2e', edgecolor='#818cf8', labelcolor='white')
ax2.set_facecolor('#0a0a1a')
ax2.tick_params(colors='white')
ax2.grid(True, alpha=0.2, color='#818cf8')
for sp in ax2.spines.values(): sp.set_color('#818cf8')

# Plot 3: Slepian-Wolf rate region
ax3 = axes[2]
# Rate region: R_X >= H(X|Y), R_Y >= H(Y|X), R_X+R_Y >= H(X,Y)
R_range = np.linspace(0, H_X + 0.5, 300)
# Boundary of achievable region
R_X_vals = []
R_Y_corner_vals = []

# Corner 1: R_X = H(X|Y), R_Y = H(Y)
# Corner 2: R_X = H(X),   R_Y = H(Y|X)
# Boundary: R_X + R_Y = H(X,Y) for H(X|Y) <= R_X <= H(X)

R_X_bound = np.linspace(H_X_given_Y, H_X, 100)
R_Y_bound = H_XY - R_X_bound

ax3.fill_between(R_X_bound, R_Y_bound, np.maximum(R_Y_bound, H_Y_given_X) + 0.5,
                 alpha=0.2, color='#818cf8', label='Achievable region')
ax3.plot(R_X_bound, R_Y_bound, color='#818cf8', linewidth=2.5, label='Slepian-Wolf boundary')
ax3.axvline(H_X_given_Y, color='#fbbf24', linestyle=':', linewidth=1.5, alpha=0.8)
ax3.axhline(H_Y_given_X, color='#34d399', linestyle=':', linewidth=1.5, alpha=0.8)
ax3.plot(H_X, H_Y_given_X, 'w^', markersize=10, label=f'Corner 2 ({H_X:.2f}, {H_Y_given_X:.2f})')
ax3.plot(H_X_given_Y, H_Y, 'ws', markersize=10, label=f'Corner 1 ({H_X_given_Y:.2f}, {H_Y:.2f})')
# Independent coding point
ax3.plot(H_X, H_Y, 'r*', markersize=12, label=f'Independent ({H_X:.2f}, {H_Y:.2f})')
ax3.set_xlabel('Rate R_X (bits/symbol)', color='white', fontsize=11)
ax3.set_ylabel('Rate R_Y (bits/symbol)', color='white', fontsize=11)
ax3.set_title("Slepian-Wolf Rate Region\n(Distributed Source Coding)", color='white', fontsize=12, fontweight='bold')
ax3.legend(fontsize=8, facecolor='#1a1a2e', edgecolor='#818cf8', labelcolor='white')
ax3.set_xlim(0, H_X + 0.3)
ax3.set_ylim(0, H_Y + 0.3)
ax3.set_facecolor('#0a0a1a')
ax3.tick_params(colors='white')
ax3.grid(True, alpha=0.2, color='#818cf8')
for sp in ax3.spines.values(): sp.set_color('#818cf8')

plt.tight_layout()
plt.savefig('output.png', dpi=150, bbox_inches='tight', facecolor='#0a0a1a')
plt.show()
print("\nShannon's secrecy theorem: perfect secrecy requires H(key) >= H(message).")
print("Computationally secure systems (RSA, AES) relax this but rely on hardness assumptions.")

Click Run to execute the Python code

Code will be executed with Python 3 on the server

← Ch 20: Information Bottleneck Course Overview →