8 : 01 実演: RSA暗号の理論と実際

← 7‒27 p↑ もくじ i 8‒02 n →

JavaScript: 触って分かる公開鍵暗号RSA

2004年 2月 4日
記事ID d40204

公開鍵暗号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の鍵の生成とは……

上のログの 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秘密鍵)です。 秘密鍵にも「指数」と「法」がありますが、よく見ると、「法」は「公開鍵」と完全に同じです。 ですので「秘密鍵」といっても、「法」は公開されているのと同じであって、 秘密鍵の秘密とは、「秘密の指数」のことなのです。

ここで観察したことをまとめると

「あとはすべて公開される」と言いましたが、じつは、もう一つだけ公開してはならない要素があります。 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![KOfpV|fG[H[MfHC:`^co9^ZiE[O[L[A[G
3q(,%EgnP[Fk[N%X[O6tU1Dau3{EG:y[M_j;dpcpc[C-*
@v2:,@3|m|g8y(CPd+I|[G*p[KY[M
-----END PigPGP MESSAGE-----

見るからに暗号文ですね。この暗号文自体はさしあたってどうでもいいことで、 問題はどういうしくみで暗号化が行われたか、です。

「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:25:22.699+09:00
DEBUG: Matrix : 1101873204, 3273236759, 1909682455, 2318114826
DEBUG: ★ Session Key : 87299389 3370057021 6126945580 2732355594  (38-digit)
DEBUG: Executing 87299389 3370057021 6126945580 2732355594  (38-digit) ^ 13  (2-digit)
         mod 413431709 4148138879 4136550065 9180344327  (39-digit)
DEBUG: Session Key ( RSA-Encrypted ) : 382228216 0834663851 1369448291 6825956097  (39-digit)
DEBUG: ** Total Cost: 0.23 seconds

まず、Matrix というのがありますが、これはセッション鍵です。 この「セッション鍵」の概念がRSAの実装を理解するうえでのいちばん難しいところなので、 以下の説明を注意深く読んでいただければと思います。

セッション鍵は、与えられた文章を暗号化するのに使うものです。暗号化の方法は基本的には何でもかまいません。 えっ、これはRSA暗号ではなかったのか?と思うでしょうか、まあ、最後まで説明させてください。

この PigPGP 0.2.3 ではヒル暗号という方式で、入力を暗号化しています。 ヒル暗号がどういうものか、を理解する必要はなく、それはRSAの本質ともまったく関係ありませんが、 要するに、Matrix と書いてあるところの 4 つのパラメータを使って入力を暗号化します。 このパラメータはランダムに生成した一回限りのものです。

ところが、このヒル暗号は対称暗号(または同じことですが慣用暗号)です。 難しそうな言葉ですが、要するに、これは「公開鍵暗号」でない「ふつう」の暗号です。 公開鍵とふつうの暗号はどう違うか。ふつうの暗号では「こうやって暗号化しましたよ」という暗号化の方法が分かれば、 暗号の解き方も分かります。これはどちらかといえば当たり前のことでしょう。 どうやって暗号化したかを公開してもそれを逆に解くことができない「公開鍵暗号」の方が、 常識に反しています。

ともあれ、上の (1101873204, 3273236759, 1909682455, 2318114826) というマトリックスは、 与えられた文章を暗号化した方法を表しており、 その下の
★ Session Key : 87299389 3370057021 6126945580 2732355594
は、マトリックスの4つの数を便宜上1つの大きな数にまとめたものです。 このセッション鍵は暗号化に使ったマトリックスそのもので、セッション鍵とマトリックスは簡単に相互変換できるので、 実質的に同じものだと考えてかまいません。要するに、

通信文
↓
セッション鍵をランダムに生成する
↓ セッション鍵872993...で暗号化
暗号文

こうしてできた暗号文を通信相手に送ればいいわけですが、ただ送っても、暗号ですから相手は読めません。 セッション鍵を一緒に送って「このセッション鍵で暗号をといて読んでください」と伝えればいいでしょうか。 それもまずいです。そもそも暗号化するのは、盗聴などされても中身が分からないようにするためです。 もし盗聴されたら、盗聴者は暗号文とセッション鍵を手に入れて、 「ははあ、このセッション鍵で暗号を解除すればいいのだな。楽勝楽勝」とせっかくの秘密の通信文を解読してしまうでしょう。

そこで、盗聴されてもいいように、872993...というセッション鍵をさらに暗号化します。

ここが概念的に難しいところです。 「鍵というのは暗号を解くためのものでしょう? 暗号を解く鍵をさらに暗号化するってどういうこと???」と思うかもしれません。 しかし、セッション鍵は上にあるように、この場合でいえば
87299389 3370057021 6126945580 2732355594
という整数であり、鍵といえども要するにただの数値ですから、その数値をさらに暗号化(=一定の計算で別の数値に変換)する、ということは、 別に理解できないことでもないでしょう……。

どのように暗号化するかというと、デバッグ出力にあるように、

DEBUG: Executing 87299389 3370057021 6126945580 2732355594  (38-digit) ^ 13  (2-digit)
         mod 413431709 4148138879 4136550065 9180344327  (39-digit)

これがそうです。87299...という38桁の数を13乗して、41343...という39桁の数で割った余りを求めます。

DEBUG: Session Key ( RSA-Encrypted ) : 382228216 0834663851 1369448291 6825956097  (39-digit)

が、結果です。RSA暗号化されたセッション鍵は38222...なんたらという39桁の数です。 この暗号化に使った「13乗」の部分は、公開鍵の「公開指数」でした。 また割り算に使った「4134なんたら」という大きな数は「法」でした。

こちらは公開鍵暗号なので、盗聴者に暗号化のしくみを知られても、痛くもかゆくもありません。 このしくみは秘密どころか、そもそも最初から公開なのです。 「わたしあてにメッセージを送るときは、13乗して4134なんたらで割った余りを送ってね」ということは大々的に公開しているのです。 公開鍵暗号なので、この暗号化のやり方が分かっても、「どうやったらそれを逆算して暗号をとけるのか」は簡単には分からないからです。

通信文
↓
セッション鍵をランダムに生成する
↓ セッション鍵872993...で暗号化
暗号文
↓
セッション鍵をRSA暗号化
↓
セッション鍵で暗号化された暗号文+RSAで暗号化されたセッション鍵

この暗号文を解読するには、スパイは、 何とかしてRSAシステムをクラックして使われたセッション鍵を割り出すか、 または、セッション鍵を使わずに何らかの方法(統計的解析など)で直接暗号文を解読するしかありません。 これは言うほど簡単なことではなく、きちんと設計しておけば、スパイもお手上げです。 (ここで説明に使っている例は鍵が128ビットしかないので、実は安全ではありませんが、 これはしくみを説明するためのミニチュアなので、気にしないでください。)

そんなことより、次の疑問が浮かぶはずです。 「ちょっと待った。そもそもセッション鍵で暗号化してそのセッション鍵をさらに暗号化などというややこしいことをしなくても、 最初からメッセージ全体をRSAで暗号化すればいいではないか。そうすれば暗号化処理は1回で済むし、 スパイによる『セッション鍵を使わない直接攻撃』も防げるではないか」

理論的にはまさにそのとおりなのですが、実際のRSA系では、セッション鍵を使うのが普通です。 そのわけは、次のセクションの実演で、実感できるでしょう。

ところで、暗号化に必要なのは、公開鍵だけです。 セッション鍵はシステムが自分でランダムに作ってくれるし、 セッション鍵をRSA暗号化する処理では「公開指数」乗して「法」で割るだけなので、 秘密鍵のデータ(秘密指数)は必要ありません。実際、「秘密鍵」の欄を空欄にしても、この暗号化のデモは問題なく動作しますので、 お試しください。

要するに、通信を送る側が通信文を暗号化するのには通信相手の「公開鍵」だけが必要で、 通信相手の「秘密鍵」を知る必要はないのです。ということは、通信相手は(公開していい)公開鍵だけを公開し、 秘密鍵はローカルにだけ置いて秘密にしておけば、それで安全な暗号通信が成り立つわけです。 これですべてつじつまが合い、スパイのつけいるすきはありません。

暗号化についてのまとめ
  1. 暗号ソフトはランダムに(それ一回限りの)使い捨てセッション鍵を発生させる
  2. 暗号ソフトは、セッション鍵を使って、通信文を暗号化する。このセッション鍵は「公開鍵暗号」ではなく、 鍵がばれると解読されてしまう。そこで……
  3. 暗号ソフトは、セッション鍵を、RSA公開鍵を使って暗号化する(鍵を使って鍵を暗号化、というのが概念的にちょっと分かりにくいと思います。じっくり考えてください)
  4. ステップ2で作った暗号文と、それを解読するのに必要なセッション鍵(ステップ3でRSA暗号化されている)の両方を通信相手に送る

上の暗号文サンプルをもう一度見てみましょう。

-----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![KOfpV|fG[H[MfHC:`^co9^ZiE[O[L[A[G
3q(,%EgnP[Fk[N%X[O6tU1Dau3{EG:y[M_j;dpcpc[C-*
@v2:,@3|m|g8y(CPd+I|[G*p[KY[M
-----END PigPGP MESSAGE-----

このサンプルで下から2行目の @v2: なんたらかんたら、というのがRSA暗号化されたセッション鍵です。 それ以外の 16t... の行から 3q(,%... の行までは、RSAではなく、ヒル暗号で暗号化されています。 (もちろん、内部的にすべては整数値なのですが、0~9までの10通りしかない数字の組み合わせを文字列として送ったら長たらしくなってしまうので、 ある方法で数値をASCII文字に変換しています。その点は本質に関係ないので、あまり気にしないでください。)

復号化(暗号文を元に戻すこと)

こうして送られてきた暗号文を元に戻すには、暗号化に使われたセッション鍵が必要です。 ところが、セッション鍵はRSA暗号化されているので、まずセッション鍵のRSA暗号をといて、生のセッション鍵を取り出し、 それを使って全体の暗号を解除する、という二段構えを行います。

実際に、デモページの入力欄に暗号文、秘密鍵欄に秘密鍵(暗号化に使った公開鍵とペアになっているもの)が入っている状態で、 「復号化」をクリックしてみてください。暗号が解けて、もともとの通信文が出てくるでしょう。

どういう処理が行われたのか、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-04T20:16:51.585+09:00
DEBUG: Session Key: ( RSA-Encrypted ) : 382228216 0834663851 1369448291 6825956097  (39-digit)
DEBUG: Executing 382228216 0834663851 1369448291 6825956097  (39-digit)
        ^ 349826831 0433040528 9967277996 9867917149  (39-digit)
        mod 413431709 4148138879 4136550065 9180344327  (39-digit)
DEBUG: ★ Session Key : 87299389 3370057021 6126945580 2732355594  (38-digit)
DEBUG: ** Total Cost: 1.813 seconds

暗号ソフトは、まず 38222... という「RSA暗号化されたセッション鍵」を認識しています。 これは暗号文自体に含まれているデータです(具体的には、@v2:,@3|m|g8y(CPd+I|[G*p[KY[M という最後の行)。 そして、

DEBUG: Executing 382228216 0834663851 1369448291 6825956097  (39-digit)
        ^ 349826831 0433040528 9967277996 9867917149  (39-digit)
        mod 413431709 4148138879 4136550065 9180344327  (39-digit)

これは、38222...というその数を、349826831 0433040528 9967277996 9867917149乗して、 413431709 4148138879 4136550065 9180344327で割った余りを求める計算をしています。 その答えが、
★ Session Key : 87299389 3370057021 6126945580 2732355594
であり、暗号化のとき使われたセッション鍵が復元されました。あとはこれを使ってヒル暗号を解除するだけです。

復元で使われた 349826831 0433040528 9967277996 9867917149 という指数は「秘密鍵」の「秘密指数」です。 また、余りを求める割り算で使われた 4134 なんたらという数は「公開鍵」「秘密鍵」共通の「法」です。

Aという数をRSA暗号化するには...
   Aを「公開指数」乗して「法」で割った余りBを求める

このBを元に戻すには
   Bを「秘密指数」乗して「法」で割る→Aに戻る

しくみはこれだけなのですが、いろいろと疑問がわくはずです。

第一の疑問は「鍵生成のアルゴリズムはどうなっているのか」ということであり、RSAを深く理解するための一つのポイントであり、 数学の理論的な部分です。

第二の疑問ですが、上の例でいえば、
382228216083466385113694482916825956097349826831043304052899672779969867917149÷413431709414813887941365500659180344327
という計算をしたわけです。割り算の部分はともかく、指数計算はべらぼうでしょう。なにせ、
382228216083466385113694482916825956097 × 382228216083466385113694482916825956097 × 382228216083466385113694482916825956097 × 382228216083466385113694482916825956097 × ....
と、このただでさえばかでかい数を、349澗8268溝3104穣3304秭0528垓9967京2779兆9698億6791万7149回も掛け合わせるのだから、 べらぼうこのうえない計算です。しかも、これは128ビットのミニチュアであり、 512ビットとか1024ビットという実際のRSAでは、これよりさらにずっと大きな規模です。 これは純粋数学というより、アルゴリズムの工夫の問題であり、「繰り返し二乗法」という方法を使えば、額面通りに上の計算をしなくて済みます。

しかし、繰り返し二乗法を使っても、これが相当な計算量であることは明らかでしょう。 実際、けっこう時間がかかります。 暗号文の中の1行(セッション鍵の部分)だけを処理するのでも、RSAではこんなすごい計算が必要になることを考えれば、 暗号文全体をRSA処理するより、基本的には「ふつう」の暗号で処理しておいて、そのふつうの暗号の鍵になるセッション鍵だけをRSA処理する、 という二段構えが現実的な選択だということが、何となく分かるのではないでしょうか。

もっと詳しく学ぶには

以上で、何となく全体の雰囲気はつかめたとは思いますが、 数学などの具体的な説明は、ほとんどしませんでした。 また、PigPGP のデモ画面をみると、「擬素数(ぎそすう)対策」というオプションがありますが、 このオプションについても、まったく触れませんでした。

このサイト(妖精現実)には、RSA暗号のいろいろな面をもう少し具体的に学ぶのに参考になる記事がいくつかあります。 なかには古い記事、あまり分かりやすい説明でない記事もあり、機会があれば更新したいとは思っていますが、 とりあえず、ないよりまし、ということで、興味を感じられたなら参考にしてみてください。

高校数学で遊ぶ公開鍵暗号RSA
実際の計算、特に繰り返し二乗法について、具体的な数値を上げて説明したものです。
フェルマーの小定理
RSAの鍵生成では大きな素数を探すことが本質的です。そのための出発点となる「フェルマーの小定理」について説明しています。
RSA暗号と擬素数(ぎそすう) - JavaScript
素数探しには「フェルマーの小定理の逆」(フェルマーテスト)が基本となります。その説明です。
ミラーテストと強擬素数(きょうぎそすう)
現実の実装では、フェルマーテストを効率化・高性能化したミラー・ラビン・テストを使います。その説明です。
巨大整数計算の実装
RSAの実装には巨大整数の計算が必要です。そのための考え方を説明してます。 これは bigint.js v0.4 当時の古いもので、現在のライブラリに使われている bigint.js v0.5 に比べると、 極めて遅いですが、基本となる考え方は大筋では同じです。
楕円曲線暗号
RSAとは関係ありませんが、RSAと並ぶもう一つの公開鍵系である楕円曲線暗号(ECC)についての紹介です。

相互リンク

大学の授業で参考資料にされたそうです。 一関工業高等専門学校でも学習参考情報としてリンクされました。 全般的にはわけの分からないサイトですが人様のお役にも立っているということで…。

この記事のURL



<メールアドレス>