暗号解読

出典: フリー百科事典『ウィキペディア(Wikipedia)』
選択平文攻撃から転送)
移動先: 案内検索

暗号解読(あんごうかいどく、Cryptanalysis)とは、暗号を解読すること、あるいは解読法に関する研究を指す。

暗号の解読とは、暗号文を作成するのに用いた秘密情報(秘密の表記法や秘密のなど)にアクセスすることなく、暗号文を平文に戻すことである。これに対して、秘密情報を用いて暗号文を平文に戻すことは復号といい、解読と復号は区別することが多い。但し英語の"decryption"は両者の意味を持ち区別されない(以下、秘密情報のことを"鍵"と記す)。

他人に知られたくない情報を秘匿する手段として暗号が生まれるのと同時に、秘密を暴くための暗号解読も生まれたと考えられる。

研究としての暗号解読には、暗号 (Cipher) の解読だけではなく、デジタル署名の偽造、ハッシュ関数のコリジョン探索、あるいは暗号プロトコルの解読なども含まれる。

解読の定義

一般には、解読は、鍵を与えられずに暗号文を平文に戻すことをいう。あるいは正当な利用者が平文に戻すことを復号といい、それ以外を解読とすることもある。

暗号文を平文に戻す際に、鍵を何かしらの方法で推測して暗号文を復号する場合も解読という。推測ではなく暗号文を作成するのに用いた鍵を不正に入手して暗号文を復号する場合は暗号の解読とはいわないが、「復号=正当な利用者が暗号文を平文に戻すこと、解読=それ以外」とする場合には解読に含まれることになる。

鍵の推定は、可能な鍵の候補を全て試みる「全数探索」と何かしらのアルゴリズムによって鍵の候補を絞り込む「ショートカット法」がある。

鍵が求められると暗号文の全てを復号でき、これを完全解読 (Total break) という。全数探索によって鍵を求める攻撃もこれに含まれる。暗号方式によっては、鍵を用いずに暗号文から平文を求めるアルゴリズムが存在することがある。このような場合、Global deduction という。

暗号解読では、平文を求めるだけではなく、暗号方式の問題を見つけることを解読ということがある。暗号方式の問題には、以下の問題がある。

  • 暗号文から(あるいは暗号文と平文から)、鍵や(他の)平文が判明する。
  • 鍵や平文を知らずに、暗号文を作り出せる。

解読法の分類

暗号の解読法は、解読に用いる情報やその仮定や前提条件を整理した攻撃モデルによって分類される。主な攻撃モデルに次の4つがある。

暗号文単独攻撃 Ciphertext-only attack (COA)

テンプレート:Main

暗号文のみを用いて、平文を求める攻撃である。既知暗号文攻撃 known-ciphertext attackということもある。
シーザー暗号などの換字式暗号は、複数の暗号文を集めて頻度分析を行うことで解読できることが知られている。
既知平文攻撃 Known-plaintext attack (KPA)
既知の平文に対応する暗号文を得られる条件で、暗号文から平文を求める攻撃である。平文が既知となる例に、通信プロトコルによってデータの最初のブロックが固定あるいは通番や日時になっていて予測可能な場合がある。
選択平文攻撃 Chosen-plaintext attack (CPA)
任意の平文に対応する暗号文を得られる条件で、暗号文から平文を求める攻撃である。公開鍵暗号の場合には、公開鍵を用いて任意の平文を暗号化できるため、選択平文攻撃に対して安全であることが必須である。
選択暗号文攻撃 Chosen-ciphertext attack (CCA)
任意の暗号文(ただし解読対象の暗号文は除く)に対応する平文を得られる条件で、ある暗号文から平文を求める攻撃である。

上記の分類にはさらに細かな分類がある。選択平文攻撃(選択暗号文攻撃)には、指定した平文(暗号文)に対応する暗号文(平文)を得られた後で、さらに別の平文(暗号文)を指定して暗号文(平文)を得られる条件の攻撃があり、これを「適応的選択平文攻撃」・「適応的選択暗号文攻撃 CCA2」という。

既知平文攻撃には、差分が既知の平文に対応する暗号文が得られる条件の攻撃である「既知平文差分攻撃」がある。これを一般化した代数的関係が既知な平文に対応する暗号文が得られる条件の攻撃である「関連平文攻撃 Related message attack」がある。

その他、平文・暗号文以外の条件を仮定することもあり、関係が既知な鍵を用いて暗号化/復号した平文・暗号文が得られる条件で行う「関連鍵攻撃 Related-key attack」がある。秘密情報に権限ベクトルを加算した値を秘密鍵として認証コードを暗号化するような装置では、秘密鍵の差分が既知となるため、関連鍵攻撃の条件を満たす。また、現実の暗号装置では、処理時間・消費電力・ノイズなど、入出力データ以外に外部へ情報を与えてしまうことがあり、これらを利用した攻撃はサイドチャネル攻撃と呼ばれる。

関連項目

テンプレート:Cryptography navbox