# 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.

Title | Merkle-Hellman scheme |
---|---|

Canonical name | MerkleHellmanScheme |

Date of creation | 2013-03-22 15:12:40 |

Last modified on | 2013-03-22 15:12:40 |

Owner | aoh45 (5079) |

Last modified by | aoh45 (5079) |

Numerical id | 5 |

Author | aoh45 (5079) |

Entry type | Definition |

Classification | msc 94A60 |

Synonym | Merkle-Hellman cryptosystem |