Merkle-Hellman scheme

The Merkle-Hellman cryptosystem was one of the earliest examples of public key cryptography, and depends on the NP-complete problem “SUBSET SUM” for its security.

Suppose Bob wants to send Alice a message.

Alice generates private key $a_1,a_2,\mathrm{\dots }{a}_n$ which is a superincreasing sequence. She then picks $d\gg {\sum }_{i=1}^n{a}_i$ and $h$ comprime with $d$. Using the euclidean algorithm, she finds $h^{-1}$ such that $h{h}^{-1}\equiv 1\mathit{\hspace{1em}}(\text{mod }d)$.

Alice now generates her public key $b_1,b_2,\mathrm{\dots }{b}_n$ where $b_i=h{a}_i\mathit{\hspace{1em}}(\text{mod }d)$ and sends this to Bob.

Bob breaks up his message into binary strings of length $n$. To send the string $m_1{m}_2\mathrm{\dots }{m}_n$ to Alice, he forms $C={\sum }_{i=1}^n{m}_i{b}_i$ and sends $C$ to Alice.

On receiving $C$, Alice forms $V=h^{-1}C\mathit{\hspace{1em}}(\text{mod }d)$. Now, since $b_i=h{a}_i\mathit{\hspace{1em}}(\text{mod }d)$, we have that $V={\sum }_{i=1}^n{m}_i{a}_i$. Since $a_i$ is a superincreasing sequence, it is easy to recover the $m_i$ if you know $V$ and $a_i$, and it takes $O(n)$ arithmetic operations.

In 1982, a fast algorithm was found for recovering the message knowing only the public key and the cryptogram $C$. It takes advantage of the fact that the public key $b_i$ is not generated in a random way, but comes from a superincreasing sequence.