暗号の数学
各種暗号技術に使われる数学の基礎について解説します．暗号化，ディジタル署名，認証などの各種セキュリティ機能を実現する暗号技術は，整数論などの数学にその基礎を置いています．特に，公開鍵暗号アルゴリズムの理解や実装には整数論や代数系等に関する知識が不可欠です．
また，暗号を実装する場合，暗号アルゴリズムを表す数式を式どおりに単純に実装しただけでは十分な性能を達成できないことが多くあります．各種演算の高速化の手法を取り入れる必要があります． このような暗号の効率的な実装に必要な各種演算の高速化手法についても紹介します．
整数論の基礎
整数
- 数と集合
整数論で使われる数の主な集合を以下に示す．$N$ ： 自然数の集合 $\{1, 2, \cdots \}$ $Z$ ： 整数の集合 $\{N, 0, -N\}$ $Z_p$ ： $0$ 以上 $p$ 未満の整数の集合 $(= Z/pZ)$ $Z^*_p$ ： $Z_p$ かつ $p$ と互いに素な整数の集合 $(= (Z/pZ)^*)$ - 商と剰余
任意の整数 $a$ と，任意の正の整数 $b$ に対して \[ a = bq + r, \quad 0 \le r \le b - 1 \] と一意に表すことができる． このとき， $q$ を商(quotient)，$r$ を剰余(remainder)という． また， $r = 0$ のとき，$b$ を $a$ の約数という．
2つの整数 $a$，$b$ に対し，$a = bq$ であるような整数 $q$ が存在するとき，$b|a$ で表す．このとき，$a$ を $b$ の倍数という． - 最大公約数と最小公倍数
2つの整数 $a$ と $b$ の共通な約数を公約数といい，そのうち正で最大なもの $d$ を最大公約数といい，$\gcd(a,b)$ または $(a, b)$ で表す．もし，$d = 1$ ならば，$a$ と $b$ は互いに素であるという．
また，2つの整数 $a$ と $b$ の共通な倍数を公倍数といい，そのうちで正で最小なものを最小公倍数といい，$\mathrm{lcm}(a, b)$ または $[a, b]$ で表す．
$\gcd$ と $\mathrm{lcm}$ は次の関係にある． \[ \gcd(a, b) \times \mathrm{lcm}(a, b) = ab \] これらの定義は，複数の整数に対しても同様に以下のように定義される．- 公約数
整数 $a,b,c,\cdots,k$ を同時に割り切る整数 - 最大公約数 $(a, b, c,\cdots k)$
整数 $a, b, c,\cdots, k$ の公約数の中で最大の整数 - 公倍数
整数 $a, b, c, \cdots, k$ の全ての倍数である整数 - 最小公倍数 $[a, b, c,\cdots, k]$
整数 $a, b, c, \cdots, k$ の公倍数の中で最小の整数 - 互いに素
$(a,b,c,\cdots,k)=1$ のとき，$a,b,c,\cdots,k$ は互いに素 - 対ごとに素
$a,b,c,\cdots,k$ の中の各々がそれらの中の他の各々と互いに素のとき，$a,b,c,\cdots,k$ は対ごとに素
- $a$ が $b$ の倍数ならば，$(a, b) = b$
- $m$ を任意の整数とするとき，$(am, bm) = (a, b)m$
- 二つの数をそれらの最大公約数で割った商は，互いに素な数である．
- $(a, b) = 1$ であれば，$(ac, b) = (c, b)$
- $(a, b) = 1$ でありかつ $ac$ が $b$ で割り切れるならば，$c$ は $b$で割り切れる．
- $(a_1,a_2,\cdots.,a_n)$ の最大公約数は以下の $d_n$ で与えられる．
$(a_1,a_2)=d_2, (d_2,a_3)=d_3, (d_3,a_4)=d_4,\cdots, (d_{n-1},a_n)=d_n$
ユークリッド互除法
2つの整数の最大公約数を求めるアルゴリズムである． $a = qb + r$ と表わされるとき， \[ \gcd(a, b)=\gcd(b, r) \] が成り立つことを利用したアルゴリズムである．
入力: 整数 $a$，$b$ $(a \gt b)$
出力: $a$ と $b$ の最大公約数- If $b = 0$ then return $a$
- $x = a;\ y = b$
- While $y \ne 0$ do
- $z = x$
- $x = y$
- $y = z \bmod x$
- Return $x$
このアルゴリズムは．次のような再帰的関数でも記述できる．- $F (a, b)$ {
- if ($b = 0$)
- return $a$
- return $F(b, a \bmod b);$
- }
拡張ユークリッド互除法
2つの整数 $a$，$b$ の最大公約数 $d$ と $d = ax + by$ なる $x$，$y$ を同時に求めるアルゴリズムである．
入力: 整数 $a$，$b$ ($a \gt b$)
出力: $a$ と $b$ の最大公約数 $d$，$d = ax + by$ なる $x$，$y$- If $b = 0$ then return ($|a|, |a|/a, 0$)
- $x = a$; $y = b$; $x_0 = 1$; $x_1 = 0$
- While $y \ne 0$ do
- $z = x;\ x = y$
- $y = z \bmod y$
- $q = \lfloor z / y \rfloor$
- $e = x_0;\ x_0 = x_1$
- $x_1 = e - x_1 q$
- Return ($x, x_0, (x - a x_0)/b$)
拡張ユークリッドの互除法は，逆元の計算に用いられる．
最大公約数 $d$ が $1$ のとき， \[ 1 = (ax + by)\ \bmod b = ax\ \bmod b \] となり，$ax = 1 \bmod b$ より $a$ の法 $b$ に対する逆元 $x$ が求められる．$d \gt 1$ ならば，逆元は存在しない．
一次方程式定理
$a$ と $b$ を $0$ でない整数とし，$g = (a, b)$ とする．方程式 \[ ax + by = g\] は，常にある正数解 $(x_1, y_1)$ をもつ．このとき，方程式のすべての解は整数 $k$ を式 \[ \left(x_1+k\frac{b}{g},\ y_1-k\frac{a}{g} \right)\] に代入することにより得られる． - 公約数
素数
素数の性質
- 素数とは
$1$と自分自身以外に約数を持たない数を素数という．素数でない数は合成数という． 暗号では，素数が重要な役割を果たす．
素因数分解の一意性
任意の数 $a$ は一意に素数 $p_i$ の積に分解できる． \[ a = p_1^{e_1}p_2^{e_2}\ldots p_k^{e_k} \] 素数は以下の性質をもつ．- 素数は無限に存在する．
- $a$ と $m$ を $(a, m) = 1$ である整数とする．このとき，$m$ を法として $a$ に合同な素数は無限に存在する(ディリクレの素数定理)．
- $1$ より大きい整数の $1$ と異なる最小の約数は素数である．
- $n$ 以下の素数の数は，漸近的に $n/(\log n)$ で表される．
- 合成数 $a$ の $1$ と異なる最小の約数（素数）は $\sqrt{a}$ を超えない．
\[ a=qa_1,\ a_1 \ge q\] \[ a \ge q^2 \] \[ q \le \sqrt{a} \]
与えられた数 $N$ を超えない素数の全てを求めるには，次のエラトステネスの篩いと呼ばれる方法がある．- $1, 2, 3, \cdots N$ を用意する.
- 最初の素数である $2$ の倍数をすべて消去する.
- $2$ に続く残った数の最初は $3$ であり素数である．$3$ の倍数をすべて消去する．
- $3$ に続く残った数の最初は $5$ であり素数である．$5$ の倍数をすべて消去する（以下同様）.
- 素数 $p$ より小さい素数のすべての倍数が消去された場合，残された $p^2$ より小さい数はすべて素数である(素数 $\le N$ の表の作成は，$\sqrt{N}$ を超えない素数のすべての倍数を消去すれば完了する）．
- 素数と擬素数
- メルセンヌ素数
$M_p = 2^p - 1$（$p$：素数) の形式の数をメルセンヌ数という． $M_p$ が素数の場合，$M_p$ をメルセンヌ素数という．
$p = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, \cdots, 82589933$ に対するメルセンヌ素数が発見されている (2023.1 現在で51個). なお，メルセンヌ素数が無限にあるかどうかは，未解決の問題である． - フェルマー数 / フェルマー素数
$2^{2^n} + 1$（$n$ は非負整数）で表される自然数をフェルマー数という．$n$ 番目のフェルマー数はしばしば $F_n$ と記される． 素数であるフェルマー数をフェルマー素数という．$F_0$ から $F_4$ は素数である． - 擬素数($a$ を底とする擬素数)
$(a,\ n)=1,\ a^{n-1}\equiv 1\pmod{n}$ を満たす合成数 $n$．
擬素数は無限にあるが，素数の個数に比べればはるかに少ない． - 絶対擬素数(カーマイケル数)
$(a, n) = 1$ なる任意の $a$ に対し， $a^{n-1} ≡ 1\pmod{n}$ を満たす合成数 $n$
- メルセンヌ素数
素数判定法
- 確率的素数判定法
確率的なアルゴリズムであり，非常に低い確率で合成数を素数と判定することがある．但し，合成数と判定した場合は常に正しい． 誤りの確率を実用的には問題ない範囲にできるので，効率の点から暗号処理には以下の Rabin法が使われることが多い．- Fermat法
いくつかのランダムに選んだ $a$ に対し， \[ (a,n) = 1,\ a^{n-1} ≡ 1\pmod{n} \] が成立するかどうかを検査する．すべての検査が通れば，$n$ が素数である可能性が高い． - Rabin法
$n=2^sm+1$ ($m$:奇数) なる $s$，$m$ を計算し，以下を $L$ 回繰り返す．- $i = 0$
- $a\ (2 \le a \le n - 1)$ をランダムに選ぶ.
- $y=a^m \bmod\ n$ を計算する．
$y = 1$ または $y = n - 1$ ならば 5.へ，さもなくば次へ進む. - $i = i + 1$，$i = s$ ならば 6.へ．
$y = y^2 \bmod n$，$y = n - 1$ ならば 5.へ，$y = 1$ ならば 6.へ． - 素数と判定 (合成数 $n$ を素数と判定する確率は $1/4^L$ 以下である).
- 合成数と判定し終了.
- Fermat法
- 確定的素数判定法
- AKS法 (多項式時間判定)
- Miller法
- Adelman-Rumely法
- Cohen-Lenstra法
素因数分解アルゴリズム
素因数分解のアルゴリズムは，素因数が特定の形を持つ場合にうまくいく方法とふるいと呼ばれる方法に分類される． 素因数が特別な条件を満たす場合に高速な方法として代表的なのが，$(p-1)$ 法と $(p+1)$ 法である．
- Pollad の $(p-1)$法
$(p-1)$ 法は素因数分解の対象数 $n$ の素因数 $p$ に対して，$p - 1$ が小さな素数 $p_i$ の積で表せる場合に有効なアルゴリズムである． すなわち，ある定数 $M$，$m_i$ に対して \[ p-1 = \prod {p_i}^{e_i}, \qquad p_i \leq M ,\quad e_i \le m_i\] と表される．
$p$ は $n$ の素因数であり，ある $a$ に対して $\gcd(a, n) = 1$ ならば，$\gcd(a, p) = 1$ となる．したがって，Fermatの定理より \[ a^{p-1} \equiv 1 \pmod{p} \] となる． さらに， $p - 1$ の倍数である $K=\prod_{i=1}^{k}p_i^{m_i}$ に対し， $a^K \equiv 1\pmod{p}$ となるので，$p$ は $a^K - 1$ と $n$ の最大公約数 $\gcd(a^K-1,n)$ を計算して求まることがある．すなわち，この最大公約数が $1$ または $n$ 以外となれば，意味のある素因数が求まる． - Williamsの $(p+1)$法
$(p+1)$ 法は，$(p-1)$ 法と同様に十分小さな $M$ に対して， \begin{eqnarray*} p+1 = \prod {p'_i}^{e_i}\\ p'_i : \mbox{素数 かつ},\ p'_i \leq M \end{eqnarray*} が成り立つ場合に有効なアルゴリズムである． ここでは，ある曲線の上の点列に関する以下の性質を利用している．
$x^2-dy^2 \equiv 4 \pmod{p}$ なる曲線で，$d=a^2 -4$，$(d/p)=-1$ ($d$ は法 $p$ のもとでの平方非剰余) のもとで，曲線上の点列 $(x_i, y_i)$ を帰納的に \begin{eqnarray*} x_0 \equiv 2,\ x_1 \equiv a,\ x_{i+1} \equiv a x_i - x_{i-1}\pmod{p}\\ y_0 \equiv 0,\ x_1 \equiv 1,\ y_{i+1} \equiv a y_i - y_{i-1}\pmod{p} \end{eqnarray*} と定義すると \[ x_i^2-dy_i^2 \equiv 4 \pmod{p} \] を満たし，次の性質が成り立つ． \begin{eqnarray*} x_{p+1} \equiv 2 \pmod{p}\\ y_{p+1} \equiv 0 \pmod{p} \end{eqnarray*} - 楕円曲線法
上記の $(p-1)$ 法，$(p+1)$ 法は構成される群の位数が計算できて，それらが小さな素因数のみを持つ場合にうまく働く方法である． 素数 $p$ を法として定義され，位数が小さな素因数のみを持つような群を構成することができるならば，上記の方法のアナロジーが展開できるというアイデアを用いたものが楕円曲線法である． 楕円曲線上の点は群構造を持ち，素数 $p$ を法として定義された楕円曲線はその位数 $m$ が \[ p+1- 2 \sqrt{p} \leq m \leq p+1+ 2 \sqrt{p} \] の範囲で一様に分布していることが知られているので，位数が小さな素因数のみを持つ楕円曲線を見つければ，効率的に素因数分解ができる． - Fermat法
合成数 $n$ の素因数 $p$，$q$ に対して，$|p - q|$ が小さい場合に有効な方法である．
$n = pq,\ p \ge q$ のとき，$x = (p+q)/2,\ y = (p-q)/2$ とおけば， \[ x^2 - y^2 = n \] となる．したがって， \[ x = \lfloor\sqrt{n}\rfloor + 1,\ \lfloor \sqrt{n}\rfloor + 2, \cdots \] と $x$ の値を変化させて，$x^2-y^2-n=0$ となるような $x$，$y$ を求めれば，$p = x + y,\ q = x - y$ より $p$，$q$ が求められる． - 2次ふるい法
2次ふるい法は，Fermat法で用いる $x^2 \equiv y^2 \pmod{n}$ の解を効率的に求める方法である．
2次ふるい法の場合， \[ Q(x)=(x+m)^2-n \quad \mbox{(}m \mbox{は} \sqrt{n} \mbox{の整数部分)} \] という関数を用いる．関数 $Q(x)$ の $x$ に小さな数 ($0, \pm1, \pm2,\ldots$) を代入して $Q(x)$ の値を求める．$Q(x)$ は比較的小さな数なので，小さな素因数に分解できて， \[ Q(x)= p_1^{d_1}p_2^{d_2} \cdots p_r^{d_r} \] と表される．そのような $Q(x)$ を集めて，各 $e_j$ が偶数になるように $Q(x_i)$ を掛け合わせると， \[ \prod_{x_i} Q(x_i)= \prod_{j=1}^r p_j^{e_j} \] となる．ここで， \begin{eqnarray*} s &=& \prod_{x_i} (x_i+m)\ \bmod n\\ t &=& \prod_{i=1}^r p_i^{(e_i)/2}\ \bmod n \end{eqnarray*} とおくことにより， \[ s^2 \equiv t^2\ \bmod n \] を満たす $s$，$t$ を求めることができる． そこで， $z = s \pm t$ として $\gcd(z, n)$ を計算すれば，$n$ の素因数が求まる．
例) $n = 2201$ の素因数分解- $Q(x) = (x + 46)^2 - 2201$
- $Q(1) = 47^2 - 2201 = 8 = 2・2・2$
- $Q(3) = 49^2 - 2201 = 200 = 2・2・2・5・5$
- $47^2・49^2 = 26・52 \pmod{2201}$
- $s = 47・49 = 2303,\ t = 2^3・5 = 40$
- $\gcd(s - t, n) = (2263, 2201) = 31$
- $n = 71・31$
- 数体ふるい法
数体ふるい法は，2次ふるい法の概念を代数的整数上で実現したものである．
／