Merkle-Hellmanナップサック暗号

出典: フリー百科事典『ウィキペディア（Wikipedia）』

Merkle-Hellmanナップサック暗号とは、1978年にRalph MerkleとMartin Hellmanが発表したナップサック問題（正確には部分和問題）を利用した公開鍵暗号の一つである。この暗号方式は、秘匿用途の方式であり、認証（デジタル署名など）を目的としたものではない。

公開鍵暗号の提案は1976年であり、比較的初期に提案された方式であるが、1982年に解読方法が発見されている。

[編集] 概要

Merkle-Hellmanナップサック暗号は部分和問題（ナップサック問題の特別なインスタンス）に基づいている。

部分和問題は、整数の列（a₁,...,a_n）と目標となる整数（t）を入力とし、 $\sum_{i\in S}a_i=t$ となる部分集合 $S \subseteq \{1,2,...,n\}$ を求める問題（a_iでtを合成する問題）である。

一般の部分和問題は、NP完全であることが知られている。しかし、超増加列と呼ばれる数列を用いた場合には、簡単に解けることが分かっている。Merkle-Hellmanナップサック暗号は、合成が簡単にできる超増加列を、見かけ上は合成がむずかしい整数列に変換し、また逆に戻せることに基づいている。超増加列とは、各数がそれまでの整数の和よりも大きい数列のことである。

超増加列の例: (1,2,4,8,16)

この暗号方式は発表時から安全性に疑問をもたれていたが、1982年にアディ・シャミア (Adi Shamir) によって一般的解読方法が発見された。これは部分和問題自体を解いたのではなく、超増加列を変換した数列を用いた場合には、どのように変換しても元の超増加という性質が残り、容易に解けることを示したものである。

シャミアの解読以降、多くのナップサック暗号の変形版が提案されているが、そのほとんどが解読可能であることが判明している。

用語については、暗号の用語および暗号理論の用語を参照のこと。

[編集] 暗号方式

[編集] 鍵生成

nビットの平文を暗号化するために、まずn個の数からなる超増加列

w = (w₁, w₂, ..., w_n)

を生成する（nはセキュリティパラメータであり、100ビット以上の数にすることが推奨されている）。

次に、整数qを q ≥ $\sum_{i = 1}^n w_i$ を満たすようにランダムに選ぶ。更に、整数 r を gcd(r,q) = 1となるようにランダムに選ぶ。整数qは、qの剰余を取ったときに暗号文が一意に定まるように選ばなければならない。そうしないと二つの平文から同じ暗号文が生成されることになり、復号できなくなる。またrはqと互いに素な整数でなければならない。これは復号時にrの逆元を使うためである。

β_i = r w_i (mod q)

とし、数列

β = (β₁, β₂, ..., β_n)

を得る。

公開鍵はβ、秘密鍵は(w, q, r)である。

[編集] 暗号化

nビットの平文

α = (α₁, α₂, ..., α_n)

を暗号化する。ここで、各 α_i は第iビットを表す (α_i ∈{0,1})。

$c = \sum_{i = 1}^n \alpha_i \beta_i$

を計算し、cを暗号文とする。

[編集] 復号

暗号文cを受け取った後、 c' = c * r^-1 (mod q) を計算する。

すると、c'はwの部分和になっている。wは超増加列なので、{1,2,...,n}の部分集合Sを次のようにして簡単に求めることができる。

まず、c'とw_nの大小を比較し、もしc'がw_n以上の場合には、平文の第nビットは 1 であり、小さい場合には、0 である。c'が大きい場合にはw_nを減算して、次にw_n-1との大小を比較し、同様に第n-1ビットを決める。これを第1ビットまで繰り返せばよい。

具体的なアルゴリズムは、次のとおりになる。

入力： w (超増加列), c'

出力： {1,2,...,n}の部分集合S

sをc'とし, Sを空集合とする。
i = n, n-1, ..., 2, 1 について次文を繰り返す。
- s≥w_i ならば、s=s-w_i とし、S=S∪{i} とする。
sが0ならばSを, 0でないならば⊥を出力する。

[編集] 安全性

Merkle-Hellmanナップサック暗号は、シャミアにより多項式時間で解読できることが示されている。

[編集] シャミアの攻撃法

シャミアの攻撃法では、公開鍵β = (β₁, β₂, ..., β_n)から、超増加列w' = (w'₁, w'₂, ..., w'_n)を求める。正しい超増加列wとシャミアの攻撃法で求めたw'は異なることが多いが、正しく解読できる。詳しくは参考文献のAdi Shamir, "A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem"を参照のこと。

[編集] 低密度攻撃

密度が低い場合、高確率で格子の最短ベクトルを求める問題 (最短ベクトル問題, Shortest Vector Problem, SVP) へ帰着できる。最短ベクトル問題は、ユークリッド距離ではRandomized帰着の元でNP困難な問題であることが知られているが、格子の次元が低い場合、LLLアルゴリズムを用いて解けることが多い。 (stub)

[編集] 参考文献

Ralph Merkle, Martin Hellman, "Hiding Information and Signatures in Trapdoor Knapsacks", IEEE Trans. Information Theory, 24(5), September 1978, pp.525–530.
Adi Shamir, "A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem", CRYPTO'82, pp.279–288, 1982. (PDF)

カテゴリ: 暗号