Encyclopedia > Merkle-Hellman

  Article Content

Merkle-Hellman

Merkle-Hellman (MH) was one of the earliest public key cryptosystems. Although its ideas are elegant, and far simpler than RSA, it has been broken. MH is based on the subset sum problem (a special case of the knapsack problem): given a list of numbers, and a third number which is the sum of the some of those numbers, determine which numbers from the list it is the sum of. In general, this problem is known to be NP-hard; however, there are some 'easy' instances which can be solved efficiently. The Merkle-Hellman is based on transforming an easy instance into a difficult instance, and back again. It was broken by Shamir, not by attacking the knapsack problem, but rather by breaking the conversion from an easy knapsack to a hard one. The algorithm is as follows:

KEY GENERATION - To encrypt n-bit messages, choose a superincreasing sequence

w = (w1, w2, ..., wn)

of n natural numbers (excluding zero). (A superincreasing sequence is a sequence in which every element is greater than the sum of all previous elements.) Pick a random integer q, such that q > wn, and a random integer r coprime to q. Now calculate the sequence

β = (β1, β2, ..., βn)
where βi = rwi (mod q). The public key is β, while the private key is (w, q, r).

ENCRYPTION - To encrypt an n-bit message

α = (α1, α2, ..., αn) ,

where αi is the i-th bit of the message, calculate

<math>c = \sum_{i = 1}^n \alpha_i \beta_i</math>.
The cryptogram then is c.

DECRYPTION - Calculate s = r-1 (mod q), and c' = c*s (mod q). The knapsack problem (wc) can be solved in linear time.

See public key cryptography



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Proclamation of 1763

... lands captured by Britain from France in the French and Indian War. The motivation for the proclamation was a desire to avoid the expense of further wars with Nativ ...