数学 - Chinese Remainder Theorem (中国剰余定理)

本記事では中国剰余定理(Chinese Reminder Theorem, CRT)1について解説する. 数学的な定義や意義について触れた後, 応用例としてRSA-CRT, Multi-Prime RSA, そしてPohlig-Hellman Attackについて述べる. 前提知識として, 簡単な初等整数論・群・環の言葉を知っていることが望ましい.

注: 本記事は2021/03/02に全面的に書き直された. レビューありがとうございます: @kimiyuki_u

CRT

準備

まず, 本節でしばしば利用される定理である以下について述べる.

Thm. 0. 任意の非零自然数$a, b$に対し, 整数$x, y$が存在して, $ax + by = \gcd(a, b)$をみたす.

この定理における$(x, y)$は存在性を示すのみならず$(a, b)$から具体的に計算することが可能であり, それを実現するアルゴリズムはしばしば 拡張ユークリッド互除法(Extended Euclidean Algorithm) と呼ばれる. このアルゴリズムの時間計算量は$O(\log\max{a, b})$と高速であり, 様々な計算に利用されるアルゴリズムである. 本記事では具体的に$(x, y)$が計算可能であることを明確にしたいため, 拡張ユークリッド互除法をあたかも定理の名前かのように濫用している.

2式の場合

Def. 1. $x, x _ 1, x _ 2, n _ 1, n _ 2$を整数とし, $0\lt n _ 1$, $0\lt n _ 2$, $0\leq x\lt n _ 1n _ 2$, $0\leq x _ 1\lt n _ 1$, $0\leq x _ 2\lt n _ 2$であるとする. このとき, 4つ組$(x _ 1, x _ 2, n _ 1, n _ 2)$に対する以下の2式を($(x _ 1, x _ 2, n _ 1, n _ 2)$に対する)連立合同方程式と呼び, $x$をそのという.

$$ \begin{aligned} x&\equiv x _ 1 \pmod {n _ 1}\cr x&\equiv x _ 2 \pmod {n _ 2}\cr \end{aligned} $$

連立合同方程式に対し, その解は一般に存在するとは限らない. たとえば, $(x _ 1, x _ 2, n _ 1, n _ 2) = (1, 2, 35, 77)$であるとき, $x\equiv 1\pmod {35}$かつ$x\equiv 2\pmod {77}$であるような整数$x$は存在しない. 以下のThm. 2は, $n _ 1, n _ 2$が互いに素であるならば解が常に存在し, かつ制約$0\leq x\lt n _ 1n _ 2$の範囲で一意であることを主張する.


Thm. 2. $x _ 1, x _ 2, n _ 1, n _ 2$を任意の整数とし, $(x _ 1, x _ 2, n _ 1, n _ 2)$がDef. 1における連立合同方程式の4つ組であると仮定する. $\gcd(n _ 1, n _ 2) = 1$であるならば, 整数$0\leq x\lt n _ 1n _ 2$が一意に存在して, その連立合同方程式の解をなす.

Proof.

  • (存在性): 拡張ユークリッド互除法より, この$n _ 1, n _ 2$に対して整数$m _ 1, m _ 2$が存在して, $m _ 1n _ 1 + m _ 2n _ 2 = 1$をみたす. いま$x := (m _ 1n _ 1x _ 2 + m _ 2n _ 2x _ 1)\mod {n _ 1n _ 2}$とおく. すると$x\equiv m _ 1n _ 1x _ 2 + m _ 2n _ 2x _ 1\pmod {n _ 1}$, $m _ 1n _ 1 + m _ 2n _ 2 \equiv m _ 2n _ 2 \equiv 1\pmod {n _ 1}$より$x\equiv m _ 1n _ 1x _ 2 + m _ 2n _ 2x _ 1\equiv m _ 2n _ 2x _ 1 \equiv x _ 1\pmod {n _ 1}$である. 同様に$x\equiv x _ 2\pmod {n _ 2}$も成立する. $0\leq x\lt n _ 1n _ 2$は明らかであるから, $x$はこの連立合同方程式の解である.
  • (一意性): 解$x$, $x'$が存在したとき, これらが一致することを示す. $x$は解であるから, $x - x'\equiv 0\pmod {n _ 1}$, $x - x'\equiv 0\pmod {n _ 2}$である. したがって, $x - x'$は$n _ 1$, $n _ 2$の公倍数である. とくに, $\gcd(n _ 1, n _ 2) = 1$より最小公倍数は$n _ 1n _ 2$であるから, ある整数$k$が存在して, $x - x' = kn _ 1n _ 2$をみたす. ところが$0\leq x\lt n _ 1n _ 2$かつ$0\leq x'\lt n _ 1n _ 2$であるため$0\leq |x - x'|\lt n _ 1n _ 2$である. これをみたすような$k$は0のみである. したがって$x = x'$.

$k$式の場合

次に, 式の個数について一般化して議論する.

Def. 3. $k$を自然数で$2\leq k$であるとする. $x, x _ 1, x _ 2, \ldots, x _ k$, $n _ 1, n _ 2, \ldots, n _ k$を整数とする. 任意の$i = 1, 2, \ldots, k$について$0\lt n _ i$, $0\leq x _ i\lt n _ i$, かつ$0\leq x\lt n _ 1n _ 2\cdots n _ k$と仮定する. このとき, $2k$-tuple $(x _ 1, x _ 2, \ldots, x _ k, n _ 1, n _ 2, \ldots, n _ k)$に対し, 以下の$k$式をこれらの連立合同方程式と呼び, $x$をその解と呼ぶ.

$$ \begin{aligned} x&\equiv x _ 1 \pmod {n _ 1}\cr x&\equiv x _ 2 \pmod {n _ 2}\cr &\vdots\cr x&\equiv x _ k \pmod {n _ k}\cr \end{aligned} $$


Thm. 4. ある自然数$2\leq k$に対し, $x _ 1, x _ 2, \ldots, x _ k, n _ 1, n _ 2, \ldots, n _ k$を任意の整数とする. この$(x _ 1, x _ 2, \ldots, x _ k, n _ 1, n _ 2, \ldots, n _ k)$はDef. 2に示す連立合同方程式の条件を満たしているものとする. このとき, 自然数$i, j$で$1\leq i\leq k$, $1\leq j\leq k$かつ$i\ne j$なるものすべてに対し$\gcd(n _ i, n _ j) = 1$であるならば, 整数$0\leq x\lt n _ 1n _ 2\cdots n _ k$が一意に存在して, その連立合同方程式の解をなす.

Proof.

  • (存在性): $M := n _ 1n _ 2\cdots n _ k$とおき, 自然数$i$で$1\leq i\leq k$をみたすものについて$M _ i := \frac{M}{n _ i} = n _ 1n _ 2\cdots n _ {i - 1}n _ {i+1}\cdots n _ k$と定義する. このとき, 任意の自然数$i$で$1\leq i\leq k$をみたすものに対し$\gcd(M _ i, n _ i) = 1$である. 拡張ユークリッド互除法より, 各$i$に対し整数$u _ i, v _ i$で$u _ iM _ i + v _ in _ i = 1$を満たすものが存在する. ここで, ある$i$に対して$u _ iM _ i\equiv 1\pmod {n _ i}$であることと, その$i$と任意の整数$j$で$1\leq j\leq k$かつ$i\ne j$をみたすものについて$u _ iM _ i\equiv 0\pmod {n _ j}$である. このことから, $$ x := \left(\sum _ {i = 1} ^ {k} x _ iu _ iM _ i\right) \mod M $$ は$0\leq x\lt M $, かつ整数$i$で$1\leq i\leq k$を満たすものに対して$x\equiv x _ i\pmod {n _ i}$をみたす.
  • (一意性): 解$x$, $x'$が存在したとき, これらが一致することを示す. 整数$i$で$1\leq i\leq k$をみたすものに対し, $x - x'\equiv 0\pmod {n _ i}$が成立. よって$x - x'$は$n _ 1, n _ 2, \ldots, n _ k$の公倍数である. 定理の仮定より, ある整数$k$が存在して$x - x' = kM $である. ところで$0\leq x'\lt M $であるから, $0\leq |x - x'|\lt M $である. これをみたす$k$は0以外に存在しない. したがって, $x = x'$である.

一般にCRTと呼ばれる定理はThm. 2若しくはThm. 4である.

代数的な取り扱い

ここまでCRTを初等整数論による証明により述べた. 他方, 代数的にこれらの性質を抽象化した定理が存在するのでこれを簡単に述べておく. 証明は別途参考文献に挙げた書籍を参考.

Thm. 5. $R$を(必ずしも可換とは限らない)環とし, $I _ 1, I _ 2, \ldots, I _ k$を$R$の両側イデアルで, 整数$i, j$に対し, $1\leq i, j\leq k$かつ$i\ne j$ならば$I _ i + I _ j = R$であるようなものとする. このとき, $\displaystyle I := \bigcap _ {1\leq i\leq k} I _ i$に対し環同型$R / I\simeq (R / I _ 1)\oplus (R / I _ 2)\oplus\cdots\oplus(R / I _ k)$が成立2.

Thm. 5の例として$k = 2$, $R = \mathbb{Z}$, $I _ 1 = 5\mathbb{Z}$, $I _ 2 = 7\mathbb{Z}$の場合を考えてみよう. 可換環なので両側イデアルなのは自明. $3\cdot 5 + -2\cdot 7 = 1$より任意の整数は$I _ 1 + I _ 2$の元で表せる. $I _ 1 + I _ 2\subset R$は明らかなので$I _ 1 + I _ 2 = R$. そして$I _ 1\cap I _ 2 = 35\mathbb{Z}$である. したがってこの場合$R / (I _ 1\cap I _ 2) \simeq (R / I _ 1)\oplus (R / I _ 2)$の成立がThm. 5よりいえる.

上に挙げた例についてくだけた言い方をすると, 「$\bmod 35$の世界の言葉は$\bmod 5$の世界と$\bmod 7$の世界の対に対する言葉ですべて言い換えることができる. 逆に, $\bmod 5$の世界と$\bmod 7$の世界の対に対する言葉も$\bmod 35$の世界の言葉ですべて言い換えることができる. 」といえる. 計算量の観点からは, $\bmod 5$と$\bmod 7$のそれぞれの計算量が小さい世界の言葉だけで$\bmod 35$というちょっと計算量が大きな世界の言葉をすべて記述することができるところに利点が存在する.

Thm. 5はCRTが構造に対してどのように作用するのかを示している. たとえば「2つの構造が存在して, それらがある条件を満たすならば, 対応する構造が一意に定まり, それらは同型である」という点で見るとCRTは二項演算としてみることもできる (実際, CRTは結合則に近い条件を満たす). 具体的に計算をする際にも時間計算量は$O(k\log \max\lbrace\,n _ 1, n _ 2, \ldots, n _ k\,\rbrace)$で済む. このため極めて計算機的な応用幅が広く, この点が後述するRSA-CRTやPohlig-Hellman Attackにおいて重宝されている.

応用例

本節ではCRTの応用例をいくつか示す. 軽い紹介程度に留めるために記号定義等かなり省略しているため, 詳しくは別途調べてほしい. また, RSA暗号については定義程度は既知であることを仮定する.

RSA-CRT

RSA暗号はおそらく最も広く知られた公開鍵暗号であろう. しかしその計算速度はビット数に比例し, 特に復号時に用いる秘密鍵$d$の大きさは概ね$\phi(n) = (p - 1)(q - 1)$3程度となる. 安全なRSA暗号を構成するためには$p$, $q$は十分大きくある必要があり, 2021年時点では素因数分解にかかる時間から$\log _ 2 p$, $\log _ 2 q$がともに2048以上であれば安全とされることが多い.

RSA暗号において復号を高速化する手法の中で一般的とされるものの一つがRSA-CRTだ. $n = pq$とCRTから$\mathbb{Z}/n\mathbb{Z}\simeq (\mathbb{Z}/p\mathbb{Z})\oplus(\mathbb{Z}/q\mathbb{Z})$であることを利用したものであり, 具体的には以下のように暗号化・復号がなされる.

鍵生成

  1. $p, q$を素数とし, $e$を$\phi(n)$と互いに素な適当な自然数とする.
  2. $n := pq$, $d := e ^ {-1}\mod {\phi(n)}$.
  3. $d _ p := d\mod (p-1)$, $d _ q := d\mod (q-1)$とおく.
  4. $(e, n)$を公開鍵, $(d _ p, d _ q, n)$を秘密鍵として出力する.

暗号化

  1. 平文${m}$に対し, $m ^ e\mod n$を暗号文として出力する.

復号

  1. 暗号文$c$に対し, $m _ 1 := c ^ {d _ p}\mod p$, $m _ 2 := c ^ {d _ q}\mod q$とする.
  2. このとき, 平文${m}$に対し$m\equiv m _ 1\mod p$, $m\equiv m _ 2\mod q$である. よって, CRTより${m}$が計算できる.
  3. ${m}$を出力する.

通常のRSAでは$c ^ d\mod n$を計算するが, この計算量が重いことが問題であった. RSA-CRTでは, $d _ p$, $d _ q$というたかだか$p$, $q$程度の大きさしか持たない指数を用いることで, 時間計算量を$O(\log _ 2\max(p, q))$程度に落としている.

Multi-Prime RSA

RSAは通常$p, q$と2つの素数で構成される. これは上に見たとおり$\mathbb{Z}/n\mathbb{Z}\simeq (\mathbb{Z}/p\mathbb{Z})\oplus(\mathbb{Z}/q\mathbb{Z})$という同型をうまく使うものである. ここで, たとえば別の素数$r$を用いて$\mathbb{Z}/pqr\mathbb{Z}\simeq (\mathbb{Z}/p\mathbb{Z})\oplus(\mathbb{Z}/q\mathbb{Z})\oplus(\mathbb{Z} / r\mathbb{Z})$という同型を用いれば, 素数を2個に限定しないRSA暗号が構成できるのではないかとも考えられる. 実際にこれは構成可能であり, Multi-Prime RSAという名前が付けられている.

Multi-Prime RSAの暗号化・復号の流れは素数が3個になること以外はRSAと同じである (位数は$\phi(pqr) = (p-1)(q-1)(r-1)$である). しかし, 素数が増えつつも素数の大きさは十分大きく保つ必要があることから, Multi-Prime RSAは基本的にその法が通常のRSAと比べて大きくなる傾向にある. すると計算時間の問題が発生するが, ここでRSA-CRTと同様に$d _ p$, $d _ q$, $d _ r$を事前計算しておくようにし, 復号にCRTを用いるようにすることでこの計算時間を比較的小さく抑えることができる. このため, Multi-Prime RSAとCRTは―理論的にはなくてもよい程度の関係でしかないものの―抱き合わせで利用されることがほとんどである.

しかし, Multi-Primeだからと安全になるわけではない. 素因数分解が難しい合成数の条件の一つによく挙げられるものとして, 「すべての素因数の大きさが同じぐらいの大きさである場合(素数の大きさに偏りがなく均等である場合)」がある. しかし, たとえば$pq$の平方根は$p$, $q$のいずれかに近い数であると考えられるため, 平方根を取って付近を探索するという手を用いることが考えられる. もちろん$2 ^ {2048}\lt \min(p, q)$のような大きい素数では探索は現実的ではないのだが, Multi-Prime RSAの場合は少しこの問題が簡単になる. 4つの素数$p _ 1, p _ 2, p _ 3, p _ 4$を用いたMulti-Prime RSAで, 最も大きな素因数を$p _ {\max}$, 最も小さな素因数を$p _ {\min}$で表したとき, この$p _ {\max} - p _ {\min}$の幅に存在する正解の素数の量は4である. 同じ"幅"をもつ通常のRSAでは正解の素数が2個しかないことを考えれば, この幅に対してMulti-Prime RSAは脆弱であると考えることができる. この正解の素数の個数は素因数の平均的な大きさに依存せず, 素因数の数を増やしたことによって脆弱なポイントとなる, Multi-Prime RSAに特有の問題である. 他にもMulti-Prime RSAに特有の脆弱になる条件が存在することも報告されており, この記事の執筆者としては一長一短だという感想を持つ.

Pohlig-Hellman Attack

攻撃においてCRTを使うとても重要な例として, Pohlig-Hellman Attackが挙げられる. これは有限巡回群に対する離散対数問題を効率よく解くためのアルゴリズムの一つである. しかし一般の場合を解けるというわけではない. 有限アーベル群の基本定理4によりもともとの有限巡回群$G$とより小さい位数を持つ$G$の部分巡回群$H _ 1, H _ 2, \ldots, H _ k$の直積との間に同型が成立することを用いて$G$における離散対数問題を小さな離散対数問題へ分割し, 別の適当なアルゴリズムでその部分問題を解く. その結果得られた部分問題の解が連立合同方程式の形をしているため, その解をCRTを用いて求めるという分割統治を用いて計算量を落とすアルゴリズムである. ゆえに素因数分解が難しい場合には意味をなさず, さらに素因数が大きい場合にも意味をなさない. 位数が複数の小さい素因数をもつ場合に限り有効なアルゴリズムである. しかしその効果は大きく, 位数の最大の素因数を$p$で, 途中で利用する離散対数問題を解くアルゴリズムの計算量を$F(p)$で表したとき, 全体の時間計算量は$O(kF(p)\log p)$である.

前提

アルゴリズム

  1. 各$p _ i$に対し, $\beta _ i := g ^ \frac{\phi(n)}{p _ i}$, $\Gamma _ i := \gamma ^ \frac{\phi(n)}{p _ i}$とおく. このとき, $\beta _ i$, $\Gamma _ i$はそれぞれ位数$p _ i$をもつことに注意.
  2. 適当な離散対数問題を解くアルゴリズム(e.g. Baby-step Giant-step法)で$\Gamma _ i \equiv \beta _ i ^ {x _ i}$をみたす$x _ i$を計算する.
  3. 各$x _ i$に対し, $x\equiv x _ i \pmod p _ i$であるから, CRTを用いて$x$を計算する.

参考文献


  1. 様々な訳が存在する. 中国剰余定理, 中国人剰余定理, 中華剰余定理, 中国の剰余定理, 中国式剰余定理等. 本記事では普段私が利用している「中国剰余定理」を採用し, 文中では特に省略形であるCRTを用いるものとする.

  2. $\oplus$は環の直和を意味する. 環の直和は, その対象となるもとの環を完全に部分環として含むような環である.

  3. Euler totient関数. RSA暗号で利用される巡回群$(\mathbb{Z} / n\mathbb{Z}) ^ \ast$の位数を表す.

  4. 任意の有限アーベル群$G$に対し, 1以上の整数$e _ 1, e _ 2, \ldots, e _ k$と素数$p _ 1, p _ 2, \ldots, p _ k$が存在して, 群同型$G\simeq (\mathbb{Z}/p _ 1 ^ {e _ 1}\mathbb{Z})\times(\mathbb{Z}/p _ 2 ^ {e _ 2}\mathbb{Z})\times\cdots\times(\mathbb{Z}/p _ k ^ {e _ k}\mathbb{Z})$が成立し, しかも$p _ 1 ^ {e _ 1}, p _ 2 ^ {e _ 2}, \ldots, p _ k ^ {e _ k}$は順序の差を除いて一意に定まる. (当初の説明が誤っていました. ご指摘ありがとうございます: @Mi_Sawa)