# How to attack Merkle-Hellman cryptosystem if the first element in the superincreasing series is too small?

In An Introduction to Mathematical Cryptography Jeffrey Hoffstein et al. claim that "It turns out that if $r_1$ is too small, then there are easy attacks, so we must insist that $r_1>2^n$." Here $r_1$ is the first element of the superincreasing series used in the Merkle-Hellman cryptosystem before it is disguised with modular arithmetic and $n$ is the number of elements in the series. Does anyone have information on how these attacks might work or a basic explanation of why too small $r_1$ is unsafe?

• Would you mind add / linking a description of the Merkle-Hellman cryptosystem? At least to me it's unknown and I'm quite sure the same applies to quite a few others here. – SEJPM Jul 11 '17 at 21:09

Let's begin with a short description of the Merkle-Hellman knapsack scheme. The private key is a superincreasing sequence of $n$ elements $b_1, b_2, \dots, b_n$, along with a secret element $W$ and $N$, with $W$ invertible modulo $N$. A superincreasing sequence is a sequence in which every element is greater than the sum of its predecessors: $$b_i > \sum_{j=1}^{i-1} b_j \,.$$
The public key is the vector $a_1, a_2, \dots, a_n$, where $a_i = W b_i \bmod N$. To encrypt a message, the sender splits the message into individual bits $m_i$, and calculates the encrypted message to be $$c = \sum_{i=1}^n m_i a_i \equiv \sum_{i=1}^n m_i b_i W \,.$$
Decryption begins by multiplying $c$ by $W^{-1}$ modulo $N$, cancelling out the contribution of $W$, and then solving the subset sum for the known superincreasing sequence.
We can break the scheme by recovering either $W$ or $N$. The following simple attack is described in Galbraith's book. Suppose $b_1$ is small—much smaller than $2^n$. Then it is likely that $b_2$ is also similarly small, and we have the interesting property: \begin{align*} a_1b_2 &\equiv a_2b_1 \pmod{N} \\ Wb_1b_2 &\equiv W b_2 b_1 \pmod{N}\,, \end{align*} and therefore $a_1b_2 - a_2b_1$ is guaranteed to be a small multiple of $N$. By bruteforcing $b_1$ and $b_2$, we can recover a short list of candidate $N$, which we can then confirm by trying to recover $W = a_1/b_1 \pmod {N}$ and verify if this $W$ applies to the other $a_i, b_i$ as well. This suggests that $b_i$ should be at least $2^{n/2}$ in size.
This is not the only attack when $b_1$ is small. Odlyzko described another two, including the famous Shamir attack. There are also very relevant lattice attacks on Merkle-Hellman, but those are already seem to be described in Hoffstein et al.