Yrurtj

暗号理論（あんごうりろん）の記事では暗号、特に暗号学に関係する理論について扱う。Category:暗号技術も参照。

3 研究内容
- 3.1 暗号の構成要素・構成法
  - 3.1.1 ブロック暗号の構成
  - 3.1.2 ストリーム暗号の構成
  - 3.1.3 公開鍵暗号の構成
  - 3.1.4 ハッシュ関数の構成
  - 3.1.5 その他
- 3.2 暗号の性能・効率
- 3.3 暗号の安全性
- 3.4 暗号理論に使用する数学

4 歴史

5 参考文献

6 注

7 関連項目

8 外部リンク

概要

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

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

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

暗号系 (cryptosystem) 、すなわち暗号化と復号、といった手続きの構成方法や性能・安全性などに関する研究

暗号や電子署名といった守秘 (confidentiality) や完全性 (integrity) を実現する、暗号アルゴリズムや暗号プロトコルの研究

暗号解読（cryptanalysis）

暗号理論は暗号学の一分野であり、暗号学の全ては理論ではカバーしきれない。古典的な暗号に比べれば現代の暗号（現代暗号）は理詰めで構成されている。それでも、暗号学としては、その運用や関与する人間の不注意といったヒューマンファクタなども考慮しなければならない。（「暗号の連鎖（chain）の強さは、最も強い環（link）の強さしかない」ということは変わっていない。）

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

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

用語

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

「暗号#用語」も参照

暗号理論 - 暗号や暗号解読を扱う理論。本ページの記事名。

暗号技術 (cryptographic techniques) - 暗号に関する技術。暗号プリミティブや暗号プロトコルを駆使して、機密 (confidentiality) ・完全性 (integrity) ・認証 (authentication) ・否認防止 (non-repudiation) などのセキュリティ機能を実現することを目的とする。鍵管理などの暗号を利用するために必要な技術も含む。

暗号学 (cryptology) - 暗号に関する学問
- 暗号[法] (cryptography) - 暗号方式（とその応用）の構成法や性能、安全性などに関する研究。暗号術ということもある。
- 暗号解読[法] (cryptanalysis) - 暗号方式（とその応用）の解読法に関する研究。暗号分析、暗号解析ということもある。

暗号学者 (cryptologist)
- 暗号研究者 (cryptographer) - 暗号を専門的に研究する人（暗号研究者の一覧）。まれに平文を暗号文に変換する作業に従事する人（暗号師）を指すことがある。
- 暗号解読者 (cryptanalyst) - 復号鍵を用いずに、暗号文を平文に戻したり、暗号文と平文を区別したり、暗号文から別の暗号文を生成することを試みる人。または、暗号文と平文の組から鍵を推定する人。まれに暗号文を復号する作業に従事する人を指すことがあるが、復号と解読は区別すべきである。

暗号プロトコル/暗号化プロトコル (cryptographic protocol/encryption protocol) - 暗号化と復号の手順

暗号プリミティブ (cryprographic 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年に提案された公開鍵暗号は、従来、秘匿用途であった暗号を認証(署名)に用いることを可能にした。秘匿と認証以外にも、様々な特殊な機能（メカニズム）の暗号が研究されている。

研究対象

暗号プリミティブ

暗号

主要なものは「コード」と「サイファー」であるが（コード (暗号) と en:Cipher を参照）、他にも多数の分類などがある。最古の文字といわれるヒエログリフでも暗号と推測される文字が見つかっていて、長い歴史を持つ。ここでは歴史的なものの含めて主な暗号を分類・一覧する。

詳細は「暗号」を参照

筆記・道具ベースの暗号
- 換字式暗号 (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)
      - ドッペルカステン
  - 多表式換字暗号 / 多アルファベット換字式暗号 (en:Polyalphabetic cipher)
    - 正方形の[換字]表 (トリテミスの多表） (en:tabula recta)
    - ヴィジュネル暗号 (ビジネル暗号ということもある） (en:Vigenère cipher)
    - ボーフォート暗号 (Beaufort cipher)
    - 連続鍵暗号 / 進行鍵暗号 (en:running key cipher) /
  - 自己鍵暗号 / 自動鍵暗号 (en:autokey cipher)
- 転置式暗号 / 転字式（en:transposition cipher）
  - 図形転置暗号
    - スキュタレー (en:Scytale)
    - レールフェンス暗号 (en:Rail Fence cipher)
  - 回転グリル型暗号
  - 鍵式転置暗号
- 分置式暗号 / 挿入式暗号 / 隠字式 (acrostic,折句)
  - カルダングリル (en:Cardan grille、あるいはカルダーノグリル、Cardano grille)
- 混合式暗号
  - ADFGVX暗号 (en:ADFGVX cipher) / VIC暗号 (en:VIC cipher)
- 暗号円盤
  - ホィール暗号機 (wheel) 、シリンダー (cylinder)
  - M-94 (en:M-94) 、ストリップ多表暗号M-138A

機械式暗号（ロータマシン（en:rotor machine）等）
- （円盤式）
  - クリハ暗号機 (en:Kryha) / 九一式暗号機
- (ロータ式)
  - ヒーバン暗号機 (en:Hebern rotor machine)
  - エニグマ暗号機 (en:Enigma machine)
  - パープル暗号機（九七式欧文印字機） (en:PURPLE)
  - ハゲリン暗号機（Hagelin） / M-209 (en:M-209)
  - シガバ (en:SIGABA or ECM MarkII)
  - タイペックス (en:Typex) or タイプX (Type X)
- （テープ式）
  - バーナム暗号（ヴァーナム暗号ということもある） (en:Vernam cipher)

計算機ベースの暗号
- 共通鍵暗号
  - ブロック暗号
    - 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 (variable)
  - ストリーム暗号 / 逐次暗号
    - / ワンタイムパッド　one time pad
    - RC4 / MULTI-SO1 / FISH / WAKE / A5/1 / A5/2 / SORFR / SNOW
- 公開鍵暗号
  - （素因数分解問題）
    - RSA暗号 / RSA-OAEP / RSA-KEM / Rabin暗号 / HIME(R) / Paillier暗号
    - EPOC
  - （離散対数問題）
    - ElGamal暗号 / ACE Encrypt
    - 楕円曲線暗号 / PSEC-KEM / ECIES
  - （ナップサック問題） / ナップサック暗号
    - Merkle-Hellmanナップサック暗号 / Chor-Rivestナップサック暗号
  - （ラティス問題） / ラティス暗号
    - NTRU暗号
  - （多次[元]多変数、多変数多項式問題）

その他
- 物理暗号
  - 量子暗号 / 量子鍵配送 / 量子秘匿通信
  - 視覚復号型暗号
- カオス暗号

デジタル署名

詳細は「デジタル署名」を参照

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

通常の署名
- 添付型署名
  - （素因数分解問題）
    - RSA署名 / RSA-PSS (en:RSA-PSS) / ACE Sign
    - ESIGN
  - (離散対数問題)
    - 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) /
- SHA-3

乱数

暗号論的擬似乱数生成器

pseudorandom function（en:Pseudorandom function family を参照。「乱数列」（random numbers）ではないことに注意^[2]）

プロトコル

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

認証
- 相手認証 / 相互認証 / 片側認証 / ユーザ認証
  - Diffie-Hellman認証 / Schnorr認証
- メッセージ認証 / メッセージ認証子
  - DES-MAC / HMAC / 鍵付きハッシュ関数
- チャレンジ・レスポンス
- 公開鍵証明書 (→ PKI)

鍵共有
- Diffie-Hellman鍵共有

ビットコミットメント

マルチパーティ計算 / 共同計算
- コイン投げ
- メンタルポーカー
- ビザンチン将軍問題
- 紛失通信 / 忘却通信路 / (en:oblivious transfer)

ゼロ知識証明 / ゼロ知識対話証明 (ZKIP) (en:Zero-knowledge proof)

暗号プロトコル応用
- 時刻証明 / タイムスタンプ
- 電子投票
- 電子入札
- 電子マネー
- 電子公証

依頼計算 server-aid computation

同時交換 fair exchange

ミックスネット mix net

秘密分散 (en:Secret sharing)
- 検証可能秘密分散 (en:verifiable secret sharing)

閾値暗号 (threshold cryptosystem)

汎用的結合可能性 (universal composability)
- UCコミットメント
- UCゼロ知識証明

研究内容

暗号の構成要素・構成法

ブロック暗号の構成

ブロック暗号は、データスクランブル部と、鍵スケジュール部の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)

Fiat-Shamirヒューリスティック

ハッシュ関数の構成

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

ほとんどのハッシュ関数は、可変長の入力メッセージ m をブロック単位に分割（最初のブロックをm_1、最後のブロックをm_nとする。m_0は所定の初期値）し、圧縮関数 H を h_i = H(h_{i-1}, m_i) のように繰り返し使って、出力 h_n を求める構成になっている。

基本構造（全体構造）
- 反復型 iterated
  - en:Merkle-Damgård construction
  - Enveloped MD
  - MD-Strengthening (パディング)

圧縮関数については、ハッシュ専用の関数を開発することの他に、ブロック暗号を利用した構成法が研究されている。ブロック暗号ベースの構成法では、構成可能な種類の数え上げや理想暗号モデル E を用いた安全性証明、構成法としての最適性などが検討されている。

圧縮関数の構成 en: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 en:Semantic security
- 頑強性 / 非展性 (NM) non-malleable en:Malleability (cryptography)
  - 平文非展性
  - 鍵非展性 → 暗号と群も参照
- 識別不能性 (IND) indistinguishable
  - 平文識別不能性 en:ciphertext indistinguishability
  - 鍵識別不能性

攻撃条件
- 既知暗号文攻撃 (COA) en:ciphertext-only attack
- 既知平文攻撃 (KPA) en:known-plaintext attack
- 既知平文差分攻撃
- 選択平文攻撃 (CPA) en:chosen plaintext attack
- 選択暗号文攻撃 (CCA) en:chosen ciphertext attack
- 適応的選択暗号文攻撃 (CCA2) 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 (cryptanalysis)
    - カシスキ・テスト en:Kasiski examination
    - 一致反復率 en:index of coincidence
- (現代暗号)
  - 差分解読法（差分暗号解読） en:differential cryptanalysis (Biham,1989)
    - 不能差分暗号解読
    - 切詰差分解読（丸め差分攻撃）(truncated differential attack)
    - 高階差分解読
      - Square攻撃
    - ブーメラン攻撃 en:boomerang attack
    - 補間攻撃 (Jakobsen, Knudsen, 1997)
      - 線形和攻撃
  - 線形解読法（線形暗号解読） en:linear cryptanalysis (Matsui,1993)
    - 差分線形攻撃 en:differential-linear attack
    - 丸め線形攻撃
  - スライド攻撃 en:slide attack (David Wagner, Alex Biryukov, 1999)
  - カイ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

根拠となる問題 / それに関する仮定
- 素因数分解問題 (IFP)
  - RSA問題 / RSA仮定 en:RSA problem
  - flexible RSA問題 / 強RSA仮定 en:strong RSA assumption
- 離散対数問題 (DLP)
  - 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
- ランダムオラクルモデル (ROM) / ランダムオラクル仮定
- シミュレーション手法
- ハイブリッドアーギュメント
- 形式的手法 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:TEMPEST）
- 締め上げ暗号分析 en:rubber-hose cryptanalysis

暗号 (Cipher) 以外の暗号プリミティブについても、同様な安全性の研究がなされている。

署名
- 安全条件
  - 全面的解読
  - 一般的偽造
  - 選択的偽造
  - 存在的偽装 en:existential forgery
- 攻撃条件
  - 直接攻撃
  - 既知文書攻撃
  - 一般的選択文書攻撃
  - 指向的選択文書攻撃
  - 適応的選択文書攻撃

ハッシュ関数
- プレイメージ (preimage)
- 2ndプレイメージ
- コリジョン (collision)

乱数 - 暗号の観点からの要請
- 暗号論的擬似乱数列生成器
- pseudorandom function（en:Pseudorandom function family、「乱数列」（random numbers）ではないことに注意^[2]）

暗号理論に使用する数学

素数判定

素体

群

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

歴史

「暗号史」を参照

参考文献

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. (最初の発表は1977だが論文公開は78年になった)

US National Bureau of Standards (NBS, 現NIST) , "Data Encryption Standard", Federal Information Processing Standards Publication 46 (FIPS-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.

注

^ 「承認 (authorization)」とまぎらわしいので注意。

^ ^a^b暗号学徒ならば、英語版の「Pseudorandom functions are not to be confused with pseudorandom generators (PRGs).」から始まる記述を最後まで読んできちんと把握すること。両者の間には重要な特性の違いがある。

外部リンク

暗号学会 International Association for Cryptologic Research

[1] 「承認 (authorization)」とまぎらわしいので注意。

[PRF-2] 暗号学徒ならば、英語版の「Pseudorandom functions are not to be confused with pseudorandom generators (PRGs).」から始まる記述を最後まで読んできちんと把握すること。両者の間には重要な特性の違いがある。

搜尋此網誌