暗号理論（あんごうりろん）とは、暗号における暗号化 () および復号 () と暗号解読 () を扱う理論のこと。暗号は、、、と対応する言葉であり、秘密の表記そのもの、またはその表記法を指すことがある。暗号理論では主に次の二つを扱う。暗号理論では、主として、アルゴリズムやプロトコルによってセキュリティ機能を実現する研究（情報セキュリティ）がなされており、OSやネットワークの特徴を生かしてセキュリティ機能を実現する研究（コンピュータセキュリティやネットワークセキュリティ）と区別される。暗号理論には、情報理論、符号理論、計算複雑性理論といった計算機科学、数論や代数幾何、離散数学といった数学、時には力学系などの物理学の知見が用いられることもある。暗号理論で使われる用語。注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年代前半には、ゼロ知識対話証明やマルチパーティ計算などの暗号プロトコルの安全性証明を統一的に扱うフレームワークの研究が進んだ。換字や転置を組み合わせた単純な古典暗号は、頻度分析で解読可能であることが9世紀頃には知られていて、15世紀から16世紀にかけて、より複雑な多表式暗号がいくつか提案されていた。しかし、多表式暗号は手作業で行うには暗号化・復号の作業が煩雑であった為、あまり使用されず、換字や転置とコード式と組み合わせるなどして複雑さを増した暗号法が長い間使われていた。それらの方式は、沢山の暗号文を時間をかけて分析・推定することでいつ解読されるか分からないもので、実際に解読された例もいくつか知られている。入手した暗号文を分析して、（平文の）言語の統計的性質を手がかりとして、使用された暗号法（の逆変換）を推測して平文を求めるという、パズルを解くような暗号解読が行われた。19世紀には100以上の暗号法が既知のものとなっていたようである（17世紀に使用されたルイ14世の大暗号も19世紀になって解読された）。ここでは、言語に関する知識やセンス（アルファベットの出現頻度やアナグラムを解くセンス）が中心であった。機械式暗号の登場（20世紀）は、速くて強い暗号が必要とされたことが背景にある。機械式暗号の解読には、多数の組合せから解を見つけることが必要になり、カンや閃きだけでは解読できなくなった。暗号解読は、暗号機を入手して分析することの他に、いかに容易な解読方法を見つけるかということが問題になった。ここでは言語学ではなく数学が中心となる。現代暗号では、暗号法の推測や逆変換の困難さではなく、暗号化・復号のアルゴリズムは既知として、暗号鍵の推測が困難であるような暗号方式の実現を目標とする。参照：ケルクホフスの原理現代暗号での暗号解読は、敵の暗号文を解読するという行為ではなく、公開された暗号法を分析し、平文や鍵を求める（数学の問題を解くのと同様な）アルゴリズムを見つけたり、隠れた問題を指摘するという研究となった。ここでの暗号法と暗号解読法の関わりは、大まかに次のように進展している。S-3のような安全性証明可能な暗号方式が完成すると、暗号の安全性は根拠となる問題（素因数分解アルゴリズムの改良や量子コンピュータの実現等）や暗号以外（平文や鍵、装置の運用等）の問題に帰着されて、計算量的な制約やモデルの仮定、証明の不備などを除くと暗号解読は不可能であることを意味する。ここでは暗号解読法はもはや不要なのかは分からないが、少なくとも設計&解読の繰り返しで強い暗号を作る時代ではなくなることを意味すると考えられる。1976年に提案された公開鍵暗号は、従来、秘匿用途であった暗号を認証(署名)に用いることを可能にした。秘匿と認証以外にも、様々な特殊な機能（メカニズム）の暗号が研究されている。主に現代暗号で公開鍵暗号の発明によって、暗号方式は、暗号 (cipher) だけではなく、署名や認証にも応用可能になった。それらはセキュリティ機能を実現するための基本的ツールとなっている。最古の文字といわれるヒエログリフでも暗号と推測される文字が見つかっていて、長い歴史を持つ。ここでは歴史的なものの含めて主な暗号を分類・一覧する。電子署名を実現する一番有力な方法がデジタル署名である。公開鍵暗号として有名なRSAは、デジタル署名を実現できる方法として最初に公開された方法でもある。RSA以前には、DiffieとHellmanによるDH鍵共有法が知られていて、DH法で共有した鍵をワンタイムパッドに用いることで暗号は可能であったが、署名や認証を実現する方法は公開されていなかった。セキュリティプロトコル（暗号プロトコルもしくは暗号化プロトコル）はセキュリティに関する機能や暗号方式を規定するプロトコルである。暗号プロトコルには暗号化アルゴリズムの使用法が記述されている。詳細に規定されたプロトコルはデータ構造やデータの表現法を含み、複数の実装で用いられることで様々なプログラム間での相互運用性を実現する。ブロック暗号は、データスクランブル部と、鍵スケジュール部の2つを主な要素とし、データスクランブル部は、ラウンドの繰返し構造になっているものが多い（product cipherという）。Product cipherの基本的な構成法に、Feistel構造とSPN構造の2つがある。公開鍵暗号の要はトラップドア関数であり、安全なトラップドア関数の存在を仮定して、安全な公開鍵暗号方式を構成する方法が研究されている。トラップドア関数は、まだ数個しか発見されておらず、新しいトラップドア関数の発見もテーマの一つである。ハッシュ関数（正確には、暗号論的ハッシュ関数）は、可変長入力、固定長出力の関数で、入力から出力を求めることは容易であるが、出力から入力（あるいは出力が同じになる入力の一つ）を求めること、出力が同一になるような2個の入力を求めることが計算量的に困難である等の性質を満たすものである。ほとんどのハッシュ関数は、可変長の入力メッセージ m をブロック単位に分割（最初のブロックをm_1、最後のブロックをm_nとする。m_0は所定の初期値）し、圧縮関数 H を h_i = H(h_{i-1}, m_i) のように繰り返し使って、出力 h_n を求める構成になっている。圧縮関数については、ハッシュ専用の関数を開発することの他に、ブロック暗号を利用した構成法が研究されている。ブロック暗号ベースの構成法では、構成可能な種類の数え上げや理想暗号モデル E を用いた安全性証明、構成法としての最適性などが検討されている。暗号化・復号に必要な演算量や、ハード・ソフト実装時の処理速度などについて、実測値の測定、暗号方式間の比較や実装方法の効率化などが研究されている。また、安全性の指標ともなる様々な特性値や、その求め方（上限や下限、近似計算）も研究されている。暗号にとって重要な特性値には、暗号解読によって発見されたものがある。共通鍵暗号は、公開鍵暗号で代用できる場合があるため、スピードや鍵サイズ、実装コストなどで公開鍵暗号よりもメリットがあることが求められる。ストリーム暗号は、ブロック暗号の一つの利用モードとして実現できるため、ストリーム暗号の存在理由として、スピードが速いこと等が求められる。擬似乱数も同じ。暗号アルゴリズムが安全であるか？を直接に示すことは、P対NP問題と同じくらい難しいことだと考えられている。そこで、安全性の目標と攻撃条件をモデル化することで暗号を攻撃する問題を定義し、それが誰もが難しいと想定している問題（安全性の根拠となる問題）と等価であることを示す証明を行うことで、安全性の証明とすることがある。その際、攻撃条件だけではなく攻撃アルゴリズムも限定して「その範囲」で安全である（目標が達成されている）ということもある。証明の際にさらに仮定やモデルを導入することもある（問題が等価であることの定義など）。また、現代暗号では、計算量的安全性（解読に要する計算量が膨大であること、例：指数時間要する）があることを安全性の前提としているものが多い。このことは計算機の進歩や時間の経過により安全性が低下していくことを意味する。また、量子計算機のように現在の計算機とは異なる計算能力を持つ計算機が実現した場合にも、影響を受ける。そのため、長期間保存する文書の安全性には情報理論的安全性が必要と言われることもある。安全性の表現の例：「○○○暗号は、ROM仮定の下、DLPが困難であれば、IND-CCA2 の安全性証明がある（計算量的安全性）」暗号の安全性では、上記のような安全性に影響する事項を見出して、より厳密な定義を構築していくことと、その定義を満たす暗号の性質が研究されている。その他、実際の暗号の安全性は、暗号方式の理論的安全性よりも、実装上、運用上の問題の有無によってより大きく影響を受けることがある。安全とされる暗号方式や暗号製品を採用するだけではなく、平文の管理（例えば個人情報の扱い）や鍵の管理などにも注意が必要である。暗号 (Cipher) 以外の暗号プリミティブについても、同様な安全性の研究がなされている。

出典:wikipedia