しょうがくせい向けRSA暗号の仕組み
RSA暗号の仕組みを小学生にでもわかりやすいように、なるべく簡単な用語を用いて解説しています。
秘密の数・秘密じゃない数とダイヤル
登場人物
- ポチさん:発表前のロトくじの当選番号をなぜか知っています。くじは0−34の数字を一つ選ぶだけの高確率くじです。
- 太郎さん:ポチさんの仲間。都合で買いにいけないポチさんに代わり、くじを買いにいきます。
- 配達屋さん:悪意のある配達屋さん。ポチさん太郎さんから当選番号を横取りしようとしています。
ダイヤル
ダイヤルがあります。特別なもので0−34までのメモリがついています。ボタンがあり好きな数だけ押すことが出来ます。すると針は一旦0にもどり「今さしていいる数」を「今押した数」だけ「かけ合わせた数ぶん」針が回ります。例えば3をさしているときにボタンを2回おすと3x3で0から9メモリ針が進みます。2をさしているときに3回おしたら2x2x2で0から8メモリ針が進みます。
問題点
ポチさんはロトくじの当選番号(0-34のどれか)を知っています。太郎さんが配達屋さんに依頼してポチさんにダイヤルを渡します。ポチさんはダイヤルを当選番号、例えば3にセットし配達屋さん経由で太郎さんに渡します。悪意のある配達屋さんは当選番号を盗み見ることで自分も、くじに当選できてしまいます。
RSA暗号によるうけわたし
そこで太郎さんは工夫します。ダイヤルの横には「公開鍵は5」と書いてあります。そして配達屋さん経由でポチさんにダイヤルを渡します。
ポチさんは当選番号、たとえば3だとするとダイヤルを3にまわしボタンを公開鍵の回数、5回押します。針は一旦0に戻り3を5回かけたメモリ分、つまり3x3x3x3x3で243メモリが自動的に進みます。ぐるぐる回って針は33でとまります。
ポチさんは33を指し示したダイヤルを配達屋さん経由で太郎さんに返します。太郎さんは二人には言っていない秘密鍵29を知っています。太郎さんは29回ボタンを押します。進む数は33x33x33x・・・・・x33。33が29回。途方も無い数です。ダイヤルはしばらく高速でぐるぐる回り、、、そして止まります。針は当選番号の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の倍数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を示します。そこから秘密鍵53回分ボタンを押すと（今度の針の進みは375710212613...全51桁分です！ ）、、、針はちゃんと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です。それでは13900217の場合は？ 多分すぐにこれが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となります。これで一つペアが見つかりました。5と5です。しかしこれでは公開鍵と秘密鍵が同じなので面白くありません。そこで5x5-24x1に（5x24-24x5）を足していきます。(5x24−24x5)はゼロなので足しても影響はありません。一度足すと5x29−24x6になります。5と29のペアが見つかりました。もう一回足すと5x53−24x11、5x53のペアです。これも先ほど確かめましたよね。詳しく知りたい方は「ユークリッド互除法をつかいRSA暗号の公開鍵と秘密鍵をもとめる方法」を参照してください。
おわりに
かけ足でしたが世の中で標準となっているRSA暗号の雰囲気だけでも感じて頂ければ幸いです。なるべく小さい子にもわかる様に剰余や累乗、変数なしで説明できないかなと思い書きました。大人の方にはよけい煩雑で複雑だったかもしれません。さらに詳しく勉強したい方は以下のサイトがとても参考になります。
参考リンク
- RSA暗号とは①～素数判定の処理～: 意志あるところに道は開く ～Where there is a will, there is a way.～
- 自堕落な技術者の日記 : RSAサイトの攻撃によるワンタイムパスワードSecurIDの影響を想像してみる - livedoor Blog（ブログ）
- RSA暗号の仕組みがすっきりと分かった瞬間｜ブログ・エス技研
- RSA暗号のしくみとSSL証明書 - makの枕草子
