Chapter 15

数論の道具 — オイラー・中国剰余定理・離散対数

この章の位置づけ. 16 章の RSA や17 章のディフィー・ヘルマン鍵交換、楕円曲線暗号は、どれも「一方向の計算は簡単だが、逆向きの計算は現実的な時間ではできない」という性質に安全性を頼っている。 この章では、その性質を生む数論の定理と問題をまとめて扱う。01 章〜03 章の合同算術と群の性質が土台になる。

この章で使う既出の用語（定義は各リンク先）. 合同式・\(\gcd\)・逆元の存在条件・繰り返し二乗法（01 章）、 群・閉性・位数・生成元・ラグランジュの定理とその帰結・\(\mathbb{Z}_n^\ast\)の記法（02 章 1 節）、\(\mathbb{Z}_p\)が体であること（02 章 3 節）、 原始元・離散対数・\(\varphi(p-1)\)と\(g^k\)の位数の式（03 章 3 節）、「\(\gcd(g, x) = 1\)なら\(g \mid xA\)から\(g \mid A\)」の論法（09 章 4 節の補題の整数版）

1. オイラーの φ 関数

定義

\(\varphi(n)\)は、\(1\)以上\(n\)以下の整数のうち\(n\)と互いに素（\(\gcd = 1\)）なものの個数である。03 章 3 節では\(n = p-1\)の場合に使った。 \(n \geq 2\)なら\(n\)自身は\(\gcd(n,n) = n \neq 1\)なので数えない。\(\varphi(1) = 1\)である。

例: \(\varphi(10)\)。\(1\)から\(10\)のうち、\(2,4,6,8,10\)は 2 を、\(5,10\)は 5 を 10 と共通に持つので除く。残る\(1,3,7,9\)の 4 個なので\(\varphi(10)=4\)である。

上の図で\(n\)を変えると、\(n\)と互いに素な数と\(\varphi(n)\)が表示される。

計算公式

(a) \(p\)が素数: \(\varphi(p) = p-1\)。\(1,\dots,p-1\)はどれも\(p\)で割り切れないので、すべて\(p\)と互いに素である。

(b) \(p\)が素数、\(k\geq1\): \(\varphi(p^k) = p^k - p^{k-1} = p^k\left(1-\dfrac1p\right)\)

導出: \(p^k\)の素因数は\(p\)だけなので、\(1\)から\(p^k\)のうち\(p^k\)と互いに素でないのは\(p\)の倍数だけである。\(p\)の倍数は\(p, 2p, \dots, p^{k-1}\cdot p\)の\(p^{k-1}\)個なので、それを引けばよい ∎

(c) 乗法性: \(\gcd(m,n)=1\)なら\(\varphi(mn) = \varphi(m)\varphi(n)\)

導出: 3 節の中国剰余定理により、\(0 \le x < mn\)の整数\(x\)と、余りの組\((x \bmod m,\ x \bmod n)\)は 1 対 1 に対応する。 \(x\)が\(mn\)と互いに素であることは、\(x\)が\(m\)とも\(n\)とも互いに素であることと同じで、さらに\(\gcd(x, m) = \gcd(x \bmod m, m)\)（互除法の原理）なので、「\(x \bmod m\)が\(m\)と互いに素、かつ\(x \bmod n\)が\(n\)と互いに素」と同じである。 そのような組は\(\varphi(m) \times \varphi(n)\)通りある ∎

(d) 一般形: \(n = p_1^{e_1}\cdots p_r^{e_r}\)と素因数分解できるとき、(b) と (c) を組み合わせて

たとえば\(\varphi(10) = 10(1 - \tfrac12)(1-\tfrac15) = 4\)である。

RSA で使う場合: \(n = pq\)（\(p, q\)は異なる素数）のとき

RSA の安全性の要点

\(n = pq\)は公開されるが、\(\varphi(n) = (p-1)(q-1)\)を計算するには\(p, q\)を知る必要がある。 逆に\(\varphi(n)\)が分かれば\(p, q\)も求まる。\(\varphi(n) = pq - p - q + 1\)を変形すると\(p + q = n - \varphi(n) + 1\)で、\(pq = n\)と合わせると、\(p, q\)は 2 次方程式

の 2 つの解である。例: \(n = 143\)、\(\varphi(n) = 120\)なら\(p + q = 24\)で、\(t^2 - 24t + 143 = 0\)の解\(t = 11, 13\)が\(p, q\)である。 つまり\(\varphi(n)\)を求めることと\(n\)を素因数分解することは、一方ができれば他方もできる、同じ難しさの問題である。

• 鍵を作る人は\(p, q\)を自分で選んだので、\(\varphi(n)\)をすぐに計算できる。
• 攻撃者は\(n\)しか知らないので、素因数分解しないと\(\varphi(n)\)が分からない。

この非対称性が RSA の仕組みの中心である（16 章）。

2. オイラーの定理

定理

\(\gcd(a,n)=1\)のとき

例: \(n = 10\)、\(a = 3\)なら\(\varphi(10) = 4\)で、\(3^4 = 81 = 8 \times 10 + 1 \equiv 1 \pmod{10}\)である。

導出（02 章の群の定理の当てはめ）

方針: \(n\)と互いに素な余りの集合\(\mathbb{Z}_n^\ast\)（02 章 1 節の記法）が掛け算について群になることを確かめ、02 章のラグランジュの定理の帰結を当てはめる。

導出: \(\mathbb{Z}_n^\ast\)が掛け算について群であることを確かめる。

• 閉性: \(\gcd(a,n)=\gcd(b,n)=1\)なら\(\gcd(ab,n)=1\)である。\(ab\)と\(n\)が素数\(r\)を共通に持つとすると、素数\(r\)は\(ab\)を割り切るので\(a\)か\(b\)を割り切り、どちらかが\(n\)と\(r\)を共通に持つことになって矛盾するからである。
• 結合律と単位元\(1\)は、整数の掛け算からそのまま成り立つ。
• 逆元: 01 章 5 節の定理より、\(\gcd(a, n) = 1\)なら逆元が存在し、逆元もまた\(n\)と互いに素である。

この群の要素数（群の位数）は、定義から\(\varphi(n)\)である。02 章 1 節のラグランジュの定理の帰結「群の要素\(a\)について\(a^{|G|} = e\)」より\(a^{\varphi(n)} \equiv 1\) ∎

系（フェルマーの小定理）: \(n=p\)が素数なら\(\varphi(p)=p-1\)なので、\(p\)で割り切れない\(a\)について\(a^{p-1}\equiv1 \pmod p\)である。

02 章でフェルマーの小定理をラグランジュの定理の帰結として導いたが、同じ議論を\(\mathbb{Z}_n^\ast\)に当てはめたものがオイラーの定理である。数論の定理に見えるが、中身は「有限の群では、要素を群の位数だけ掛けると単位元に戻る」という群の性質である。

3. 中国剰余定理 (CRT)

定理

\(m_1,\dots,m_r\)がどの 2 つも互いに素（\(i \neq j\)なら\(\gcd(m_i, m_j) = 1\)）のとき、連立合同式

は、\(M = m_1\cdots m_r\)を法としてただ 1 つの解を持つ。

導出（解を実際に作る）

方針: 「法\(m_i\)では 1、ほかの法では 0」になる数を\(i\)ごとに作り、\(a_i\)倍して足す。

存在: \(M_i = M/m_i\)（\(m_i\)以外の\(r-1\)個の積）とおく。\(M_i\)の素因数はすべて\(m_i\)以外の\(m_j\)から来るので\(\gcd(M_i, m_i)=1\)であり、01 章 5 節より逆元\(N_i = M_i^{-1} \bmod m_i\)が存在する。

とおくと、これが解である。法\(m_j\)で見ると

• \(i \neq j\)の項: \(M_i\)は\(m_i\)以外すべての積なので\(m_j\)を因数に持ち、\(a_i M_i N_i \equiv 0\)。
• \(i = j\)の項: \(N_j\)の定義より\(M_j N_j \equiv 1\)なので、\(a_j M_j N_j \equiv a_j\)。

よってすべての\(j\)で\(x \equiv a_j \pmod{m_j}\)である。

一意性: 解が 2 つ\(x, x'\)あるとすると、\(z = x - x'\)はすべての\(m_i\)で割り切れる。\(m_1\)で割り切れるので\(z = m_1 z_1\)と書け、\(m_2\)は\(m_1 z_1\)を割り切り\(\gcd(m_1, m_2) = 1\)なので、09 章 4 節の補題と同じ論法（ベズーの等式\(u m_1 + v m_2 = 1\)の両辺に\(z_1\)を掛ける）で\(m_2\)は\(z_1\)を割り切る。 これを繰り返すと\(z\)は\(M = m_1 \cdots m_r\)で割り切れ、\(x \equiv x' \pmod M\)である ∎

実例

\(M = 105\)、\(M_1=35\)、\(M_2=21\)、\(M_3=15\)である。

• \(N_1 = 35^{-1} \bmod 3\): \(35\equiv2\)で、\(2\cdot2=4\equiv1\)なので\(N_1=2\)
• \(N_2 = 21^{-1}\bmod 5\): \(21\equiv1\)なので\(N_2=1\)
• \(N_3 = 15^{-1}\bmod 7\): \(15\equiv1\)なので\(N_3=1\)

検算: \(23 = 3\cdot7+2\)、\(23=5\cdot4+3\)、\(23=7\cdot3+2\)で、3 つとも満たしている。

上の図で余りと法を変えると、同じ手順で解が計算される。

CRT による RSA の高速化

RSA の復号\(m = c^d \bmod n\)（\(n=pq\)、16 章）は、大きな数のべき乗なので重い。そこで CRT を使う。

1. \(m_p = c^{d \bmod (p-1)} \bmod p\)を計算する（法の大きさは半分）。
2. \(m_q = c^{d \bmod (q-1)} \bmod q\)を計算する。
3. CRT で\(m \equiv m_p \pmod p\)、\(m \equiv m_q \pmod q\)を満たす\(m\)を求める。

指数を\(d \bmod (p-1)\)に減らしてよいのは、フェルマーの小定理より\(c^{p-1} \equiv 1 \pmod p\)なので、指数は\(p-1\)で割った余りだけが効くからである。

\(n\)を\(2k\)ビットとすると、速くなる理由は 2 つ重なる。

• 1 回の掛け算（筆算の方法）の手間はビット数の 2 乗に比例するので、法が\(k\)ビットになると約\(1/4\)になる。
• べき乗に必要な掛け算の回数は指数のビット数に比例する（01 章 6 節）。指数が\(2k\)ビットの\(d\)から\(k\)ビットの\(d \bmod (p-1)\)になるので、約\(1/2\)になる。

合わせて 1 本あたり\(1/8\)で、それを\(p\)側と\(q\)側の 2 本行うので\(2/8 = 1/4\)、全体で約 4 倍速くなる。実際の RSA の実装（OpenSSL など）はほぼすべてこれを使っている。

フォールト攻撃の危険: 電源やクロックに瞬間的な異常を与えて\(m_p\)の計算だけを誤らせると、\(m_q\)は正しいまま、誤った結果\(m'\)が出力される。 正しい\(m\)と比べると、\(m' - m\)は\(q\)の倍数だが\(p\)の倍数ではないので、\(\gcd(m' - m, n) = q\)となり秘密の素数\(q\)が分かってしまう（Bellcore 攻撃）。 署名の場合は、正しい値を知らなくても、誤った署名\(s'\)と公開鍵\(e\)から\(\gcd(s'^{\,e} - (\text{署名対象の値}), n) = q\)として同じことができる（署名は18 章）。 そのため実装では、計算結果を公開鍵で検算してから出力する必要がある。

4. 位数と原始根

位数

\(\gcd(a,n)=1\)のとき、\(a^k \equiv 1 \pmod n\)となる最小の正整数\(k\)を\(a\)の位数という。群\(\mathbb{Z}_n^\ast\)での要素の位数（02 章 1 節）と同じものである。

性質: 位数は\(\varphi(n)\)を割り切る。\(a\)のべき全体は位数と同じ要素数の部分群になり、ラグランジュの定理より部分群の要素数は群の要素数\(\varphi(n)\)を割り切るからである。

原始根

位数がちょうど\(\varphi(n)\)の\(a\)を原始根という。\(a, a^2, \dots, a^{\varphi(n)}\)が\(n\)と互いに素な余りをすべて尽くす、ということである。\(n = p\)が素数のときは03 章 3 節の原始元と同じもので、ここでは一般の\(n\)に広げている。

存在定理（証明は省き、事実として使う）: 原始根が存在するのは、\(n\)が\(1, 2, 4, p^k, 2p^k\)（\(p\)は奇素数）のいずれかの形のときに限る。 たとえば\(n = 8\)には原始根が無い。\(\mathbb{Z}_8^\ast = \{1, 3, 5, 7\}\)の要素はどれも 2 乗すると 1 になる（\(9, 25, 49\)はどれも 8 で割って 1 余る）ので、位数は最大でも 2 で、\(\varphi(8) = 4\)に届かない。

個数: 原始根が存在するときは\(\varphi(\varphi(n))\)個ある。原始根\(g\)を 1 つ取ると、互いに素な余りはすべて\(g^k\)（\(1 \le k \le \varphi(n)\)）と書ける。 \(g^k\)の位数は\(\varphi(n)/\gcd(k, \varphi(n))\)である（03 章 3 節の段階 3 と同じ議論）。位数が\(\varphi(n)\)になるのは\(\gcd(k, \varphi(n)) = 1\)のときで、そのような\(k\)は\(\varphi(\varphi(n))\)個ある。

5. 離散対数問題 (DLP)

定義

\(p\)を素数、\(g\)を\(\mathbb{Z}_p^\ast = \{1,\dots,p-1\}\)の原始根とする。与えられた\(y\)に対し

を満たす\(x\)（\(0 \leq x < p - 1\)）を求める問題を離散対数問題という。

難しさの非対称性

知られているアルゴリズム:

準指数時間とは、\(p\)の桁数に比例する\(\ln p\)について、多項式\((\ln p)^k\)よりは大きいが、指数関数\(p^{c} = e^{c \ln p}\)よりは小さい計算量のことである。\(L_p[1/3]\)は\(\ln p\)の\(1/3\)乗が指数に乗る形で、\(\sqrt p = e^{(\ln p)/2}\)（指数に\(\ln p\)の 1 乗）よりずっと小さい。

ポーリッヒ・ヘルマン法: 群の要素数\(p-1\)が小さな素数の積に分解できると、3 節の中国剰余定理を使って、小さな素数ごとの離散対数問題に分けて解ける。したがって安全のためには、\(p-1\)が大きな素因数を持つように\(p\)を選ぶ必要がある。

楕円曲線暗号への接続

\(\mathbb{Z}_p^\ast\)の離散対数問題には Index Calculus という準指数時間の方法が使えるので、安全を保つには\(p\)を 2048 ビット以上にする必要がある。 Index Calculus は、\(g^k \bmod p\)を整数として見て、小さな素数だけの積に分解できるもの（滑らかな数）を集め、連立方程式を作る方法である。 17 章の楕円曲線の点の群には「小さな素数の積に分解する」に当たる操作が無く、一般の楕円曲線では Index Calculus のような準指数時間の方法は知られていない。使えるのは、群の要素数\(n\)に対して\(O(\sqrt n)\)の Pollard の ρ 法などだけである。 そのため、同じ安全性をずっと短い鍵で実現できる。

鍵の長さはおよそ 10 分の 1 から 30 分の 1 で、求める安全性が高いほど差が開く。これが楕円曲線暗号が広く使われるようになった理由である。

6. 素数判定 — 鍵生成に必須

RSA-2048 には 1024 ビット程度の素数が 2 つ必要である。その見つけ方を述べる。

素数定理

\(x\)以下の素数の個数を\(\pi(x)\)とすると、\(\pi(x) \approx x/\ln x\)である（素数定理、証明は省く）。 したがって\(n\)付近の数が素数である確率は約\(1/\ln n\)で、1024 ビットの数なら\(1/\ln(2^{1024}) \approx 1/710\)である。偶数を除けば約 355 個に 1 個が素数なので、ランダムな奇数を選んで判定を繰り返せば、すぐに見つかる。

フェルマー・テスト

\(a^{n-1} \equiv 1 \pmod n\)を満たさなければ、\(n\)は合成数である（フェルマーの小定理の対偶）。

弱点: カーマイケル数（561, 1105, 1729, …）は合成数なのに、\(n\)と互いに素なすべての\(a\)で\(a^{n-1} \equiv 1\)となり、テストを通過してしまう。\(\gcd(a, n) \neq 1\)の\(a\)なら不合格になるが、そのような\(a\)を偶然選ぶ確率は小さい。 たとえば\(561 = 3 \times 11 \times 17\)で、\(2^{560} \equiv 1 \pmod{561}\)が成り立つ。

ミラー・ラビン・テスト（実用の標準）

\(n-1 = 2^s d\)（\(d\)は奇数、\(s \ge 1\)）と分解する。\(n\)が素数なら、\(n\)と互いに素な任意の\(a\)について

手順: \(x_0 = a^d \bmod n\)を計算し、\(x_1 = x_0^2, x_2 = x_1^2, \dots, x_s = x_{s-1}^2\)（\(= a^{n-1}\)）と 2 乗を\(s\)回繰り返す。 \(x_0 = 1\)であるか、\(x_0, \dots, x_{s-1}\)のどこかに\(-1\)（\(= n - 1\)）が現れれば「たぶん素数」、そうでなければ「確実に合成数」と判定する。

方針: 素数なら\(\mathbb{Z}_n\)は体なので、「2 乗して 1 になる数は\(\pm 1\)だけ」である。列\(x_0, \dots, x_s\)の中に「\(\pm 1\)でないのに 2 乗すると 1」の数があれば、体ではない、つまり合成数だと分かる。

導出: \(n\)が素数なら\(\mathbb{Z}_n\)は体（02 章 3 節）なので、\(x^2 \equiv 1\)、すなわち\((x-1)(x+1) \equiv 0\)の解は、零因子が無いことから\(x \equiv \pm1\)だけである。 列\(x_0, x_1, \dots, x_s\)は最後が\(x_s = a^{n-1} \equiv 1\)（フェルマーの小定理）で、各項は前の項の 2 乗である。最後から逆にたどると、\(1\)の直前は 2 乗して 1 になる数なので\(\pm 1\)のどちらかである。\(1\)ならさらにその前も\(\pm1\)、と続く。 したがって列は「\(1\)ばかり」か「途中で\(-1\)が現れ、その後は\(1\)が続く」のどちらかの形しかとれない。これが上の条件である ∎

例: カーマイケル数\(n = 561\)、\(a = 2\)。\(560 = 2^4 \times 35\)なので\(s = 4\)、\(d = 35\)である。

\(x_4 = 1\)なのでフェルマー・テストは通過するが、\(x_2 = 67\)は\(\pm 1\)（1 と 560）でないのに\(x_3 = 67^2 \equiv 1\)になっている。\(x_0\)〜\(x_3\)に\(-1 = 560\)は現れないので、561 は合成数と判定される。

誤り確率: 1 回のテストで合成数を「たぶん素数」と誤判定する確率は\(1/4\)以下であることが知られている（証明は省く）。\(a\)を変えて\(k\)回繰り返せば\(4^{-k}\)以下になり、64 回なら\(2^{-128}\)以下である。

7. まとめ