暗号理論
暗号理論(あんごうりろん)の記事では暗号、特に暗号学に関係する理論について扱う。暗号技術も参照。
英語では、暗号を cryptography といい、暗号学を cryptology という。また、日本ではもっぱら総称される暗号には、「コード」と「サイファ (cipher)」という分類がある。
暗号理論は、暗号学の一分野である。
暗号の理論の主な分野には、以下のようなものがある。
暗号系 (cryptosystem) 、すなわち暗号化と復号、といった手続きの構成方法や性能・安全性などに関する研究
暗号や電子署名といった守秘 (confidentiality) や完全性 (integrity) を実現する、暗号アルゴリズムや暗号プロトコルの研究
暗号解読(cryptanalysis)
それでも、暗号学としては、その運用や関与する人間の不注意といったヒューマンファクタなども考慮しなければならない。(「暗号の連鎖(chain)の強さは、最も強い環(link)の強さしかない」ということは変わっていない。)
コンピュータセキュリティやネットワークセキュリティ、より総合的には情報セキュリティと暗号や暗号理論とは密接な関わりがある。例えば、(論理的な)アクセス制御は、「ユーザが誰であるか」という認証(authentication)に従ってOSの機能などによって制御される。しかし、認証自体には、例えばユーザ本人だけが知り得る秘密情報(パスワードなど)を使うといった暗号的な手法が必要であるし、無線や公衆網を通してコンピュータを利用する場合には、そのパスワードを直接やりとりしてしまうようなことは避けなければならない。そういったプロトコルの設計には、暗号理論に従った裏付けが必要である。
暗号学には総合の学であるという面がある。暗号理論にもそれは言えて、情報理論や符号理論、計算複雑性理論といった理論計算機科学などと、合同算術、数論、代数幾何、離散数学といった数学などが広く関係する。
暗号理論で使われる用語。
暗号理論 - 暗号や暗号解読を扱う理論。本ページの記事名。
暗号技術 (cryptographic techniques) - 暗号に関する技術。暗号プリミティブや暗号プロトコルを駆使して、機密 (confidentiality) ・完全性 (integrity) ・認証 (authentication) ・否認防止 (non-repudiation) などのセキュリティ機能を実現することを目的とする。鍵管理などの暗号を利用するために必要な技術も含む。
暗号学 (cryptology) - 暗号に関する学問
暗号[法] (cryptography) - 暗号方式(とその応用)の構成法や性能、安全性などに関する研究。暗号術ということもある。
暗号解読[法] (cryptanalysis) - 暗号方式(とその応用)の解読法に関する研究。暗号分析、暗号解析ということもある。
暗号学者 (cryptologist)
暗号研究者 (cryptographer) - 暗号を専門的に研究する人(暗号研究者の一覧)。まれに平文を暗号文に変換する作業に従事する人(暗号師)を指すことがある。
暗号解読者 (cryptanalyst) - 復号鍵を用いずに、暗号文を平文に戻したり、暗号文と平文を区別したり、暗号文から別の暗号文を生成することを試みる人。または、暗号文と平文の組から鍵を推定する人。まれに暗号文を復号する作業に従事する人を指すことがあるが、復号と解読は区別すべきである。
暗号プロトコル/暗号化プロトコル (cryptographic protocol/encryption protocol) - 暗号化と復号の手順
暗号プリミティブ (cryptographic primitive) - 暗号方式を、元々の目的であった秘匿だけではなく、署名・認証などの基本的ツールに適応したもののこと。cipher, signature, hash などがある。別の用法として、主に公開鍵暗号方式で、要となるトラップドア関数と、パディング等の周辺部分に分けて、前者を暗号プリミティブと称することがある(後者は暗号スキームという)。
暗号方式 / 暗号システム / 暗号系 (cryptographic scheme, cryptographic system, cryptosystem) - 暗号化鍵 (encryption key) を用いて、平文 (plaintext) を暗号文 (cryptogram) に変換する暗号化 (encryption) アルゴリズムと、復号鍵 (decryption key) を用いて、暗号文を平文に変換する復号 (decryption) アルゴリズム、鍵、平文、暗号文などからなるシステムのことである。
暗号アルゴリズム (cryptographic algorithm) / 暗号関数 - 暗号方式における暗号化および復号のアルゴリズム。
暗号化 (encryption)
復号 (decryption)
鍵生成 (key generation)
暗号鍵 / 鍵 (key)
暗号化鍵 (encryption key)
復号鍵 (decryption key)
メッセージ (message)
平文 (plain text) / 明文 (clear text)
暗号文 (cryptogram)
共通鍵暗号方式 / 対称鍵暗号方式 - 暗号化鍵 (encryption key) と復号鍵 (decryption key) が同じ、あるいは片方の鍵から他方の鍵を容易に求めることができる暗号方式。
共通鍵 (common key) / 秘密鍵 (secret key) / 共有鍵 (shared key)
公開鍵暗号方式 / 非対称鍵暗号方式 - 暗号化鍵から復号鍵を求めること、または復号鍵から暗号化鍵を求めることが難しい暗号方式。
鍵ペア (key pair) - 公開鍵と秘密鍵の組。
公開鍵 (public key) - 公開鍵暗号方式における暗号化鍵(または復号鍵)。
秘密鍵 / 私有鍵 / 私用鍵 / プライベート鍵 (private key) - 公開鍵暗号方式における復号鍵(または暗号化鍵)。過去にはprivate keyの意味でsecret keyと記述することもあった。共通鍵暗号方式における共通鍵を秘密鍵と呼ぶこともあった。
公開鍵演算 (public-key operation) - 公開鍵を用いた演算。暗号 (cipher) の場合は暗号化 (encipherment) であり、署名 (signature) の場合は、検証 (verify) になる。
秘密鍵演算 (private-key operaion) - 秘密鍵を用いた演算。暗号 (cipher) の場合は復号 (decipherment) であり、署名 (signature) の場合は、署名 (sign) になる。
暗号 (cipher)
サイファ化 (encipherment)
デサイファ化 (decipherment)
暗号化アルゴリズム (enciphering algorithm)
復号アルゴリズム (deciphering algorithm)
暗号化鍵 (enciphering key)
復号鍵 (deciphering key)
暗号文 (cipher text)
署名 (signature)
署名 (sign)
検証(verify)
署名鍵(signature key)
検証鍵(verification key)
メッセージ / 文書
署名データ / 署名
ハッシュ関数 (hash function) / メッセージダイジェスト (message digest)
メッセージ / プレイメージ (pre-image)
ハッシュ値 / フィンガープリント / ハッシュ
秘匿通信 (secret communication)
認証 (authentication) / ディジタル署名 (digital signature)
注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年代前半には、ゼロ知識対話証明やマルチパーティ計算などの暗号プロトコルの安全性証明を統一的に扱うフレームワークの研究が進んだ。
秘匿による安全性、難解さに基づくセキュリティ - アルゴリズムは非公開
情報理論的安全性 information theoretic security
計算量的安全性 computational security
経験則による安全性 - アルゴリズムは公開、安全性の根拠は非公開または未知
証明可能な安全性 provable security
換字や転置を組み合わせた単純な古典暗号は、頻度分析で解読可能であることが9世紀頃には知られていて、15世紀から16世紀にかけて、より複雑な多表式暗号がいくつか提案されていた。しかし、多表式暗号は手作業で行うには暗号化・復号の作業が煩雑であった為、あまり使用されず、換字や転置とコード式と組み合わせるなどして複雑さを増した暗号法が長い間使われていた。
それらの方式は、沢山の暗号文を時間をかけて分析・推定することでいつ解読されるか分からないもので、実際に解読された例もいくつか知られている。
入手した暗号文を分析して、(平文の)言語の統計的性質を手がかりとして、使用された暗号法(の逆変換)を推測して平文を求めるという、パズルを解くような暗号解読が行われた。
19世紀には100以上の暗号法が既知のものとなっていたようである(17世紀に使用されたルイ14世の大暗号も19世紀になって解読された)。
ここでは、言語に関する知識やセンス(アルファベットの出現頻度やアナグラムを解くセンス)が中心であった。
機械式暗号の登場(20世紀)は、速くて強い暗号が必要とされたことが背景にある。
機械式暗号の解読には、多数の組合せから解を見つけることが必要になり、カンや閃きだけでは解読できなくなった。暗号解読は、暗号機を入手して分析することの他に、いかに容易な解読方法を見つけるかということが問題になった。ここでは言語学ではなく数学が中心となる。
現代暗号では、暗号法の推測や逆変換の困難さではなく、暗号化・復号のアルゴリズムは既知として、暗号鍵の推測が困難であるような暗号方式の実現を目標とする。参照:ケルクホフスの原理
現代暗号での暗号解読は、敵の暗号文を解読するという行為ではなく、公開された暗号法を分析し、平文や鍵を求める(数学の問題を解くのと同様な)アルゴリズムを見つけたり、隠れた問題を指摘するという研究となった。ここでの暗号法と暗号解読法の関わりは、大まかに次のように進展している。
S-1 ある暗号研究者が提案した暗号を別の暗号研究者が分析して解読方法を見つけ、さらに改良された暗号が提案されたり、さらに解読方法も改良されたりした。ここでは、暗号の問題点を見つけるために暗号解読が必要とされ、暗号法の発表と同様にそれらの解読に関する発表が行われた。
S-2 既存の暗号解読法に対して安全であることを主張&証明する暗号が提案され、さらに、それ以外の暗号解読法の発見が望まれた。実際に安全と思われていた暗号に暗号解読法が発表されたりした。
S-3 理想的な暗号を定義し、実際の暗号が理想的暗号と計算量的識別不能であることの証明を行うことが目的となった(暗号文が乱数と区別できない、あるいは、暗号関数が擬似ランダム置換族と区別できないような暗号方式等)。
S-3のような安全性証明可能な暗号方式が完成すると、暗号の安全性は根拠となる問題(素因数分解アルゴリズムの改良や量子コンピュータの実現等)や暗号以外(平文や鍵、装置の運用等)の問題に帰着されて、計算量的な制約やモデルの仮定、証明の不備などを除くと暗号解読は不可能であることを意味する。ここでは暗号解読法はもはや不要なのかは分からないが、少なくとも設計&解読の繰り返しで強い暗号を作る時代ではなくなることを意味すると考えられる。
安全性の証明に不備がある現代暗号(第2期)
1976年に提案された公開鍵暗号は、従来、秘匿用途であった暗号を認証(署名)に用いることを可能にした。秘匿と認証以外にも、様々な特殊な機能(メカニズム)の暗号が研究されている。
主要なものは「コード」と「サイファー」であるが(コード (暗号) と Cipher を参照)、他にも多数の分類などがある。最古の文字といわれるヒエログリフでも暗号と推測される文字が見つかっていて、長い歴史を持つ。ここでは歴史的なものの含めて主な暗号を分類・一覧する。
筆記・道具ベースの暗号
換字式暗号 (Substitution cipher)
単表式換字暗号 / 単アルファベット換字式暗号 (monoalphabetic cipher)
単一換字式暗号 / 単文字換字暗号 / 単純換字暗号 (simple substitution cipher)
アトバシュ (Atbash) / albam
ポリュビオスの暗号表(換字表)(Polybius square) / 忍びいろは / 字変四八
シフト暗号 (shift cipher)
シーザー暗号 (Caesar cipher) / ROT13 (ROT13)
アフィン暗号(affine cipher)
ピッグ・ペン or フリーメーソンの暗号 (Pigpen cipher)
同音異綴暗号 / ホモフォニック換字式暗号 (homophonic substitution cipher)
ブック暗号 (book cipher)
綴字換字暗号 / 多重音字換字暗号 (polygraphic substitution cipher)
ノーメンクラタ (Nomenclator)
(ルイ14世の)大暗号 (Great Cipher)
プレイフェア暗号 (Playfair cipher)
ヒル暗号 (Hill cipher)
多表式換字暗号 / 多アルファベット換字式暗号 (Polyalphabetic cipher)
正方形の[換字]表 (トリテミスの多表) (tabula recta)
ヴィジュネル暗号 (ビジネル暗号ということもある) (Vigenère cipher)
ボーフォート暗号 (Beaufort cipher)
連続鍵暗号 / 進行鍵暗号 (running key cipher) /
自己鍵暗号 / 自動鍵暗号 (autokey cipher)
転置式暗号 / 転字式(transposition cipher)
スキュタレー (Scytale)
レールフェンス暗号 (Rail Fence cipher)
分置式暗号 / 挿入式暗号 / 隠字式 (acrostic,折句)
カルダングリル (Cardan grille、あるいはカルダーノグリル、Cardano grille)
ADFGVX暗号 (ADFGVX cipher)  / VIC暗号 (VIC cipher)
ホィール暗号機 (wheel) 、シリンダー (cylinder)
M-94 (M-94) 、ストリップ多表暗号M-138A
機械式暗号(ロータマシン(rotor machine)等)
(円盤式)
クリハ暗号機 (Kryha) / 九一式暗号機
(ロータ式)
ヒーバン暗号機 (Hebern rotor machine)
エニグマ暗号機 (Enigma machine)
パープル暗号機(九七式欧文印字機) (PURPLE)
ハゲリン暗号機(Hagelin) / M-209 (M-209)
シガバ (SIGABA or ECM MarkII)
タイペックス (Typex) or タイプX (Type X)
(テープ式)
バーナム暗号(ヴァーナム暗号ということもある) (Vernam cipher)
Lucifer / AES / Camellia / CIPHERUNICORN-A / RC6 / MARS / CAST-256 / Twofish / MISTY2 / MAGENTA / SEED / LOKI97 / Serpent
SHACAL-2
other block size
RC5 (variable)
ストリーム暗号 / 逐次暗号
/ ワンタイムパッド one time pad
RC4 / MULTI-SO1 / FISH / WAKE / A5/1 / A5/2 / SORFR / SNOW
(素因数分解問題)
(離散対数問題)
ElGamal暗号 / ACE Encrypt
楕円曲線暗号 / PSEC-KEM / ECIES
(ナップサック問題) / ナップサック暗号
Merkle-Hellmanナップサック暗号 / Chor-Rivestナップサック暗号
(ラティス問題) / ラティス暗号
(多次[元]多変数、多変数多項式問題)
電子署名を実現する一番有力な方法がディジタル署名である。一般的に言って原理上、公開鍵暗号の発見によりディジタル署名が可能になった。
(素因数分解問題)
RSA署名  / RSA-PSS (RSA-PSS) / ACE Sign
(離散対数問題)
ElGamal署名 / Schnorr署名 / DSA
(行列分解問題)
FLASH / SFLASH
(格子問題)
NSS / NTRU-SIGN
(楕円離散対数問題)
/ ECDSA
RSA-PSS-R
ブラインド署名 (blind signature)
否認不可署名 (undeniable signature)
フェイルストップ署名 (fail-stop signature)
検証者指定可能署名 designated verifier signature
MD2 / MD4 / MD5 /
Secure Hash Algorithm (SHA)
SHA-0 /
SHA-1 /
SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512) /
pseudorandom function(Pseudorandom function family を参照。「乱数列」(random numbers)ではないことに注意)
暗号プロトコルは、暗号化に関係するプロトコル(暗号化プロトコル)などから成る。または、より広い情報セキュリティ一般に関係するセキュリティプロトコルなど。
相手認証 / 相互認証 / 片側認証 / ユーザ認証
Diffie-Hellman認証 / Schnorr認証
メッセージ認証 / メッセージ認証子
DES-MAC / HMAC / 鍵付きハッシュ関数
チャレンジ・レスポンス
公開鍵証明書 (→ PKI)
マルチパーティ計算 / 共同計算
紛失通信 / 忘却通信路 / (oblivious transfer)
ゼロ知識証明 / ゼロ知識対話証明 (ZKIP) (Zero-knowledge proof)
時刻証明 / タイムスタンプ
依頼計算 server-aid computation
同時交換 fair exchange
ミックスネット mix net
秘密分散 (Secret sharing)
検証可能秘密分散 (verifiable secret sharing)
閾値暗号 (threshold cryptosystem)
汎用的結合可能性 (universal composability)
ブロック暗号は、データスクランブル部と、鍵スケジュール部の2つを主な要素とし、データスクランブル部は、ラウンドの繰返し構造になっているものが多い(product cipherという)。Product cipherの基本的な構成法に、Feistel構造とSPN構造の2つがある。
Product cihper
Feistel構造 / フェイステル・ネットワーク Feistel network
SPN構造 (substitution-permutation network)
F関数 / Sボックス S-box
鍵拡大 / キースケジュール / ラウンド鍵
初期変換 / 最終変換
公開鍵暗号の要はトラップドア関数であり、安全なトラップドア関数の存在を仮定して、安全な公開鍵暗号方式を構成する方法が研究されている。
トラップドア関数は、まだ数個しか発見されておらず、新しいトラップドア関数の発見もテーマの一つである。
一方向性関数 one way function
トラップドア関数 / 落し戸付き一方向性関数
ハードコア述語 / ハードコア関数 (hardcore predicate)
RSAモジュラス (N=P* Q)
ESIGNモジュラス (N=P* P* Q)
ハッシュ関数(正確には、暗号論的ハッシュ関数)は、可変長入力、固定長出力の関数で、入力から出力を求めることは容易であるが、出力から入力(あるいは出力が同じになる入力の一つ)を求めること、出力が同一になるような2個の入力を求めることが計算量的に困難である等の性質を満たすものである。
ほとんどのハッシュ関数は、可変長の入力メッセージ m をブロック単位に分割(最初のブロックをm_1、最後のブロックをm_nとする。m_0は所定の初期値)し、圧縮関数 H を h_i = H(h_{i-1}, m_i) のように繰り返し使って、出力 h_n を求める構成になっている。
基本構造(全体構造)
反復型 iterated
Enveloped MD
MD-Strengthening (パディング)
圧縮関数については、ハッシュ専用の関数を開発することの他に、ブロック暗号を利用した構成法が研究されている。ブロック暗号ベースの構成法では、構成可能な種類の数え上げや理想暗号モデル E を用いた安全性証明、構成法としての最適性などが検討されている。
圧縮関数の構成 one-way compression function
MDx 等
代数的関数(法剰余)
Davies-Meyer法 h' = h xor E(m,h)
Matyas-Meyer-Oseas法 h' = m xor E(g(h),m), ISO/IEC 1-118-2
Miyaguchi-Preneel法  h' = m xor E(g(h),m) xor h
MDC-2、MDC-4
ハイブリッド暗号 / KEM / DEM
暗号化・復号に必要な演算量や、ハード・ソフト実装時の処理速度などについて、実測値の測定、暗号方式間の比較や実装方法の効率化などが研究されている。
また、安全性の指標ともなる様々な特性値や、その求め方(上限や下限、近似計算)も研究されている。暗号にとって重要な特性値には、暗号解読によって発見されたものがある。
共通鍵暗号は、公開鍵暗号で代用できる場合があるため、スピードや鍵サイズ、実装コストなどで公開鍵暗号よりもメリットがあることが求められる。
ストリーム暗号は、ブロック暗号の一つの利用モードとして実現できるため、ストリーム暗号の存在理由として、スピードが速いこと等が求められる。
線形・差分特性
一般に、安全性の目標と攻撃条件をモデル化することで暗号を攻撃する問題を定義し、それが誰もが難しいと想定している問題(安全性の根拠となる問題)と等価であることを示すことで、安全性の評価とする。その際、攻撃条件だけではなく攻撃アルゴリズムも限定して「その範囲」で安全である(目標が達成されている)ということもある。証明の際にさらに仮定やモデルを導入することもある(問題が等価であることの定義など)。また、現代暗号では、計算量的安全性(解読に要する計算量が膨大であること、例:指数時間要する)があることを安全性の前提としているものが多い。このことは計算機の進歩や時間の経過により安全性が低下していくことを意味する。
安全性の表現の例:「○○○暗号は、ROM仮定の下、DLPが困難であれば、IND-CCA2 の安全性証明がある(計算量的安全性)」
暗号の安全性では、上記のような安全性に影響する事項を見出して、より厳密な定義を構築していくことと、その定義を満たす暗号の性質が研究されている。
その他、実際の暗号の安全性は、暗号方式の理論的安全性よりも、実装上、運用上の問題の有無によってより大きく影響を受けることがある。安全とされる暗号方式や暗号製品を採用するだけではなく、平文の管理(例えば個人情報の扱い)や鍵の管理などにも注意が必要である。
安全性の目標(ゴール)
完全秘匿 perfect secrecy
強秘匿 / セマンティックセキュア (SS) semantic secure Semantic security
頑強性 / 非展性 (NM) non-malleable Malleability (cryptography)
鍵非展性 → 暗号と群も参照
識別不能性 (IND) indistinguishable
平文識別不能性 ciphertext indistinguishability
既知暗号文攻撃 (COA) ciphertext-only attack
適応的選択暗号文攻撃 (CCA2) adaptive chosen ciphertext attack
関連鍵攻撃 related-key attack
(汎用的攻撃)
総当たり攻撃 / 全数探索 / Brute force attack exhaustive key search
(古典暗号)
カシスキ・テスト Kasiski examination
一致反復率 index of coincidence
(現代暗号)
差分解読法(差分暗号解読) differential cryptanalysis (Biham,1989)