前のページ 1/1 次のページ

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

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

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

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

◆ 解読の定義

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

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

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

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

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

・ 暗号文から(あるいは暗号文と平文から)、鍵や(他の)平文が判明する。

・ 鍵や平文を知らずに、暗号文を作り出すことができる。

などがある。

平文や鍵は、全部が判明するだけではなく、その1bitでも1/2より高い確率で推定できる場合(部分解読)、さらには特定の1bitではなく平文や鍵に関する何かしらの特徴が得られる場合(乱数との識別可能)には、問題があるということがある。これらは、特定の平文や鍵(weak key)を選択した場合にのみ平文が求まる場合と、鍵や平文に関係なく一般に求まる場合がある。

平文を求めるのではなく、暗号文を変更することで暗号文に対応する平文を変更できる場合にも、暗号方式に問題があるということがある。暗号文の1bitを反転することで平文の1bitを反転できると、平文を知ることができなくてもその内容を操作することができてしまう。

現代暗号は、計算量的安全性を根拠とし、暗号方式を公開した暗号が多いため、全数探索によって鍵を求めても暗号方式に問題があるとは言わず、全数探索よりも効率的に鍵を特定できる方法(ショートカット法)があるときに問題があるということがある。

◆ 解読法の分類

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

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

:暗号文のみを用いて、平文を求める攻撃である。既知暗号文攻撃 known-ciphertext attackということもある。

:シーザー暗号などの換字式暗号は、複数の暗号文を集めて頻度分析を行うことで解読できることが知られている。

; 既知平文攻撃 Known-plaintext attack (KPA)

:既知の平文に対応する暗号文を得られる条件で、暗号文から平文を求める攻撃である。平文が既知となる例に、通信プロトコルによってデータの最初のブロックが固定あるいは通番や日時になっていて予測可能な場合がある。

; 選択平文攻撃 Chosen-plaintext attack (CPA)

:任意の平文に対応する暗号文を得られる条件で、暗号文から平文を求める攻撃である。公開鍵暗号の場合には、公開鍵を用いて任意の平文を暗号化することができるため、選択平文攻撃に対して安全であることが必須である。

; 選択暗号文攻撃 Chosen-ciphertext attack (CCA)

:任意の暗号文(ただし解読対象の暗号文は除く)に対応する平文を得られる条件で、ある暗号文から平文を求める攻撃である。

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

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

その他、平文・暗号文以外の条件を仮定することもあり、関係が既知な鍵を用いて暗号化/復号した平文・暗号文が得られる条件で行う「関連鍵攻撃 Related-key attack」がある。秘密情報に権限ベクトルを加算した値を秘密鍵として認証コードを暗号化するような装置では、秘密鍵の差分が既知となるため、関連鍵攻撃の条件を満たす。

◆ 関連項目

・ 暗号理論

・ 解読 - 頻度分析 (暗号) 差分解読法 線形解読法 高階差分解読法

・ 計算量的安全性 - 証明可能安全性

・ 信頼性の低い暗号アルゴリズム

・ 暗号解析上の仮定

前のページ 1/1 次のページ

・暗号解読 page1