読者です 読者をやめる 読者になる 読者になる

射影座標を用いた場合のMiller Algorithmについてのメモ

Miller Algorithmの実装を高速化した際のメモ。

Miller Algorithmは基本紹介される際にはEuclid空間上の楕円曲線の点について紹介されるが、変数変換をしてやることで射影座標上のアルゴリズムとすることが出来る。(なお、Miller Algorithm自体は任意の種数の代数曲線について適用が可能。詳しくは元論文。)

以降、$E/K$ を標数が2でない体 $K$ 上の楕円曲線とし、 $E[m]$ を $E$ の $ m $ ねじれ点の集合とする。また、$x(P)$, $y(P)$, $z(P)$はそれぞれ点 $P$ の $x, y, z$ 座標を表すこととし、$E$はWeierstrass標準形 $y ^ 2 = x ^ 3 + ax + b$ と表せるとする。

line_coeff関数

入力: $ P, Q \in E$

$$ \mathrm{line\_coeff}(P, Q) = \begin{cases} \frac{3x(P) ^ 2+az(P) ^ 2}{2y(P)z(P)} & x(P)z(Q) = z(P)x(Q) \newline \frac{y(Q)z(P) - y(P)z(Q)}{x(Q)z(P) - x(P)z(Q)} & other \end{cases} $$

h関数

入力: $ P, Q, R \in E[m] $

if (P == Q and y(P) == 0) or (P != Q and x(P) * z(Q) = x(Q) * z(P)) {
  return (x(R) * z(P) - x(P) * z(R)) / (z(P) * z(R))
}

l = line_coeff(P, Q)
p = z(Q) * (y(R) * z(P) - y(P) * z(R) - l * (x(R) * z(P) - x(P) * z(R)))
q = x(P) * z(Q) * z(R) + z(P) * x(Q) * z(R) + z(P) * z(Q) * x(R) - l^2 * z(P) * z(Q) * z(R)

return p / q

miller関数

入力: $P, Q \in E[m]$

出力: $f_P(Q)$

if (P == Q) {
  return 1
}
T = P
b_i = mの2進展開の列
n = mのビット数
f = 1
for (i = 0; i < n; i = i + 1) {
  f = f^2 * h(T, T, Q)
  T = 2 * T
  if (b_i == 1) {
    f = f * h(T, P, Q)
    T = T + P
  }
}

return f

参考文献

楕円曲線の位数2, 3を持つ点の個数

$\def\O{\mathcal{O}}$

ここでは標数2, 3の体は考えないため, 全ての楕円曲線はWeierstrass標準形 $y ^ 2 = x ^ 3+ax+b$ で表せるとする. また, 楕円曲線上の点 $P$ の $x$ 座標を $x(P)$ , $y$ 座標を $y(P)$ と表す.

位数2の点

複素数体上の楕円曲線 $y ^ 2 = x ^ 3 + ax + b$ 上の無限遠点$\O$を除く点のうち, 位数2を持つ点の個数は1個, 2個, 3個のうちいずれかである.

証明

$2P = \O$ から $P = -P$ . $P$ を座標表示すると $(x, y)$ となり, これを用いて $-P$ を表すと $-(x, y) = (x, -y)$ なので $P = -P$ のとき $y = -y$ である. これは $y = 0$ に他ならない.

楕円曲線の定義式 $y ^ 2 = x ^ 3 + ax + b$ から $y = 0$ ならば $x$ は $x ^ 3 + ax + b = 0$ の根であることがわかる.

以上より, 位数2を持つ点 $P$ は方程式 $x ^ 3 + ax + b = 0$ が重根を持たないと仮定すると, $\alpha, \beta, \gamma$ としたとき, $(\alpha, 0)$ , $(\beta, 0)$ , $(\gamma, 0)$ の3個である. また, 方程式が2重根ないし3重根を持つときはそれぞれ同様に考えることで2個, 1個の点を持つことがわかる.

位数3の点

複素数体上の楕円曲線$y ^ 2 = x ^ 3 + ax + b$上の無限遠点 $\O$ を除く点のうち, 位数3を持つ点の個数は2個, 4個, 6個, 8個のうちいずれかである.

証明

$3P = \O$ から $2P = -P$ . $x$ 座標のみを考えると, $x(2P) = x(-P)$ だが, $x(P) = x(-P)$ なので, $x(2P) = x(P)$ を証明すればよい.

点 $2P$ の $x$ 座標は、$P = (x, y)$ としたとき,

$$ \lambda = \frac{3x ^ 2+a}{2y}\\ x(2P) = \lambda ^ 2 - 2x $$

と表される. ここから方程式を考える.

$$ \begin{align} x(2P) &= x(P)\\ \lambda ^ 2 - 2x &= x\\ \end{align} $$

$$ \frac{9x ^ 4+6ax ^ 2 + a ^ 2}{4y ^ 2} - 2x = x\\ \frac{9x ^ 4+6ax ^ 2+a ^ 2}{4y ^ 2} - 3x = 0 \\ 9x ^ 4+6ax ^ 2+a ^ 2 - 12xy ^ 2 = 0\\ 9x ^ 4+6ax ^ 2+a ^ 2 - (12x ^ 4+12ax ^ 2+12bx) = 0\\ \underline{\therefore 3x ^ 4+6ax ^ 2+12bx-a ^ 2 = 0}\\ $$

よって、方程式 $3x ^ 4+6ax ^ 2+12bx-a ^ 2 = 0$ の根はそれぞれ $P$ の $x$ 座標となる. また, $y$ 座標はある $x$ について $y = \pm\sqrt{x ^ 3+ax+b}$ であることから, $x$ 座標が一つ確定したとき, 対応する点は2個存在する.

以上より, 位数3を持つ点は方程式 $3x ^ 4+6ax ^ 2+12bx-a ^ 2 = 0$ の根を $x_1, x_2, x_3, x_4$ とするとき, $(x_1, \pm\sqrt{x_1 ^ 3+ax_1+b})$ , $(x_2, \pm\sqrt{x_2 ^ 3+ax_2+b})$ , $(x_3, \pm\sqrt{x_3 ^ 3+ax_3+b})$ , $(x_4, \pm\sqrt{x_4 ^ 3+ax_4+b})$ の8個である. 方程式が2重根, 3重根ないし4重根を持つときも同様に考えることで6個, 4個, 2個の点が存在することがわかる.

参考文献

数学 - 中国人剰余定理

中国人剰余定理とは、初等整数論の定理の一つであり、非常に多くの応用が存在する定理である。この記事では、この定理に注目してその一般化と応用について解説する。


連立合同方程式

補題

連立合同方程式

$$ \begin{align} x &\equiv a \mod n_1\\ x &\equiv b \mod n_2 \end{align} $$

の解$x$が一意的に存在することを示す。ここでは、$\gcd(n_1, n_2) = 1$とする。このとき、$un_1 + vn_2 = 1$を満たす$u, v$を拡張ユークリッドの互除法で求めることが可能である。これにより$un_1 = 1 - vn_2$と書けるが、これは$un_1 \equiv 1 \mod n_2$と同値である。同様に、$vn_2 \equiv 1 \mod n_1$である。$avn_2 \equiv a \mod n_1$なので、$avn_2 \equiv x \mod n_1$。同様に、$bun_1 \equiv b \mod n_2$、$bun_1 \equiv x \mod n_2$。

$avn_2 + bun_1$を考える。この式は、$avn_2 + bun_1 \equiv avn_2 \equiv a \equiv x \mod n_1$、$avn_2 + bun_1 \equiv bun_1 \equiv b \equiv x \mod n_2$となる。

$avn_2 + bun_1 \equiv x \mod n_1$、$avn_2 + bun_1 \equiv x \mod n_2$ということは、$avn_2 + bun_1$は$n_1, n_2$の公倍数であると考えられる。$n_1, n_2$の公倍数は最小公倍数$\mathrm{lcm}(n_1, n_2)$の倍数で表せるが、この場合$n_1, n_2$は互いに素であるため、$\mathrm{lcm}(n_1, n_2) = n_1n_2$である。 すると、$avn_2 + bun_1 \equiv x \mod n_1n_2$と書ける。よって、式$avn_2 + bun_1 \mod n_1n_2$は上の連立剰余方程式を満たす。

解が一意的であることを示す。 解$x, y$が存在したとして、$x-y \equiv 0 \mod n_1$, $x-y \equiv 0 \mod n_2$が成り立つ。上と同様の議論により、$x-y \equiv 0 \mod n_1n_2$が成り立つ。つまり、$x, y$は$n_1n_2$を法として合同である。このため、$x, y$は一意的に定まる。

これは、補助定理と呼ばれる定理で、これを一般化することで中国人剰余定理が得られる。

中国人剰余定理 (Chinese Reminder Theorem)

$\gcd(n_i, n_j) = 1$ ($i \neq j$)となるような$n_1, n_2, \ldots, n_k$を法とした連立剰余方程式

$$ \begin{align} x &\equiv a_1 \mod n_1\\ \vdots\\ x & \equiv a_k \mod n_k \end{align} $$

の解$x$は$0 \leq x < \prod ^ k_{i=1} n_i$の範囲に一意的に存在する。

Gaussによる証明がわかりやすい。簡略化した証明を示す。

$\displaystyle M = \prod _ {i = 1} ^ k n_i$, $\displaystyle M _ i = \frac{M}{n_i}$とする。すると、$\gcd(M_i, n_i) = 1$なので、補助定理より$M_iu_i \equiv 1 \mod n_i$となるような$u_i$を探すことができる。後は補助定理と同様の議論により、$\displaystyle x \equiv \sum ^ k _ {i=1} a_iu_iM_i \mod n_i$を計算することで、解$x$を求められる。一意性については補助定理とほぼ同じなので省略する。

法についての一般化

上に示した形では、$n_1, \ldots, n_k$はどの2つをとっても互いに素という条件があった。この条件は実は外すことができる。 ここでは$k=2$の時に限定するが, 実際には任意の$k$について同様のことが言える。(暇があればどうぞ)

法$n_1, \ldots, n_k$について、連立剰余方程式

$$ \begin{align} x &\equiv a_1 \mod n_1\\ x &\equiv a_2 \mod n_2\\ \end{align} $$

を考える。この時、$g = \gcd(n_1, n_2)$とし、$g \neq 1$とする。 拡張ユークリッドの互除法より、$Xn_1 + Yn_2 = g$となるような$X$, $Y$を見つけることが出来る。ここで、$n_1$, $n_2$はそれぞれ$g$で割り切れるため、$n_1' = n_1/g$, $n_2' = n_2/g$と定義すると$Xn_1' + Yn_2' = 1$となる. ここから、$a_1 Y n_2' + a_2 X n_1$を考えることにより補題と同様の議論によって解$x$が計算できる。また、解$x$は$0 \leq x < \mathrm{lcm}(n_1, n_2)$の範囲内に存在する。これは途中の操作から明らか。

実装例:

gist901d223135965308a5f9ff0cf99dd7c8

以上から、$x \equiv a_k \mod n_k$の形の剰余連立方程式は常に解を持つことがわかる。

抽象化

この定理は任意の環上のイデアルへと抽象化できるため、環論での応用が可能だ。本筋ではないため証明については参考文献を見られたい。

$A$を環、$I_1, \cdots, I_n \subsetneq A$をイデアルで、$i \neq j$なら$I_i + I_j = A$であるとする。 このとき、以下の事実が成り立つ。

  • $i = 1, \ldots, n$について、$I_i + \prod_{j \neq i} I_j = A$
  • $I_1 \cap\cdots\cap I_n = I_1\cdots I_n$
  • $A/(I_1\cap\cdots\cap I_n) \simeq A/I_1\times\cdots\times A/I_n$

その系として、以下を得られる。これは非常に便利な事実なので、頭の片隅にでも入れておくと役に立つ(かもしれない)

$m_1,\ldots,m_k \in\mathbb{Z}\backslash\left\{0\right\}$ かつ$i\neq j$なら$\gcd(m_i, m_j) = 1$とする。このとき、 $$ \mathbb{Z}/m_1\cdots m_k\mathbb{Z} \simeq \mathbb{Z}/m_1\mathbb{Z}\times\cdots\times\mathbb{Z}/m_k\mathbb{Z} $$

応用例

このように非常に応用に富む中国人剰余定理だが、実際の応用としてはどのようなものがあるか、暗号の視点から見てみる。

RSA-CRT

RSA暗号はEulerの定理を応用した公開鍵暗号だが、実際の速度的な問題が存在する。というのも、パラメータ$e$は 65537 = 0x10001 = 0b10000000000000001 というように非常に計算しやすいものを比較的自由に選ぶことが出来るが、秘密鍵$d$については殆どの場合$e$から計算されるためにそのような計算しやすさは考慮されない。($d$を任意に選択して$e$を計算すれば良いではないか、ともなるが、そのようにすると多くの場合Boneh-Durfee AttackやCommon Private Exponent Attackのような攻撃の脅威に晒されやすくなってしまう。)つまり、復号時の計算量は非常に多くなってしまうのだ。 ここで、RSA暗号は$\mathbb{Z}/n\mathbb{Z}$つまり$\mathbb{Z}/pq\mathbb{Z}$の上で計算されることを考える。これは、先の系より$\mathbb{Z}/pq\mathbb{Z} \simeq \mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/q\mathbb{Z}$と書くことができる。これは、大きな群での計算($\mathbb{Z}/n\mathbb{Z}$)をより小さな群($\mathbb{Z}/p\mathbb{Z}$, $\mathbb{Z}/q\mathbb{Z}$)の上での計算に帰着させられることを示している。 この場合の計算は次のようにされる。

  • $d_p \equiv d \mod p-1$, $d_q \equiv d \mod q-1$を計算しておく。
  • 暗号文$c$について、$m_1 \equiv c^{d_p} \mod p$, $m_2 \equiv c^{d_q} \mod q$を計算する。すると、$m \equiv m_1 \mod p$, $m \equiv m_2 \mod q$という連立方程式が立てられるので、これを中国人剰余定理によって解いて$ m $を求める。

なお、openssl等では中国人剰余定理の内部計算を最適化し、$q^{-1} \mod p$を追加のパラメータとして秘密鍵に加えてある場合がある。

Multi-Prime RSA

RSAは何も$p, q$の2つの素数でないといけないわけではない。多変数に拡張されたRSA暗号を、Multi-Prime RSAと呼ぶ。 Multi-Prime RSAが通常のRSAと異なる点は、どのように$\phi(n)$を計算するかと復号処理だろう。前者についてはEulerのTotient関数について見てもらうとして、今回は復号部分について注目したい。 といっても複雑なことはしない。先の系より剰余類を小さな剰余類の直積と見ることによってRSA-CRTの要領で平文を計算し、中国人剰余定理によって平文を復元するだけだ。

Pohlig-Hellman Attack

Pohlig-Hellman Attackとは、任意の合成数位数の巡回群での離散対数問題を効率よく解くアルゴリズムである。アルゴリズムは以下のように与えられる。

  1. 巡回群$P$とその位数$n = \#P$、位数$n$の素因数分解$n = p_1\cdots p_k$が判明しており、$\gamma = g ^ x $となる$g$, $\gamma$が判明しているとする。
  2. 各$p_i$について、$\beta_i = g^{\phi(n)/p_i}$, $\Gamma_i = \gamma^{\phi(n)/p_i}$を考える。この時、$\beta_i$, $\Gamma_i$は位数$p_i$を持つことに注意する。
  3. $\Gamma_i \equiv \beta_i^{x_i} \mod p_i$なる$x_i$を求める。これはBaby-Step Giant-Step法等適当なアルゴリズムで良い。
  4. 各$x_i$について、$x \equiv x_i \mod p_i$が成り立っている。このため、中国人剰余定理を用いて$x$を求めることが出来る。

今回は乗法巡回群として話を進めたが、これは任意の巡回群に適用可能である。例えば、有限体や楕円曲線の群でも適用できる。

参考文献/参考サイト