Skip to content
検索結果に戻る

線形暗号解読

提唱者
Mitsuru Matsui
年
1993
種類
linear approximation attack
系統
Cryptanalytic technique

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

線形暗号解読(Linear Cryptanalysis)は、暗号の非線形変換に対する線形近似を利用して秘密鍵ビットを復元する既知平文攻撃である。1993年に松井充によって導入された線形暗号解読は、DESのような暗号に対する実用的な攻撃を提供し、その計算複雑性は総当たり攻撃よりも小さい。この手法は、平文ビットと暗号文ビットの線形結合が鍵ビットとどのように関連するかについての統計的偏りを分析し、少ないデータ要件で鍵を復元することを可能にする。

手法の背後にある直感

線形暗号解読は、平文ビット、暗号文ビット、および鍵ビットの関係を示す線形方程式を見つける。暗号ラウンドにおける非完全な混合のため、これらの線形方程式はランダムよりもわずかに高い確率で成り立つ。多数の平文・暗号文ペアを収集し、どの鍵値がこれらの方程式をより頻繁に満たすかを観察することにより、攻撃者は正しい鍵を絞り込むことができる。

歴史学

線形暗号解読は、1993年に松井によってDESに対する既知平文攻撃として導入された。1994年、松井は線形暗号解読を用いたDES標準の最初の実験的暗号解読を実証し、2^43個の既知平文で鍵を復元した。この画期的な成果は、展開された標準に対する実用的な攻撃を示し、証明された耐性境界を持つAESの開発に影響を与えた。

使うべき場面

線形暗号解読は、暗号解読の研究および暗号設計評価に使用される。暗号設計者は、線形近似に耐性のあるSボックスおよび変換を選択する際の指針となる。現代の暗号は、線形近似強度に対する証明された境界値を持つように設計されている。

限界と注意点

  • 現代の暗号(AES)は、証明された境界値を持つ線形暗号解読に耐えるように慎重に設計されている
  • 既知平文・暗号文ペアを必要とするが、これはすべてのシナリオで利用可能とは限らない
  • 計算およびデータ要件が、適切に設計された暗号に対して実用的な実現可能性を超える可能性がある
  • 現代の暗号に対する強力な線形近似の発見は極めて困難である

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • DESに対する実用的な攻撃であり、2^43個の平文・暗号文ペアと2^39回の操作を必要とする
  • 近似偏りを分析するための、よく形式化された数学的フレームワーク(積み上げの法則)
  • 差分暗号解読が逃す可能性のある弱点を発見する、差分暗号解読を補完する
  • Sボックス選択およびラウンド変換のための暗号設計要件を形成する

応用

  • ブロック暗号の暗号解読、研究および標準化におけるセキュリティ特性の評価
  • 適切な線形近似境界を確保するための暗号設計およびSボックス選択
  • 線形耐性分析を要求する暗号標準の検証(NIST、ETSI)
  • レガシー暗号の廃止および置換決定のための評価

使い方

使い方

1

線形近似の発見:確率が0.5から有意に異なる確率で成り立つ、平文ビット、暗号文ビット、および鍵ビット間の線形関係。

2

ラウンド変換の統計的分析を用いて、各線形近似の偏り(0.5からのずれ)を推定する。

3

候補鍵値について、既知平文・暗号文ペアにおいて線形近似が成り立つ頻度を数える。正しい鍵が近似を最も頻繁に成り立つようにする。

4

復号された暗号文を復号し、正しさを確認することによって、復元された鍵ビットを検証する。

よくある落とし穴

  • すべての線形近似が利用可能であると仮定すること。弱い近似は最小限のアドバンテージしか提供しない
  • 理論的なデータ要件が妥当に見える場合に、実用的な攻撃の難しさを過小評価すること
  • 暗号分析における線形特性と差分特性の間の相互作用を無視すること

よくある質問

積み上げの法則とは何か?

積み上げの法則は、個々のラウンド近似の偏りを組み合わせることによって、複数ラウンドにわたる線形近似の偏りを計算する方法を提供する。これは線形暗号解読の基礎である。

AESはどのように線形暗号解読に耐えるのか?

AESは、最大線形近似確率を最小化するように選択されたSボックスと、ラウンド全体にわたる線形偏りの高速拡散を保証する拡散層を使用している。証明された境界値が、実用的な線形近似が存在しないことを保証する。

線形暗号解読と差分暗号解読の違いは何か?

差分分析は入出力差を研究するのに対し、線形分析は線形近似(平文ビットと暗号文ビットのXOR)を研究する。どちらも暗号の構造的弱点を悪用する。

現代の暗号を線形暗号解読で破ることはできるか?

実用的にはできない。AESのような現代の暗号は、線形近似に対する証明された境界値を持っており、攻撃を計算上実行不可能にしている。

自分の暗号設計における線形耐性をどのように評価するか?

Sボックスの線形近似テーブルを分析し、積み上げの法則を用いてラウンド全体での最大偏りを計算する。すべての可能な線形近似に対して最大偏りが無視できる程度であることを確認する。

関連する手法

参考文献

  1. Matsui, M. (1993). Linear cryptanalysis method for DES cipher. In Advances in Cryptology - EUROCRYPT 1993, LNCS 765, pp. 386-397.

    DOI 文献を開く
    コピーしました。
  2. Matsui, M. (1994). The first experimental cryptanalysis of the Data Encryption Standard. In Advances in Cryptology - CRYPTO 1994, LNCS 839, pp. 1-11.

    DOI 文献を開く
    コピーしました。