暗号理論

出典: フリー百科事典『ウィキペディア（Wikipedia）』
2013年12月26日 (木) 20:32時点におけるClaw of Slime (トーク)による版 (→‎デジタル署名 (digital signature))
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先: 案内、 検索

暗号理論（あんごうりろん）とは、暗号における暗号化 (encryption) および復号 (decryption) と暗号解読 (cryptanalysis) を扱う理論のこと。

暗号は、cryptography、cipher、codeと対応する言葉であり、秘密の表記そのもの、またはその表記法を指すことがある。

暗号理論では主に次の二つを扱う。

  1. 暗号系 (cryptosystem) の構成方法や性能・安全性などに関する研究
  2. 暗号や電子署名といった守秘 (confidentiality) や完全性 (integrity) を実現する、暗号アルゴリズムや暗号プロトコルの研究

暗号理論では、主として、アルゴリズムやプロトコルによってセキュリティ機能を実現する研究（情報セキュリティ）がなされており、OSやネットワークの特徴を生かしてセキュリティ機能を実現する研究（コンピュータセキュリティやネットワークセキュリティ）と区別される。

暗号理論には、情報理論、符号理論、計算複雑性理論といった計算機科学、数論や代数幾何、離散数学といった数学、時には力学系などの物理学の知見が用いられることもある。

概要

用語

暗号理論で使われる用語。暗号の用語も参照。

  • 暗号理論 - 暗号や暗号解読を扱う理論。本ページの記事名。
  • 暗号技術 (cryptographic techniques) - 暗号に関する技術。暗号プリミティブや暗号プロトコルを駆使して、機密 (confidentiality) ・完全性 (integrity) ・認証 (authentication) ・否認防止 (non-repudiation) などのセキュリティ機能を実現することを目的とする。鍵管理などの暗号を利用するために必要な技術も含む。
  • 暗号学 (cryptology) - 暗号に関する学問
    • 暗号[法] (cryptography) - 暗号方式（とその応用）の構成法や性能、安全性などに関する研究。暗号術ということもある。
    • 暗号解読[法] (cryptanalysis) - 暗号方式（とその応用）の解読法に関する研究。暗号分析、暗号解析ということもある。
  • 暗号学者 (cryptologist)
    • 暗号研究者 (cryptographer) - 暗号を専門的に研究する人（暗号研究者の一覧）。まれに平文を暗号文に変換する作業に従事する人（暗号師）を指すことがある。
    • 暗号解読者 (cryptanalyst) - 復号鍵を用いずに、暗号文を平文に戻したり、暗号文と平文を区別したり、暗号文から別の暗号文を生成することを試みる人。または、暗号文と平文の組から鍵を推定する人。まれに暗号文を復号する作業に従事する人を指すことがあるが、復号と解読は区別すべきである。
  • 暗号プロトコル (cryptographic 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)
  • 暗号方式の実現手段に関する用語
    • 共通鍵暗号方式 / 対称鍵暗号方式 - 暗号化鍵 (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)
      • ハッシュ値 / フィンガープリント / ハッシュ
    • 擬似乱数
      • シード (seed)
  • 暗号方式の主な用途
    • 秘匿通信 (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年代前半には、ゼロ知識対話証明やマルチパーティ計算などの暗号プロトコルの安全性証明を統一的に扱うフレームワークの研究が進んだ。(stub)

解読

換字や転置を組み合わせた単純な古典暗号は、頻度分析で解読可能であることが9世紀頃には知られていて、15世紀から16世紀にかけて、より複雑な多表式暗号がいくつか提案されていた。しかし、多表式暗号は手作業で行うには暗号化・復号の作業が煩雑であった為、あまり使用されず、換字や転置とコード式と組み合わせるなどして複雑さを増した暗号法が長い間使われていた。

それらの方式は、沢山の暗号文を時間をかけて分析・推定することでいつ解読されるか分からないもので、実際に解読された例もいくつか知られている。 入手した暗号文を分析して、（平文の）言語の統計的性質を手がかりとして、使用された暗号法（の逆変換）を推測して平文を求めるという、パズルを解くような暗号解読が行われた。 19世紀には100以上の暗号法が既知のものとなっていたようである（17世紀に使用されたルイ14世の大暗号も19世紀になって解読された）。 ここでは、言語に関する知識やセンス（アルファベットの出現頻度やアナグラムを解くセンス）が中心であった。

機械式暗号の登場（20世紀）は、速くて強い暗号が必要とされたことが背景にある。(stub)

機械式暗号の解読には、多数の組合せから解を見つけることが必要になり、カンや閃きだけでは解読できなくなった。暗号解読は、暗号機を入手して分析することの他に、いかに容易な解読方法を見つけるかということが問題になった。ここでは言語学ではなく数学が中心となる。

現代暗号では、暗号法の推測や逆変換の困難さではなく、暗号化・復号のアルゴリズムは既知として、暗号鍵の推測が困難であるような暗号方式の実現を目標とする。参照：ケルクホフスの原理

現代暗号での暗号解読は、敵の暗号文を解読するという行為ではなく、公開された暗号法を分析し、平文や鍵を求める（数学の問題を解くのと同様な）アルゴリズムを見つけたり、隠れた問題を指摘するという研究となった。ここでの暗号法と暗号解読法の関わりは、大まかに次のように進展している。

S-1 ある暗号研究者が提案した暗号を別の暗号研究者が分析して解読方法を見つけ、さらに改良された暗号が提案されたり、さらに解読方法も改良されたりした。ここでは、暗号の問題点を見つけるために暗号解読が必要とされ、暗号法の発表と同様にそれらの解読に関する発表が行われた。
S-2 既存の暗号解読法に対して安全であることを主張&証明する暗号が提案され、さらに、それ以外の暗号解読法の発見が望まれた。実際に安全と思われていた暗号に暗号解読法が発表されたりした。
S-3 理想的な暗号を定義し、実際の暗号が理想的暗号と計算量的識別不能であることの証明を行うことが目的となった（暗号文が乱数と区別できない、あるいは、暗号関数が擬似ランダム置換族と区別できないような暗号方式等）。

S-3のような安全性証明可能な暗号方式が完成すると、暗号の安全性は根拠となる問題（素因数分解アルゴリズムの改良や量子コンピュータの実現等）や暗号以外（平文や鍵、装置の運用等）の問題に帰着されて、計算量的な制約やモデルの仮定、証明の不備などを除くと暗号解読は不可能であることを意味する。ここでは暗号解読法はもはや不要なのかは分からないが、少なくとも設計&解読の繰り返しで強い暗号を作る時代ではなくなることを意味すると考えられる。 暗号解読 (cryptanalysis) に関するメイン記事：暗号解読を参照。

  • 信頼性の低い暗号
    • アルゴリズムが既知となった古典暗号
    • 計算量的安全性の低い現代暗号
    • 鍵の全数探索よりも効率的な解読法が存在する現代暗号
    • 安全性の証明に不備がある現代暗号（第2期）

拡張

1976年に提案された公開鍵暗号は、従来、秘匿用途であった暗号を認証(署名)に用いることを可能にした。秘匿と認証以外にも、様々な特殊な機能（メカニズム）の暗号が研究されている。 (stub)

研究対象

暗号プリミティブ

主に現代暗号で公開鍵暗号の発明によって、暗号方式は、暗号 (cipher) だけではなく、署名や認証にも応用可能になった。それらはセキュリティ機能を実現するための基本的ツールとなっている。

暗号 (cipher)

最古の文字といわれるヒエログリフでも暗号と推測される文字が見つかっていて、長い歴史を持つ。ここでは歴史的なものの含めて主な暗号を分類・一覧する。 詳細は各記事、暗号 (cipher) に関するメイン記事：暗号を参照。

デジタル署名 (digital signature)

電子署名を実現する一番有力な方法がデジタル署名である。公開鍵暗号として有名なRSAは、デジタル署名を実現できる方法として最初に公開された方法でもある。RSA以前には、DiffieとHellmanによるDH鍵共有法が知られていて、DH法で共有した鍵をワンタイムパッドに用いることで暗号は可能であったが、署名や認証を実現する方法は公開されていなかった。

  • 通常の署名
    • 添付型署名
    • メッセージリカバリ署名
      • RSA-PSS-R
  • 特殊機能な署名
    • ブラインド署名 (blind signature)
    • 否認不可署名 (undeniable signature)
    • フェイルストップ署名 (fail-stop signature)
    • 多重署名
    • リング署名
    • グループ署名
    • 代理署名
    • 検証者指定可能署名 designated verifier signature
    • オブリビアス署名

ハッシュ関数 (hash function)

(stub)

擬似乱数 (pseudorandom)

(stub)

暗号プロトコル

(stub)

研究内容

暗号の構成要素・構成法

(stub)

ブロック暗号の構成

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

ストリーム暗号の構成

(stub)

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

公開鍵暗号の構成

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

ハッシュ関数の構成

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

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

圧縮関数については、ハッシュ専用の関数を開発することの他に、ブロック暗号を利用した構成法が研究されている。ブロック暗号ベースの構成法では、構成可能な種類の数え上げや理想暗号モデル 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
  • 多重暗号

(stub)

暗号の性能・効率

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

また、安全性の指標ともなる様々な特性値や、その求め方（上限や下限、近似計算）も研究されている。暗号にとって重要な特性値には、暗号解読によって発見されたものがある。 (stub)

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

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

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

暗号の安全性

暗号アルゴリズムが安全であるか？を直接に示すことは、P対NP問題と同じくらい難しいことだと考えられている。 そこで、安全性の目標と攻撃条件をモデル化することで暗号を攻撃する問題を定義し、それが誰もが難しいと想定している問題（安全性の根拠となる問題）と等価であることを示す証明を行うことで、安全性の証明とすることがある。 その際、攻撃条件だけではなく攻撃アルゴリズムも限定して「その範囲」で安全である（目標が達成されている）ということもある。 証明の際にさらに仮定やモデルを導入することもある（問題が等価であることの定義など）。 また、現代暗号では、計算量的安全性（解読に要する計算量が膨大であること、例：指数時間要する）があることを安全性の前提としているものが多い。 このことは計算機の進歩や時間の経過により安全性が低下していくことを意味する。 また、量子計算機のように現在の計算機とは異なる計算能力を持つ計算機が実現した場合にも、影響を受ける。 そのため、長期間保存する文書の安全性には情報理論的安全性が必要と言われることもある。

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

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

その他、実際の暗号の安全性は、暗号方式の理論的安全性よりも、実装上、運用上の問題の有無によってより大きく影響を受けることがある。安全とされる暗号方式や暗号製品を採用するだけではなく、平文の管理（例えば個人情報の扱い）や鍵の管理などにも注意が必要である。 暗号解読の仮定 も参照。


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

  • 署名
    • 安全条件
    • 攻撃条件
      • 直接攻撃
      • 既知文書攻撃
      • 一般的選択文書攻撃
      • 指向的選択文書攻撃
      • 適応的選択文書攻撃
  • ハッシュ関数
    • プレイメージ (preimage)
    • 2ndプレイメージ
    • コリジョン (collision)
  • 擬似乱数 - 暗号学的に安全な擬似乱数
    • 予測不能性 / hard-core predicate

暗号理論に使用する数学

参考文献

  • 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.

関連項目

外部リンク


「http://wikippe.e-do-match.com/index.php?title=暗号理論&oldid=36100」から取得