Computational cryptography › Public-key encryption and key exchange
PUBLIC-KEY ENCRYPTIONPrimitiveHistorically broken

Merkle-Hellman knapsack

In plain words

One of the first public-key encryption schemes (1978), faster than RSA, broken in 1982.

The idea: To encrypt, write the message in bits and add up the public numbers where the bits are 1: the sum is the ciphertext. Getting the bits back means solving a knapsack, hard in general. The owner undoes the disguise, gets an easy knapsack, and reads the bits off greedily.

Why it matters: Shows how young public-key cryptography was, and how many early ideas didn't survive.

The details

On the map: ✗ 1978, one of the first public-key schemes

Ralph Merkle and Martin Hellman's 1978 knapsack cryptosystem[1] was one of the first public-key encryption schemes, published right after RSA[2]. It was much faster than RSA, and for a few years it looked like a serious rival.

Shamir's 1982 attack ended it[3], and later knapsack schemes were broken one after another. Chor-Rivest lasted until 1998 (Vaudenay)[4].

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

Nothing on the map depends on it: it is an end point, something people use directly.

References

  1. R. Merkle and M. Hellman. Hiding information and signatures in trapdoor knapsacks. IEEE Transactions on Information Theory, 1978. doi:10.1109/tit.1978.1055927
  2. R. L. Rivest, A. Shamir and L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Defense Technical Information Center, 1978. doi:10.21236/ada606588
  3. Adi Shamir. A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem. Advances in Cryptology, 1983. doi:10.1007/978-1-4757-0602-4_27
  4. Serge Vaudenay. Cryptanalysis of the Chor-Rivest cryptosystem. Advances in Cryptology — CRYPTO '98, 1998. doi:10.1007/bfb0055732