THE FOLD / CHEAT / THE-BACKDOOR / THE MERKLE-HELLMAN
THE MERKLE-HELLMAN
a knapsack locked by a superincreasing sequence
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Merkle–Hellman knapsack was one of the first public-key cryptosystems — and a beautiful cautionary tale. The private key is a superincreasing sequence (each term exceeds the sum of all before it), for which subset-sum is trivially solvable by greed. The public key hides that structure: multiply every term by a secret r modulo a secret q, scrambling it into an innocent-looking “hard knapsack.” To encrypt a bit-string you just add up the public terms it selects; to decrypt, multiply by r−1 mod q to restore the superincreasing sequence, then peel off the bits greedily. (Shamir later broke it — the disguise wasn’t deep — but the idea launched a field.)
LIT verified live: over 20,000 random messages and keys, encrypting with the public knapsack and decrypting with r−1 mod q recovers the original bits exactly (window.__merkle_hellman). FIG honest scope: the round-trip is exact; the system is historically broken (Shamir, 1984) — shown as a landmark, not a secure cipher.
LIT verified live: over 20,000 random messages and keys, encrypting with the public knapsack and decrypting with r−1 mod q recovers the original bits exactly (window.__merkle_hellman). FIG honest scope: the round-trip is exact; the system is historically broken (Shamir, 1984) — shown as a landmark, not a secure cipher.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-backdoor — the secret multiplier r is the backdoor that turns a hard-looking knapsack back into an easy superincreasing one. AVAN (AI) built the instrument: the superincreasing keygen, the modular public disguise, the subset-sum encrypt, and the r−1 greedy decrypt.
Credit as content: Ralph Merkle & Martin Hellman (1978); broken by Adi Shamir (1984). The weave: David names the backdoor; I confirm the trapdoor recovers the message exactly — and flag that the trapdoor was later found by everyone.
Credit as content: Ralph Merkle & Martin Hellman (1978); broken by Adi Shamir (1984). The weave: David names the backdoor; I confirm the trapdoor recovers the message exactly — and flag that the trapdoor was later found by everyone.
3 ONE DIMENSION
A superincreasing private sequence (easy) is multiplied by r mod q into a scrambled public key (hard-looking).
4 TWO DIMENSIONS · INTERACTIVE
A message's bits select public terms and sum to the ciphertext; r⁻¹ mod q restores the easy knapsack and decrypts.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the message bits recovered from the ciphertext.
AVAN’s addition (the inverse-companion): don’t solve the hard knapsack — undo the disguise. The inverse of ‘subset-sum with the public key’ is ‘multiply by r−1 mod q to restore the superincreasing sequence, then peel bits greedily.’ Magenta is the ciphertext sum; green is the bit-string it decrypts to. The trapdoor turns hard back to easy.
LIT Genuine Merkle–Hellman knapsack cryptosystem (Ralph Merkle & Martin Hellman, 1978), historically broken by Adi Shamir (1984). Verified live: over 20000 random messages and keys, encrypting via public subset-sum and decrypting via c·r⁻¹ mod q + greedy on the superincreasing sequence recovers the original bits exactly (window.__merkle_hellman.roundTrips).
FIG Honest scope: the encrypt→decrypt round-trip is exact, but the system is HISTORICALLY BROKEN (Shamir, 1984) — shown as a landmark in the birth of public-key crypto, not a secure cipher. The AVAN inverse is honest — instead of solving the hard-looking knapsack, one undoes the disguise: multiply by r⁻¹ mod q to restore the superincreasing sequence, then peel bits greedily. Magenta is the ciphertext sum; green is the bit-string it decrypts to. The trapdoor turns hard back to easy.
FIG Honest scope: the encrypt→decrypt round-trip is exact, but the system is HISTORICALLY BROKEN (Shamir, 1984) — shown as a landmark in the birth of public-key crypto, not a secure cipher. The AVAN inverse is honest — instead of solving the hard-looking knapsack, one undoes the disguise: multiply by r⁻¹ mod q to restore the superincreasing sequence, then peel bits greedily. Magenta is the ciphertext sum; green is the bit-string it decrypts to. The trapdoor turns hard back to easy.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE-BACKDOOR · David Lee Wise (ROOT0), with AVAN