Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 37 ยท Applications

Information Theory in Cryptography

Apply entropy to security: Shannon's perfect secrecy and the one-time pad, key reuse failures, password entropy, min-entropy and unicity distance, with Python demos.

Claude Shannon founded information theory in 1948, but his first major result was about secrecy: his classified 1945 report on cryptography became the 1949 paper "Communication Theory of Secrecy Systems". It defined, in the language of entropy, what it means for a cipher to be unbreakable, and it proved what that costs.

This lesson uses entropy to talk about security: perfect secrecy and the one-time pad, why reusing a pad is fatal, how to measure the strength of passwords and keys, and how much ciphertext an attacker needs (the unicity distance). It is conceptual groundwork, not a guide to building production cryptography; use vetted libraries for real systems.

Perfect secrecy

A cipher turns a plaintext M and a secret key K into a ciphertext C. It has perfect secrecy when the ciphertext tells an eavesdropper nothing about the message:

TEXT
I(M; C) = 0      equivalently      P(M = m | C = c) = P(M = m) for every m and c

Shannon proved a sobering theorem: for perfect secrecy the key must carry at least as much entropy as the message, H(K) >= H(M). The one-time pad achieves it: use a truly random key as long as the message and XOR it with the message, never using the key twice.

Python One-time pad: every plaintext is possible

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Contrast this with a Caesar cipher (shift each letter by a secret amount), which has only 25 non-trivial keys. An attacker tries all shifts and exactly one gives readable English. The ciphertext does contain information about the message, in fact nearly all of it, once the attacker has enough text.

The two-time pad

The one-time pad is only perfect if the key is used once. If two messages are encrypted with the same key, XORing the ciphertexts cancels the key: C1 xor C2 = M1 xor M2. The result depends only on the plaintexts, and natural-language redundancy (a space XOR a letter is recognizable) lets an attacker recover both. This is the reason the Venona project could read parts of Soviet traffic.

Python Why you must never reuse a pad

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two offsets pass the printable-text filter: offset 6 is a false positive, while offset 11 reveals ONEY, a true fragment of the second message. Once part of one plaintext is guessed, the key bytes at that position follow, and they decrypt the same positions of every other message that used the pad.

Measuring key strength with entropy

A secret is only as strong as the attacker's uncertainty about it. If a password is chosen uniformly from N possibilities, its entropy is log2 N bits. For L symbols drawn uniformly from an alphabet of size A, that is L log2 A. Humans rarely choose uniformly, so the entropy of the distribution used matters, not the apparent length.

A better measure of resistance to guessing is min-entropy, H_min = -log2( max_x p(x) ): the attacker's best single guess succeeds with probability 2^(-H_min). Shannon entropy can look comfortable while a few very popular passwords make guessing easy.

Python Shannon entropy versus min-entropy

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If one account in ten uses the same password, an attacker who just tries it first gets 10% of the accounts immediately. This is why system designers think in terms of min-entropy and blocklists of popular passwords, not just average entropy.

Unicity distance

How much ciphertext does an attacker need before only one key makes sense? Shannon's unicity distance is U = H(K) / D, where D is the redundancy of the plaintext language per character: D = log2|A| - H_L, with H_L the entropy rate of the language. For a simple substitution cipher on English, H(K) = log2(26!) โ‰ˆ 88.4 bits. English has an entropy rate of roughly 1.0 to 1.5 bits per letter, giving D of about 3.2 to 3.7 bits, so U is around 25 letters: beyond that, the ciphertext almost surely has a single sensible decryption.

Python Unicity distance for classic ciphers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The unicity distance is a statement about information, not effort: even a ciphertext longer than U may be very hard to break computationally. Modern ciphers like AES have no unicity problem in practice, because they are designed so that only brute force works, and the key space is far beyond reach. The one-time pad is the only cipher whose security does not depend on computational hardness.

True randomness matters. Keys must come from a cryptographically secure generator such as Python's secrets module or the operating system's random source, never from random. A predictable generator reduces the effective entropy of the key to that of its seed.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the condition for perfect secrecy?

    The ciphertext must be statistically independent of the message, which Shannon showed needs H(K) >= H(M).
  2. 2. What happens if a one-time pad key is used twice?

    The key cancels out in C1 xor C2 = M1 xor M2, and language redundancy lets an attacker recover the messages.
  3. 3. An 8-character lowercase random password has about how many bits of entropy?

    8 * log2(26) = 8 * 4.7 = 37.6 bits.
  4. 4. Why use min-entropy to assess guessing resistance?

    Min-entropy is -log2 of the most likely value, so a few popular choices lower it even when Shannon entropy looks high.

Summary

  • Perfect secrecy means I(M; C) = 0 and needs a key with at least as much entropy as the message.
  • The one-time pad is perfect only if the key is random, as long as the message and used once.
  • Entropy measures the attacker's uncertainty: L log2 A for uniform choices.
  • Min-entropy captures the danger of popular choices.
  • Unicity distance H(K)/D estimates how much ciphertext makes the key unique.

Next: Entropy of Text, DNA and Real Data