暗号解読に必要な計算量

2010年 03月 22日

    暗号計算は読むものにとっては簡単で、解く物にとっては難しなくてはならない。
    わかりやすいものに計算式の量で表すことができる物が有る。
    ここでP問題（Polynomial Problem）、NP問題（Nondeterministic Polynomial problem）が出てくる。

    • P問題は決定性チューリングマシン（Deterministic Turing Machine）によりnビット長の多項式オーダの時間で解ける問題のことである。

      • 決定性チューリングマシン：計算経路が1つしかない。
      簡単に言えば、関数化されていれば、nの増加により処理時間は増えるが解は判っていること。
      例、10桁の暗証番号

    • NP問題は非決定性チューリングマシン（Non-deterministic Turing Machine）により多項式オーダの時間で解ける問題のことである。

      • 非決定性チューリングマシン：計算経路が木構造で存在。
      簡単に言えば、多価関数であり分岐が複雑にはなるが、処理時間をかければ解が判るもの。
      例、RSA

    • NP-完全問題（NP-complete problem）はすべてのNP問題が多項式計算量で帰着できるNP問題で、NP-完全問題はNP問題の中で困難な問題であると考えられる。

      • NP完全

      前回話したヴィジュネル暗号は英字26文字なので、
      26n（n = 文字数）・・・①
      で表すことができる。
      さらにこの中から意味のなす文を選ばなくてはいけないので、本文より短いことであろうと思われる鍵を①式に当てはめた方が早いだろうと思われる。

    • 鍵が3文字だった場合（263 = 17,576）1秒で10通り処理すると総当たりで約30分。
    • 同じ条件で7文字（267 = 8,031,810,176）になるといだけで約25.4年に膨れ上がる・・・

      • このようにしてみると、指数関数時間 (EXPTIME）は理論上解けないというのがよくわかる。


    暗号
    ★☆★☆★☆　ナウでヤングなレンタルサーバー！ロリポップ！　☆★☆★☆★
    月額１０５円～容量最大30ＧＢ！WordpressやMovable Typeの簡単インストール付★

    1. 1 トラックバック(s)

    2. 3月 23, 2010: ｶﾞﾁﾑｷ覚書 » Blog Archive » ヴィジュネル暗号 を PHPで書く

    Post a Comment