暗号解読
暗号解読（あんごうかいどく、英: cryptanalysis）とは、暗号を解読すること、あるいは解読法に関する研究を指す。
概要
編集暗号の解読とは、暗号文を作成するのに用いた秘密情報（秘密の表記法や秘密の鍵など）にアクセスすることなく、暗号文を平文に戻すことである。
これに対して、秘密情報を用いて暗号文を平文に戻すことは復号といい、研究者は復号と解読とを区別する。 英語では、復号を decryption といい、解読を cryptanalysis という。
他人に知られたくない情報を秘匿する手段として暗号が生まれるのと同時に、秘密を暴くための暗号解読も生まれたと考えられる。
研究としての暗号解読には、暗号の解読だけではなく、デジタル署名の偽造、ハッシュ関数のコリジョン探索、暗号プロトコルの解読なども含まれる。
解読の定義
編集素朴な意味での暗号解読は、鍵を与えられずに暗号文を平文に戻すことをいう。
暗号文の復号を行う目的の他に、暗号化に使われる鍵を求める場合もあり、何らかの手段で鍵を推定すること自体も暗号解析に含まれる。
鍵の推定は、可能な鍵の候補を全て試みる「全数探索」と何かしらのアルゴリズムによって鍵の候補を絞り込む「ショートカット法」がある。
鍵が求められると暗号文の全てを復号でき、これを完全解読という。全数探索によって鍵を求める攻撃もこれに含まれる。暗号方式によっては、鍵を用いずに暗号文から平文を求めるアルゴリズムが存在することがある。このような場合、global deduction という。
暗号解読では、平文を求めるだけではなく、暗号方式の問題を見つけることを解読ということがある。暗号方式の問題には、以下の問題がある。
- 暗号文から（あるいは暗号文と平文から）、鍵や（他の）平文が判明する。
- 鍵や平文を知らずに、暗号文を作り出せる。
解読法の分類
編集暗号の解読法は、解読に用いる情報やその仮定や前提条件を整理した攻撃モデルによって分類される。主な攻撃モデルに次の4つがある。
- 暗号文単独攻撃 (COA)[注 1]
- 暗号文だけを用いて、平文を求める攻撃である。既知暗号文攻撃[注 2]ということもある。
- シーザー暗号などの換字式暗号は、複数の暗号文を集めて頻度分析を行うことで解読できることが知られている。
- 既知平文攻撃 (KPA)[注 3]
- 既知の平文に対応する暗号文が得られている条件で、暗号文から平文を求める（または暗号文と平文の組みから鍵を求める）攻撃である。平文が既知となる例に、通信プロトコルによってデータの最初のブロックが定型文または通番や日時になっていて予測可能な場合がある。
- 選択平文攻撃 (CPA)[注 4]
- 任意の平文に対応する暗号文が得られる条件で、暗号文から平文を求める攻撃である。公開鍵暗号の場合には、公開鍵を用いて任意の平文を暗号化できるので、選択平文攻撃に対して安全であることが必須である。
- 選択暗号文攻撃 (CCA)[注 5]
- 任意の暗号文（ただし解読対象の暗号文は除く）に対応する平文が得られる条件で、ある暗号文から平文を求める攻撃である。
選択平文攻撃および選択暗号文攻撃はさらに、選択した平文から暗号文（または暗号文から平文）を得て、その平文・暗号文の組を解析し、次の平文選択（または暗号文選択）をする場合が想定される。このような攻撃は、それぞれ適応的選択平文攻撃 (CPA2)、適応的選択暗号文攻撃 (CCA2) と分類される。
既知平文攻撃には、差分が既知の平文に対応する暗号文が得られる条件の攻撃である既知平文差分攻撃がある。これを一般化した代数的関係が既知な平文に対応する暗号文が得られる条件の攻撃である関連平文攻撃[注 6]がある。
その他、平文・暗号文以外の条件を仮定することもあり、関係が既知な鍵を用いて暗号化・復号した暗号文・平文が得られる条件で行う関連鍵攻撃[注 7]がある。秘密情報に権限ベクトルを加算した値を秘密鍵として認証コードを暗号化するような装置では、秘密鍵の差分が既知となるので、関連鍵攻撃の条件を満たす。
現実の暗号装置では、処理時間・消費電力・ノイズなど、入出力データ以外に外部へ情報を与えてしまうことがあり、これらを利用した攻撃はサイドチャネル攻撃と呼ばれる。