注1) 「暗号アルゴリズム (cryptographic algorithm) は、暗号方式 (cipher) のことである」という定義もあるが、ここでは、暗号アルゴリズムとは、暗号方式 (cryptosystem) を定義する一つの要素であり、暗号方式には、暗号 (cipher) を始めとする幾つかの暗号プリミティブがあるという解釈で分類している。 暗号自体は古代エジプトの時代から存在したが、その理論的研究は1949年のシャノン (Shannon) の研究に始まる。シャノン以前には、9世紀にキンディ (Al-Kindi) 、15?16世紀に アルベルティ (Alberti) 、トリテミウス (Trithemius) 、ポルタ (Porta) が執筆した暗号の書籍が残されているが、多くは秘密であった。 シャノンは、攻撃者が無限の計算能力をもっているという仮定の下で、平文に関する情報量がどの程度攻撃者に漏れるかを研究し(情報理論的安全性)、この意味で安全な暗号方式はワンタイムパッドを用いる暗号方式だけであることを示した。 暗号法や暗号解読法は、利用できる道具によって大きく影響を受ける。特に1940年代前後から始まった電子計算機によって、暗号解読可能な範囲が飛躍的に広がり、また、電子回路によって暗号がより効率的に実装できるようになった。 このような計算機の発展を背景にして、1970年代の後半に誕生したDESとRSAが現代暗号の代表である。共に、アルゴリズムが公開されていて、暗号鍵が秘密であることが安全性の前提となっている(計算量的安全性)。 これ以前にも、暗号アルゴリズムと暗号鍵が分離されていて、暗号アルゴリズム(暗号器)が漏洩しても、暗号鍵がないと暗号文を復号できないことをねらった暗号も存在したが、解読の手間(計算量)の点で、DES以前と以後では一線を引くことができよう。何よりも、従来、秘匿することが前提であったアルゴリズムの詳細を公開し、誰でも暗号の安全性を検討できる点が現代暗号の特徴である。それ以前のシーザー暗号からエニグマまでをまとめて古典暗号という。紙と鉛筆と多少の道具のみを使用していた暗号とエニグマなどの機械式暗号を区別して、後者を近代暗号とすることもある。また1949年の暗号理論を現代暗号の始まりと考える人もいる。 1990年代後半から、計算量理論的アプローチによる、暗号アルゴリズムの安全性証明の手法やモデル化の研究がなされ、計算量的に困難と仮定されている問題 (IFPやDLP) と等価であることを証明可能な暗号アルゴリズムが提案された。あるいは既知の暗号解読法では解読できないことを証明できる暗号アルゴリズムが提案された。これらを「現代暗号の第2期」ということがある(証明可能安全性)。安全性証明は、Rabin暗号やゼロ知識対話証明のように90年以前から研究があり、それらの成果の集積である。 2000年代前半には、ゼロ知識対話証明やマルチパーティ計算などの暗号プロトコルの安全性証明を統一的に扱うフレームワークの研究が進んだ。.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%;font-size:90%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}html.client-js body.skin-minerva .mw-parser-output .mbox-text-span{margin-left:23px!important}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}} 換字や転置を組み合わせた単純な古典暗号は、頻度分析で解読可能であることが9世紀頃には知られていて、15世紀から16世紀にかけて、より複雑な多表式暗号がいくつか提案されていた。しかし、多表式暗号は手作業で行うには暗号化・復号の作業が煩雑であった為、あまり使用されず、換字や転置とコード式と組み合わせるなどして複雑さを増した暗号法が長い間使われていた。 それらの方式は、沢山の暗号文を時間をかけて分析・推定することでいつ解読されるか分からないもので、実際に解読された例もいくつか知られている。入手した暗号文を分析して、(平文の)言語の統計的性質を手がかりとして、使用された暗号法(の逆変換)を推測して平文を求めるという、パズルを解くような暗号解読が行われた。19世紀には100以上の暗号法が既知のものとなっていたようである(17世紀に使用されたルイ14世の大暗号も19世紀になって解読された)。ここでは、言語に関する知識やセンス(アルファベットの出現頻度やアナグラムを解くセンス)が中心であった。 機械式暗号の登場(20世紀)は、速くて強い暗号が必要とされたことが背景にある。
展開
古典暗号
筆記と道具ベース
秘匿による安全性、難解さに基づくセキュリティ(英語版) - アルゴリズムは非公開
近代暗号
機械式暗号
現代暗号
電子計算機ベース
情報理論的安全性 information theoretic security
計算量的安全性 computational security
経験則による安全性 - アルゴリズムは公開、安全性の根拠は非公開または未知
証明可能な安全性 provable security
物理暗号
物理的理論にもとづく暗号
解読
機械式暗号の解読には、多数の組合せから解を見つけることが必要になり、カンや閃きだけでは解読できなくなった。暗号解読は、暗号機を入手して分析することの他に、いかに容易な解読方法を見つけるかということが問題になった。ここでは言語学ではなく数学が中心となる。
現代暗号では、暗号法の推測や逆変換の困難さではなく、暗号化・復号のアルゴリズムは既知として、暗号鍵の推測が困難であるような暗号方式の実現を目標とする。参照:ケルクホフスの原理
現代暗号での暗号解読は、敵の暗号文を解読するという行為ではなく、公開された暗号法を分析し、平文や鍵を求める(数学の問題を解くのと同様な)アルゴリズムを見つけたり、隠れた問題を指摘するという研究となった。ここでの暗号法と暗号解読法の関わりは、大まかに次のように進展している。S-1 ある暗号研究者が提案した暗号を別の暗号研究者が分析して解読方法を見つけ、さらに改良された暗号が提案されたり、さらに解読方法も改良されたりした。ここでは、暗号の問題点を見つけるために暗号解読が必要とされ、暗号法の発表と同様にそれらの解読に関する発表が行われた。S-2 既存の暗号解読法に対して安全であることを主張&証明する暗号が提案され、さらに、それ以外の暗号解読法の発見が望まれた。実際に安全と思われていた暗号に暗号解読法が発表されたりした。S-3 理想的な暗号を定義し、実際の暗号が理想的暗号と計算量的識別不能であることの証明を行うことが目的となった(暗号文が乱数と区別できない、あるいは、暗号関数が擬似ランダム置換族と区別できないような暗号方式等)。
S-3のような安全性証明可能な暗号方式が完成すると、暗号の安全性は根拠となる問題(素因数分解アルゴリズムの改良や量子コンピュータの実現等)や暗号以外(平文や鍵、装置の運用等)の問題に帰着されて、計算量的な制約やモデルの仮定、証明の不備などを除くと暗号解読は不可能であることを意味する。ここでは暗号解読法はもはや不要なのかは分からないが、少なくとも設計&解読の繰り返しで強い暗号を作る時代ではなくなることを意味すると考えられる。詳細は「暗号解読」を参照 1976年に提案された公開鍵暗号は、従来、秘匿用途であった暗号を認証(署名)に用いることを可能にした。秘匿と認証以外にも、様々な特殊な機能(メカニズム)の暗号が研究されている。 主要なものは「コード」と「サイファー」であるが(コード (暗号) と en:Cipher
信頼性の低い暗号
アルゴリズムが既知となった古典暗号
計算量的安全性の低い現代暗号
鍵の全数探索よりも効率的な解読法が存在する現代暗号
安全性の証明に不備がある現代暗号(第2期)
拡張
研究対象
暗号プリミティブ
暗号
筆記・道具ベースの暗号
換字式暗号 (en:Substitution cipher)
単表式換字暗号 / 単アルファベット換字式暗号 (monoalphabetic cipher)
単一換字式暗号 / 単文字換字暗号 / 単純換字暗号 (simple substitution cipher)
アトバシュ (en:Atbash) / albam
ポリュビオスの暗号表(換字表)(en:Polybius square) / 忍びいろは / 字変四八
シフト暗号 (shift cipher)
シーザー暗号 (en:Caesar cipher) / ROT13 (en:ROT13)
鍵付きシーザー暗号
アフィン暗号(en:affine cipher)
ピッグ・ペン or フリーメーソンの暗号 (en:Pigpen cipher)
同音異綴暗号 / ホモフォニック換字式暗号 (homophonic substitution cipher)
ブック暗号 (en:book cipher)
綴字換字暗号 / 多重音字換字暗号 (polygraphic substitution cipher)
ノーメンクラタ (Nomenclator)
(ルイ14世の)大暗号 (en:Great Cipher)
プレイフェア暗号 (en:Playfair cipher)
ヒル暗号 (en:Hill cipher)
ドッペルカステン