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

前のページに戻る

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

素因数分解に掛かる時間

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

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

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

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

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

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

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

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

実験は旧式のコンピュータを使用しましたが、処理時間増加の傾向は掴めるでしょう。

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

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

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

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

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

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

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

530秒の処理時間でした。

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

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

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

以下に桁数が1桁から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暗号で暗号化したものです。

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

数学アラカルトに戻る