2011年01月05日
容疑者Aの本能 ≡ 数学者Bの挑戦 (mod盗難車Xのメッセージ) (PC)
まずはじめに、2010年度、盗難車ワースト10は以下通りです。。。
1位
ハイエース
2位
ランドクルーザー
3位
セルシオ
4位
ワゴンR
5位
クラウン
6位
マークX
7位
タント
8位
キャンター
9位
ステップワゴン
10位
インプレッサ
車種からお分かりの通り、盗難車の多くはドバイを経由して、アフリカなどに流れてるそうです。
セキュリティ技術が発達した現在も尚、車の盗難件数は減るどころか増える一方です(≧≦)
RSA暗号は、インターネットセキュリティやカーセキュリティでも広く利用されている話題の暗号です。この暗号をはじめとする現代の暗号は、戦争中に一部組織でのみ使用されてきた暗号とは全く異なり、情報セキュリティを確保する根幹技術として、情報ネットワーク社会に生きる我々に大きな安心を与えてくれるものです。ともすれば、既に無意識のうちに利用されている方もいるでしょうし、少なくともこれからの生活には必要不可欠なものとなるでしょう。
このような現代暗号には、RSA暗号の他にも DES (デス,ディ・イー・エス)や AES(エー・イー・エス)など、非常に数多くの方式が存在します。多くの暗号が複雑な設計であるのに対し、現代暗号の中で最も特徴的な RSA 暗号のエッセンスはとっても単純かつ面白い理論によって成り立っています。
僕が今回気になったのは、暗号の方式ではなく、暗号の「からくり」の方です。
ということで、普段何気なく使用していの暗号のカラクリを、ある優秀な大学生の書き物を読んで勉強してみました。
RSA暗号ではある数を法(モジュロ)とする世界で、平文の数値を別の数値に変換します。RSA暗号を支えるこの世界の数値の興味深い性質をお話しします。
RSA暗号は、自由に選んだ異なる二つの素数を掛けた数を法とする世界を利用します。 素数というのは、例えば、2, 3, 5, 7, 11, ... のように、その数自身と 1 以外の自然数では割りきることができない 2 以上の整数のことです。 4 は 2 で、 6 は 2 や 3 で割りきることができるから素数ではありません。では、そのような世界の例として、二つの素数に 3 と 11 を選び、これらを掛けた数 33 を法とする世界を考えてみましょう。 33 を法とする世界に存在する数は、0 から 32 までだけです( 33 までいったら 0 に戻るからです)。
この世界に存在する全ての数のべき乗を全て求めて表にしてみます。
これは、ある数値の○乗はいくつか?という表です。一番左の列がべき乗されるこの世界の数、一番上の行が何乗するかという数です。例えば、べき乗される数が 2 の時は、 1 乗で 2、 2 乗で 4、 3 乗で 8、 4 乗で 16、 5 乗で 32、 6 乗で 64 … 64 は 33 を法とする世界では 31 になります。そしてまた、 6 乗で 62 … 62 は 33 を法とする世界では 29 … という風に続けていきます。
さて、この表をよく見て下さい。 33 を法とする世界に存在する 1 から 32 までの全ての数は、べき乗する度に予想のつかない数に変わっていきながらも、全ての数はなんと11 乗又は 21 乗すると自分自身に戻っているでしょう!(水色のセルの部分)このように、2つの素数( P, Q とします)をかけた数を法とする世界では、全ての数が自分自身に戻るべき乗数が必ず存在します。そして、これが何乗なのかは、最初の2つの素数 ( P , Q ) によって決まります。つまり、実はその2つの素数さえ分かってさえいれば、このべき乗数は簡単に求めることができるのです。
それは、P と Q からそれぞれ 1 を引いた P-1 と Q-1 の最小公倍数に 1 を足した数です。すべての数は、この数の回数だけべき乗した時、必ずもとの数に戻るのです。そして、そのようになるべき乗数は、一定のペースでまたやってきます。そのペースとは、 P-1 と Q-1 の最小公倍数です。従って、P×Q を法とする世界で、全ての数が自分自身に戻るべき乗数は、n × ( P-1 と Q-1 の最小公倍数)+ 1と表すことができます。ちなみに (P-1)×(Q-1) という式は必ず( P-1 と Q-1 の最小公倍数)の倍数 になります ので、このべき乗数の一部は簡単に
n × (P - 1) × (Q - 1) + 1
(但し n は任意の正の整数)
として求めることができます。
どうでしょう、先程の2つの素数 P=3, Q=11 とする時、 P-1=2 と Q-1=10 の最小公倍数は 10 であり、n × ( P-1 と Q-1 の最小公倍数)+ 1 は n=1 で 1×10 + 1 = 11 となりますが、確かに上記の表を見てみると 11 乗でどの数も必ず自分自身に戻っています! また、n×(P-1)×(Q-1) + 1も、 n=1 で 1×(3-1)×(11-1) + 1 = 2×10 + 1 = 21 となり、上記の表と同じく、 21 乗でも同様のことが起こっているのが分かります。
さぁ、これをどう暗号化に利用するのでしょうか? 気が付きますか? RSA暗号では、このように適当な素数 P , Q を掛けた数 P×Q を法とする世界を考え、暗号化したい平文の数値 (但し P×Q 未満) を、「適当な数」 分だけべき乗してしまうのです。ここで何乗するかというのが1つ目の鍵(E) となります。 すると、あらゆる数は予想がつかない数に変換されます。これが暗号化でこれにより変換された数値が暗号文 (暗号語) となるのです。そして、この暗号化された数値をもとの数値に戻す復号を行なうには、暗号化の際べき乗した数( E乗 )の部分から、全体として自分自身に戻るようなべき乗数になるようさらにべき乗してやればよいのです。このべき乗数が鍵 (E) に対応するもう一つの鍵 (D) となるのです。
ここで 「わざわざ (D) 乗しなくても単に (E) 乗根を求めれば元の数が得られるのでは?」 という疑問を持たれる人もいるかもしれません。それは確かに私たちが住んでいる普通の世界なら可能です。例えば 2 を 4 乗して 16 を得た時、 16 の 4 乗根を求めれば元の 2 が得られます。しかし、今、この暗号で利用している素数を二つかけ合わせた数を法とする世界は我々の世界のような単純な割算はできないため、逆に( E乗 )分を逆算して元の数に戻すことができないのです。これが暗号化に使用した鍵では復号ができない 「からくり」 になっているのです。
いかがでしょうか?RSA暗号 のからくりが、なんとなく分かってきましたか?まだわかっていなくても、大丈夫。次でもう一度具体的に解説しますから。
では実際に、自由に選んだ2つの素数の例に P=3, Q=11 を選び、それらを掛けた P×Q = 33 を法とする世界を利用して、RSA暗号による暗号化を行ってみます。
相手に秘密に伝えたい平文の数値列を、7 13 17 24 とでもします(実際に文字を暗号化する時は、一旦文字を数値に直すのです)。これを友人から自分に送ってもらうことを想定します。まず、暗号化するための鍵(公開鍵暗号方式の概念を覚えていますか?暗号化するための鍵はみんなに公開してしまうのです)を決めます。すなわち、 33 を法とする世界で暗号化の際に一旦何乗するかということです。
では、この公開する鍵を適当に 3 に決めましょう(但し、実際は適当にはとれず多少の制限があります)。そしてこれを友人に伝えます。" 33 を法として、鍵を 3 として暗号化してくれ"と。よって公開する情報は、法とする数 33 と公開鍵 3 です。友人は平文 7 13 17 24 を言われた通りの条件で暗号化します。 33 を法とする世界でのべき乗表をもう一度下記に示しておきますので、参考にしてください。
まず 7 は、 3乗すると 13。
次、 13 は、 3乗すると 19。
次、 17 は、 3乗すると 29。
最後 24 は、 3乗すると 30。
従って、平文 7 13 17 24 の暗号文は 13 19 29 30 となります。
さて、この暗号文を受け取ったあなたはこれを復号して平文に戻します。それには、公開した鍵 3 のペアとなる秘密の鍵を求めて、さらにその数分だけ暗号文をべき乗してやればよいはずです。 33 を法とする時、存在する全ての数は n×(3-1)×(11-1) + 1 乗すると元に戻るのですから、 3 という鍵で暗号化したなら(既に 3 乗されているので)、3 乗した時の数をさらにある数 (D) 乗した結果が、全体として n×(3-1)×(11-1) + 1 乗 (n は任意の整数)になるようにすればいいのです。 分かりますか?
A を平文の数値とする時、暗号化に使った鍵が 3 なので A を暗号化した後の値はすでに 3 乗されているため、全体として A が再び元の A に戻るだけの べき乗 にしてしまうような秘密の鍵 D は、
(A3)D = A{n × (P - 1) × (Q - 1) + 1}
という関係がなければならないので(但し n は自由な正の数)、
3 × D = n × (P - 1) × (Q - 1) + 1
↓
3 × D = n × (3 - 1) × (11 - 1) + 1
↓
D = 3分の n × 2 × 10 + 1
という式を満たす必要があります。このような D としては… n が 1 の時にD=7となりますから、この 7 が暗号化の鍵 (E) として 3 を使った暗号文を復号できる秘密の鍵 (D) となります。では求めた秘密の鍵 7 で送られてきた暗号文 13 19 29 30 を復号してみましょう。 33 を法とする世界で考えるんでしたね。
まず 13 は、7 乗すると 7 。
次、 19 は、7 乗すると 13。
次、 29 は、7 乗すると 17。
最後 30 は、7 乗すると 24。
結果、7 13 17 24 となり、最初の平文に一致します。見事に復号することができました。
RSA暗号の暗号化と復号の手順が分かりました。少しだけまとめると、まず自由な2つの異なる素数 P , Q を定め、 N ( = P×Q ) を法とする世界を考えるのです。この P×Q を法とする世界で、平文の数値を適当に定めた E 乗することで暗号化を行ないます。この時、全ての数は n×(P-1)×(Q-1) + 1 乗するとどんな数も必ず自分自身に戻るため、
(AE)D = A{n × (P - 1) × (Q - 1) + 1}
という関係がなければならないので (但し n は自由な正の数)、
E × D = n × (P - 1) × (Q - 1) + 1
↓
D = E分の n × (P - 1) × (Q - 1) + 1
(専門書では 「逆元」 と 「ユークリッドの互除法」 により同式を得ます)
から D を求め、暗号化した数値を D 乗すれば、ふたたび元の平文の数値に戻ることになるはずです。従って、この D が、E 乗して暗号化した暗号文を復号できる鍵になります (但し E は (P-1)×(Q-1) と互いに素な数とする必要があります)。
結局、重要なのは2つの素数P と Qです。法とする数 P×Q と、暗号化に使う鍵 E は公開してしまうので、もしも P と Q がバレてしまったら秘密にしなければならない鍵 D を上の式から求められてしまいます。 P と Q は暗号としては2つの鍵を作り出すのに必要なだけで、直接暗号化や復号の作業には登場しないものなので、一度鍵を作ったら P と Q をメモした紙は食べてしまうくらいな方が一番よいかもしれません。
しかし、このような仕組みでは、ある疑問がわきませんか? 「 P×Q の結果は公に教えてしまうのに P と Q 自体は教えてはいけない」 なんて…でも 「P×Q を教えたら P と Q が分かってしまうのではないのか?」 と。 つまり、先ほどの例で言えば「ある素数と素数を掛けたら 10 になった ( P×Q = 10 )」 ということは教えるけども、つまり 「それがいくつといくつか ( P=2, Q=5 )」 は教えてはいけないなんて、 P×Q = 10 が分かれば、誰でも P=2, Q=5 って分かっちゃうんじゃじゃないの…?ということです。
それが RSA暗号 の重要なミソのなのです。これ、素因数分解の事ですよね。
「素因数分解」 は、中学生三年生で習うはずです。ある数が与えられたら、その数と 1 でしか割りきることができない 2 以上の整数…すなわち素数を使った掛け算の式に分解することです。例えば、 33 なら 3×11 という式に分解できますね。 3 も 11 もそれぞれ素数ですよね。
あらま!?、そんな方法があるのなら、法とする数 P×Q = 33 を公開してしまえば、誰にでも P=3, Q=11 であることが分かってしまいまいますョ…。そして公開する鍵 E は公開されてるから秘密の鍵 D を求められてしまいます。う~ん、これは困りましたね…。 でもこの 33 の素因数分解、あなたはどのような方法で 3×11 に分解できることが分かったのですか?
実はこれ、人間の勘と長年の経験によるところが非常に大きいのです。その証拠に、それでは6887はどう素因数分解されますか?これも2つの素数に分解できるのですが、一体どうしたら分解できるかなんて数学者でもきっと思い付かないでしょう。思い付いたとして、きっと2 から順に 3, 5 ...って割れないかどうか順に試してみるくらいがオチじゃないですか?
それもそのはず、なんと現在のところ巨大な二つの素数を掛け合わせた数を素因数分解する効率的な方法が見つかっていないのです…。つまり二つの素数 P=3 と Q=11 を掛けて P×Q = 3×11 = 33 を求めることは簡単にできますが、逆に掛けた結果の P×Q = 33 から P と Q ( 3 と 11 ) を知ることは極めて難しいのです。これが重要なのです。 6887 を素因数分解できなかったのは、決して僕の頭が悪かったからではないのです。ちなみにこれは 71 と 97 に素因数分解できます。実際に掛けてみて下さい、71 と 97 を掛けて 6887 を求める方は小学生でも出来ますから。
先ほどの RSA暗号 は試しに P=3, Q=11 で P×Q = 33 という小さな数で行ったために P×Q = 33 から P=3 と Q=11 を割り出せてしまいましたが、これが巨大な素数を掛けたものとなると決して割り出せなくなってしまうのです。この結果、法とする数 ( P×Q ) と 公開鍵 E を公開してしまっても、 P, Q を使って秘密鍵 D を求めた本人以外に、秘密鍵 D を知られずに済むのです。 RSA暗号は、暗号のしくみは 「奇跡が起きるべき乗数」 に、そして安全性はこの素因数分解の難しさによって保証されているのです。
暗号解読の前に数学って面白いですね^^
その面白いという心を正義の為に使って欲しいのですが、数学者や科学者または物理学者は、発明した後の、使う人間のことまでは考えてくれませんよね。。。
PS
タイトルの容疑者Aの本能 ≡ 数学者Bの挑戦 (mod盗難車Xのメッセージ)とは、以下の通りです。
a, b, m を整数とする。
a と b を m で割った余りが等しい時、a と b は m を法として合同であるといい、
a ≡ b ( mod m ) と書きます。
例 )
5 ≡ 2 ( mod 3 )
8 ≡ 18 ( mod 2 )
14 ≡ 0 ( mod 14 )
-7 ≡ 19 ( mod 13 ) 等。
ブログ一覧 |
気になって仕方ないこと | クルマ
Posted at
2011/01/05 06:14:36
タグ
今、あなたにおすすめ