如果超增級數中的第一個元素太小，如何攻擊 Merkle-Hellman 密碼系統？
在*《數學密碼學導論》中，*杰弗裡·霍夫斯坦等人。聲稱“事實證明，如果 $ r_1 $ 太小的話容易被攻擊，所以一定要堅持 $ r_1>2^n $ 。“ 這裡 $ r_1 $ 是 Merkle-Hellman 密碼系統中使用的超增級數的第一個元素，然後用模運算和 $ n $ 是系列中的元素數。有沒有人有關於這些攻擊如何工作的資訊或為什麼太小的基本解釋 $ r_1 $ 不安全？
讓我們從Merkle-Hellman背包方案的簡短描述開始。私鑰是一個超增序列 $ n $ 元素 $ b_1, b_2, \dots, b_n $ ，以及一個秘密元素 $ W $ 和 $ N $ ， 和 $ W $ 可逆模 $ N $ . 超增序列是一個序列，其中每個元素都大於其前任元素之和：
$$ b_i > \sum_{j=1}^{i-1} b_j ,. $$ 公鑰是向量 $ a_1, a_2, \dots, a_n $ ， 在哪裡 $ a_i = W b_i \bmod N $ . 為了加密消息，發送者將消息拆分為單獨的位 $ m_i $ , 併計算加密消息為
$$ c = \sum_{i=1}^n m_i a_i \equiv \sum_{i=1}^n m_i b_i W ,. $$ 解密從乘法開始 $ c $ 經過 $ W^{-1} $ 模組 $ N $ , 抵消貢獻 $ W $ ，然後求解已知超增序列的子集和。
我們可以通過恢復 $ W $ 或者 $ N $ . Galbraith的書中描述了以下簡單的攻擊。認為 $ b_1 $ 小——遠小於 $ 2^n $ . 那麼很可能 $ b_2 $ 也同樣小，我們有有趣的性質：
$$ \begin{align*} a_1b_2 &\equiv a_2b_1 \pmod{N} \ Wb_1b_2 &\equiv W b_2 b_1 \pmod{N},, \end{align*} $$ 因此 $ a_1b_2 - a_2b_1 $ 保證是小倍數 $ N $ . 通過暴力破解 $ b_1 $ 和 $ b_2 $ ，我們可以恢復一個候選者的簡短列表 $ N $ ，然後我們可以通過嘗試恢復來確認 $ W = a_1/b_1 \pmod {N} $ 並驗證這是否 $ W $ 適用於對方 $ a_i, b_i $ 也是。這表明 $ b_i $ 至少應該是 $ 2^{n/2} $ 在尺寸方面。 這不是唯一的攻擊 $ b_1 $ 是小。Odlyzko描述了另外兩個，包括著名的沙米爾襲擊。對 Merkle-Hellman 也有非常相關的格攻擊，但這些似乎已經在 Hoffstein 等人中有所描述。