この記事では、RSA暗号における素数生成の仕組みとして、ミラー＝ラビン素数判定法について解説する。
目次
1. はじめに
インターネットの普及にともない、通信を介した情報のやり取りは日常生活において今や不可欠なものである。個人間のメッセージ送信から、金融取引に至るまで、あらゆる場面でデジタルな通信が活用されている。
この様な環境下において、通信内容の安全性を確保することは極めて重要である。そのため、一般的には通信を介したやり取りには、暗号を用いて、通信の内容を秘匿した状態で受信者に送る。
暗号の設計においては、19世紀の軍事暗号研究所ケルクホフスによって提唱された「暗号の安全性は暗号方式自体ではなく、その鍵の秘密性に依拠すべきである」という原理（ケルクホフスの原理）が広く受け入れられている。すなわち、暗号方式が知られていることを前提にしても、その安全性が保たれるべきだとする考え方である。
この原理に基づき、現在一般的なインターネット通信で利用されている暗号の１つに RSA暗号 がある。RSA暗号は、桁数の大きい合成数の素因数分解が、現実的な時間内で困難であることを安全性の根拠とした公開鍵暗号方式であり、鍵のみが秘密とされ、その暗号方式そのものは公開されている。RSA暗号は2つの大きな素数を利用して、公開鍵と秘密鍵を生成し、決められた演算を行うことで暗号化される仕組みである。
では、この2つの大きな素数というのは、どのようにして求められるのか?
RSA暗号は、大きな合成数を素因数分解することが現実的に困難である、という前提の上になり立っている。であるならば、「そもそもその素因数である素数自体を、どうやって見つけるのか?」という疑問が浮かぶ。素因数分解が難しいのであれば、素数を探すことも自体もまた難しいのではないか、という一見矛盾したような問いである。
実は、素因数分解は非常に難しいが、大きな素数を生成すること自体は比較的容易である。これは素数が自然数全体にある程度の頻度で現れるという「素数定理」に支えられており、ランダムに大きな数を生成して素数かどうかを判定するというアプローチが、現在取られている。
本記事では、こうした大きな素数の生成に実際に用いられている「ミラー＝ラビン法」について解説する。
ケルクホフスの原理
「暗号方式は、秘密鍵以外のすべてが公知になったとしても、なお安全であるべきである」
— Wikipedia「ケルクホフスの原理」より要約
19世紀の軍用通信の経験則に基づき提案されたこの原理は、
“The enemy knows the system.” — C. E. Shannon
としても知られる。
現代暗号では 方式は公開し、鍵だけを秘密にする という設計哲学の土台となっており、
RSA をはじめとする公開鍵暗号もこの考え方を前提にしている。
2. ミラー＝ラビン素数判定法
2.1. ミラー＝ラビン素数判定法の流れ
前述の通り、ミラー＝ラビン法は、RSA暗号において公開鍵と秘密鍵を生成する際に必要となる大きな素数を効率的に見つけるために用いられるアルゴリズムである。このアルゴリズムは、確率的素数判定法に分類される。すなわち、合成数を素数と誤判定する可能性を完全には排除できない。しかし、複数回実行することで誤判定の確率を小さくできることが知られており、実用上は極めて信頼性の高い素数判定法として広く利用されている。
ミラー＝ラビン法は、以下のアイディアに則る。$n$ を奇数とすると、$n - 1$ は偶数であるから、
$$
n - 1 = 2 ^ s t
$$
となるような $s \geqq 1$ と奇数 $t$ が1つだけ定まる。例えば、$n = 113$ の場合、$n - 1 = 112 = 2 ^ 4 \cdot 7$ となる。この場合、$s = 4$、$t = 7$ となる。
ここでフェルマーの小定理より、素数 $n$ に対して任意の $a \in {1, 2, ..., n - 1 }$ に対して、以下が成り立つ。
$$
a ^ {n - 1} \equiv 1 \pmod{n}
$$
よって、前述の $n - 1 = 2 ^ s t$ を用いると、
$$
a ^ {n - 1} = a ^ {2 ^ s t} \equiv 1 \pmod{n}
$$
が成り立つはずである。ミラー＝ラビン法では、この $a$ の値は「テストに使う基数」であり、複数回テストを行う場合には、毎回異なる $a$ をランダムに選んで使用する。
ここでミラー＝ラビン法の核心は、このべき乗の途中経過に注目する点にある。具体的には、次のように指数を2のべき乗で細かく調べていく。
\begin{align*}
x_0 &= a^t \pmod n \\
x_1 &= (x_0) ^2 = a^{2t} \pmod n \\
x_2 &= (x_1) ^2 = a^{4t} \pmod n \\
x_3 &= (x_2) ^2 = a^{8t} \pmod n \\
&\vdots \\
x_s &= (x_{s-1})^2 = a^{2^s t} \equiv a^{n-1} \pmod n
\end{align*}
これは、$s$ に $0$から$1, 2, ..., s$ まで代入していった時の値を $x_i$ と置いたものである。
ここで、$n$ が素数である場合、どこかで1が現れ、以後1が続くことになる可能性が高い（$\Rightarrow$ 偽素数の存在があるので断定はできない）。これは以下のことから説明することができる。
x ^ 2 \equiv 1 \pmod{n}
とする。この時、二つの差は $n$ の倍数になるはずである。このことから、
\begin{align*}
x ^ 2 - 1 &= 0 \pmod n \\
(x + 1) (x - 1) &= 0 \pmod n
\end{align*}
$n$ が素数の時、$x - 1$ あるいは $x + 1$ が $n$ の倍数になるはずである。これは、
x \equiv \pm 1 \pmod n
であることを意味している。これはつまり、法 $n$ (=素数) のもとで、一度 ±1 が出た場合、以後2乗しても1であり続けることを示している。
2.2. 強い擬素数と強い嘘つき
2.1. 節にて紹介したミラー＝ラビン法では、最終的な計算結果が1になること、あるいは途中で-1が現れることによって、与えられた数が素数らしいと判断される。
しかし実際には、合成数であるにも関わらず、ミラー＝ラビン法の判定条件をすべて満たしてしまう合成数 $n$ が存在する。これは強い擬素数と呼ばれる。またこの時の、$a$ の値は強い嘘つきと呼ばれる。
2.3. 強い擬素数の存在がありながら、ミラー＝ラビン法が利用される理由
2.2節にて、擬素数の存在について述べた。これは、素数判定の目的で使用されるアルゴリズムにもかかわらず、素数でない数（=擬素数）を素数と誤判定してしまう可能性があることを意味する。
それにもかかわらず、なぜこの方法が広く実用されているのだろうか。
それは、誤判定の確率が非常に小さいことが理論的に保証されているからである。
具体的には、任意の奇数の合成数 $n$ に対して、1から $n - 1$ の範囲から一様ランダムに選んだ $a$ が「強い嘘つき」でない（＝正しく合成数だと判定できる）確率は、少なくとも $\frac{3}{4}$ であることが知られている。
したがって、1回の判定で「強い嘘つき」に当たってしまう確率は高々 $\frac{1}{4}$ であり、テストを $L$ 回独立に繰り返すことで、
合成数を素数と誤判定してしまう確率は
$$
\left(\frac{1}{4}\right)^L
$$
以下に抑えられる。たとえば、$L = 10$ 回テストすれば誤判定確率はおよそ $10^{-6}$ 以下となり、実用上の安全性を十分に確保できる。
このように、ミラー＝ラビン法は繰り返し回数を増やすことで誤判定の確率を指数関数的に小さくできるため、RSAなどの実用暗号において、高速かつ信頼性の高い素数判定法として広く利用されている。
3. さいごに
今回はRSA暗号の秘密鍵と公開鍵を生成する時に使われる素数判定法のアルゴリズムであるミラー＝ラビン法について説明をした。
4. 参考資料
[1]. RSA暗号
[2]. ケルクホフスの原理
[3]. Pythonで学ぶ暗号理論