素数

久しぶりの安息日を楽しむつもりが・・・先週末は猛烈に忙しかった竹井です、こんばんは。昨日の日曜日、家に帰ってテレビつけたら、NHK スペシャルでリーマン予想についての番組やってて、ちょっとそれにそそられて記事を書きたくなっちゃいましたもんで、ちょっと。

実は昔、素数が織り成す理論に心底から陶酔していた時期があって (いまでも素数は大好きですけど)、整数論についての本を色々読んでみたり、素数列挙のアルゴリズムを色々書いてみたり・・・、挙句の果てに RSA 暗号のシステムを自分の手で作ったことさえありました。思えば中高生のころ、まだ若かったですね。ちなみに、番組の途中で、マーカス デュ ソートイというオックスフォード大の教授が出てましたが、この方が書かれた本の訳書「素数の音楽」を読んであまりにもそれが面白くて、原著まで買ってしまったほど。

最初に僕が RSA 暗号を作りたいと思ったモチベーションは良く覚えてはいませんが、妖精現実 フェアリアルという Web サイトにはだいぶお世話になりました。ここでは JavaScript を利用した RSA 暗号の構成方法などが事細かに説明されていて、巨大整数を扱う方法、素数の探し方 (素数判定方法)、実際の暗号化のアルゴリズム、そして高速化など多くのことを学びました。

// C# によるエラトステネスの篩の実装
var n = 1000;
var sieve = new bool[n + 1];
var m = (int)Math.Floor(Math.Sqrt(n)) + 1;
for (var i = 2; i <= n; i++) sieve[i] = true;
for (var i = 2; i < m; i++)
    if (sieve[i])
        for (var j = i * i; j <= n; j += i)
            sieve[j] = false;
for (var i = 2; i <= n; i++)
    if (sieve[i])
        Console.WriteLine(i);

僕自身は中学 3 年のころ、もうそのときにはすでに C# を使っていて、RSA 暗号の実装をマネするのに UInt4096 という多倍長整数の実装などからガリガリやりました。先ほどの Web サイトの JavaScript 実装では、内部に文字列で長整数を保存するという方法をとっていたみたいでしたが、C# で実装するにあたって高速に演算させることを念頭に置きました。そこで byte 型の 512 要素配列を使って、加減算はポインタを利用して short 型の演算に置き換えたり、乗算についてはなるべくループ回数を減らしつつ楽に演算を行えるようにするなど・・・本当にいろいろ今の自分の原点のようなところがありましたね。今よりも、断然頭が柔らかかったと思います。そしてそれだけあの時に書いたプログラムへの思い入れも大きいです。

そういえば高校の時、かなり感動した証明がありました。ベルトランの仮説というものをご存知ですか？ いかなる 2 以上の整数 n について、必ず n と 2n の間に少なくとも 1 つは素数がある、というものですが、これはチェビシェフによって初等的な証明が与えられています。ほとんどが二項係数 (組み合わせの数 _nC_k のこと) をいじくりまわすだけで示すという感じでして、高校生でも十分理解できる内容でした。素数が登場するこんなに素朴で根源的な命題に対して、自分が持ち合わせているツールで証明が与えられるということを知ったのは、本当にうれしかったですね。

RSA 暗号の原理

というところで、ここで唐突に RSA 暗号の仕組みをちょろっと紹介してみましょうかね。やっぱり、素数が一番活躍している場所って言ったら暗号系だと思います。ただ暗号っていうと、結構複雑なイメージがあるかもしれませんが、原理はすごく単純です。あくまで触りしか書かないので、バックグラウンドの理論が知りたければ適当に調べてください。では、はじまりはじまり。

まず、最初におっきな素数を 2 つ見つけてきます。こいつらを p, q としておきます。そして n = pq, u = (p - 1)(q - 1) という 2 つの値を計算します。ここで、適当に素因数に p, q を持たない適当な数 α を選んできて、うまい具合に αβ ≡ 1 (mod u) となるような β を求めます (まぁ実際には拡張ユークリッドの互除法というアルゴリズムを使いますが) これで準備は終了です。公開鍵は α と n、秘密鍵は β と n になります。

はい、いよいよデータの暗号化の段階です。あらかじめデータは数値データに変換しておきます。たとえば d とでもしておきましょう。暗号化は単に d^α mod n という式を計算するだけです。この値が c という暗号化されたデータになります。復号化するには逆に c^β mod n という式を計算するだけ。本当に単純でしょ？ 実際にやってみましょう。

素数を 2 つ選んできます: p = 83, q = 79
n = pq = 6557, u = (p-1)(q-1) = 6396

そして鍵のペアを作ります。まず片方の α を決めます: α = 89 (公開鍵)
この α に対し、αβ ≡ 1 (mod u) となる β を計算します: β = 3737 (秘密鍵)

実際に暗号化してみましょう。適当にデータを選びます: d = 231 (平文)
(d^α) mod n = (231^89) mod 6557 = 1912 (暗号文)
そして元に戻してみます。
(d^α) mod n = (1912^3737) mod 6557 = 231 (復号化した後の平文)

というわけでうまく行きました！

そんなこんなで、なんか取りとめもない記事になっちゃいましたが、、、やっぱり素数って美しいですよね！ こんなまとめ方でいいのか・・・ははは(笑) ではでは