数理解析研究所講究録 1420 巻 2005 年 142-149

142

円分数, 暗号及び 2 次分割
松田修三 *平松豊- \dag er

Shuzo Matsuda

Toyokazu Hiramatsu

法政大学工学部

Department of Systems and Control Engineering
Faculty of Engineering, Hosei University1

ストリーム暗号

暗号方式の分類
送信者と受信者が同じ鍵を秘密に共有する暗号系を共通鍵暗号系という. 共通鍵暗号系のうち, 平文のビット列 $M=(b_{1}, b_{2}, \cdots)$ を, 鍵のビッ
ト列 $K=(k_{1}, k_{2}, \cdots)$ (鍵系列) を用いて$Ii^{r}$$c_{1}=b_{1}\oplus k_{1},$“$\mathrm{E}$-mail : matsuda@k.hosei.ac.jp-mail : hiramatu@lk.hosei.ac.jp$\dagger \mathrm{E}$$c_{2}=b_{2}\oplus k_{2},$$\cdots$

143と暗号化する暗号系をストリーム暗号という. ここで, 演算とする加算を表す. $C=(c_{1}, c_{2}, \cdots)$ が暗号文となる.

$\oplus$は 2 を法ストリーム暗号ストリーム暗号方式は, 高速な暗号処理が実現可能であり, 通信ネットワークにおける回線暗号装置等で用いられる. この方式では, 鍵系列発生器すなわち擬似乱数発生器でいかに完全乱数に近い乱数を生成できるかが暗号の安全性に対する重要な要因の一つである. 代表的な例としては,
RC4 (RSA Security 社), MULTI-SOI ( 日立, 2000 年) 等がある.
ここで ストリーム暗号方式をもう少し一般的に定義しておこう.
次の条件を満たす組 $\{F, C, K, L, F, E, D\}$ をストリーム暗号方式と呼ぶ.

1) $P$ は平文の有限集合 ;2) $C$ は暗号文の有限集合 ;は鍵の有限集合で, 鍵空間という ;3)$I\acute{\iota}$

4)

$L$

5)

$F^{\urcorner}=(f_{1}, f_{2}, \cdots)$は鍵ストリームアルファベットと呼ばれる有限集合 :は鍵ストリーム生成関数である :$\oint_{i}.$: $K\mathrm{x}P^{i-1}arrow L$$(i\geq 1)$;$\in E$ が一つ存在し, これに対応した復6) 各 $z\in L$ に対し, 暗号化規則: $Carrow P$号化規則 $d_{z}\in D$ が一つ存在する, そして, $\epsilon j:Pzarrow C$ とは任意の平文 $x\in P$ に対し, $d_{z}(e_{z}(x))=x$ をみたす.
$e_{\sim},$$d_{z}$に対しブロック暗号はストリー 暗号の鍵ストリー で, すべての$i\geq 1$て $z_{i}=K$ の場合と考えられる. また, ストリーム暗号は, すべての$\text{ム}$$\text{ム}$$\mathrm{i}\geq 1$

144
で $z_{i+d}=z_{i}$ のとき, 周期$d$をもっという. 更に, $P=C=L=\mathrm{F}_{2}=\{1,0\}$のとき,$x\oplus z$$=$$e_{z}(x)$,$d_{z}(y)=y\oplus z$となる,2円分数とその原点

2.1$n\geq 2$とし,$\mathrm{F}_{n}=\mathbb{Z}/n\mathbb{Z},$$\mathrm{F}_{n}^{\mathrm{x}}=\mathrm{F}_{n}-\{0\}$$(i\neq j)$$D_{i}\cap D_{j}=$

Fごをみたすとき, これをりの $D_{i}=g_{i}D_{0}(g_{j}.$.

$\mathrm{F}_{n}^{\mathrm{x}}$$\in \mathrm{F}_{n}^{\mathrm{x}})$分群$D_{0}$,$=\overline{\mathrm{U}}^{D_{i}}d1\dot{\mathrm{z}}=0$の分割という, 特に,のとき$D_{i}$

達を位数$(ij,)_{d}=|(D_{i}+1)\cap D_{j}|$なる高々とする. $\{D_{0)}D_{1)}\ldots, D_{d-1}\}$ がの部分群で, 残の円分類という. また,$D_{\mathrm{f}\mathit{3}}$$d$が$\mathrm{F}_{n}^{\mathrm{x}}$$(\mathrm{i},j=0,1, \ldots,d-1)$の指数 の部
個の数を位数 の円分数という, ただし,はいくつもありうる. その選び方によって, 異なる円分数が与え$d^{2}$$d$$\mathrm{F}_{n}^{\mathrm{x}}$$d$られる.の原始元,
ここで特に, $n=p=df+1$ を奇素数とし, をで生成された部分群とする. このとき $(i, j)_{d}$ は次の性質をもつ.
$\theta$$\mathrm{F}_{p}^{\mathrm{x}}$$\rangle$$1^{\mathrm{O}}$.

$i\equiv i’,$$j\equiv j’(\mathrm{m}\mathrm{o}\mathrm{d} d)$のとき$(i,j)_{d}=(\cdot i_{7}’j’)_{d}.\cdot$$2^{\mathrm{o}}$.

$($$(i, j)_{d}=(d-i,j-i)_{d}=\{$/, $i)_{d}$ ,$(j+ \frac{d}{2}, i+\frac{d}{2})_{d}$

$f$

,

$f$

: even,: odd.

$D_{0}$

を$\theta^{d}$145$3^{\mathrm{o}}$.

ここで,$\sum_{j=0}^{d-1}(i,j)_{d}=f-n_{i\gamma}$1,$n_{i}=\{$ 1,0,$4^{\mathrm{o}}$.

.

$i\equiv 0$(nlOd ),$f$: even,$i \equiv\frac{d}{2}$$(\mathrm{m}\mathrm{o}\mathrm{d} d)$,$f$: odd,

$d$

他.

ここで,

$\sum_{i=0}^{d-1}(i,j)_{d}=f-h_{j)}’$1,$h_{\grave{j}}=\{$$j\equiv 0$0,$f\llcorner \mathrm{b}$,.

$f-1_{7}j=0$ ,$j’\neq 0$ .
,.

$\sum_{i=0}^{d1}(i,i+j)_{d}=\{$$6^{\mathrm{O}}$.

$\sum_{i=0}^{d-1}\sum_{j=0}^{d-1}(i,j)_{d}=df-1=n-2$$7^{\mathrm{o}}$.

$(i, j)_{d’}=(\mathrm{i}, j)_{d}$$5^{\mathrm{o}}$$(\mathrm{n})\mathrm{o}\mathrm{d}d)$$f$$(i, j)_{d’}$

は,

.

.

$\theta’\equiv\theta^{s}$(nlod$n$) なる原始元を base にしたもの.

必要なら, $(s_{?}n-1)=1)$ .

2.2
円分数の原点は Gauss にある (: Disquisitiones Arithmeticae, 1801).
$p=df+1$ を素数とし,のとき,$\theta=\in \mathrm{i}^{\frac{2\pi i}{\mathrm{p}}},$$g$を$\mathrm{F}_{p}^{\mathrm{x}}$の原始元$\lambda$k$\mathfrak{B}\mathrm{k}\Leftarrow$

数とする.

こ

$(f; \lambda)=\sum_{j=0}^{f-1}\theta^{\lambda g^{dj}}$を Gauss は周期と呼んだ, そして, D。を$D_{i}=g^{i}D_{0}(0\leq i\leq d-1)$ とする.

$g^{d}$$(f;g^{i})= \sum_{r\in D_{i}}\theta^{r}$で生成された$\mathrm{F}_{p}^{\mathrm{x}}$の部分群,

148が成立する. この等式の右辺は, 円分方程式 $x^{p}-1=0$ の根の和を表すの選び方によらない, また, $\{D_{0}, D_{1}, \ldots, D_{d-1}\}$ ははから, 周期の分割を与える故,$(f;\lambda)$$g$$\mathrm{F}_{p}^{\mathrm{x}}$$\sum_{i=0}^{d-1}(f;g^{i})=-1$となる. この周期を使って,Theorem 2.1(Gauss) $4p=a^{2}+27b^{2},$とき,$x^{3}-y^{3}\equiv 1$$a\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d} 3)$とする.

この$(\mathrm{m}\mathrm{o}\mathrm{d} p)$の解 $(x, y)$ の個数 $N$ は, $N=p+a-2$ で与えられる.

Proof $p=3[+1$ とし, 2 つの周期 (f). ), $(f.;\mu)$ を考え,$\lambda$$(f;\mu)=\theta^{\mu 1}+\cdots+\theta^{\mu_{f}}$とおく. このとき)$(*)$$(f’; \lambda)(f).\mu)=\sum_{j=1}^{f}(f\cdot;\lambda+_{l}x_{\mathrm{j}})$が成立する. そこで, Gauss は)$0\leq mn\leq\rangle f-1$$\mathrm{i},$$j\in\{0,1,2\}$に対し, 円分数 ( , のを$i$

で$1+g^{3m+i}\equiv g^{3n+j}$をみたす組 $(m,n)$ の個数として定義する.
き, $(*)$ 等により$(\mathrm{m}\mathrm{o}\mathrm{d} p)$$(i_{i}j)=(j, i)_{3}$である. このと$N=9\cdot(0,0)+6$ ,$\alpha=(1,2)=(2,1)=(0,0)+1$ ,$a=9\alpha-p-1$と計算でき, $a=N-p+2$ を得る$\blacksquare$147
3円分数と暗号化生成関数をアーベル群とし, $|G|=d$ とおく. 暗号化生成関数を $f(x)$ とし $g_{i}\in G$ に対し,$\{G, +\}$$\rangle$$C_{i}=\{x\in \mathrm{F}_{n} :f(x)=g_{\dot{\mathrm{t}}}\}$の任意の分割とおくとき, $\{C_{0}, C_{1}, \ldots, C_{d-1}\}$ を特性類という.
. . . , $D_{d-1}$ } に対し, これを特性類とする暗号化生成関数 $f(x)$ がある.の $f(x)$ を構成する. $n=p=df^{1}+1$ を奇素数とし,$\{D_{0},$$\mathrm{F}_{n}^{\mathrm{x}}$$D_{1}$,

こ$G=\{g_{0},g_{1,7}\ldots g_{d-1}\}$とする. このとき,$f(x)$ : $\mathrm{F}_{p}arrow G$なる関数 f(のの構成は次のようである.とし,$C_{0},=D_{0}\cup\{0\}$,$C_{i}=D_{i}$$\{D_{0}, D_{1}, \ldots, D_{d-1}\}$

を円分類$(i=1,2, \ldots,d-1)$とおく. このとき, $x\in C_{i}$ に対し$f(x)=g_{i}$とする. 暗号の安全性のために大切な $f(x)$ の非線形性が円分数によって決定されることが知られている,

42 次分割の整数論
円分数は暗号の鍵系列生成をデザインするのに有用であった. その円に始まる. 位数 3 の円分数は, $4p=$分数と 2 次分割の関係はの円分数$x^{2}+27y^{2},$ $x\equiv 1$ (nlod 3) の解 $(x, y)$ によって決まり, 位数 9の鰍 , ) によって決まる. 実 t よ殆ど
は, $4p=x^{2}+27y^{2},$$\mathrm{G}\mathrm{a}\mathrm{t}1\mathrm{s}_{\mathrm{k}}\mathrm{s}$$x\equiv 7(\mathrm{m}\mathrm{o}\mathrm{d} 9)$$x$$y$の円分数は, 素数 の表現 $p=x^{2}+ny^{2}$ によって決まることが知られている. その 2 次分割について, 整数 $n(\neq 0)$ , 奇素数 $p(p\{n)$ に対し$p$$p|(x^{2}+ny^{2}),$$(x, y)=1$

く\Leftrightar ow (- -pn)$=1$を法とする Legendre 記号を表す, そこで 7はが成立する. ここで,次の 2 つのアプローチが考えられる :$( \frac{*}{p})$

$p$

148

アプローチ 1 $p=x^{2}+ny^{2}$ と表される大きな素数をみつけよ. ここ$p$は暗号のためにデザインされたパラメータを表すそして必要ならで,ばこの 2 次分割を得るためのアルゴリズムをみつけよ.
$n$アプローチ 2 与えられた暗号化パラメータ $n$ に対し, 集合 $B(n)=\{x^{2}+$$ny^{2}$: $x,$$y\in \mathbb{Z}$} から大きな素数をさがせ.

更に, これらのアプローチを分けて考える. アプローチ 1 については,
問 LA与えられた$n$に対し, どの素数$p$が $p=x^{\underline{9}}+ny^{2}$ と表されるか?

これについては次の結果がある :で squarefree な正整数とする 5 そのTheorem 41 をとき, nlonic で次数 $h(-4n)$ の整係数既約多項式 $f_{n}(x)$ があって, 奇素数
で $p\{7l,$ $p\{D_{f}n$ (. は几の判別式) に対し$n\not\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d} 4)$$n$$D_{f_{rr}}$$p$$p=x^{2}+ny^{2} \Leftrightarrow(\frac{-n}{p})=1$

で几 $(x)\equiv 0$(IllOd ) が$p$整数解をもつが成立する. ここで, $h(-4n)$ は判別式 $-4n$ の正定値原始 2 次形式の類数を表す 9 更に,は実代数的整数) が虚 2 次体
(上のヒルベルト類体のとき 7 $f_{n}(x)$ は の最小多項式である.
$I\zeta(\alpha)$$I\zeta=\mathbb{Q}(\sqrt{-n})$$c\mathrm{v}$$\alpha$

問 1.B

もしそうなら, $p=x^{2}+ny^{2}$ となる解
た, 解 $(x_{7}y)$ をみつけるアルゴリズムはあるか ?

$(x_{\mathrm{J}}y)$は何個あるか ? ま

この間 IB の後半については, Cornacchia のアルゴリズムがある. 前半
は open problenl である,

アプローチ 2 については,
問 2A

どんな$n$に対し, $B(n)$ は無限個の素数を含むか ?

これについては,Theorem 42 $ax^{2}+bxy+cy^{2}$ を判別式 $D(<0)$ の正定値原始 2 次形式とし, これが表す素数の集合を $PB(a, b, c)$ とするとき, Dirichlet 密度は$\delta(PB(a,b,c))=\frac{1}{h(D)}$または$\frac{1}{2h(D)}$で与えられる. 特に, $ax^{2}+bxy+c\{J^{2}$ は無限個の素数を表現する.

149

問

そのような

$2.\mathrm{B}$

この問$2.\mathrm{B}$$n$に対し,, $B(n)$ から大きな素数をいかにみつけるか?

は open problem である.

参考文献
[1] D. A. Cox ;Primes of the Form $x^{2}+ny^{2},$ John Wiley and Sons, Inc.,$19\mathrm{S}9$.

[2] T. W. Cusick, C. Ding and A. Renvall;Stream Ciphers andTheory (&vised Edition) North-Holland, 2004.

$\mathrm{N}\iota \mathrm{l}\mathrm{n}\mathrm{l}\mathrm{b}\mathrm{e}\mathrm{r}$$)$and its appliNew generalized[3] C. Ding and T.
cations, Finite Fields and their Applications, 4 (1998), 140-166.
$\mathrm{H}\mathrm{e}11\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{t}_{\mathrm{J}}\}_{1}$$.$)$\mathrm{C}_{\backslash }\mathrm{v}\mathrm{c}1\mathrm{o}\mathrm{t}\mathrm{o}\mathrm{m}\mathrm{y}$