Merkle-Hellmanナップサック暗号
Merkle-Hellmanナップサック暗号は、ラルフ・マークルとマーティン・ヘルマンによって1978年に発表された公開鍵[[暗号]]です。この暗号は、ナップサック問題（より正確には部分和問題）を基盤としています。
Merkle-Hellmanナップサック暗号は、部分和問題という、与えられた整数の集合から特定の合計値を生成する部分集合を見つける問題に基づいています。この問題は一般的にNP完全であることが知られていますが、特定の数列、特に超増加列を用いることで容易に解くことが可能です。超増加列とは、数列内の各項が、それ以前のすべての項の合計よりも大きい数列です。
この暗号方式では、まず簡単に解ける超増加列を作成し、それを一見複雑な整数列に変換します。この変換は可逆であり、秘密鍵を持つ者だけが容易に元の超増加列に戻すことができます。しかし、この変換が弱点となり、1982年にアディ・シャミアによって、この暗号の一般的な解読方法が発見されました。
シャミアの解読法は、部分和問題を直接解くのではなく、超増加列を変換した数列が元の超増加列の性質を保持していることを利用し、容易に解読可能であることを示したものです。この解読法の発見以降、多くのナップサック暗号の変形版が提案されましたが、そのほとんどが解読可能であることが判明しています。
暗号化を行うには、まず以下の手順で鍵を生成します。
1. 超増加列の生成: nビットの平文を暗号化するために、n個の数からなる超増加列 \( w = (w_1, w_2, ..., w_n) \) を生成します。nはセキュリティパラメータであり、通常100ビット以上の数が推奨されます。
2. qの選択: 整数 q を、\( q > \sum_{i=1}^{n} w_i \) を満たすようにランダムに選択します。qは、暗号文が一意に定まるように選ぶ必要があります。
3. rの選択: 整数 r を、\( gcd(r, q) = 1 \) を満たすようにランダムに選択します。rはqと互いに素である必要があります。これは復号時にrの逆元を使用するためです。
4. 公開鍵と秘密鍵:
\( \beta_i = r \cdot w_i \pmod{q} \) で数列 \( \beta = (\beta_1, \beta_2, ..., \beta_n) \) を生成します。
公開鍵はβ、秘密鍵は (w, q, r) となります。
平文 \( \alpha = (\alpha_1, \alpha_2, ..., \alpha_n) \) （各\( \alpha_i \) は0または1）を暗号化するには、以下の計算を行います。
\( c = \sum_{i=1}^{n} \alpha_i \cdot \beta_i \)
ここでcが暗号文となります。
暗号文cを受け取った後、以下の手順で復号します。
1. \( c' = c \cdot r^{-1} \pmod{q} \) を計算します。\( r^{-1} \) は、rのqを法とする逆元です。
2. \( c' \) は、超増加列 w の部分和になっているため、\( \{1, 2, ..., n\} \) の部分集合 S を容易に求めることができます。
3. 具体的には、次のアルゴリズムでSを求めます。
- \( c' \) と \( w_i \) を比較して、\( c' >= w_i \) なら、S に i を追加し、\( c' = c' - w_i \) とします。これを全てのiについて繰り返します。
- S に含まれる i に対応する平文 \( \alpha_i \) は1、それ以外は0となります。
Merkle-Hellmanナップサック暗号は、シャミアによって多項式時間で解読可能であることが示されています。
シャミアの攻撃法では、公開鍵βから、超増加列 \( w' \) を求めます。この \( w' \) は、元の超増加列 w とは異なることが多いですが、復号が可能となります。
ナップサック問題の密度が低い場合、高確率で格子の最短ベクトルを求める問題（最短ベクトル問題、SVP）に帰着できます。この問題は一般的にNP困難ですが、格子の次元が低い場合は、LLLアルゴリズムなどを用いて解けることがあります。
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.
J. C. Lagarias and A. M. Odlyzko: “Solving Low Density Subset Sum Problems,” J. Assoc. Comp.Math., vol.32, pp.229–246, Preliminary version in Proc. 24th IEEE, 1985
M. J. Coster, B. A. LaMacchia, A. M. Odlyzko and C. P. Schnorr: “An Improved Low-Density Subset Sum Algorithm,” In Advances in Cryptology Proc. EUROCRYPTO'91,LNCS, pp.54–67.Springer-Verlag, Berlin, 1991.
公開鍵[[暗号]]
暗号理論
信頼性の低い暗号アルゴリズム
Chor-Rivestナップサック暗号
概要
Merkle-Hellmanナップサック暗号は、部分和問題という、与えられた整数の集合から特定の合計値を生成する部分集合を見つける問題に基づいています。この問題は一般的にNP完全であることが知られていますが、特定の数列、特に超増加列を用いることで容易に解くことが可能です。超増加列とは、数列内の各項が、それ以前のすべての項の合計よりも大きい数列です。
この暗号方式では、まず簡単に解ける超増加列を作成し、それを一見複雑な整数列に変換します。この変換は可逆であり、秘密鍵を持つ者だけが容易に元の超増加列に戻すことができます。しかし、この変換が弱点となり、1982年にアディ・シャミアによって、この暗号の一般的な解読方法が発見されました。
シャミアの解読法は、部分和問題を直接解くのではなく、超増加列を変換した数列が元の超増加列の性質を保持していることを利用し、容易に解読可能であることを示したものです。この解読法の発見以降、多くのナップサック暗号の変形版が提案されましたが、そのほとんどが解読可能であることが判明しています。
暗号方式
鍵生成
暗号化を行うには、まず以下の手順で鍵を生成します。
1. 超増加列の生成: nビットの平文を暗号化するために、n個の数からなる超増加列 \( w = (w_1, w_2, ..., w_n) \) を生成します。nはセキュリティパラメータであり、通常100ビット以上の数が推奨されます。
2. qの選択: 整数 q を、\( q > \sum_{i=1}^{n} w_i \) を満たすようにランダムに選択します。qは、暗号文が一意に定まるように選ぶ必要があります。
3. rの選択: 整数 r を、\( gcd(r, q) = 1 \) を満たすようにランダムに選択します。rはqと互いに素である必要があります。これは復号時にrの逆元を使用するためです。
4. 公開鍵と秘密鍵:
\( \beta_i = r \cdot w_i \pmod{q} \) で数列 \( \beta = (\beta_1, \beta_2, ..., \beta_n) \) を生成します。
公開鍵はβ、秘密鍵は (w, q, r) となります。
暗号化
平文 \( \alpha = (\alpha_1, \alpha_2, ..., \alpha_n) \) （各\( \alpha_i \) は0または1）を暗号化するには、以下の計算を行います。
\( c = \sum_{i=1}^{n} \alpha_i \cdot \beta_i \)
ここでcが暗号文となります。
復号
暗号文cを受け取った後、以下の手順で復号します。
1. \( c' = c \cdot r^{-1} \pmod{q} \) を計算します。\( r^{-1} \) は、rのqを法とする逆元です。
2. \( c' \) は、超増加列 w の部分和になっているため、\( \{1, 2, ..., n\} \) の部分集合 S を容易に求めることができます。
3. 具体的には、次のアルゴリズムでSを求めます。
- \( c' \) と \( w_i \) を比較して、\( c' >= w_i \) なら、S に i を追加し、\( c' = c' - w_i \) とします。これを全てのiについて繰り返します。
- S に含まれる i に対応する平文 \( \alpha_i \) は1、それ以外は0となります。
安全性
Merkle-Hellmanナップサック暗号は、シャミアによって多項式時間で解読可能であることが示されています。
シャミアの攻撃法
シャミアの攻撃法では、公開鍵βから、超増加列 \( w' \) を求めます。この \( w' \) は、元の超増加列 w とは異なることが多いですが、復号が可能となります。
低密度攻撃(LDA)
ナップサック問題の密度が低い場合、高確率で格子の最短ベクトルを求める問題（最短ベクトル問題、SVP）に帰着できます。この問題は一般的にNP困難ですが、格子の次元が低い場合は、LLLアルゴリズムなどを用いて解けることがあります。
参考文献
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.
J. C. Lagarias and A. M. Odlyzko: “Solving Low Density Subset Sum Problems,” J. Assoc. Comp.Math., vol.32, pp.229–246, Preliminary version in Proc. 24th IEEE, 1985
M. J. Coster, B. A. LaMacchia, A. M. Odlyzko and C. P. Schnorr: “An Improved Low-Density Subset Sum Algorithm,” In Advances in Cryptology Proc. EUROCRYPTO'91,LNCS, pp.54–67.Springer-Verlag, Berlin, 1991.
関連項目
公開鍵[[暗号]]
暗号理論
信頼性の低い暗号アルゴリズム
Chor-Rivestナップサック暗号
もう一度検索
【記事の利用について】
タイトルと記事文章は、記事のあるページにリンクを張っていただければ、無料で利用できます。
※画像は、利用できませんのでご注意ください。
【リンクついて】
リンクフリーです。