暗号の数学
計算量
計算複雑度
あるアルゴリズムを解くのに必要な計算時間であり，対象とする問題の入力のサイズ $n$ の関数で表す． あるアルゴリズムの計算複雑度が $n$ を使って関数 $f(n)$ で表すことができて，
\[ n \gt n_0\ に対して， f(n) \lt c|g(n)| \quad (n_0: 定数）\]となれば，$O(g(n))$ の複雑度があるという．
また，計算量の評価を以下の式で表すことがある．
\[ \mathrm{L_n}[v, c] = \exp\{(c + o(1))(\log n)^v(\log\log n)^{(1-v)} \}\]ここで，
- $v=0$ のとき，$\log n$ に対して多項式的
- $v=1$ のとき，$\log n$ に対して指数的
- $0 \lt v \lt 1$ のとき，$\log n$ に関して準指数的
である． また， $o(1)$ は $1$ を超えない定数であり，$n \rightarrow \infty$ のとき $0$ に漸近する．
計算量による問題の分類
- 多項式時間計算量問題
問題のサイズを $n$ とするとき $O(n^k)$ の計算量で解ける問題 - 指数時間計算量問題
問題のサイズを $n$ とするとき $O(k^n)\ (k \gt 1)$ の計算量で解ける問題 - P問題
多項式時間の決定性アルゴリズムで解ける易しい問題 - NP問題
非決定性アルゴリズムで多項式時間で解ける問題
(非決定性アルゴリズムとは，計算手順が一意には決まらず選択可能な道が複数あり，うまく計算手順が選ばれれば，多項式時間で解けるものである)．
多項式サイズの証拠を与えられたときは，その正しさを多項式時間で検証することができる． - NP困難問題
NPに属する任意の問題と比べて，少なくとも同等以上に難しい問題（NPに属するとは限らない） - NP完全問題
NP問題の中で解くのが特に難しい問題 (NP困難であり，かつNPに属する問題)
暗号の実現に使われる解くのが困難な代表的な問題には，次のようなものがある．
- 素因数分解問題
素因数分解問題とは，合成数 $n$ からその素因数を求める問題である． 例えば，RSA暗号では $n (= pq)$ が公開鍵であり，その素因数 $p$，$q$ が秘密鍵である．したがって，暗号として成立するには $n$ から $p$，$q$ を求めることが困難である必要がある．
素因数分解を行うアルゴリズムには次のようなものがある．- 計算時間が $n$ の最大素因数 $p$ のサイズに依存するアルゴリズム
$p-1$ 法，$p+1$ 法，楕円曲線法 - 計算時間が $n$ のサイズに依存するアルゴリズム
連分数法，線形ふるい法，2次ふるい法，数体ふるい法
代表的な素因数分解アルゴリズムの計算量は以下のようになる．- 小さな素因数から構成されている合成数の分解
$p-1$ 法/$p+1$ 法 ： $\mathrm{L_p}[1, 1]$
楕円曲線法： $\mathrm{L_p}[1/2, \sqrt{2}+o(1)] \qquad$ ($p$: $n$ の最大の素因数) - 大きな素因数のみを持った合成数の分解
連分数法 ： $\mathrm{L_n}[1/2, 1.414]$
線形ふるい法 ： $\mathrm{L_n}[1/2, 1.117]$
2次ふるい法 ： $\mathrm{L_n}[1/2, 1.020]$
数体ふるい法 ： $\mathrm{L_n}[1/3, 1.923]$
現状の素因数分解アルゴリズムの計算量は，準指数関数的であり合成数(あるいは含まれる素因数)を十分大きくとれば，素因数分解は困難であると考えられている． - 計算時間が $n$ の最大素因数 $p$ のサイズに依存するアルゴリズム
- 離散対数問題
素数 $p$ を定めたとき，${Z_p}^*$ における原始元 $g$ に対して， \[ y = g^x\ \bmod\ p \] ならば，$x = \log_g y$ と記して $y$ の $g$ に対する離散対数という．
離散対数問題とは，$p,\ g,\ y$ が与えられたとき，$x = \log_g y$ を求める問題である．
代表的な離散対数問題の解法アルゴリズムの計算量は以下のようになる．- Pohlig-Hellman法
$y=g^x\ \bmod\ p$ において，$g$ の位数 (原始根の場合 $p - 1$) が小さな素数の積に分解されるとき有効な方法 (計算量：$\sqrt{p}$) - 指数計算法
ある素数の集合に対する対数を求め，それを利用して離散対数を求める方法 (計算量： $\mathrm{L_n}[1/2,1.4]$) - 数体ふるい法
指数計算法の一種で，素因数分解問題に対する数対ふるい法を離散対数問題に応用した方法 (計算量： $\mathrm{L_n}[1/3,1.922]$)
- Pohlig-Hellman法
- ナップザック問題
正整数 $C$ と正整数のベクトル $A=(a_1,a_2,…,a_n)$ が与えられた時，$A$ の要素の部分集合の和が $C$ となるような $A$ の要素の部分集合を求める問題である．
すなわち， $C = AM$ となる \[ C = \sum_{i=1}^n a_i m_i, \quad m_i = \{0, 1\}\ (1 \le i \le n)\] 2進ベクトル $M=(m_1,m_2,\cdots,m_n)$ を求める問題である．
$n$ のサイズが大きくなると解くのが非常に難しいNP完全問題になる．
数の表現
整数の表現
- 多倍長整数
一般に計算機上では基本演算の対象であるデータの長さ(語長)が決まっている(32ビット，64ビット等)．1語が32ビットならば $0$ 以上 $2^{32}$ 未満の数しか表現できない．しかし語が複数集まることによりそれ以上の数を表現できるようになる．
ここで1語が $n$ ビットとすると，一般の正整数 $A$ は， \begin{eqnarray*} A = A_m x^{m-1} + A_{m-1} x^{m-2}+ \cdots + A_2 x +A_1 \\ x = 2^n, 0 \leq A_i \lt x, A_m \neq 0 \end{eqnarray*} と書くことができ，$m$ 個の語の配列 $A_m,A_{m-1},\ldots ,A_1$ として計算機内で扱うことができるようになる．このように表現された整数を多倍長精度整数という．それに対して1語で表現できる整数を単精度整数ということがある．
多倍長整数演算の実現は，多倍長の整数を整数型の配列として格納し，演算を行なわせるものである．このとき，配列へのポインタ，配列の長さ，有効ビット数などの要素を持った構造体を新たな型(多倍長整数型)として定義する．この型の変数を引数とする各種の多倍長整数演算関数を実装する．また，演算関数以外に整数を表す文字列と内部のデータ構造(多倍長整数型)との相互変換を行なう入出力関数等も必要になる． - 基数変換
- 自然数 $n$ を基数 $b$ で表すには，$n$ を $b$ で割った商と余りを求め，商を新たに $n$ と置く，という操作を繰り返せば良い．出てきた余りの列は，$n$ を $b$ 進表記したときの下位の桁から順に並べたものになる．
- 整数部が $0$ の正の実数 $r$ の基数変換を行うには，$r$ を $b$ 倍して整数部と小数部に分け，小数部を新たに $r$ と置く，という操作を繰り返せば良い．出てきた整数部の列は，$r$ の小数部を上位の桁から順に並べたものになる．
- 一般の実数は整数部と小数部に分け，それぞれを上に述べた方法で基数変換すれば良い．実行時間は $O(n^2)$ である．
- 符号付き数表現
自然数 $n$ は，以下の式で表すことができる． \[ n = \sum_{i=0}^{l}s_i2^i, \qquad s_i \in \{-1, 0, 1\} \] これを二進符号付き桁(SD: Signed Digit)表示と呼ぶ． この表現は，$3^{l+1}$ の組合せがあるため冗長性がある．この表現において，隣接した $0$ でないビットが存在しないこと，すなわち任意の $i \ge 0$ に対して $s_is_{i+1}=0$ になるとき，SD表現は非隣接形式(NAF: Non-Adjacent Form)と呼ばれる．
任意の整数は $n$ は一意にNAFを持つことが知られている．NAFは $n$ の全てのSD表示の中で最小重みを持つ．それは，$n$ の最短のSD表示より長くても1桁だけである．
以下のアルゴリズムは，二進表現で与えられた負でない整数のNAFを計算する．
入力： 整数 $k = \sum_{j=0}^{l-1} k_j 2^j,\quad k_j \in \{0, 1\}$
出力： NAF $k = \sum_{j=0}^{l}s_j 2^j,\quad s_j \in \{-1, 0, 1\}$
- $c_0 \leftarrow 0$
- For $j = 0$ to $l$ do
- $c_{j+1} \leftarrow \lfloor(k_j + k_{j+1} + c_j)/2 \rfloor \qquad (i \ge l$ に対して$k_i=0$を仮定)
- $s_j \leftarrow k_j + c_j - 2c_{j+1}$
- Return $(s_ls_{l-1}\cdots s_0)$
／