暗号理論

暗号理論の記事では暗号、特に暗号学に関係する理論について扱う。も参照。

1. 概要
-----

英語では、暗号を cryptography といい、暗号学を cryptology という。また、日本ではもっぱら総称される暗号には、「コード」と「サイファ 」という分類がある。

暗号理論は、暗号学の一分野である。

暗号の理論の主な分野には、以下のようなものがある。

暗号系  、すなわち暗号化と復号、といった手続きの構成方法や性能・安全性などに関する研究
暗号や電子署名といった守秘  や完全性  を実現する、暗号アルゴリズムや暗号プロトコルの研究
暗号解読 それでも、暗号学としては、その運用や関与する人間の不注意といったヒューマンファクタなども考慮しなければならない。

コンピュータセキュリティやネットワークセキュリティ、より総合的には情報セキュリティと暗号や暗号理論とは密接な関わりがある。例えば、アクセス制御は、「ユーザが誰であるか」という認証に従ってOSの機能などによって制御される。しかし、認証自体には、例えばユーザ本人だけが知り得る秘密情報を使うといった暗号的な手法が必要であるし、無線や公衆網を通してコンピュータを利用する場合には、そのパスワードを直接やりとりしてしまうようなことは避けなければならない。そういったプロトコルの設計には、暗号理論に従った裏付けが必要である。

暗号学には総合の学であるという面がある。暗号理論にもそれは言えて、情報理論や符号理論、計算複雑性理論といった理論計算機科学などと、合同算術、数論、代数幾何、離散数学といった数学などが広く関係する。

1.1. 用語
-------

暗号理論で使われる用語。

暗号理論 - 暗号や暗号解読を扱う理論。本ページの記事名。
暗号技術  - 暗号に関する技術。暗号プリミティブや暗号プロトコルを駆使して、機密  ・完全性  ・認証  ・否認防止  などのセキュリティ機能を実現することを目的とする。鍵管理などの暗号を利用するために必要な技術も含む。
暗号学  - 暗号に関する学問
暗号[法]  - 暗号方式の構成法や性能、安全性などに関する研究。暗号術ということもある。
暗号解読[法]  - 暗号方式の解読法に関する研究。暗号分析、暗号解析ということもある。
暗号学者 
暗号研究者  - 暗号を専門的に研究する人。まれに平文を暗号文に変換する作業に従事する人を指すことがある。
暗号解読者  - 復号鍵を用いずに、暗号文を平文に戻したり、暗号文と平文を区別したり、暗号文から別の暗号文を生成することを試みる人。または、暗号文と平文の組から鍵を推定する人。まれに暗号文を復号する作業に従事する人を指すことがあるが、復号と解読は区別すべきである。
暗号プロトコル/暗号化プロトコル  - 暗号化と復号の手順
暗号プリミティブ  - 暗号方式を、元々の目的であった秘匿だけではなく、署名・認証などの基本的ツールに適応したもののこと。cipher, signature, hash などがある。別の用法として、主に公開鍵暗号方式で、要となるトラップドア関数と、パディング等の周辺部分に分けて、前者を暗号プリミティブと称することがある。
暗号方式 / 暗号システム / 暗号系  - 暗号化鍵  を用いて、平文  を暗号文  に変換する暗号化  アルゴリズムと、復号鍵  を用いて、暗号文を平文に変換する復号  アルゴリズム、鍵、平文、暗号文などからなるシステムのことである。
暗号アルゴリズム  / 暗号関数 - 暗号方式における暗号化および復号のアルゴリズム。
暗号化 
復号 
鍵生成 
暗号データ
暗号鍵 / 鍵 
暗号化鍵 
復号鍵 
メッセージ 
平文  / 明文 
暗号文 
暗号方式の実現手段に関する用語
共通鍵暗号方式 / 対称鍵暗号方式 - 暗号化鍵  と復号鍵  が同じ、あるいは片方の鍵から他方の鍵を容易に求めることができる暗号方式。
共通鍵  / 秘密鍵  / 共有鍵 
公開鍵暗号方式 / 非対称鍵暗号方式 - 暗号化鍵から復号鍵を求めること、または復号鍵から暗号化鍵を求めることが難しい暗号方式。
鍵ペア  - 公開鍵と秘密鍵の組。
公開鍵  - 公開鍵暗号方式における暗号化鍵。
秘密鍵 / 私有鍵 / 私用鍵 / プライベート鍵  - 公開鍵暗号方式における復号鍵。過去にはprivate keyの意味でsecret keyと記述することもあった。共通鍵暗号方式における共通鍵を秘密鍵と呼ぶこともあった。
公開鍵演算  - 公開鍵を用いた演算。暗号  の場合は暗号化  であり、署名  の場合は、検証  になる。
秘密鍵演算  - 秘密鍵を用いた演算。暗号  の場合は復号  であり、署名  の場合は、署名  になる。
暗号方式を応用した場合の用語
暗号 
サイファ化 
デサイファ化 
暗号化アルゴリズム 
復号アルゴリズム 
暗号化鍵 
復号鍵 
暗号文 
署名 
署名 
検証
署名鍵 
ボーフォート暗号 
連続鍵暗号 / 進行鍵暗号  /
自己鍵暗号 / 自動鍵暗号 
転置式暗号 / 転字式
図形転置暗号
スキュタレー 
レールフェンス暗号 
回転グリル型暗号
鍵式転置暗号
分置式暗号 / 挿入式暗号 / 隠字式 
カルダングリル 
混合式暗号
ADFGVX暗号  / VIC暗号 
暗号円盤
ホィール暗号機  、シリンダー 
M-94  、ストリップ多表暗号M-138A
機械式暗号
クリハ暗号機  / 九一式暗号機

ヒーバン暗号機 
エニグマ暗号機 
パープル暗号機 
ハゲリン暗号機 / M-209 
シガバ 
タイペックス  or タイプX 
バーナム暗号 
計算機ベースの暗号
共通鍵暗号
ブロック暗号
64bitブロック
DES / トリプルDES / CIPHERUNICORN-E / FEAL / MISTY1 / Blowfish / CAST-128 / IDEA / KASUMI / GOST / RC2 / TEA / MULTI2
128bitブロック
Lucifer / AES / Camellia / CIPHERUNICORN-A / RC6 / MARS / CAST-256 / Twofish / MISTY2 / MAGENTA / SEED / LOKI97 / Serpent
256bitブロック
SHACAL-2
other block size
RC5 
ストリーム暗号 / 逐次暗号
/ ワンタイムパッド 　one time pad
RC4 / MULTI-SO1 / FISH / WAKE / A5/1 / A5/2 / SORFR / SNOW
公開鍵暗号
RSA暗号 / RSA-OAEP / RSA-KEM / Rabin暗号 / HIME / Paillier暗号
EPOC
ElGamal暗号 / ACE Encrypt
楕円曲線暗号 / PSEC-KEM / ECIES
/ ナップサック暗号
Merkle-Hellmanナップサック暗号 / Chor-Rivestナップサック暗号
/ ラティス暗号
NTRU暗号
その他
物理暗号
量子暗号 / 量子鍵配送 / 量子秘匿通信
視覚復号型暗号
カオス暗号

1.1.1. デジタル署名
-------------

電子署名を実現する一番有力な方法がディジタル署名である。一般的に言って原理上、公開鍵暗号の発見によりディジタル署名が可能になった。

通常の署名
添付型署名
'////
//
ESIGN

ElGamal署名 / Schnorr署名 / DSA
'////
//
'////
//
'////
//
メッセージリカバリ署名
RSA-PSS-R
特殊機能な署名
ブラインド署名 
否認不可署名 
フェイルストップ署名 
多重署名
リング署名
グループ署名
代理署名
検証者指定可能署名 designated verifier signature
オブリビアス署名

1.1.2. ハッシュ関数
-------------

暗号学的ハッシュ関数
MD2 / MD4 / MD5 /
Secure Hash Algorithm 
SHA-0 /
SHA-1 /
SHA-2  /
SHA-3

1.1.3. 乱数
---------

暗号論的擬似乱数生成器
pseudorandom function

1.2. プロトコル
----------

暗号プロトコルは、暗号化に関係するプロトコルなどから成る。または、より広い情報セキュリティ一般に関係するセキュリティプロトコルなど。

認証
相手認証 / 相互認証 / 片側認証 / ユーザ認証
Diffie-Hellman認証 / Schnorr認証
メッセージ認証 / メッセージ認証子
DES-MAC / HMAC / 鍵付きハッシュ関数
チャレンジ・レスポンス
公開鍵証明書 
鍵共有
Diffie-Hellman鍵共有
ビットコミットメント
マルチパーティ計算 / 共同計算
コイン投げ
メンタルポーカー
ビザンチン将軍問題
紛失通信 / 忘却通信路 / 
ゼロ知識証明 / ゼロ知識対話証明  
暗号プロトコル応用
時刻証明 / タイムスタンプ
電子投票
電子入札
電子マネー
電子公証
依頼計算 server-aid computation
同時交換 fair exchange
ミックスネット mix net
秘密分散 
検証可能秘密分散 
閾値暗号 
汎用的結合可能性 
UCコミットメント
UCゼロ知識証明

2. 研究内容
-------

2.1. 暗号の構成要素・構成法
----------------

2.1.1. ブロック暗号の構成
----------------

ブロック暗号は、データスクランブル部と、鍵スケジュール部の2つを主な要素とし、データスクランブル部は、ラウンドの繰返し構造になっているものが多い。Product cipherの基本的な構成法に、Feistel構造とSPN構造の2つがある。

Product cihper
Feistel構造 / フェイステル・ネットワーク Feistel network
SPN構造 
F関数 / Sボックス S-box
鍵拡大 / キースケジュール / ラウンド鍵
初期変換 / 最終変換
暗号利用モード

2.1.2. ストリーム暗号の構成
-----------------

鍵系列
線形フィードバックシフトレジスタ

2.1.3. 公開鍵暗号の構成
---------------

公開鍵暗号の要はトラップドア関数であり、安全なトラップドア関数の存在を仮定して、安全な公開鍵暗号方式を構成する方法が研究されている。 トラップドア関数は、まだ数個しか発見されておらず、新しいトラップドア関数の発見もテーマの一つである。

一方向性関数 one way function
トラップドア関数 / 落し戸付き一方向性関数
ハードコア述語 / ハードコア関数 
RSAモジュラス 
ESIGNモジュラス 
Fiat-Shamirヒューリスティック

2.1.4. ハッシュ関数の構成
----------------

暗号学的ハッシュ関数は、可変長入力、固定長出力の関数で、入力から出力を求めることは容易であるが、出力から入力を求めること、出力が同一になるような2個の入力を求めることが計算量的に困難である等の性質を満たすハッシュ関数である。

ほとんどのハッシュ関数は、可変長の入力メッセージ m をブロック単位に分割し、圧縮関数 H を h_i = H のように繰り返し使って、出力 h_n を求める構成になっている。代表的にはMerkle-Damgård constructionがある。SHA-3はそれとは異なり、出力よりも大きい内部状態を持ち、出力の時点で大きな内部状態を圧縮するスポンジ構造をしている。

基本構造
反復型 iterated
:en:Merkle-Damgård construction
Enveloped MD
MD-Strengthening 圧縮関数については、ハッシュ専用の関数を開発することの他に、ブロック暗号を利用した構成法が研究されている。ブロック暗号ベースの構成法では、構成可能な種類の数え上げや理想暗号モデル E を用いた安全性証明、構成法としての最適性などが検討されている。

圧縮関数の構成 :en:one-way compression function
ハッシュ専用関数
MDx 等
代数的関数
ブロック暗号ベース
単ブロック長
Davies-Meyer法 h' = h xor E
Matyas-Meyer-Oseas法 h' = m xor E,m), ISO/IEC 1-118-2
Miyaguchi-Preneel法 h' = m xor E,m) xor h
倍ブロック長
MDC-2、MDC-4

2.1.5. その他
----------

鍵 
ハイブリッド暗号 / KEM / DEM
多重暗号

2.2. 暗号の性能・効率
-------------

暗号化・復号に必要な演算量や、ハード・ソフト実装時の処理速度などについて、実測値の測定、暗号方式間の比較や実装方法の効率化などが研究されている。

また、安全性の指標ともなる様々な特性値や、その求め方も研究されている。暗号にとって重要な特性値には、暗号解読によって発見されたものがある。

共通鍵暗号は、公開鍵暗号で代用できる場合があるため、スピードや鍵サイズ、実装コストなどで公開鍵暗号よりもメリットがあることが求められる。

ストリーム暗号は、ブロック暗号の一つの利用モードとして実現できるため、ストリーム暗号の存在理由として、スピードが速いこと等が求められる。

データ量
ラウンド数
ビット演算量
有効鍵
線形・差分特性
ビットバランス性

2.3. 暗号の安全性
-----------

一般に、安全性の目標と攻撃条件をモデル化することで暗号を攻撃する問題を定義し、それが誰もが難しいと想定している問題と等価であることを示すことで、安全性の評価とする。その際、攻撃条件だけではなく攻撃アルゴリズムも限定して「その範囲」で安全であるということもある。証明の際にさらに仮定やモデルを導入することもある。また、現代暗号では、計算量的安全性があることを安全性の前提としているものが多い。このことは計算機の進歩や時間の経過により安全性が低下していくことを意味する。

安全性の表現の例：「○○○暗号は、ROM仮定の下、DLPが困難であれば、IND-CCA2 の安全性証明がある」

暗号の安全性では、上記のような安全性に影響する事項を見出して、より厳密な定義を構築していくことと、その定義を満たす暗号の性質が研究されている。

その他、実際の暗号の安全性は、暗号方式の理論的安全性よりも、実装上、運用上の問題の有無によってより大きく影響を受けることがある。安全とされる暗号方式や暗号製品を採用するだけではなく、平文の管理や鍵の管理などにも注意が必要である。

安全性の目標
完全秘匿 perfect secrecy
強秘匿 / セマンティックセキュア  semantic secure :en:Semantic security
頑強性 / 非展性  non-malleable :en:Malleability 
平文非展性
鍵非展性 → 暗号と群も参照
識別不能性  indistinguishable
平文識別不能性 :en:ciphertext indistinguishability
鍵識別不能性
攻撃条件
既知暗号文攻撃  :en:ciphertext-only attack
既知平文攻撃  :en:known-plaintext attack
既知平文差分攻撃
選択平文攻撃  :en:chosen plaintext attack
選択暗号文攻撃  :en:chosen ciphertext attack
適応的選択暗号文攻撃  :en:adaptive chosen ciphertext attack
関連鍵攻撃 :en:related-key attack
攻撃アルゴリズム
総当たり攻撃 / 全数探索 / :en:Brute force attack exhaustive key search
誕生日攻撃 :en:birthday attack
タイム・メモリ・トレードオフ
中間一致攻撃 :en:meet-in-the-middle attack
頻度分析  :en:frequency analysis 
カシスキ・テスト :en:Kasiski examination
一致反復率 :en:index of coincidence

差分解読法 :en:differential cryptanalysis 
不能差分暗号解読
切詰差分解読
高階差分解読
Square攻撃
ブーメラン攻撃 :en:boomerang attack
補間攻撃 
線形和攻撃
線形解読法 :en:linear cryptanalysis 
差分線形攻撃 :en:differential-linear attack
丸め線形攻撃
スライド攻撃 :en:slide attack 
カイ2乗攻撃
mod n攻撃 :en:mod n cryptanalysis
XSL攻撃 :en:XSL attack
リプレイ攻撃 :en:replay attack
ビット反転攻撃 :en:bit-flipping attack
中継攻撃 :en:man in the middle attack
辞書アタック / 辞書攻撃 :en:dictionary attack
素因数分解 :en:integer factorization
格子基底縮小 lattice reduction, LLL :en:Lenstra-Lenstra-Lovász lattice reduction algorithm
根拠となる問題 / それに関する仮定
素因数分解問題 
RSA問題 / RSA仮定 :en:RSA problem
flexible RSA問題 / 強RSA仮定 :en:strong RSA assumption
離散対数問題 
DH問題 / Diffie-Hellman仮定
DDH問題 / Decision-Diffie-Hellman仮定 :en:decisional Diffie-Hellman assumption
ナップサック問題 :en:knapsack problem
部分和問題 :en:subset sum problem
ラティス問題
SVP / CVP
巡回セールスマン問題 :en:traveling salesman problem
証明に関する手法 / 仮定 / モデル
確率的証明 probabilistically cheacable proofs
ランダムオラクルモデル  / ランダムオラクル仮定
シミュレーション手法
ハイブリッドアーギュメント
形式的手法 formal method
帰着の効率
識別不能
negligible / overwhelming
安全性の前提
情報理論的安全性
計算量的安全性
指数関数時間
準指数関数時間
多項式時間
そのほか
サイドチャネル攻撃 :en:side channel attack
故障利用攻撃
タイミング攻撃 :en:timing attack
キャッシュ攻撃
音響解析攻撃 :en:acoustic cryptanalysis
電力解析攻撃 :en:power analysis
単純電力解析攻撃 :en:simple power analysis
差分電力解析攻撃 :en:differential power analysis
電磁波解析攻撃
締め上げ暗号分析 :en:rubber-hose cryptanalysis暗号  以外の暗号プリミティブについても、同様な安全性の研究がなされている。

署名
安全条件
全面的解読
一般的偽造
選択的偽造
存在的偽装 :en:existential forgery
攻撃条件
直接攻撃
既知文書攻撃
一般的選択文書攻撃
指向的選択文書攻撃
適応的選択文書攻撃
ハッシュ関数
プレイメージ 
2ndプレイメージ
コリジョン 
乱数 - 暗号の観点からの要請
暗号論的擬似乱数列生成器
pseudorandom function

2.4. 暗号理論に使用する数学
----------------

素数判定
素体
群
数論
:en:Modular arithmetic
:en:Modular multiplicative inverse
素数
ブラム数
フェルマーの小定理
オイラーのトーティエント関数
中国の剰余定理
平方剰余 
ガロア体
有限体内の離散対数

3. 歴史
-----

4. 参考文献
-------

Claude Elwood Shannon, "Communication theory of secrecy system", Bell System Technial Journal, Vol.28-4, pp.656-715, Oct. 1949.
Whitfield Diffie, Martin E. Hellman, "New directions in cryptography", IEEE Trans. Information Theory, IT-22,6, pp.644-654, Nov. 1976.
Ron L. Rivest, A. Shamir, Leonard M. Adleman, "A method for obtaining digital signatures and public-key cryptosystems", Communications of the ACM, Vol.21, pp.120-126, Feb. 1978. 
US National Bureau of Standards  , "Data Encryption Standard", Federal Information Processing Standards Publication 46 , 1977.
Ran Canetti, "Universally Composable Security: A New Paradigm for Cryptographic Protocols", Proceeding s IEEE Symposium on Foundations of Computer Science, FOCS 2001, pp.136-145, Oct. 2001.

5. 脚注
-----

5.1. 注釈
-------

6. 関連項目
-------

暗号関係の書籍 / 暗号研究者の一覧
暗号評価プロジェクト ---- CRYPTREC / NESSIE
暗号アルゴリズム標準化 -- ISO/IEC_18033
暗号アプリケーション ---- PGP / GnuPG / TLS / SSH
暗号と情報セキュリティシンポジウム  - 新しい理論はここで発表されることが多い。

7. 外部リンク
--------

[1]