Dmytro Huz

Posted on Jun 26 • Edited on Aug 28

Introduction to Cryptography: Perfect secrecy

#learning #programming #security #computerscience

A signals-hut, France, August 1944

Rain hammered the tin-roof shack perched on a Normandy field. Inside, amber filament bulbs hissed and smoked cigarettes stacked in chipped enamel mugs. Five operators hunched over Remington typewriters, ribbons clacking in counter-rhythm to the wireless set’s static.

Captain Reid slammed a telephone cradle hard enough to rattle the coils of paper tape.

“A linguist, Headquarters?” he had barked moments earlier. “This is a radio-encryption post, not a poetry salon. I need mathematicians, not lyricists. … Roger.”

Click.

Now his blood-shot stare settled on the newcomer, Junior Lieutenant Elena Lenz, twenty-one and rain-soaked from the lorry ride. She clenched the orders that had routed her—mysteriously—from translation duty to “Station V-12, Signals.”

“Lieutenant,” Reid growled, “do you know anything about what we do here?”

Lenz swallowed. “You send messages… by radio, sir.”

“A start.” He thrust a grease-smudged pamphlet into her hands. DEV Community—Introduction to Cryptography: Basic Blocks was stamped across the cver. “Study this while I’m outside. I’ll explain once—and only once. Miss a point and men die. Understood?”

“Yes, sir.”

Reid strode into the storm, leaving ozone, cigarette smoke, and curiosity in his wake.

Basic binary conversion

The scrap lay between Lieutenant Lenz and Captain Reid:

ATTACK AT DAWN

Reid folded his arms. “We have to send that—without tipping off the U-boats. How?”

Lenz glanced at the Morse key. “Radio gives us only short and long—ones and zeros.”

She pulled a pad closer. “So first we turn the text into numbers, then into bits.”

Lenz bit her pencil, murmuring: “Sixty-five for ‘A’, one sixteen for ‘t’…”

Step 1 — ASCII

A t t a c k _ a t _ d a w n

65 116 116 97 99 107 32 97 116 32 100 97 119 110

Lenz hesitated. “Sir, this isn’t the actual radio code. ASCII’s American, and not even invented yet.”

Reid almost grinned. “It isn’t—but it’ll do for showing the principle. Clarity first, perfection later. Get the bones right, then worry about flesh.”

Step 2 — hex shorthand

65 → 0x41, 116 → 0x74, …

Step 3 — eight-bit binary

0x41 → 0100 0001, 0x74 → 0111 0100, …

She wrote each value into the grid, pausing as the logic started to click:

Char	ASCII (dec)	Hex	Binary (8 bits)
A	65	0x41	01000001
t	116	0x74	01110100
t	116	0x74	01110100
a	97	0x61	01100001
c	99	0x63	01100011
k	107	0x6B	01101011
␣ (space)	32	0x20	00100000
a	97	0x61	01100001
t	116	0x74	01110100
␣ (space)	32	0x20	00100000
d	100	0x64	01100100
a	97	0x61	01100001
w	119	0x77	01110111
n	110	0x6E	01101110

Four minutes later the order was a wall of zeros and ones—ready for the keyer.

Reid allowed the hint of a smile. “Quick thinking. But suppose Jerry ("Jerry" was a common nickname used by Allied soldiers, particularly the British, to refer to German soldiers) also converts those dits and dahs back to text?”

“He’d read the plan,” Lenz admitted. “We’d walk into an ambush.”

“Exactly. Which brings us”—he tapped the table—“to perfect secrecy.”

Perfect secrecy and the One-Time Pad

Perfect secrecy means that after intercepting the ciphertext—no matter how clever or well-equipped—the enemy learns absolutely nothing about the original message. Not “almost nothing.” Not “nearly impossible.” Literally: nothing at all.

—from the field notes of Prof. Elena Lenz

“Our goal,” Lenz wrote, “is to encrypt messages so that, without the secret key, even a genius attacker can’t tell if the original was YES or NO, or anything else. After eavesdropping, every possible message remains equally likely. This, and only this, is called perfect secrecy.”

Let’s make that rigorous.

Let:

M be the set of all possible plaintext messages
C the set of all possible ciphertexts

Mathematically :

For every pair of messages m0, m1 and every ciphertext c:

This means that the probability any message encrypts to any ciphertext is always the same.

In words:

No matter which message you pick, the chance it encrypts to any particular ciphertext is always the same.

The enemy sees only noise—never a clue.

How can any cipher achieve this?

Only one system ever has: the One-Time Pad.

Here’s how it works:

The message m is a string of bits, say n bits long.
The key k is also a string of n bits—no shorter, no longer.
The key is generated with true randomness—like flipping a coin for each bit.
Each key is used for only one message, then destroyed.

Encryption is beautifully simple:

E(m, k) = m ⊕ k = c
Just XOR every bit of your message with the corresponding bit of your key.

To decrypt:

D(c, k) = c ⊕ k = m

XOR the ciphertext with the same key, and your message is restored.

The iron laws of perfect secrecy

To achieve this gold standard, all of the following must be true:

Key length matches message length: ∣k∣=∣m∣|k| = |m|
Key is chosen completely at random: every possible key is equally likely
Key is used exactly once: reuse it, and all secrecy is lost

Break any rule and you might as well broadcast your message in the clear.

Lenz raised her hand. “But Captain, who generates these keys? How do we get them here?”

Reid paused his lection and nodded. “Headquarters flips a coin for every bit, then the courier brings us a new pad every night—rain, mud, or bullets. Lose the courier, lose the war.”

He slid the fresh pad across the desk.

“Now, Lieutenant, let’s see you encrypt ‘A’ using the pad—one random byte at a time.”

A gust of wind rattled the windows. Somewhere out in the night, the courier was overdue.

Reid’s gaze lingered on the grey booklet, then flicked to the clock.

His voice, suddenly quieter, carried more weight than before:

“Remember—if you ever run out of key, don’t improvise. Don’t reuse. I don’t care if command is screaming for news. One mistake, and all our secrets belong to the enemy.”

He turned to leave, but paused at the door, silhouetted by lightning.

“And tonight, Lieutenant, I need you to hope that courier isn’t late.”

Lenz stared at the pad in her hands, feeling its importance—and the gathering sense that before the night was over, the rules might be tested.

Secrets in the Rain

Rain hammered the tin roof. The pad of random numbers lay on Lenz’s desk like a talisman. Captain Reid’s voice was hard but low:

“Every letter, one random key byte. No tricks. You know the rules.”

Lenz steadied herself, writing “ATTACK” in block letters. Reid handed her the key slip—six random numbers.

Key (random bytes): 191, 22, 107, 76, 33, 201

She built her table:

Letter	Plain (ASCII)	Plain (Bin)	Key (Dec)	Key (Hex)	Key (Bin)	Cipher (Dec)	Cipher (Hex)	Cipher (Bin)
A	65	01000001	191	BF	10111111	254	FE	11111110
t	116	01110100	22	16	00010110	98	62	01100010
t	116	01110100	107	6B	01101011	31	1F	00011111
a	97	01100001	76	4C	01001100	45	2D	00101101
c	99	01100011	33	21	00100001	66	42	01000010
k	107	01101011	201	C9	11001001	162	A2	10100010

She read each operation aloud:

A: 01000001 ⊕ 10111111 = 11111110 (FE)
t: 01110100 ⊕ 00010110 = 01100010 (62)
t: 01110100 ⊕ 01101011 = 00011111 (1F)
a: 01100001 ⊕ 01001100 = 00101101 (2D)
c: 01100011 ⊕ 00100001 = 01000010 (42)
k: 01101011 ⊕ 11001001 = 10100010 (A2)

She handed the strip to the radio operator:

FE 62 1F 2D 42 A2

And repeated the same process for the rest of message: “at down.”

To anyone listening, it was just a scatter of bits—impossible to decipher.

The Fatal Reply Arrives

Rain pounded the roof, leaking into the corners. The radio spat a new burst of coded Morse. Lenz grabbed her last key strip and decoded the urgent message.

Received ciphertext:

117 69 70 72 102 44 82 95 100 41 72 73 88 71 37 65 79 82 70

Key used:

55 23 7 30 41 12 29 17 33 9 11 8 22 19 5 22 14 27 18

Her table (first five shown for clarity):

Cipher	Cipher (Bin)	Key	Key (Bin)	Plain (ASCII/Bin)	Plain (Char)
117	01110101	55	00110111	66 / 01000010	B
69	01000101	23	00010111	82 / 01010010	R
70	01000110	7	00000111	65 / 01000001	A
72	01001000	30	00011110	86 / 01010110	V
102	01100110	41	00101001	79 / 01001111	O
…	…	…	…	…	…

Decryption:

Lenz, with trembling fingers, called out letter by letter:

“B… R… A… V… O… [pause] O… N… E… [pause] C… A… N… T… [pause] W… A… I… T…”

She looked up, heart racing.

“Bravo One can’t wait. They’re moving.”

Reid went pale. “One of our groups is attacking now—alone. If the others don’t move, Bravo will be slaughtered before dawn.”

He stared at the last used key page. “The other pads are gone. We have only this key left.”

A beat passed. The rain was louder than the men’s voices.

“We have to warn the other groups—now. There’s no time. Lenz, reuse the key. Send: ‘NOW ATTACK’ to all frequencies. Do it.”

Lenz prepares the fatal reply

Lenz stared at the half-used line of the pad, lips tight.

“But Captain, ‘NOW ATTACK’ is much shorter than ‘BRAVO ONE CANT WAIT’. The pad… what do we do with the extra numbers?”

Reid didn’t hesitate.

“We never leave gaps, Lieutenant. If your message is shorter, pad it with dummy letters—X, Q, Z, whatever you like—until it fills the line. Jerry must never learn our real message length from the cipher alone. Every transmission should look the same size, even if you’re just saying ‘YES’ or ‘NO’.”

Lenz nodded, jotting the rule in her logbook. As she prepared the next message, she added extra letters at the end, just as ordered: NOW ATTACK QXZXQ QZ.

Now the ciphertext would be the same length as “BRAVO ONE CANT WAIT.” The enemy would see only a string of numbers—never guessing how much was real, and how much was padding.

Her hands shook as she finished. The room felt colder, and the shadows heavier.

Reid put a hand on her shoulder—“They’ll make it. We did what we had to do.”

But both of them knew:

The pad had been reused. The system’s perfection was now only an illusion. And somewhere, the enemy might be listening…

The Enemy’s Room: Breaking the Code

The German signals bunker hummed with tension. Oberleutnant Krüger and his cryptanalyst, Feldwebel Weber, pored over intercepted Allied radio.

“Same length, same time of night. Probably same key. If so, we can break it.”

Krüger drummed his fingers. “They’re clever enough to pad, but I bet their English gives them away.”

Weber nodded.

“We’ll use the oldest trick: the space attack.”

He explained, as much for the junior code clerk as for Krüger:

“When you XOR two ciphertexts encrypted with the same OTP key, you get the XOR of the two messages:

C₁ ⊕ C₂ = (M₁ ⊕ K) ⊕ (M₂ ⊕ K) = M₁ ⊕ M₂

In English, spaces (ASCII 32) are everywhere—right after short words, or between call signs and orders.”

He pointed to position 4 in the XOR’d values:

Pos	CT1	CT2	CT1⊕CT2	Likely M2	Guess for M1
4	72	62	118	“ “ (32)	118 ⊕ 32 = 86 (“V”)

Weber grinned:

“See? Position 4. If I guess message 2 has a space there, M1[4] = 118 ⊕ 32 = 86, which is ‘V’. ‘BRAVO’—it fits.”

They continued:

Pos	CT1⊕CT2	M2 guess	M1 = (CT1⊕CT2)⊕M2	ASCII
6	116	“ “ (32)	116 ⊕ 32 = 84	T
10	107	“ “ (32)	107 ⊕ 32 = 75	K

Weber continued, excited:

“Now, we drag this ‘space’ guess across the message—right after every short word. Each time, if the XOR gives us a plausible English letter, our guess is probably correct.”

Krüger watched as the messages began to unfold. “It’s like a crossword: once you have a few anchors—spaces, common words—the rest just falls into place.”

Sidebar: How the Space Trick Works

The Space Trick in Breaking OTP Reuse

In English, spaces are predictable—between words, after commands, etc. If you have two ciphertexts made with the same pad, XOR them to get the XOR of their plaintexts.
Guess that a position in one message is a space (ASCII 32). XOR the result at that position with 32. If you get a valid English letter, your guess is likely right.
This is called “crib-dragging”—a method so effective it broke real WWII ciphers when desperate operators reused keys.

Technical Example:

Suppose the two encrypted messages, both 19 characters:

Ciphertext 1: from “BRAVO ONE CANT WAIT”
Ciphertext 2: from “NOW ATTACK QXZXQ QZ”

XOR’d at position 6:

CT1 = 44, CT2 = 88 → 44 ⊕ 88 = 116
Guess M2[6] = “ ” (32): 116 ⊕ 32 = 84 = “T” (in “ATTACK”)

Narrative Payoff

Weber turned to Krüger, eyes bright:

“Once you see where the spaces fall, the rest is just English. They padded their message—but reused the key. Their perfect cipher turned to glass.”

Krüger, smiling coldly:

“Let’s finish the puzzle—and send them a message of our own.”

Forgery—Change ‘NOW ATTACK’ to ‘NOT ATTACK’

Krüger:

“Let’s forge an order to tell them not to attack. No authentication on their system—so if we change the ciphertext and transmit, it’ll look like Reid sent it.”

To change “NOW ATTACK” (N O W A T T A C K) to “NOT ATTACK” (N O T A T T A C K):

Only change needed is letter 3: “W” (87) → “T” (84)
For that position, original key: K = Ciphertext[3] ⊕ “W” = 80 ⊕ 87 = 7
Forged ciphertext: “T” ⊕ 7 = 84 ⊕ 7 = 83

So, original ciphertext (for “NOW ATTACK”):

Cipher	Key	Plain
121	55	N (78)
88	23	O (79)
80	7	W (87)
…	…	…

Forged ciphertext (for “NOT ATTACK”):

[121, 88, 83……]

Krüger’s team transmits the forged message.

Wrap up

Allied radio operators— and Lenz, exhausted, received the message—without a way to check authenticity or integrity. And with reused keys.

She decrypts it as always and read aloud: “NOT ATTACK QXZXQ QZ”.

Reid stared, horrified, as across the line, Bravo pressed forward—alone. The rest of the groups held their ground.

In the darkness, the trap snapped shut.

Weber, at the enemy desk, smiles thinly.

“No integrity. No secrecy. And tonight, no survivors.”

The Price of a Single Mistake

A bitter wind rattled the Normandy hut as Lenz stared at the empty pad, her pencil trembling in her hand. The Morse set fell silent, the storm swallowing any reply.

Captain Reid stood by the window, shoulders hunched, eyes distant.

The perfect cipher—broken by one decision, one night, one desperate reuse.