# Unicity Distance of the Merkle-Hellman Knapsack Cryptosystem with Hidden Public Key

The original Merkle-Hellman scheme has undergone many successful attacks, the most famous being Shamir's from 1982. As Shamir noted about his method, "An important property of the proposed attack is that it is directed at the public key rather than at individual ciphertexts." So, has anyone mounted a ciphertext-only attack?

If we were to make the public key private in the original Merkle-Hellman knapsack scheme, what would the unicity distance be of the algorithm?

If we look at a very simple example, even it seems that the unicity distance would be quite long:

2  x 31 mod 105 = 62
3  x 31 mod 105 = 93
6  x 31 mod 105 = 81
13 x 31 mod 105 = 88
27 x 31 mod 105 = 102
52 x 31 mod 105 = 37

Private key = (62, 93, 81, 88, 102, 37)


Plaintext                       Ciphertext

011000 = 93 + 81 =              174

110101 = 62 + 93 + 88 + 37 =    280

101110 = 62 + 81 + 88 + 102 =   333


The ciphertext looks like this:

174,280,333


(Example was taken from Schneier's Applied Cryptography)

Could someone say (1) whether a cipher-text only attack has been successful against this scheme, and (2) explain what is the unicity distance when both keys are private?

• Is the plaintext English? How is it encoded? – kodlu Aug 17 at 1:47
• @kodlu I edited it because of your questions. The underlying plaintext is English letters. One digit equals one letter. So the ciphertext is comprised of three letters. – Patriot Aug 17 at 2:30
• @kodlu Encoded with 8-bit ASCII. Sorry to have forgotten your second question. – Patriot Sep 24 at 10:39