マークル・ヘルマン・ナップサック暗号システム

1. ブロックサイズを選択してください${\displaystyle n}$. までの整数${\displaystyle n}$この鍵を使えば、長さのビットを暗号化できます。
2. ランダムな超増加数列を選択します${\displaystyle n}$正の整数
   ${\displaystyle W=(w_{1},w_{2},\dots ,w_{n})}$
   超増加要件とは、${\displaystyle w_{k}>\sum _{i=1}^{k-1}w_{i}}$、 のために${\displaystyle 1<k\leq n}$。
3. ランダムな整数を選択する${\displaystyle q}$そのため
   ${\displaystyle q>\sum _{i=1}^{n}w_{i}}$
4. ランダムな整数を選択する${\displaystyle r}$そのため${\displaystyle \gcd(r,q)=1}$（つまり、${\displaystyle r}$そして${\displaystyle q}$互いに素である）。
5. 数列を計算する
   ${\displaystyle B=(b_{1},b_{2},\dots ,b_{n})}$
   どこ${\displaystyle b_{i}=rw_{i}{\bmod {q}}}$。

公開鍵は${\displaystyle B}$秘密鍵は${\displaystyle (W,q,r)}$。

させて${\displaystyle m}$になる${\displaystyle n}$-ビットで構成されるビットメッセージ${\displaystyle m_{1}m_{2}\dots m_{n}}$、 と${\displaystyle m_{1}}$最上位ビットを選択してください。${\displaystyle b_{i}}$そのために${\displaystyle m_{i}}$はゼロ以外であり、それらを足し合わせます。同様に、計算します。

${\displaystyle c=\sum _{i=1}^{n}m_{i}b_{i}}$。

暗号文は${\displaystyle c}$。

暗号文を解読する${\displaystyle c}$、次の部分集合を見つけなければなりません${\displaystyle B}$つまり、${\displaystyle c}$我々は、問題を部分集合を見つける問題に変換することによってこれを行う。${\displaystyle W}$その問題は、以下の理由により多項式時間で解決できます。${\displaystyle W}$超増加している。

1. のモジュラー逆数を計算する${\displaystyle r}$モジュロ${\displaystyle q}$拡張ユークリッドアルゴリズムを使用する。逆行列は存在する。${\displaystyle r}$は互いに素である${\displaystyle q}$。
   ${\displaystyle r':=r^{-1}{\pmod {q}}}$
   計算${\displaystyle r'}$これはメッセージの内容とは無関係であり、秘密鍵を生成する際に一度だけ実行すればよい。
2. 計算する
   ${\displaystyle c':=cr'{\bmod {q}}}$
3. 部分和問題を解く${\displaystyle c'}$超増加数列を使用する${\displaystyle W}$、以下に説明する単純な貪欲アルゴリズムによって。${\displaystyle X=(x_{1},x_{2},\dots ,x_{k})}$要素のインデックスの結果として得られるリストは${\displaystyle W}$合計すると${\displaystyle c'}$（つまり、${\displaystyle c'=\sum _{i=1}^{k}w_{x_{i}}}$）
4. メッセージを作成する${\displaystyle m}$それぞれに1が入っています${\displaystyle x_{i}}$ビット位置と、その他のすべてのビット位置に0：
   ${\displaystyle m=\sum _{i=1}^{k}2^{n-x_{i}}}$