RSA公開鍵暗号を紙上体験 part2 | 数学アラカルト [実践] | 逆ポーランド電卓の実践ウェブ rpn hacks!

逆ポーランド電卓の実践ウェブ rpn hacks!

逆ポーランド電卓rpnの実践ウェブ   
rpn hacks! アールピーエヌ・ハックスサイトマップ

rpn | 実戦 | 数学アラカルト | 数学に関する話題をrpnで探求!数字と遊んでみよう。

HOME > 実践 > 数学アラカルト > RSA公開鍵暗号を紙上体験 part2 hatena yahoo buzzurl livedoor del.icio.us nifty newsing twitter facebook rss ソーシャルブックマーク

RSA公開鍵暗号を紙上体験 part2

前のページに戻るLinkIcon

RSA暗号の解読(ブルートフォースアタック)

 現実に使われているRSA暗号の解読はほぼ不可能ですが、本記事程度の素数であれば解読することが可能です。実際、モジュロ内のどれかの数字が秘密鍵なので、総当りで復号すれば平文に戻ります。まず、暗号化された数値の並びがファイルの"crypt.txt"にあるとします。

  >type crypt.txt
  1 9 32 8 10 7


これに対して、1からモジュロ-1の数値を秘密鍵と仮定します。モジュロは公開されているので、後は復号の計算をするだけです。秘密鍵を1からモジュロ-1まで指定しながら復号できるか試します。

  >rpn 1 35 -c rsa <crypt.txt
  1 9 32 8 10 7
  >rpn 2 35 -c rsa <crypt.txt
  1 11 9 29 30 14
  >rpn 3 35 -c rsa <crypt.txt
  1 29 8 22 20 28
  >rpn 4 35 -c rsa <crypt.txt
  1 16 11 1 25 21
  >rpn 5 35 -c rsa <crypt.txt
  1 4 2 8 5 7


5回目で平文の「142857」が出てきます。もちろん、復号した文自体に意味を読み取れなければ解読したことにはなりません。今回の場合は、少なくとも一桁の数字の集まりである等の事前情報がなければ解読できないでしょう。

実際のRSA暗号では300桁以上の素数を使用しているのでモジュロの桁数も大きく、総当り攻撃による解読は非現実的です。

RSA暗号の解読(素因数分解)

 公開鍵方式の理論的基盤なので当然ですが、RSA暗号では2つの素数が判明するとすぐに解読されます。2つの素数を掛け合わせた数であるモジュロが公開されているので、モジュロを素因数分解することで2つの素数が分かってしまいます。

RSA暗号は素因数分解問題が、そして楕円曲線暗号とエルガマル暗号は離散対数問題が簡単には解けないこと、つまり、P≠NPを想定しています。

例題のモジュロで試してみましょう。モジュロが35の場合、以下のrpnプログラムで簡単に素因数分解されます(35=5*7)。

  >rpn 35 -c primes
  5 7


情報primesは素因数分解のrpnプログラムです。応用コーナープライバシーは素数が守るにあります。興味のある人は閲覧ください。

2つの素数が分かってしまえば、公開鍵の情報を使って秘密鍵は簡単に特定されてしまいます。この場合、総当りのように復号した平文に意味があるかどうかを考える必要はありません。

では、素因数分解自体は簡単なのでしょうか。確かに人間がやるとなると大変です。123456を素因数分解することはまず無理でしょう。「偶数なので2で割れる。半分になった61728は偶数だからまた2で割ってみて…」となります。

2で割っていくと最後に643が残りますが、1と自分自身以外(643)で割り切れる数を調べるのは大変です。結局は試行錯誤で見つけ出すしかありません。しかし、コンピュータなら一瞬です。123456は8つの素数に分解されることが分かります(643は素数だった!)。

  >rpn 123456 -c primes
  2 2 2 2 2 2 3 643


公開鍵方式による暗号で使用するモジュロは高々2つの素数の掛け合わせなのですが、それでも素因数分解は困難です。例えば、たった7桁の3402829は2つの素数からなるのですが、人間業で素因数分解はまず不可能です。しかし、これもコンピュータなら一瞬です。

  >rpn 3402829 -c primes
  1091 3119


仮に10桁の数であっても、数秒で素因数分解されてしまいます。

  >rpn 9998000099 -c primes
  99989 99991


こうして素因数分解の実例を眺めてみると、公開鍵方式で使用するモジュロを構成する2つの素数は大きなものでなければならないことが分かりますね。

素因数分解に掛かる時間

 公開鍵方式によるRSA暗号では大きな素数同士を掛け合わせた数の素因数分解が困難であるという数学的問題に基づいています。ここでの困難とは素因数分解するには時間が掛かるということを意味します。

100年掛かって素因数分解して、暗号を解読できたとしても意味がありません(通常、解読した平文を利用する価値がなくなっている)。つまり、仮に解読されても問題がないくらい長時間掛けないと素因数分解ができないモジュロを用意すればよいわけです。

完全な実験ではありませんが、桁数が増えるのに従って素因数分解の時間がどのように変化するのか確かめてみましょう。以下の数字は適当に選んだ隣り合った2つの素数を掛け合わせた数値です(公開鍵方式のモジュロに相当)。

  6
  35
  437
  8633
  53357
  988027
  5157437
  99400891
  544008967
  9998000099
  98222067191
  999962000357
  1007202923989
  99999640000243


それぞれの素因数分解に掛かる時間をバッチファイルを使って計測します。以下のrpn式がファイルの"timer.bat"に格納されているとします。

  rpn w -fd >time.txt
  rpn 6 -c primes -fd >prime.txt
  rpn w -fd >>time.txt
  rpn 35 -c primes -fd >>prime.txt
              :
            (中略)
              :
  rpn 1007202923989 -c primes -fd >>prime.txt
  rpn w -fd >>time.txt
  rpn 99999640000243 -c primes -fd >>prime.txt
  rpn w -fd >>time.txt


timerバッチを実行すれば、prime.txtに素因数分解された数値が、time.txtに時間が記録されます。

  >timer
     :
  (処理中)
     :


先に素因数分解できた数を表示しておきます。

  >type prime.txt
  2 3
  5 7
  19 23
  89 97
  229 233
  991 997
  2269 2273
  9967 9973
  23321 23327
  99989 99991
  313399 313409
  999979 999983
  1003589 1003601
  9999973 9999991


次に時間の差分を取ることで経過時間を算出します。それぞれのモジュロ桁数のサンプルが1つしかないので、値にバラつきが発生する可能性が高いですが、大体の様子は分かります。

  >rpn -c rowdif <time.txt
  0
  0
  0
  0
  0
  1
  0
  0
  2
  5
  15
  50
  50
  495


では、グラフ化していきましょう。横軸がモジュロの桁数で縦軸が素因数分解に要した時間です(単位は秒)。処理時間は素因数分解のアルゴリズムにも、コンピュータ性能にも依存するので、あくまで参考としてみてください。

実験は旧式のコンピュータを使用しましたが、処理時間増加の傾向は掴めるでしょう。
  >rpn -c rowdif <time.txt | rpn 1 -c rownum | xyp -x,14 -y,500 -m -s1,100
  ^y 500                                 *
  |
  -
  |
  |
  -
  |
  |
  -
  |
  |
  -
  |
  |                                *  *  x
  |o              *        * *  *       14
  +-*--*--*--*-*|--|-*--*--|--|--|--|--|->


14桁になると処理時間が爆発的に増加していることが分かります。縦軸の対数を取ってみましょう。

  >rpn -c rowdif <time.txt | rpn 1 -c rownum | xyp -x,14 -yl,500 -m -s1,100
  ^y 500                                 *
  |
  |
  -
  |
  |                                *  *
  |
  |
  |                             *
  |
  |
  |                          *
  |
  |                        *             x
  |o                                    14
  +-|--|--|--|--|-*|-|--|--|--|--|--|--|->


片対数グラフでも急激な処理時間の伸び(増加率が一定)が分かります。15桁だったらどうなるのでしょう。もっと跳ね上がるのでしょうか。

素因数分解の処理時間予測

 そこで、先ほどの経過時間ファイルのtime.txtの9桁から14桁までの処理時間を抜き出して、処理時間の常用対数をとってから回帰式を導出してみます。

  >rpn -c rowdif <time.txt | rpn 1 -c rownum | rpn 9 14 -c lookup >tmp
  >rpn j <tmp | rpn -c expr
  y=0.442594x-3.71172


xに15を代入して計算すると、答えは次のようになります。

  >rpn .442594 15 * 3.71172 -
  2.92719


これは乗数なので、最後に10の冪乗を取って元に戻します。

  >rpn .442594 15 * 3.71172 - 10 x p
  845.649


処理時間は845秒のはずです。試しに15桁の116511907273759を素因数分解してみます。さっそく、簡単なバッチを作って試してみましょう。

  >rpn w -fd >tmp
  >rpn 116511907273759 -c primes -fd
  10749631 10838689
  >rpn w -fd >>tmp
  >rpn -c rowdif <tmp
  530


530秒の処理時間でした。

  >rpn 530 845 -c err
  -0.59434


予想より短い処理時間です。誤差百分率も-59%でかなりの外れ具合でした。ただ素数の組み合わせによって、素因数分解の処理時間も変わるので一例だけでは何とも言えません。

ちなみに同じ15桁の854511398490223の素因数分解に要した時間は1417秒。530秒と比較して2.7倍の時間です。

試しに16桁だったらどうなるでしょう。8324330666941631を素因数分解してみると…4132秒(1時間9分)でした。先ほどの予測式では2343秒になりますから、今度は予想を大きく上回る秒数ですね。その誤差は76%です。

以下に桁数が1桁から16桁までの処理時間のグラフを示します。

  ^y 5000                          ^y 5000                      *
  -                     リニア     -                    片対数
  |                            *   |
  |                                |                        * *
  -                                |
  |                                |
  |                                |
  -                                |                    * *
  |                                |                  *
  |                                |
  -                                |                 *
  |                        * * x   |               *            x
  |o        *     * ** * *    16   |o                          16
  +*-*-*-*-*-|*|*-|-|-|-|-|-|-|>   +|-|-|-|-|*|-||-|-|-|-|-|-|-|>


片対数グラフを見ると、桁数が1桁増えると対数の傾きに合わせて処理時間が急増していくことが分かりますね。桁数が10桁増えたら…、20桁増えたら…。最新のコンピュータを使っても素因数分解は容易でなくなることが想像できます。

実際のRSA暗号では300桁以上の素数を使用するため、モジュロの桁数は大体600以上になります。600桁以上の数字を素因数分解するのは並大抵ではありません。

RSA暗号による暗号の大衆化

 歴史上、いかなる国においても暗号の理論や作成、そして解読は諜報機関が主体でした。素晴らしく強固な暗号方式や解読方式が発見・発明されたとしても、全ては闇の中であり、まさに門外不出。

2014年現在、世界の光ファイバーケーブルの80%がアメリカ経由ですが、NSAは全ての音声通信を収集・保存していると内部告発した人がいます。その人物はNSA関係者で元暗号解読者です。

DESや公開鍵暗号が出現するまでは、大学等の学術畑にも文献はなく、アマチュア暗号同好会と同レベルだったそうです。つまり、一般大衆は暗号技術を学ぶことも使うこともできなかったわけです。

その暗号が民間企業によるDESで、そしてアマチュア数学者による公開鍵暗号で大きく変わり、RSA暗号で花開きます(ジマーマンのPGPの貢献も大きい)。特に公開鍵暗号は暗号界に一大センセーションを巻き起こしました。本当に数百年に一度の大発明だったのです。

これにより暗号技術が大衆の手に渡ったことになります。暗号を政府や軍部、諜報機関が独占する時代は過ぎ去りました。ウェブ閲覧、ネットバンキング、eコマース、衛星放送、デジタル認証…。ほとんどの分野にRSA公開鍵暗号が使われています。

知らず知らずのうちにRSA暗号を使っているとき、情報は素数によって守られていたわけです。

ブレイク・ザ・コード - RSA暗号が終わりを迎えるとき -

 今やRSA暗号は社会基盤のあらゆる場所で使われていますが、その暗号は素因数分解の困難さに機軸をおいています。従って、モジュロを作り出している2つの素数を知る何らかの方法(魔法のネジ)が発見されれば、RSA暗号は崩壊します。

公開鍵暗号自体が20世紀後半に発明された歴史の浅い暗号方式です。だからと言って歴史のある共通鍵暗号のほうが強固とも言えません。誕生から20年以上も第一線で活躍してきたDESですら、コンピュータの処理能力の向上による総当り攻撃が可能になり、ついに脆弱性が認知されることになりました。
2001年、DESの後継としてベルギーのラインディールがアメリカ新暗号規格のAES(Advanced Encryption Standard)に選ばれています。国外の暗号ということでバックドアの疑念もほぼ払拭されました。
公開鍵暗号のデメリットは処理速度の遅さです。そのため、現在では公開鍵暗号で共通鍵を送り、共通鍵暗号で平文を暗号化するハイブリッドな使い方が主流です。つまり、未だにメッセージの秘匿化は共通鍵暗号が握っているわけですね。

外交を含む国家機密、軍事情報、金融ネットワーク、インフラストラクチャー、様々なセキュリティー、プライバシー情報…。全てが瓦解する可能性があるのです。

ハイブリッドな暗号システムの場合は公開鍵暗号を破った次に共通鍵暗号も破る必要があるので、いきなり瓦解とまではいきません。

原理的にもショートカット的にも素因数分解を効率的に行なう方法は過去数世紀に渡って発見されていないことから、RSA暗号はまず大丈夫だろうと思われていますが、暗号の世界が将来どうなっていくか誰も想像はできません。

量子コンピュータが実用化されれば、現在のコンピュータの10000000000000000000000000000倍くらい速くなります。P≠NPを仮定している暗号方式のほとんどが解読される処理速度です。

番外編:暗号クイズ

 暗号文を解いてみませんか。以下に24の意味不明な数字が並んでいます。これらは、ある平文をRSA暗号で暗号化したものです。

74603 98890 74603 79816 98890 46882 78545 388246 368874 170059 98890 320498 240800 188717 43928 325277 98890 46416 98890 72851 43928 31266 183696 138884

ただし、rpnの計算精度では簡単に素因数分解できてしまうので、ちょっと難易度を上げてみます。秘密鍵はもちろん、モジュロと公開鍵も秘密。果たして、解読できるでしょうか。

実践数学アラカルトに戻るLinkIcon

情報RSA暗号で使用するモジュロは素数同士の掛け算ですが、素数に関しては興味深い話がたくさんあります。応用コーナープライバシーは素数が守るでもいくつかトピックを紹介しています。興味のある方は閲覧ください。

警告rpnプログラムを実行するには、rpn試用版かrpn標準版が必要です(バージョンの違いはこちら)。

情報lookupはユーティリティーパッケージに同梱されています。rownum, rowdifはカンタン分析パッケージに同梱されています。expr, errはビジネス統計(単回帰編)に同梱されています。xypとnpdはrpnの姉妹ソフトウェアです。詳しくはプロダクトを参照ください。

数学アラカルト

数字と遊んでみよう

※実践コーナーのTOP

紹介 rpnの利用シーンはこちら…

講座初めての人のrpn基礎もどうぞ
講座しっかり学べるrpn入門もどうぞ
講座すぐに使えるdos入門もどうぞ

実践他の分野への挑戦は実践TOP

応用rpnアプリケーションは応用TOP

part2

数字と遊んでみよう

※実践コーナーのTOP

講座初めての人のrpn基礎もどうぞ
講座しっかり学べるrpn入門もどうぞ
講座すぐに使えるdos入門もどうぞ

実践他の分野への挑戦は実践TOP

応用rpnアプリケーションは応用TOP

書籍紹介

記事に関連した書籍

本ウェブサイトで扱った話題に関連した書物で、スタッフが実際に読了したものを紹介。

書籍数学の書籍
数の世界は思ったよりもエキサイティング。

  • 書籍統計の書籍
  • ビジネスで統計が使えるととっても有利。

書籍投資の書籍
失敗しない投資には広範囲で実践的な知識が必要。

警告バックスラッシュはエンマークに読み替えてください( IEのみ)。
バックスラッシュとエンマーク

警告文字で作られた図表や式が崩れることがあります。ブラウザによっては固定幅フォントをMSゴシックにするときれいに表示されます。それでも崩れる場合は図表や式をメモ帳にコピー後、閲覧下さい。

警告rpn試用版と標準版(2kリビジョン)はダブルクォートで囲ってください。

rpn 1 2 + ⇒ rpn "1 2 +"
rpn 1 -c foo ⇒ rpn "1" -c "foo"

ダブルクォートは省略できることが多いのですが、慣れない間は囲んだほうが無難です。なお、本ウェブサイトの記事ではrpn標準版(98リビジョン)を使用しているため囲っていません。詳しくは技術サポートの「rpn TIPS参照ください。

注意rpnの障害情報はこちら

警告rpn試用版の場合、複雑なプログラムや処理時間のかかるプログラムの一部には動作しないものがあるかもしれません。あくまで無料提供であることを勘案・了承ください。rpn標準版は、すべてのプログラムが動作します。