公開鍵暗号RSAの各面について。
本に書いてあるような理論的説明でなく、
実地に体験しながら、具体的に見ていきましょう。
JavaScript で実装したRSA暗号系 PigPGP 0.2.3 日本語版 を使います。
このデモは、内部で実際に行っている演算の様子をガラス張りにして見せてくれます。
初めに
例えばパソコンについて理解するのに、本を読んだだけで十分に納得がいくものでしょうか。
やはりパソコンについてよく分かるようになるにはパソコンをいじってみるのがいちばんでしょう。
同じように、ここではRSA暗号について実感として分かることが目的ですから、
RSA暗号系を自分の手でいじってみるのがいちばんです。
PigPGP 0.2.3 日本語版がそれです。
これは JavaScript で実装されており、
Netscape 4.06 以上、Internet Explorer 4.01 以上で動作しますから、
このページをお読みのかたの大半は、実際に暗号系の動作を手元でひとつひとつ確かめながら、理解を深めていただけることと思います。
まずは枝葉の部分にとらわれず、全体の雰囲気をつかみましょう。
もくじ
鍵の生成
2つの大きな素数を適当に選んで、かけるだけです。
鍵の情報
そうやって作った﹁2素数の積﹂が公開鍵・秘密鍵共有の﹁法﹂になります。
鍵にはこの﹁法﹂のほかに﹁指数﹂という要素があります。なんだか難しそうですが、
具体例を見れば意外なほどシンプルな計算です。
暗号化︵普通の文を暗号文にすること︶
暗号化したいデータを﹁公開指数﹂乗して﹁法﹂で割った余りを求めます。
復号化︵暗号文を元に戻すこと︶
暗号化されたデータを﹁秘密指数﹂乗して﹁法﹂で割った余りを求めます。
もっと詳しく学ぶには
他の記事へのリンク。
上記各プロセスを理解するのに必要な事柄ごとに別記事がありますから、
興味を感じたらさらにお読みください。
鍵の生成
デフォルトの設定︵128-bit︶のまま﹁操作﹂の﹁鍵の生成﹂をクリックしてみましょう。1秒～10秒くらいで、いちばん下の﹁Debug﹂欄に、次の例のような出力が出ます。
----- PigPGP 0.2.3 DEBUG LOG -----
Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.7a) Gecko/20040203
Current Time: 2004-02-04T19:20:25.131+09:00
DEBUG: * Passed at Step 2 / 3
DEBUG: SPRP(2)
DEBUG: * Passed at Step 1 / 1
DEBUG: SPRP(2)
DEBUG: Key Length : 128.18-bit
DEBUG: ** Total Cost: 2.663 seconds
1行目は単なるログのヘッダ、2行目はブラウザの種類︵Windows 上ではIEの方が高速ですが、この例は Mozilla です︶、3行目は時刻です。これらは、まあ、あまり本質に関係ありません。さて、次に
DEBUG: * Passed at Step 2 / 3
と表示されています。この﹁Passed﹂というのは、内部である試験にパスした、という意味なのです。
どういう試験かというと﹁素数を合格させて、素数でないものを失格させる﹂ような試験です。
要するに、素数を探しているのです。
この点は、後でもう少し詳しく説明します。﹁Step 2 / 3﹂とあるのは、この場合、
判定結果が出るまで最大3つのステップがあって、そのうち2番目のステップで合格と判定されたことを表しています。
次の行に SPRP(2) とあるのは、テストに合格した数が
﹁2を底とする強い概(がい)素(そす)数(う)﹂であることを意味します。
予備知識がなければ何のことだかさっぱり分からないでしょうが、
今はとりあえず気にすることありません。
一応、簡単に説明すると、SPRPは﹁ほぼ素数に間違いない数﹂です。
﹁ほぼ間違いない﹂などというのは、数学の威厳にかかわる不愉快な表現であり、
素数であるかないか白黒はっきりさせたいところですが、
2004年現在、それがなかなか難しいのです。
一方、SPRP判定は簡単にできるうえ、
条件さえ整えれば、SPRPと判定されたものが実は素数でなかった、という困った確率を、
無視できるくらい小さくできるので、実用上はそれで問題ありません。
これらと同様の出力がもう1組あります。さらに別の素数を探したわけです。
試験に合格した︵つまり素数と判定された︶場合だけが記録され、
素数でないと判定された場合はログに書かれないため、このログは簡潔ですっきりしています。
最後に﹁Key Length﹂とあるのは、生成された鍵の長さのことです。
鍵は長ければ長いほど強い︵つまり暗号を破られにくい︶のです。
この場合、約128ビットで、このような学習・研究目的のサンプルにはいいですが、実用にはやや弱すぎます。
どのくらいの強さがちょうどいいのか、といったことは、後でもう少し詳しく説明します。
次に﹁プログレス／エラー表示﹂欄を見ると、次のような奇妙な模様が出力されています。
-*^*-------**-**^
これは、2つの素数が見つかるまで、内部で何が起きていたかを表しています。
- が表示されたところは﹁エラトステネスのふるい﹂でふるい落とされたことを意味します。
具体的にいうと、テストした数が5000以下の範囲のどれかの数で割り切れてしまったのです。1と自分自身以外に約数がない素数を探しているのですから、そんな小さい数であっさり割れてしまったら、予選落ち、ということになります。
次に * が表示された場合は﹁エラトステネスのふるい﹂を通過したことを意味します。
5000までの範囲のどの数でも割れないような数なので、素数である可能性があります。
でも、5000より大きい約数がある場合もあるので、これだけではまだ合格とは言えません。
* に続けて ^ が出たときは﹁ミラー・ラビンテスト﹂というより本格的なテストに合格し、素数と認定された場合です。
* に続けて ^ が出ない場合は﹁ミラー・ラビンテスト﹂にかけたら﹁素数でありません！﹂と判定され、
残念ながら失格になってしまった場合です。
素数を2個探すので、*^ というシークエンスが2回現れると、捜索終了です。
﹁公開鍵﹂﹁秘密鍵﹂の欄を見ると、
PUB_PIGv2@d@3^hisr[Gva^g[FYV[AU{Dcr]
のような奇妙な文字列が出力されました。これが暗号系で使用する﹁鍵﹂です。暗号系の﹁鍵﹂とは何でしょうか。
それは暗号化したり、暗号化したものを元に戻すのに必要な﹁パスワードのようなもの﹂のことです。
この﹁鍵﹂を使って、文章を暗号化したり元に戻したりするわけです。
﹁公開鍵﹂は暗号化するのに使うもの、
﹁秘密鍵﹂は暗号化したのを元に戻すのに使うものです。
詳細出力
それでは上の方の﹁詳細なデバッグ出力﹂にチェックを入れてから、もう一度、﹁鍵の生成﹂をしてみましょう。
今度は次のような長いログがとれます。
DEBUG: *Cost ( Eratosthenes: 89742554895025297 ): 0 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025301 ): 10 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025303 ): 20 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025307 ): 10 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025309 ): 10 ms
DEBUG: Checking 8974255 4895025313 (17-digit)
DEBUG: *Cost ( Miller-Rabin ): 280 ms
DEBUG: NOT prime
まず8京9742兆5548億9502万5297 という数からスタートしています。
この最初の数は、できあがる鍵が目的の長さになるように、内部的にランダムに選択されてます。
この8京なんとかの数は、エラトステネスのふるいでふるい落とされてしまっています。
そして、ほんの少しだけ大きくした別の数がテストされますが、これもふるい落とされます。
以下同様に、ふるいを通過できる数が見つかるまで、少しずつ数を増やしていきます。
8974255 4895025313
という17桁の数が最初にふるいを通過し、
ミラー・ラビンのテストに進みますが、結果は﹁NOT prime﹂ ―― 残念ながら結局、これも素数ではありませんでした。
ところで、10ms などと付記されているのは、そのテストにかかった時間です。msは﹁ミリ秒﹂つまり0.001秒のこと。10ms なら10ミリ秒=0.01秒で一瞬ですが、最終的に鍵ができるまで、
こういうテストを何十回、何百回も繰り返すので、0.01秒程度のコストも﹁ちりも積もれば﹂でばかになりません。
以下同じように﹁ふるい﹂の予選を通過した
8974255 4895025367
を﹁ミラー・ラビン﹂にかけますが、
これも不合格。NOT prime と言われてしまいました。ちぇっ。
DEBUG: *Cost ( Eratosthenes: 89742554895025319 ): 20 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025321 ): 10 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025327 ): 20 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025331 ): 20 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025333 ): 20 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025337 ): 20 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025339 ): 20 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025343 ): 30 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025349 ): 30 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025351 ): 21 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025357 ): 20 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025361 ): 20 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025363 ): 20 ms
DEBUG: Checking 8974255 4895025367 (17-digit)
DEBUG: *Cost ( Miller-Rabin ): 480 ms
DEBUG: NOT prime
さらに同じことをやると、今度は﹁ふるい﹂を通過した
8974255 4895025421
が見事﹁ミラー・ラビン﹂も通過し、
めでたく SPRP(2) ―― ほぼ素数に間違いない数 ―― に認定されます。
これが第一の素数:
P : 8974255 4895025421
として採用されます。
DEBUG: *Cost ( Eratosthenes: 89742554895025369 ): 60 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025373 ): 20 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025379 ): 20 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025381 ): 61 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025387 ): 20 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025391 ): 40 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025393 ): 20 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025397 ): 30 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025399 ): 30 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025403 ): 30 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025409 ): 30 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025411 ): 30 ms
DEBUG: *Cost ( Eratosthenes: 89742554895025417 ): 20 ms
DEBUG: Checking 8974255 4895025421 (17-digit)
DEBUG: * Passed at Step 2 / 2
DEBUG: *Cost ( Miller-Rabin ): 531 ms
DEBUG: SPRP(2)
DEBUG: P : 8974255 4895025421 (17-digit)
以下まったく同じようにして、第二の素数:
Q : 42 4987303679 2309197137
が見つかると、PとQをかけ算して
N : 381394464 3012221988 6034889662 7715419677
という数を作ります。
RSA暗号の鍵とは、要するに、このようにして大きな2つの素数をかけ算したものであり、
その積︵上のNという数︶の長さをビットで表したものが﹁鍵の長さ﹂なのです。
上の﹁鍵﹂は
381394464 3012221988 6034889662 7715419677
という39桁の数ですが、2の128乗は
340282366 9209384634 6337460743 1768211456
という39桁ですから、このNがだいたい128ビットの長さだ、ということが分かります。
この鍵というのを具体的にどうやって使うのか、とか、
そもそも素数であるかどうか調べる﹁ミラー・ラビンテスト﹂とはどういうしくみなのか、とか、
いろいろ疑問はあるとは思いますが、何となくの様子は分かったでしょう。
要するに、RSAの鍵の生成とは……
●基本的には、大きな素数を2つ見つけることである。
●﹁大きい素数﹂とはどのくらい大きいのか、というと、作りたい鍵の長さしだい。
128ビットという短い鍵でも2素数の積は39桁という、かなり大きな整数。
1024ビットなら300桁を超える。
●素数を見つけるには、まず﹁エラトステネスのふるい﹂にかけて5000以下の小さい約数があるようなザコをふるい落としておいてから、
﹁ミラー・ラビンのテスト﹂という本格的なテストで調べる。
上のログのmsの表示をよくみると、エラトステネスのふるいは一瞬ですが、ミラー・ラビンは10倍以上、時間がかかることが分かります。
ですので、ザコはさくっとふるっておいて、見込みがありそうな数だけを、ミラー・ラビンでじっくり調べます。
理論的には、全員にミラー・ラビン試験を実施してもいいのですが、それだと時間がかかりすぎるので、
エラトステネスで予選をするわけです。
納得がいくまで、上のプロセスのデモを何度か繰り返してみてください。
鍵の生成の所要時間は、ランダムに選んだ数を出発点に素数が2つ見つかるまでの時間ですから、
運次第です。難しい言葉で言えば、RSA暗号の鍵生成は、確率的アルゴリズムなのです。
鍵を生成すると、
﹁公開鍵﹂﹁秘密鍵﹂の欄に妙な文字列が表示されますが︵そしてこれらが実際に使う鍵なのですが︶、
この妙な文字列は、だいたいにおいて、上のようにして選んだ巨大整数そのものです。
鍵の情報
とりあえず雰囲気が飲み込めたら、鍵を生成したあとで﹁鍵の情報﹂をクリックしてみましょう。
デバッグ出力欄に、例えば、次のように表示されるでしょう。
* KEY INFO ABOUT:
PUB_PIGv2@d@4dHh9FMd[D_FAT0%[G`yHr]
RSA Public Key (PigPGP v0.2)
Key length: 128.28-bit
power: 13 (2-digit)
modulus: 413431709 4148138879 4136550065 9180344327 (39-digit)
これは
PUB_PIGv2@d@4dHh9FMd[D_FAT0%[G`yHr]
という鍵に関する情報です。この鍵は、RSA Public Key︵RSA公開鍵︶で、
Key length︵鍵の長さ︶は約128ビットです。ここで、
power: 13
というのは、この公開鍵の﹁指数﹂が13であることを意味します。また、
modulus: 413431709 4148138879 4136550065 9180344327
というのは、この公開鍵の﹁法﹂がこの39桁の数であることを意味します。これらの意味は、すぐ後で説明しますが、
﹁法﹂が最初に生成した2つの大きな素数の積であり、つまりは鍵の主要部分です。
﹁指数﹂は、この鍵を実際に運用するときに必要になる補助的なパラメータです。
さらに、その下には、次のような情報表示があるはずです。
* KEY INFO ABOUT:
SEC_PIGv2@3N|*v4x45s[O)r_[L[N)[G-N@4dHh9FMd[D_FAT0%[G`yHr]
RSA Secret Key (PigPGP v0.2)
Key length: 128.28-bit
power: 349826831 0433040528 9967277996 9867917149 (39-digit)
modulus: 413431709 4148138879 4136550065 9180344327 (39-digit)
これは
SEC_PIGv2@3N|*v4x45s[O)r_[L[N)[G-N@4dHh9FMd[D_FAT0%[G`yHr]
という鍵に関する情報で、RSA Secret Key︵RSA秘密鍵︶です。
秘密鍵にも﹁指数﹂と﹁法﹂がありますが、よく見ると、﹁法﹂は﹁公開鍵﹂と完全に同じです。
ですので﹁秘密鍵﹂といっても、﹁法﹂は公開されているのと同じであって、
秘密鍵の秘密とは、﹁秘密の指数﹂のことなのです。
ここで観察したことをまとめると
●RSAの鍵は﹁公開鍵﹂と﹁秘密鍵﹂のペアから成っている
●どちらの鍵も内部的には﹁法﹂と﹁指数﹂という2つの整数の組み合わせ︵鍵が2種類あって、2種類のそれぞれがまた2種類の数の組み合わせ︶
●﹁法﹂が鍵システムの本質で、それは2つの巨大素数の積である
●﹁指数﹂は﹁公開鍵﹂と﹁秘密鍵﹂で異なる
●﹁秘密鍵﹂の﹁指数﹂だけが“人には言えない本当の秘密”で、あとはすべて公開される
﹁あとはすべて公開される﹂と言いましたが、じつは、もう一つだけ公開してはならない要素があります。2素数の積として﹁法﹂を構成したわけですが、この﹁法﹂そのものは公開するけれど、
﹁法﹂を構成している2素数は秘密にする必要があります。というのも、これらの2素数が分かれば、
﹁公開鍵﹂の﹁指数﹂から﹁秘密鍵﹂の﹁指数﹂を簡単に計算できてしまうからです。
﹁秘密鍵の指数﹂とは“人には言えない本当の秘密”であり、これがばれると、暗号が簡単に解読されてしまうのです。
というわけで、最初のPとQをかけ算したNは公開するのですが、Nの元になっているPとQ自体は非公開とします。
いくら非公開にしてもNはしょせんPとQの積ですから、強力な因数分解アルゴリズムを使って、Nを因数分解すれば、PとQが分かってしまいます。よく﹁因数分解ができればRSAはクラックされる﹂というのは、このことなのです。
実際のRSAでは、法は300桁以上あるような、とても大きな整数です。
このくらい大きいと、2004年現在のテクノロジーでは、まず因数分解できません。
逆に﹁因数分解されると解読されてしまい困るから、とても大きな素数の積を使う﹂というわけです。
大きな数の因数分解が難しいのか、どのくらい難しいのか、スーパーコンピュータを使ってもできないくらい難しいのか？ といったことは、
実際に試してみた経験がないと実感がつかめないと思いますが、とりあえず、結論だけ言えば、80桁くらいまでの整数は、ちょっとがんばれば因数分解できますが、
100桁を超えたあたりから困難になり、300桁などは、世界最高のコンピュータでも今のところ因数分解できません。
ここで説明のために使っている例は39桁ですから、その気になれば簡単に因数分解できます。
といっても39桁の数をパッと与えて因数分解してみろ、といっても、かなり数学が得意な人でも、そう簡単にはできないでしょう。
実際のRSA暗号系は少なくとも100桁、通常、300桁以上の法を使うので、今のところとりあえず安全です。
ところで説明なしに﹁法﹂という言葉を使いましたが、これはもちろん﹁法律﹂の﹁法﹂のことではなくて、
数学用語であり、簡単に言えば﹁割り算で︵割られる方ではなく︶割る方の数﹂……のようなもののことです。
あとでもう少しちゃんと説明します。
︵言葉は耳慣れないかもしれませんが、別に難しい概念ではありません。︶
もうひとつ。例えば、法これこれ、指数これこれ、という﹁実際には2つの整数の組﹂にすぎないものを、なんで
SEC_PIGv2@3N|*v4x45s[O)r_[L[N)[G-N@4dHh9FMd[D_FAT0%[G`yHr]
みたいな変てこな記号で表すのでしょうか？
この点には、技術的には全然意味がありません。十進数の数字は0から9まで10通りしかありませんが、
アルファベットは26文字あり、大文字小文字記号なども含めれば100近くの記号があります。10通りの記号しかない生の﹁数字﹂だけで書けば長くなるものも、
一定の規則に当てはめて、100近くある半角英数字の組み合わせで書き表せば、短くなり、便利です。
︵例えば12をa、13をb、14をc…などと決めておけばいい。︶ただそれだけのことです。
内部的に意味があるのは﹁公開指数﹂﹁秘密指数﹂﹁共通で使う法﹂の3種類の整数です。
それを具体的にどのように書き表すかは、単なる便宜上の問題で、深く考える必要ありません。
暗号化︵普通の文を暗号文にすること︶
では﹁入力﹂欄に適当な文章を入力して︵デフォルトで既に例文が入っているのでそのままでもかまいません︶、
﹁暗号化﹂をクリックしてみましょう。ほとんど一瞬で、入力欄が次のような感じに暗号化されます。
-----BEGIN PigPGP MESSAGE-----
Version 0.2.3 http://www.faireal.net/demo/PigPGP/0_2_3
16t{Qen+s|G2P8oj9[OFQbxR;[ClPU[N3mjSV}2hB}DkF[Az[AbE)[D[K
l[N(IL3B(a38[B7ROag[Mp[Lr-[CrG6-E[B7dNxVGlSy[Fko2Rd=1[G.=m
dGPe:w9[C8[FsEuB[FyQDy[Jz;[BJUq~[MavF[L~xTjV9PUc=[Lu/mM[I-J
6^Jv%Gi[O[N+yi0+_C7o[K[I8[F-Fcd[AVI%jE2/-eD[KOF9ez[CM1f3|1
0eu8EEk[IZcfXX[LwAjRcG9m_P$8[J[L[K2d[GT[O=Df-$ykQ5Gmb9g7r
5z[E|Lm[G2*LiZ^Y[CFe^;T2YK0tf4nuTp`jMfe[FNzfbWQM+lMu:o
b;K`ozaaAnjFZLOb45zgBC_a~xSrL9x%j8,dBz2c0jh;,8%3`.
B(`|Lh_w:wdm[H[N%1ggbHFYNhMyPU+r1R0d^l[I{:934[E[LFp[O_AN
o$/7[Fp[H|sFh%[C#vGKp`qd%d.oyXvONG5qoFA?([Ide[N_lOy`p6x
ki[F`YoCmEux~c!MqL[Ko(6j
前 7‒27 p ｜ 
もくじ i ｜ 次 8‒02 n 
