Merkle-Hellmanナップサック暗号
n ビットの平文を暗号化するために、まずn 個の数からなる超増加列
w = (w1, w2, ..., wn)
を生成する(n はセキュリティパラメータであり、100ビット以上の数にすることが推奨されている)。
次に、整数q を q > ∑ i = 1 n w i {\displaystyle \sum _{i=1}^{n}w_{i}} を満たすようにランダムに選ぶ。 更に、整数 r を gcd(r,q) = 1 となるようにランダムに選ぶ。 整数q は、q の剰余を取ったときに暗号文が一意に定まるように選ばなければならない。そうしないと二つの平文から同じ暗号文が生成されることになり、復号できなくなる。またr はq と互いに素な整数でなければならない。これは復号時にr の逆元を使うためである。
βi = r wi mod q
とし、数列
β = (β1, β2, ..., βn )
を得る。
公開鍵はβ、秘密鍵は(w, q, r )である。