差分解読法のソースを表示

'''差分解読法'''（さぶんかいどくほう、{{Lang-en-short|differential cryptanalysis}}）は、主に[[ブロック暗号]]に対して用いられる[[暗号解読|暗号解読法]]の一種である。[[ストリーム暗号]]や[[ハッシュ関数]]の攻撃にも用いられる。広い意味では、入力差分がどのように出力差分に影響を及ぼすか考察することである。ブロック暗号においては、置換ネットワークを通してどのように差分が波及するかを追跡することによって、暗号アルゴリズムの非ランダム性を発見し、秘密鍵を復元するような性質を発見することを意味する。

==歴史==
差分解読法の発見は[[Eli Biham]]および[[アディ・シャミア|Adi Shamir]]によって[[1980年代]]の末に一般に発表された。BamfordのPuzzle Palaceでは、[[IBM]]では[[1970年代]]にはすでに知られていて、それに基づいて[[Data Encryption Standard|DES]]の[[Sボックス]]は小修正をされたとされている。DESを開発したメンバーの一人である[[Don Coppersmith]]は、[[1974年]]のはじめにはIBM内で差分解読法が知られていて、DESの設計目標の中に差分解読法への耐性があった、と[[1994年]]に発表した論文内で述べている<ref name="coppersmith">
{{cite journal |last = Coppersmith |first = Don |year = 1994 |month = May |title = The Data Encryption Standard (DES) and its strength against attacks |journal = IBM Journal of Research and Development |volume = 38 |issue = 3 |pages = 243 |url = http://www.research.ibm.com/journal/rd/383/coppersmith.pdf |format = PDF }}</ref>。
[[Steven Levy]]によると、IBMは差分解読法を自ら発見していて、[[アメリカ国家安全保障局|NSA]]はそのテクニックをおそらくすでに知っていた<ref>{{cite book| |last = Levy |first = Steven |authorlink = Steven Levy |title = "Crypto: How the Code Rebels Beat the Government — Saving Privacy in the Digital Age |publisher = [[Penguin Books]] |date = 2001 |id = ISBN 0-14-024432-8 |pages = 55–56 }}</ref>。
「NSAとの議論の後、設計方針の公開は多くの暗号に対して効果的なテクニックである差分解読法を暴露すると確信した。これは暗号学分野における合衆国の優位性を弱めることとなる」とCopperthmithが述べたように、IBMは秘密を守った<ref name="coppersmith"/>。
IBMでは、差分解読法は "T-attack"<ref name="coppersmith"/> あるいは "Tickle attack"<ref>Matt Blaze, [[sci.crypt]], [[15 August]] 1996, [https://groups.google.com/g/sci.crypt/c/VfZ6GE35C9E/m/WsxykzJK0VwJ Re: Reverse engineering and the Clipper chip"]</ref>と呼ばれていた。<!-- not the solidest of cites -->

DESは差分解読法に対して耐性を持つように設計されていたが、他の暗号は脆弱であった。最も初期の攻撃対象は、ブロック暗号[[FEAL]]であった。最初に提案された4段のFEAL (FEAL-4) はたった8個の[[選択平文攻撃|選択平文]]で解読可能であった。31段でさえも攻撃は可能である。

差分攻撃法が一般に認知された後は、この攻撃に対して耐性を持たせることが暗号設計者にとって基本的問題であり、新しい暗号アルゴリズムには、この攻撃に対して耐性があることが望まれるべき性質になっている。[[Advanced Encryption Standard|AES]]をはじめとする多くの暗号は、この攻撃に対して安全であると数学的に証明されている（[[証明可能安全性を持つ暗号|証明可能安全性]]）。

==攻撃手法==
差分解読法は、攻撃者が自由に選択した平文に対する暗号文が入手できるという条件で可能な攻撃法であり、選択平文攻撃に分類できる。
DESを解読するためには、2<sup>47</sup>の選択平文が必要である。
しかしながら、[[既知平文攻撃]]や[[暗号文単独攻撃]]を適用できるような拡張も存在する。
基本的な手法においては、ある固定された差を持つ二つの平文の組を用いる。差の定義にはいくらかの変形があるが、たいていは[[排他的論理和]]が用いられる。 
攻撃者は、暗号文の組の差を計算し、その分布の中に統計的パターンを発見しようとする。これらの差を差分と呼ぶ。
この統計的性質は、暗号化に用いられる[[Sボックス]]の性質に由来している。
それゆえ攻撃者はこれらのSボックス <math>S</math> に対して、<math>(\Delta_X, \Delta_Y)</math>（ただし <math>\Delta_Y = S(X) \oplus S(X \oplus \Delta_X)</math>）となるような差分を解析する。
基本的な攻撃では、ひとつの特徴的な暗号文差分が高い確率で生起することが期待される。このようにして、暗号アルゴリズムは、ランダム関数と区別される。さらに洗練された手法では、全数探索法より速く鍵を復元できる。
ほとんどの暗号では、攻撃が成功するためには、差分を注意深く選ぶ必要がある。解析はアルゴリズムの内部構造を調査する。標準的な手法では、それぞれの段の高確率の差分のパスを追跡することによって行われる。このようにして得られたものを差分特性と呼ぶ。

==参考文献==
<references/>
* Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 1993. ISBN 0-387-97930-1, ISBN 3-540-97930-1.
* Biham, E. and A. Shamir. (1990). Differential Cryptanalysis of DES-like Cryptosystems. Advances in Cryptology &mdash; CRYPTO '90. Springer-Verlag. 2&ndash;21.
* Eli Biham, Adi Shamir,"Differential Cryptanalysis of the Full 16-Round DES," CS 708, Proceedings of CRYPTO '92, Volume 740 of Lecture Notes in Computer Science, December 1991. [http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1991/CS/CS0708.ps (Postscript)]
* Eli Biham, slides from {{PDFlink|[http://www.cs.technion.ac.il/~biham/Reports/Slides/fse2006-history-dc.pdf "How to Make a Difference: Early History of Differential Cryptanalysis"]|850&nbsp;[[Kibibyte|KiB]]<!-- application/pdf, 870636 bytes -->}}, [[March 16]], 2006, FSE 2006, Graz, Austria

==関連項目==
* [[暗号理論]]
* [[ブロック暗号]]
* [[線形解読法]]
* [[差分確率]]
* 関連した攻撃：[[切詰差分解読法]] / [[高階差分解読法]] / [[丸め差分攻撃]] / [[不能差分攻撃]] / [[ブーメラン攻撃]]

==外部リンク==
* [http://www.engr.mun.ca/~howard/Research/Papers/ldc_tutorial.html A tutorial on differential (and linear) cryptanalysis]
* [http://www.adastral.ucl.ac.uk/~helger/crypto/link/block/dc.php Helger Lipmaa's links on differential cryptanalysis]
* [http://home.earthlink.net/~mylnir/desdoc.html A description of the attack applied to DES]

{{cryptography navbox|block|stream|hash}}
{{デフォルトソート:さふんかいとくほう}}
[[category:暗号技術|さふんこうけきほう]]
[[Category:暗号解読攻撃]]