暗号理論

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

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

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

暗号の理論の主な分野には、以下のようなものがある。 暗号系 (cryptosystem) 、すなわち暗号化と復号、といった手続きの構成方法や性能・安全性などに関する研究 暗号や電子署名といった守秘 (confidentiality) や完全性 (integrity) を実現する、暗号アルゴリズムや暗号プロトコルの研究 暗号解読（cryptanalysis） 暗号理論は暗号学の一分野であり、暗号学の全ては理論ではカバーしきれない。古典的な暗号に比べ、現代暗号はアルゴリズムの詳細を公開した上で安全性を数学的に論じる手法が確立されている。

それでも、暗号学としては、その運用や関与する人間の不注意といったヒューマンファクタなども考慮しなければならない。（「暗号の連鎖（chain）の強さは、最も弱い環（link）の強さしかない」ということは変わっていない。）

コンピュータセキュリティやネットワークセキュリティ、より総合的には情報セキュリティと暗号や暗号理論とは密接な関わりがある。例えば、（論理的な）アクセス制御は、「ユーザが誰であるか」という認証（authentication「承認 (authorization)」とまぎらわしいので注意。）に従って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 operation) - 秘密鍵を用いた演算。暗号 (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) ストリーム暗号 / 逐次暗号 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署名 / / 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）ではないことに注意暗号学徒ならば、英語版の「Pseudorandom functions are not to be confused with pseudorandom generators (PRGs).」から始まる記述を最後まで読んできちんと把握すること。両者の間には重要な特性の違いがある。）

プロトコル 暗号プロトコルは、暗号化に関係するプロトコル（暗号化プロトコル）などから成る。または、より広い情報セキュリティ一般に関係するセキュリティプロトコルなど。 認証 相手認証 / 相互認証 / 片側認証 / ユーザ認証 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 を求める構成になっている。代表的にはMerkle-Damgård constructionがある。SHA-3はそれとは異なり、出力よりも大きい内部状態を持ち、出力の時点で大きな内部状態を圧縮するスポンジ構造をしている。

基本構造（全体構造） 反復型 iterated :en:Merkle-Damgård construction Enveloped MD