Understand Information Theory and Entropy
The Mathematical Foundation of Compression, Communication, and Secrecy
Claude Shannon's 1948 paper "A Mathematical Theory of Communication" defined information precisely, derived the limits of compression and reliable transmission, and — one year later — proved the conditions for perfect secrecy in cryptography. These results share the same mathematical core.
Shannon Entropy
Shannon entropy H(X) = -sum(p_i * log_2(p_i)) measures the average surprise in a random variable X. If an event is certain (p = 1), it contributes zero information: log_2(1) = 0. A fair coin flip has H = 1 bit. A fair six-sided die has H = log_2(6) approx
The Noiseless Coding Theorem
Shannon's first theorem: the minimum average number of bits required to encode one symbol from a source X equals H(X). No compression scheme can do better on average. Huffman coding and arithmetic coding approach this limit. This defines what compression
1bit
4.7bits
Channel Capacity and the Shannon-Hartley Theorem
The maximum reliable information rate over a noisy channel is C = B * log_2(1 + S/N) bits per second, where B is bandwidth and S/N is the signal-to-noise ratio. This is not an engineering limitation — it is a theorem. Any transmission scheme can approach
Perfect Secrecy and the One-Time Pad
Shannon proved in 1949 that a cipher has perfect secrecy if and only if the ciphertext reveals zero information about the plaintext — formally, if the ciphertext and plaintext are statistically independent. Achieving this requires key entropy at least as
Entropy as Password Strength
A password chosen uniformly at random from a set of M equally likely symbols has log_2(M) bits of entropy. Lowercase letters give log_2(26) approximately 4.7 bits per character. Adding digits and symbols increases entropy per character slightly — but addi
Go Deeper: Entropy, Logarithms, and Number Theory
Shannon entropy is defined using logarithms and probability — the same mathematical objects appear throughout number theory and analysis. The number-theoretic results that cryptography directly uses, including Fermat's little theorem and the structure of prime fields, are worth studying as a foundation in their own right.
Understand Number Theory for Cryptography
A focused introduction to the number theory results that cryptography actually uses — Euler's theorem, the Chinese Remainder Theorem, and the primality tests that make RSA key generation fast.