暗号コラム③

The real mathematics is almost wholly useless.

こんにちは、鈴木です。皆さん、数学はお好きですか？ よく耳にするのは「数学なんて将来の役に立たない」というボヤキです。そんなボヤキをTwitterやLINEでつぶやく時にも実は数学は使われています。前回、「公開鍵暗号と秘密の通信」というコラムで秘密の通信を行うための方法を紹介しました。SSLなどで暗号通信を行う際に公開鍵暗号の1つであるRSA暗号が利用されます。RSA暗号は整数の性質を巧みに利用した暗号です。今回は公開鍵暗号の1つであるRSA暗号とその裏でキラリと輝く数学を紹介したいと思います。

余りものには数学がある

ここで、皆様に簡単な問題を出します。次の問題を解いてみてください。ここで * と / はそれぞれ乗算、除算の記号です。

2 * 3 = ?

3 / 4 = ?

6 と 4分の3 (0.75) に決まっているじゃないか、と思ったかもしれません。そんな風に考えていた時期が私にもありました。実は、数学では2 * 3が 6 ではない世界 があります。3 / 4 が 2となる世界があります。RSA暗号ではそんな世界を使って構成されています。

その世界は言わば余りの世界と呼びます。小学生のとき、このような割り算の計算をやった覚えがあるかと思います。

13 ÷ 5 = 2 あまり 3

17 ÷ 5 = 3 あまり 2

小学校では「あまり」という言葉を用いますが、数学の世界ではあまり使いません。数式では次のように書くことが多いです。

13 = 5 * 2 + 3

17 = 5 * 3 + 2

「13 = 5 * 2 + 3」は「13を5で割ると、商は2、剰余は3」という意味になります。数学ではあまりの事を剰余と呼びます。漢字で書くとかっこいいですね。

割り算の話を一般化して、「自然数 n を 自然数 mで割ると、商は q 、剰余は r」を数式で表すと次のようになります。

n = m * q + r.

この 剰余 r　が大切になります。¹

具体例を考えてみましょう。m = 2 とします。自然数を 2 で割ると剰余は 0 か 1 になります。これは、自然数は偶数か奇数のいずれかである、ということを意味しています。この様に、偶数、奇数は 2 で割った剰余に着目して自然数を分類しています。つまり、自然数を「mで割った剰余」に着目することで無限にある自然数を m 種類に分類することができます。²

剰余の世界の不思議な演算

不思議な世界に入るためには剰余の世界に四則演算を定義する必要があります。例として、5で割った剰余の世界を考えてみます。自然数を5で割った場合の剰余は 0, 1, 2, 3, 4 のいずれかになります。偶数・奇数の考え方と同様に、自然数を0から4のいずれかのグループに分類した、ということです。³

この世界での演算を2つ、加法と乗法を定義したいと思います。

加法 : a + b = (a + b を 5で割った剰余)

乗法 : a * b := (a * b を 5で割った剰余)

簡単に言うと、普通の計算をした後に5で割りその剰余を 「剰余の世界における加法と乗法の結果」としている、ということになります。

例えば、

2 + 3 = (5 を 5で割った剰余) = 0

2 * 3 = (6 を 5で割った剰余) = 1

となります。そうです、今まで知っていた足し算や掛け算では 2 + 3 = 5 や 2 * 3 = 6　が当たり前でした。ところかこの世界では 2 + 3 = 0, 2 * 3 = 1 のようにそうはならないのです。

減法はどのように定義したらよいでしょうか。例えば、 -2　というのは、「2と足すと0になる数」という意味です。つまり、 2 + (-2) = 0 となるように -2 を定義します。よって、2 + 3 = 0 という関係から -2 = 3 となります。同様にして、 -1 = 4, -3 = 2, -4 = 1, となることがわかります。よって、

減法 : a – b = (a + (-b) を 5で割った剰余)

とすればよいことがわかります。例えば、

2 – 3 = 2 + (-3) = 2 + 2 = 4

となります。引いたはずなのに増えている…とつい思ってしまいますね。⁴

除法はどうなるでしょうか。剰余の世界にも割り算はあるのです。まず、除法の代わりに逆数を考えます。逆数とはある数と乗算をすると1となる数のことです。2の逆数を2^-1と書くことにすると、 2 * 2^-1 = 1 となるような数2^-1を2の逆数と呼びます。

剰余の世界では、2 * 3 = 1という関係がありますので、2^-1 = 3 となります。同様にして、1^-1 = 1, 3^-1 = 2, 4^-1 = 4 となります。

ある数を割る、ということはある数に逆数をかける、ということですので除法は次のようになります。

除法 : a / b = a * b^-1 を 5で割った剰余

とすればよいことがわかります。例えば、

3 / 4 = 3 * 4^-1 = 3 * 4 = 2

となります。

素数の意外な性質

不思議な世界とはいえ、それらしい四則演算が定義できました。これにはカラクリがあります。上記の例では5で割った剰余を扱いましたが、これを6にするとどうなるでしょうか？2に関する積算を見てみましょう。

2 * 0 = 0, 2 * 1 = 2, 2 * 2 = 4

2 * 3 = 0, 2 * 4 = 2, 2 * 5 = 4

先程、「逆数とはある数と乗算をすると1となる数のことです。」と述べました。ところが、そのような数は2に関する乗算の結果をみてもどこにも存在しません。実は、割る数が素数ではない場合はこのように逆数が存在しないことが必ず起きます。一方、割る数が素数の場合は、このような事は決して起こらず、それらしい四則演算が定義できます。今回の場合、6が前者、5が後者の例となります。剰余の世界には割り算が無い場合もあるのです。

こんなところにも素数の意外な性質が垣間見る事ができます。素敵ですね。⁵

そしてRSA暗号へ…

2 * 3 = 1, 3 / 4 = 2 と不思議な世界ですが、一体何の役に立つのでしょうか？ 今まで知っていた計算と違って直感的じゃないと感じた方も多いと思います。普通の計算に変な制限をつけたもの、と見えるかもしれません。

制限というのは面倒なこともありますが豊かな世界を作り出す事もあります。例えば、サッカーというスポーツは基本的に腕や手を使う事が禁じられています。制限がある一方、足による華麗な足捌きや戦術が生まれて面白くなります。勿論、全身を使ったラグビーやアメリカンフットボールといったスポーツも劣らず面白いものです。小学校や中学校で習った普通の整数の計算も十分役に立ちますし、 それにある種の制限を加えた剰余の世界もまた、普通の整数とは違った豊かな世界を持っています。

RSA暗号はこの豊かな剰余の世界の演算を用いて構成されます。少々長くなりました。次回はRSA暗号の核心部分に迫りたいと思います。

参考文献

• 楫元 『工科系のための初等整数論入門』 培風館 2000
• G・H・ハーディ、C・P・スノー 『ある数学者の生涯と弁明』 シュプリンガー 1994
• B.L. van der Waerden 『Algebra』(7th edition) Springer 2003