|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ 暗号 ： [あんごう] 【名詞】 1. code 2. password 3. cipher ・ 号 ： [ごう] 1. (n,n-suf) (1) number 2. issue 3. (2) sobriquet 4. pen-name
Merkle-Hellmanナップサック暗号とは、1978年にラルフ・マークルとマーティン・ヘルマンが発表したナップサック問題（正確には部分和問題）を利用した公開鍵暗号の一つである。 この暗号方式は、秘匿用途の方式であり、認証（デジタル署名など）を目的としたものではない。 公開鍵暗号の提案は1976年であり、比較的初期に提案された方式である。 1982年に解読方法が発見されたため、現在は使用されていない。 近年になり、鍵の生成に量子コンピュータを用いることにより、量子コンピュータでも解けない暗号として機能することが示され、ふたたび注目を浴びている。 == 概要 == Merkle-Hellmanナップサック暗号は部分和問題（ナップサック問題の特別なインスタンス）に基づいている。 部分和問題は、整数の列（''a''1,...,''a''n）と目標となる整数（''t''）を入力とし、となる部分集合を求める問題（''a''''i'' で''t'' を合成する問題）である。 一般の部分和問題は、NP完全であることが知られている。しかし、超増加列と呼ばれる数列を用いた場合には、簡単に解けることが分かっている。Merkle-Hellmanナップサック暗号は、合成が簡単にできる超増加列を、見かけ上は合成がむずかしい整数列に変換し、また逆に戻せることに基づいている。超増加列とは、各項がそれまでの全ての項の和よりも大きい数列のことである。 この暗号方式は発表時から安全性に疑問をもたれていたが、1982年にアディ・シャミア (Adi Shamir) によって一般的解読方法が発見された。これは部分和問題自体を解いたのではなく、超増加列を変換した数列を用いた場合には、どのように変換しても元の超増加という性質が残り、容易に解けることを示したものである。 シャミアの解読以降、多くのナップサック暗号の変形版が提案されているが、そのほとんどが解読可能であることが判明している。 用語については、暗号の用語および暗号理論の用語を参照のこと。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Merkle-Hellmanナップサック暗号」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Merkle-Hellman knapsack cryptosystem 」があります。 スポンサード リンク
|