暗号の数学

素体と拡大体

素体 (Prime Finite Field)

素体上の演算
$m$ を法とする剰余類 \[　Z_m＝\{0, 1, 2, \ldots, m-1\} \] は $m$ を法とする加法および乗法のもとに環をなす．
$m$ が素数 $p$ に等しい場合，集合 $Z_p$ は体を構成し，$\mathbb{F}_p$ (または $\mathrm{GF}(p)$) と表される．有限体 $\mathbb{F}_p$ では，$0$ 以外の任意の数による剰余除算が可能である．
$\mathbb{F}_p$ の $0$ を除いた要素の集合は ${\mathbb{F}_p}^*$ で表わされる．
$\mathbb{F}_p$ 上の加算と乗算は， \[ a + b = a + b \bmod\ p \] \[a・b = a・b \bmod\ p \] であり，加法の逆元は， \[ -a = \left\{ \begin{array}{ll} 0 & (a = 0),\\ p -a & (a \ne 0).\\ \end{array}\right. \] である．また，乗法の逆元は，$ab = 1 \bmod p$ なる $b$ である．
位数 (Order)
${\mathbb{F}_p}^*$ の要素 $c$ の位数とは，$c^v \equiv 1 \pmod{p}$ となる最小の正の整数 $v$ である．位数は常に存在し，$p - 1$ を割り切る．
$k$ と $l$ が整数で，$c^k \equiv c^l \pmod{p}$ となるのは，$k \equiv l \pmod{v}$ のときのみであり，そのときに限られる．
- 法 $p$ における整数の位数を求める．
  入力：素数 $p$，整数 $g\ (1 \lt g \lt p)$
  出力：法 $p$ における $g$ の位数 $k$
  1. $b \leftarrow g,\ j \leftarrow 1$
  2. $b \leftarrow gb \bmod p,\ j \leftarrow j + 1$
  3. If $b \gt 1$ then go to step 2
  4. Return $j$
- 与えられた位数の整数を求める．
  入力：素数 $p$，$p - 1$ を割り切る整数 $T$
  出力：法 $p$ における位数 $T$ を持つ整数 $u$
  1. $1$ と $p$ の間の整数 4g$ をランダムに生成する．
  2. 法 $p$ における $g$ の位数 $k$ を計算する．
  3. $T$ が $k$ を割り切らないならば，step 1へ．
  4. Return $u := gk/T \bmod p$
生成元 (Generator)
数 $v$ が $p - 1$ を割り切るならば，位数 $v$ を持つ ${\mathbb{F}_p}^*$ の要素が存在する．
特に，${\mathbb{F}_p}^*$ において，位数 $p - 1$ の要素 $g$ が存在し，生成元と呼ばれる． ${\mathbb{F}_p}^*$ の全ての要素が $g$ のべき乗で表わされるためである．
指数と離散対数
体 ${\mathbb{F}_p}^*$ の要素 $g$ が位数 $v$ を持つとき，${\mathbb{F}_p}^*$ の要素 $h$ は $h^v = 1 \pmod{p}$ のときに限り，ある $l$ に対して $h = g^l \pmod{p}$ を満足する．指数 $l$ は，$h$ の離散対数と呼ばれる．離散対数は，$v$ を法とした整数である．
素体と暗号
- 離散対数型暗号 (DL-based cryptography)
  ${\mathbb{F}_p}^*$ の位数が $r$ (素数)の要素 $g$ を仮定する．このとき，鍵ペアを次のように定義する．
  - 秘密鍵 $s$ を $r$ を法とした整数とする．
  - 対応する公開鍵 $w$ を $w = g^s \pmod{p}$ で定義される ${\mathbb{F}_p}^*$ の要素とする．
  これが暗号として成立するには，対応する公開鍵から秘密鍵を計算すること(離散対数を求めること)が困難であることが必要である．すなわち，このタイプの公開鍵暗号の安全性は離散対数問題の困難性に依存している．
- 素因数分解型暗号 (IF-based cryptography)
  RSA暗号では，公開鍵を $n$，$e$，秘密鍵を $d$ として用いる．ここで， \[ n = pq,\ de \equiv 1 \pmod{ \mathrm{lcm} (p-1, q-1)} \] である．このとき， $n$ と $e$ が与えられて $d$ を求めることは，$n$ を素因数分解するのと同等に難しいことが知られている．このため，このタイプの公開鍵暗号の安全性は素因数分解問題に依存している．

拡大体

体上の多項式
体 $\mathbb{F}$ の要素を係数にもつ多項式全体の集合 $F[x]$ を体上の多項式という． \[ f(x) = c_nx^n + c_{n-1}x^{n-1} + \cdots + c_1x + c_0 \] 非零の係数の最高次数が $n$ のとき，$n$ 次の多項式といい，その次数を \[ \mathrm{deg}\ f(x) = n\] で表す．次数が $0$ の多項式を定数という．また，最高次の係数が $1\ (c_n = 1)$ の多項式をモニック多項式と呼ぶ．
体 $\mathbb{F}$ 上の任意の多項式 $A$ と非零な多項式 $B$ は次の関係を満たす． \[ A=B・Q+R　(\mathrm{deg}\ R \lt \mathrm{deg}\ B) \] このとき，$Q$ を商多項式，$R$ を剰余多項式と呼ぶ．また， $R = 0$ のとき，$A$ を $B$ の倍多項式，$B$ は $A$ の約多項式と呼ぶ．
ある多項式のモニック約多項式が定数 $1$ 以外にないとき，既約多項式と呼ぶ．
拡大体
有限体 $\mathbb{F}$ 上の多項式 $f(x)$ が規約である場合，$f(x) = 0$ の 1 つの根を $\alpha$ とするとき，$\mathbb{F}$ 上の $\alpha$ の $n - 1$ 次以下の多項式の全体を $\mathbb{K}$ とする．この体 $\mathbb{K}$ を $\mathbb{F}$ の拡大体 (Extension Field)と呼ぶ．また，$\mathbb{F}$ を基礎体と呼ぶ．
位数が $q$ の有限体 $\mathrm{GF}(q)$ は， $q$ が素数のべきであるときのみ存在する．
拡大体 $\mathbb{K}$ は，$\mathbb{F}$ の位数を $q$，$f(x)$ の次数を $n$ とするとき $\mathrm{GF}(q^n)$ である．
同型写像
- 準同型写像
  可換環 $R$ から可換環 $S$ への写像 $\varphi: R \rightarrow S$ は以下の性質を持つとき，準同型写像(homomorphism)という．
  - $R$ の任意の元 $a$，$b$ に対して \[ \varphi(a + b) = \varphi(a) + \varphi(b) \] \[ \varphi(ab) = \varphi(a) \varphi(b) \] が成立つ．
  - $R$ の単位元を $1_R$，$S$ の単位元を $1_S$ とするとき， \[ \varphi(1_R) = 1_S \] が成立つ．
- 同型写像
  可換環 $R$ から可換環 $S$ への準同型写像 $\varphi: R \rightarrow S$ に対して， \[ \mathrm{Ker}\ \varphi = \{ \alpha \in R \ | \ \varphi(\alpha) = 0 \} \] とおくと，$\mathrm{Ker}\ \varphi$ は可換環 $R$ のイデアルである．但し，$0$ は $S$ の零元とする． $\mathrm{Ker}\ \varphi$ は $\varphi$ の核 (kernel) と呼ばれる．
  $\mathrm{Ker}\ \varphi = {0}$ のとき，$\varphi$ は中への同型写像 (isomorphism)と呼ばれる．また， $\varphi(R) = S$ のとき $\varphi$ は上への同型写像と呼ばれる．

Page Top