ダイヤルはしばらく高速でぐるぐる回り、、、そして止まります。針は当選番号の3を示しています。悪意のある配達屋さんは途中の33しか知りません。無事、太郎さんはポチさんからロトくじの番号を配達屋さんに知られずに受け取ることができました。疑問がいくつかわきます。当選番号が3じゃなくて他の数の場合でもちゃんと太郎さんはダイヤルを戻せるのか?どこから公開鍵3と秘密鍵29が出てくるのか。他の数はありえるのか?ダイヤルは35メモリじゃないといけないのか?配達屋さんは途中の33のダイヤルと公開鍵の3から当選番号がわかるのでは?一つ一つ答えていきます。当選番号が3じゃなくて他の数の場合でもダイヤルを戻せるのか?例えば次の回の当選番号が4だったとします。ポチさんが公開鍵の3回ボタンを押すと4x4x4x4で1024メモリ0からぐるぐる回って指し示すのは9。太郎さんは前回と同じくボタンを秘密鍵の29回押します。9x9x9x9x.....、9が29回。なんと針は4710128697246244834921603689メモリ進みます。回った針は、、、ちゃんと当選番号の4になりました。どこから公開鍵5と秘密鍵29が出てくるのか3と29のふたつの鍵はダイヤルのメモリ数が35であることと強く関わっています。35を最も細かいかけ算の組み合わせにすると7x5です(これらの様な他の数のかけ算では表せない数のことを「素数」といいます)。それぞれから1ひいた数、6と4をかけ合わせます。この24の倍数24、48、72、96、120、144・・にそれぞれ1を足した25、49、73、97,121,145・・の中からふたつの数のかけ算で表せる数を探します。145は5に29をかけた数ですね。この5と29のふたつのペアが公開鍵と秘密鍵となります。それでは同じ様に5と53のペアではどうでしょう。これもかけたら265で24の倍数+1の数のうちの一つになります。当選番号は4にします。ダイヤルを4にセットしてボタンを5回、針はぐるぐるまわり9を示します。)、、、針はちゃんと4に戻っているはずです。逆に5、29ではなく29、5と公開鍵秘密鍵を選んだ場合はどうでしょうか。当選番号4を29回(公開鍵)かけ合わせた数を進ませたら針はは9。次にその9を5回(秘密鍵)かけ合わせると9x9x9x9x9で59049。回転した針は、、もとの4です。公開鍵と秘密鍵は扱いが違うだけで逆にしてもちゃんと使用できます。配達屋さんは途中の33のダイヤルと公開鍵の5から当選番号がわかるのでは?これは、実はかんたんにできます。してかというとダイヤルの35は7x5なので、それぞれから1をひいた6と4、かけて24なのがすぐにわかるからです。24の倍数+1の数である24、48、72、96、120、144・・・の中から1足して公開鍵の5で割り切れる数を探します。144が1を足して5で割ると29で割り切れます。これで秘密鍵29がばれました。あとは上の手順で当選番号が得られます。こんなに簡単に解けてしまうRSA暗号がどうして世の中で標準的に使われているのでしょう。そのポイントは配達屋さんがダイヤルの35から7x5を思いついた所にあります。それではもしダイヤルが35ではなく221だったらどうでしょうか。うーん、13x17です。これが3433x4049の組み合わせであると言える人は少ないと思います。大きな数の素数の組み合わせを計算でさがすのは難しいのです。実際のコンピュータではもっともっと大きな数を使っています。これが世界中で使われているRSA暗号の安全性をささえている土台です。RSA暗号の原理さらに疑問が残る人もいるでしょう。そもそもなぜダイヤルを使うのか上で行った公開鍵秘密鍵を作るときの計算はどういう意味があるのか。24の倍数+1になるふたつの数を簡単に探していたが組み合わせはどうやって探せばいいのか簡単に解説します。まっすぐのものさしはメモリ4cmの所から5cm延ばしたら9cmの所になります。ところが一周7のダイヤルの場合はメモリ4から5メモリ回したら、、9ではなくダイヤルは一周して2になります。これを9を7でわった剰余(じょうよ)といいます。シンプルな公開鍵暗号ダイヤルの一周が素数(それ以上割り切れない数)の場合、メモリがどの位置にあってもその数をダイヤルの一周の数(ここでは7)だけかけ合わせた数(2の場合は2x2x2x2x2x2x2で128)、その数をゼロから回すと元の数に戻ることを「フェルマーの小定理」といいます。実はこれだけでも公開鍵暗号は作れてしまいます。上の例だと7をふたつに分けて4と3にして、それぞれを使い適当な数、例えば2を鍵の数だけかけあせます。2x2x2x2で32を公開鍵としてみんなに伝え2x2x2の16を秘密鍵として自分で秘密にしておくのです。当選番号が3だとするとそれを公開鍵の32にかけて96メモリダイヤルを回すと針は5。5を秘密鍵の16をかけ80。ゼロから80ダイヤルを回すと、、、3。この方法の問題点はすぐにわかります。ダイヤルの数7から公開鍵の2のかけ合わせ数、つまり4をひくと秘密鍵のもとの3が得られ2を3回かけると秘密鍵の16がかんたんに導かれてしまいます。改善した公開鍵暗号そこでもう少し改善します。上の問題点はダイヤルの数から公開鍵と秘密鍵の合計をかんたんに推測できたことでしたね。先ほどはダイヤルの数を素数にしましたが今度はふたつの素数をかけ合わせた数をダイヤル数とします。例と同じく35(7x5)とします。このような時、メモリがどの位置にあっても「0と7と5を使わないでかけ算で表せるメモリの数」だけかけ合わせると元の数に戻るのです。今の場合、「0と7と5を使わないでかけ算で表せるメモリの数」は24個あります。このダイヤルではメモリがどの位置にあってもその数を24回かけ合わせると元に戻るのです。このようなことを「オイラーの定理」といいますここでの「素数の成分を使わないでかけ算で表せるメモリの数」はそれぞれの素数から1引いた数をかけ合わせた数になります。7x5だと6と4をかけた数、24です。ここから公開鍵と秘密鍵を作ります。この計算は上の方で公開鍵と秘密鍵を作る時にした計算と同じですね。(実際のRSA暗号ではここでいう6と4の最小公倍数という数を使います)ふたつの素数をかけ合わせた数からそれぞれの素数を導くことが難しいのは前述の通りです。これで信頼性の高いRSA公開鍵暗号が完成しました。24の倍数+1になるふたつの数を簡単に探していたが組み合わせはどうやって探せばいいのかまず24からから適当な数を選びます。この時24の素数である2と3を含んだかけ算で表現できる数は使わないようにします。例と同じく5としましょう。これに何かをかけると24の倍数+1になります。5x(なにか)と24x(なにか)の差は1になるはずです。24を5でわると4あまり4。このあまりの4を5からひくと1。4というのはつまり(24−5x4)なので5から(24-5x4)をひくと1なのと同じです。整理すると5x5-24x1が1となります。これで一つペアが見つかりました。これでは公開鍵と秘密鍵が同じなので面白くありません。そこで5x5-24x1に(5x24-24x5)を足していきます。(5x24−24x5)はゼロなので足しても影響はありません。一度足すと5x29−24x6になります。5と29のペアが見つかりました。一回足すと5x53−24x11、5x53のペアです。これも先ほど確かめましたよね。詳しく知りたい方は「ユークリッド互除法をつかいRSA暗号の公開鍵と秘密鍵をもとめる方法」を参照してください。おわりにかけ足でしたが世の中で標準となっているRSA暗号の雰囲気だけでも感じて頂ければ幸いです。小さい子にもわかる様に剰余や累乗、変数なしで説明できないかなと思い書きました。大人の方にはよけい煩雑で複雑だったかもしれません。詳しく勉強したい方は以下のサイトがとても参考になります。しょうがくせい向けRSA暗号の仕組み。