数理解析研究所講究録 1420 巻 2005 年 183-192

183

XTR を用いた暗号とその高速実装

野上

岡山大学・工学部・通信ネットワーク工学科

保之 (Yasuyuki Nogami)Communication Network Engineering,
Okayama University

1

はじめに
近年, 情報セキュリティ技術, とりわけ電子認証技術の重要性は高まってきており, これを実現するための技術として公開鍵暗号は必要不可欠である. これまで RSA (Rivest Shamir Adleman) 暗号が広く用いられてきたが, 楕円曲線暗号,

XTR (Efficient and Compact Subgroup hace$\mathrm{R}\mathrm{e}\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n};\mathrm{E}\mathrm{C}\mathrm{S}\mathrm{T}\mathrm{R}arrow \mathrm{X}\mathrm{T}\mathrm{R}$)を用いた暗号などが, 次世代の公開鍵暗号技術として注目されている $[1],[2]$ . 楕円曲線暗号と XTR を用いた暗号との共通点は, RSA 暗号に比べて鍵長が短くて済むこと, また暗号化および復号処理が高速に行えること, 定義体として位数の大きな有限体を用いていることなどが挙げられる. 本論文では, 位数の大きな

XTR を用いた暗号の暗号化/復号処理の高速化という観点から紹介する.
拡大体の高速実装に関する従来の研究においては, OEF (Optimal Extension Field)[3], AOPF (All

拡大体の高速実装法を,

One Polynomial Field)[4], TypeII AOPF (TypeII All One Polynomial Field)[5] がよく知られている.
位数の大きな拡大体の高速実装においては, その拡大体における乗算に必要となる計算コスト, 計算処理
. 時間が鍵となる. これら 3 つの拡大体においては, その標数 法多項式, 乗算アルゴリズムなどを工夫することで, 計算コストを少なくし, 計算処理を高速化している. 例えば OEF では, 赤数に擬メルセンヌ

素数 法多項式に既約 2 項式を用い, 乗算に Karatsuba 法 [6] を採用することで高速実装して る. 一方
AOPF では, TypeI ONB (Optimal Normal Basis) [7] を利用する乗算アルゴリズム CVMA (Cyclic Vector$\mathrm{k}^{\mathrm{a}}$Multiplication Algorithm) を用いて高速化を実現している. ただし AOPF は, 偶数次数の拡大体しか構成できず, これを奇数次数の拡大体も構成できるよう改良したものが TypeII AOPF であり, TypeII ONB お
よび CVMA を改良したものを用いていることが特徴である. 本論文では, XTR を用 た暗号の高速実装$|,$という観点から,$\mathrm{a}$とくに乗算の計算コストについて, これら拡大体の性能を比較する.

とくに断らない限り, $p$ を素数,$m$を正整数として, 素体$F_{\mathrm{p}}$上の $m$ 次拡大体を$F_{p^{m}}$のように表す. $X|Y$

および $X \int Y$ は, それぞれ $X$ が $Y$ を割り切ること, および割り切らないことをそれぞれ表す

2

XTR
本章では,

楕円曲線暗号とともに次世代の公開鍵暗号に用いることができるとして注目されている XTR(Efficient and Compact Subgroup hace

) につ , ‘て紹介する.
$\iota$$\mathrm{R}\mathrm{e}\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n};\mathrm{E}\mathrm{C}\mathrm{S}\mathrm{T}\mathrm{R}$

184
2.1

XTR で用いる乗法群とトレース表現

XTR では, 単位元 1 を除くすべての元が$F_{p^{6m}}$の真性元 1 であり, かつ位数が $p^{2m}-p^{m}+1$ を割り切る

170 ビット以上の素数であるような以下に示す乗法群を準備する.
く $\{g, g^{2}, \cdots,g^{t}=1\},$

$g$

は位数が

$\cdot>$,$t|(p^{2m}-p^{m}+1)$ ,ここで・は, 乗算を表すものとする.

$t$の $F_{p^{6m}}$ の真性元であり上記の乗法群の生成元である.

$t$

課すことによって,$F_{p^{6m}}$

トレース関数を用いて(1)は 170 ビット以上の素数

位数

$t$

に対して, 上式のような条件をの真性元であることが保障されることとなる. この乗法群の各元を, 以下に示す$F_{p^{2m}}$の元に写像し,$\mathrm{R}(x)=x+x^{p^{2m}}$十(2)$x^{p^{4n}}$次のような群を構成する.
$<\{\mathrm{b}(g), \mathrm{b}(g^{2}), \cdots,\mathrm{h}(g^{t})=3\},$

ここで演算

は,

$\circ$$:\mathrm{R}(q^{i})\circ’\mathrm{R}(q^{j})=\mathrm{T}\mathrm{r}(g^{i+j})$というように, 式 ($1\rangle$(3)$\circ>$に示した乗法群の演算・を踏襲するような形で理解すればよい. これを用いて, 23 に紹介する XTR-DH 鍵交換などを構成することとなる. Lenstra
ら [2] によって提案された XTR は, 定義体$F_{p^{6m}}$に対して $m=1$ としており, これを Lim ら [8] が$F_{p^{6m}}$に拡張して XTR が実現できることを示した. 以降では, 表記の簡単化のために旺 (gn) $=c_{n}$ とする. XTR

では以下の関係式を駆使して演算$\circ$を実装する.

(4a)へ $=3$$c_{1}=$

(4b)

Tr(g)

$c_{n+2}=\mathrm{c}_{1}\cdot c_{n+1}-\mathrm{c}_{1}^{p^{m}}$.

$c_{n}+c_{n-1}$$c_{2n}=c_{n}^{2}-2d_{n}^{t^{m}}$(4c)$(4\mathrm{d})$$c_{2n-1}=c_{n-1}\cdot c_{n}-c_{1}^{\mathrm{p}^{m}}\cdot d_{n}^{2^{m}}+c_{n+1}^{\mathrm{p}^{m}}$$(4\mathrm{e})$$\mathrm{c}_{2n+1}=c_{n+1}\cdot c_{n}-c_{1}\cdot d_{n}^{\mathrm{z}^{m}}+c_{n-1}^{\mathrm{p}^{m}}$$(4\mathrm{f})$$(4\mathrm{g})$

以下に,

[

$c_{r}=\mathrm{T}\mathrm{r}(g^{r})$$c_{r}=\mathrm{T}\mathrm{r}(g^{r})$INPUT :

Stepl :

$r$の計算アルゴリズ A 】$c_{1}=\mathrm{T}\mathrm{r}(g)$OUTPUT :の計算アルゴリズムを示す.

, 整数

$r$

$c_{r}=\mathrm{b}(g^{r})$が奇数のとき $n=r$ , 偶数のとき $n=r-1$ とする.

Step2 : $h=(n-1)/2$ とし,

Step3 : 式 ($4\rangle$

1 真部分体} $.$ }を用いて,$\mathrm{g}\mathrm{g}$$\mathrm{g}$な$\overline{S}_{k}=(c_{2k}, c_{2k+1}, c_{2k+2})$$\overline{S}_{1}=(c_{2}, c_{3}, c_{4})$$\mathrm{k}^{\backslash }\overline{\pi}\theta 2=\text{と}$を計算する.

giRffl\pi -\geq ffs‘.\sim - ととする.

とおく,

185
$\mathrm{S}\mathrm{t}\mathrm{e}\mathrm{p}4$:$h$を以下のように 2 進表現する. ここで,

$h_{i}\in\{0,1\},$$l-1\geq \mathrm{i}\geq 0$$h=h_{0}+h_{1}2+h_{2}2^{2}+h_{3}2^{3}+\cdots$ 十 $h_{l}2^{l}$

Step5 :

期値は

.

(5)

$h_{l}=1$

を除く $h_{l-1},$ $\cdots h0$ に対し, 上位ビット $h_{l-1}$ から $h0$ の順に以下の操作を繰り返す. ここで, 初$h\iota$

.

,

である.

$k=1,\overline{S}_{1}=(c_{2}, c_{3}, \mathrm{c}_{4})$とする.

この繰り返しによりビットが 1 のとき, 式 (4) を用いて$\overline{S}_{k}$ビットが 0 のとき, 式 (4) を用いて$\overline{S}_{k}$が偶数の場合には, 式 (4) を用いて

Step6 :

$r$

Step7:$S_{r}=(c_{r-1}, c_{r}, \mathrm{c}_{r+1})$となり,$c_{r}$を$\acute{\not\in}\ovalbox{\tt\small REJECT}$$S_{n}$からから$\overline{s}_{2k}$$S_{n}=\overline{S}_{k}$を求め,$\overline{S}_{2k+1}$

$2k$

を

$k$

となり,

$S_{n}$

が求まる.

で置き換える.

を求め, $2k+1$ を$k$で置き換える,から $s_{n+1}$ を計算し, $n+1$ を $n$ で置き換える.

る$\bullet$アルゴリズムから分かるように, XTR を用いた暗号においては, 式 (4) の計算を多用することとなる.

フロベニアス写像を高速に計算処理できるものが有効である

このことは, すなわち定義体としては, 乗算,

ことを意味する. ここで, 式 (4) の計算は場

22

ではなく,

$6m$

上で行われることに注意する.

トレース表現における離散対数問題

いわゆる有限体上の離散対数問題 ($\dot{\mathrm{D}}\mathrm{i}\mathrm{s}\mathrm{c}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{e}$Logarithm$a=g^{x}$$a,$ $g$$F_{p^{2\mathrm{m}}}$の情報のみから,$\mathrm{P}_{1\exists}$

数部

$x$

を求めることが E,$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m};\mathrm{D}\mathrm{L}\mathrm{P}$) は, 次式のような関係に対して,(6)$a,g\in F$

であるという問題である. 計算機を用いてもなお$\mathrm{B}\ovalbox{\tt\small REJECT}$

なで t まトレー問題とするために, 有限体 $F$ の位数は非常に大きくなければならない 2. これに対して, XTR

ス表現における離散対数問題 (XTR-DLP) を次式のように考える.
$a=\mathrm{T}\mathrm{r}(g^{x})$,$g\in F_{p^{6n}},$(7)$a\in F_{\mathrm{p}^{2m}}$

このような関係を満たす および駈 (g) から, その指数部 を求めることはやはり困難な問題であり, Lenstra
さは同等であることが示されてし る 3. それに加え XTR では,
ら [2] によって, XTR-DLP と DLP の
$s$

$a$

$\mathrm{a}$$\ovalbox{\tt\small REJECT}$

トレース関数を用いて部分体$F_{p^{2n}}$$\text{し}$の元として暗号鍵を構成するため, DLP に基づく暗号方式よりも ‘鍵長

さらに先に示した計算アルゴリズムを用いて部分体の計算などが行われることから, 高速な暗号化/復号処理が実現できることとなる.

が 1/3

2.3

$\ovalbox{\tt\small REJECT}^{\mathrm{t}}\mathrm{a}\mathrm{e}’\not\in$と短くて済み,$F_{p^{2m}}$上で$\S_{\mathrm{B}}^{4\mathrm{t}}$号化XTR-DH 鍵交換(DH)
ここでは, 簡単のために XTR を用いた場合の Diffie-Hellman

対交換につ[XTR-DH 鍵交換】

公開鍵 ; 定義体

$F_{p^{6m}}$

および$\mathrm{T}\mathrm{r}(g),$$g\in F_{p^{6m}}$$\overline{2\#\mathrm{g}\doteqdot|_{\vee}^{}ffl\mathrm{t}^{\mathrm{a}}6k_{\Omega}^{\mathrm{A}}\}’.\mathrm{f}2:,\mathscr{L}4\mathrm{f}*\epsilon\not\in \mathrm{f}\mathrm{f}\mathrm{l}\mathrm{Y}6T_{\vee}^{\wedge}d\}\}’.}$, 他にも幾つかの条件が課せられる.

3 XTR-DLP および DLP それぞれの生成元 $g$ が属する有限体が同程度の位数であるとする.

$\backslash$$\acute{.}$て示す.

$/’\not\in\tau^{\mathrm{D}}\text{処理}$$\iota\epsilon\epsilon$

Alice と Bob の問で鍵を共有する.

目的 :Stepl :Alice は乱数

$a$

を用いて丑

Step2 : Bob は乱数 を用いて狂$b$$(g^{a})$$(g^{b})$を計算して Bob に送信する.

を計算して Alice に送信する,

Step3 : Alice, Bob は, それぞれにおいて Tr
有限体上の DLP を用いた通常の$\mathrm{D}\mathrm{H}$$(g^{ab})$を計算し, これを用いて鍵を共有する.

$\blacksquare$

XTR-DH 鍵交換ではやり取りする鍵データが短鍵交換と比べて,くて済み, それぞれの計算処理についても楕円曲線暗号よりも高速であると言われる [2].

2.4

XTR に用いる拡大体

Lenstra ら [2] が提案した XTR は, 定義体を

$F_{p^{6}}$とし, その部分体

号計算処理を行うというものである. これを Lim ら [8] が$F_{p^{6m}}$$F_{p^{2}}$を用いて鍵の構成, 暗号化/ 復に拡張して XTR を実現できることを示した. 拡張したことの最大の効果は, 選択できるパラメータが回数 $p$ および拡大次数 $m$ の 2 っになることにある.

XTR を用いた暗号の安全性を確保するためには, 定義体である

以上でなければならない 4. すなわち, これを確保するための標数$6m\log p\geq 1024$

となり,

$p$

$F_{p^{6m}}$の位数 $p^{6m}$ が 1024 ビットのビット数と, 拡大次数 $m$ の関係はこれを満たす組み合わせとして工数と拡大次数を選ぶことができる.

表 1; $6m\log p\approx 1024$ となる標数

例えば $6m\log p$ が 1024 になるような標数

$p$

$p$

と拡大次数 $m$ の組み合わせと拡大次数 $m$ の組み合わせば, おおよそ表 1 のようになる.

3 において具体的に説明するが, パソコンやマイコンなどのように, ワードサイズが 16 ビットや 32 ビットなど決まっている計算機で XTR を用いた暗号を実装する場合, その有限体の標数 がワードサイズ未満であるのは, プログラムの高速化やコンパクト実装の面から都合がよい. 言い換えれば, 用いる計算機のワー$p$

ドサイズに合わせて標数を設定し, その上で十分な安全性を確保できるように拡大次数を決定すればよい.
そのような工夫に基づきながら, 定義体となる拡大三$F_{p^{6m}}$

を高速かっコンパクトに実装することが, XTRを用いた暗号の高速実装につながる.

3$\mathrm{X}\mathrm{T}\mathrm{R}$を用いた暗号の高速実装

本章では, 乗算, フロベニアス写像を高速に処理できる拡大体として, OEF, AOPF, および TypelI

AOPF を紹介し, XTR に用いるという観点からこれらを比較する.

31

OEF (Optimal Extension Field)

Bailey ら [3] によって提案された OEF は, 次のように定義される拡大体

42004 年 11 月の時点でそのように言われている.

$F_{p^{m}}$

である.

187
標数

$p$

:

$n$

が計算機のワードサイズ未満である擬メルセンヌ素数 $p=2^{n}\pm c,$$\lfloor n/2\rfloor\geq\log_{2}c$法多項式 :2 次既約多項式 $x^{m}-s,$ $s\in F_{p}$基底 : 法多項式の零点による擬多項式基底 :$\omega$.

(8)$\{1, \omega,\alpha),\cdot\omega^{m-1}’\}2.$

このような罪数$p$および法多項式を選ぶことは, それぞれ素体における乗算の後の剰余演算および拡大体における多項式乗算の後の多項式剰余演算を高速に行うための工夫である. とくに, 標数 がメルセンヌ素数である場合を TypeI OEF, 法多項式が $x^{m}-2$ である場合を TypeII OEF と呼び, さらに高速な実装を実現することができる. OEF の高速実装に関する詳細については文献 [3] を参照していただきたいが, OEF$p$における多項式乗算には Karatsuba 法を応用して高速化を図っている. 法多項式に対する条件として, 拡
大次数 $m$ のすべての素因数は $p-1$ を罰り切らなければならない. また, フロベニアス写像には, $m-1$
回の$F_{p}$

上での乗算を必要とする.

AOPF (All One Polynomial Field)

32

AOPF は, 筆者らがこれまでに提案した拡大体であり, 拡大次数は必ず偶数でなければならず,
瑞 のように表せば, 以下のように定義される拡大体である [4].

これを

$2m$

標数

$p$

:

$n$

が計算機のワードサイズ未満である擬メルセンヌ素数 $p=2^{n}\pm c,$$\lfloor n/2\rfloor\geq\log_{2}c$法多項式 : $2m$ 次詳細多項式 $(.x^{2m+1}-1)/(x-1)$
基底 : 法多項式の零点$\omega$による擬多項式基底 :(9a)$\{\omega,\omega^{2}, \cdots,\omega^{2m-1},\omega^{2m}\}$式 (9a) の擬多項式$\text{基底}$は, 式 (9b) に示す挙$\mathrm{f}\mathrm{f}\mathrm{l}\text{基}$底と等価 fx

合であり,TypeI Optimal Normal Basis(ONB) とも呼ばれ, 乗算を高速実装するのに適している.
(9b)$\{\omega,\omega^{p},\omega^{p^{2}}, \cdots’\omega^{\mathrm{p}^{2m-1}}\}$

また, ‘l‘#多 aex $(x^{2m+1}-1)/(x-1)$ 力$\grave{\grave{1}}$$F_{p}$

上で既$\hslash’\backslash ^{\backslash }$2: なるためには, 以下に示す条件が必要+分である.

1: $2m+1$ が素数である.
2: $F_{2m+1}$ において元$p$が原始元である.

Multiplication Al-

AOPF における乗算は, 以下に紹介する高速乗算アルゴリズム CVMA (Cyclic Vector
力 , $(x^{2m+1}-1)/(x-1)$
gorithm) により行う. CVM A では, AOPF の基底である式 (9a) を構成する元の任意元に対する乗算を高速に行う.
の零点であることから満たす次の 2 つの関係式を駆使し,$1*$$\omega$$F_{p^{2m}}$$\omega^{2m+1}=1$,$\omega+\omega^{2}+\cdots+\omega^{2m}=-1$

(10)

188
まず式 (9a) で与えられる擬多項式基底で次のようにベクトル表現される$X=(x_{1}, x_{2}, \cdots, x_{2m})$$x_{i},$,$Y=(y_{1},y_{2}, \cdots, y_{2m})$$y_{i}\in F_{p}$$F_{p^{2m}}$の

2 元 $X,$

$Y$

に対し,

(lla)

,

, where $2m\geq i\geq 1$

これら 2 元 $X_{1}Y$ の積 $Z$ を次式で考えれば,$Z=XY=(z_{1}, z_{2}, \cdots, z_{2m}),$CVMA により, $2m\geq j\geq 0$ として次式の$q_{j}$$z_{i}\in F_{p}$を求め,$q_{j}= \sum_{k=1}^{n}\{(x_{\langle 2^{-\mathrm{q}}j+k\rangle}-x_{\langle 2j-k\rangle}-1)\cdot(y_{\langle 2^{-1}j+k\rangle}-y_{\langle 2^{-1}j-k\rangle})\}$

$Z$

(12)

, where $2m\geq i\geq 1$

,

(13a)

の各係数 $zi$ は次式により求められる.
$z_{i}=q_{0}-q_{i}$,$2m\geq i\geq 1$

.

(13b)

Katatsuba 法と異なり, CVMA は式 (13a) のように具体的な計算式に基づくため, 計算コストを拡大次数
を $F_{2m+1}$ において計を用いた定式により与えることができる [4]. なお, 式 (13a) にみられる記号$\langle\cdot\rangle l3;,$$\cdot$

算した結果を示す. CVMA の例として, $m=2$ とした場合について以下に示す.
$z_{1}=q_{0}-\{(x_{2}-x_{4})(y_{2}-y_{4})+x_{1}y_{1}\}$(14a)$z_{2}=q_{0}-\{(x_{3}-x_{4})(y_{3}-y_{4})+x_{2}y_{2}\}$(14b)$z_{3}=q_{0}-\{(x_{1}-x_{2})(y_{1}-y_{2})+x_{3}y_{3}\}$(14c)$z_{4}=q_{0}-\{(x_{1}-x_{3}\rangle(y_{1}-y_{3})+x_{4}y_{4}\}$$(14\mathrm{d})$$q_{0}=(x_{1}-x_{4})(y_{1}-y_{4})+(x_{2}-x_{3})(y_{2}-y_{3})$$(14\mathrm{e})$CVMA は, 拡大次数が小さい場合にとくに有効であることに加え, 式 (14) から分かるように次に定義される自己相反元に対してとくに有効となる [4]. 後者の有効性については 33 で詳しく述べる.
定義 1$F_{p^{2m}}$の元 $A=(a_{1}, a_{2}, \cdots, a_{2m})$ に対し.

$A^{*}=(a_{2m},$ $\cdots,$ $a_{2},$ $a_{1}$

}を

$A$

の相反元と呼び,成り立つとき $A$ を自己相反元と呼ぶ
なお,

CVMA の計算式である式 (13a) と式 (13b) は, $2m$ 次 AOP の零点

みから導かれ,$A=A^{*}$

力S$\blacksquare$$\omega$に対して成り立つ式 (10) のこれが既約であるか否か, すなわち式 (9a) が基底を成しているか否かには依存しないことに注意する [4]. この事実は 33 で重要となる. なお, フロベニアス写像には, 正規基底を用いていることからも分かるように, 加算や乗算といった計算は必要としない.

3.3

TypeII AOPF (TypeII All One Polynomial Field)

まず Typell AOPF が基底として用いる TypeII ONB を紹介して, つついて TypeII AOPF の定義を与える. そして,32 で紹介した自己相反元と TypeII AOPF の元との関係を示す.

188
331

TypeII Optimal Normal Basis

TypeII ONB は, 以下のように定義される [7].
定義 2 瑞上の $2m$ 次 AOP $(x^{2m+1}-1)/(x-1)$ の零点を$\omega$とし, 次に示す $m$ 個の元の集合を考える.

(15a)$\{\omega+\omega^{-1}, \omega^{2}+\omega^{-2}, \cdots,\omega^{m}+\omega^{-m}\}$

このとき, 拡大次数 $m$ と標数 $p$ が以下に示す条件 1 を満たし,

これに加えて条件$2\mathrm{a}$あるいは$2\mathrm{b}$のいず

れかを満たすとき,

1: $2m+1$ が素数$2\mathrm{a}$: $F_{2m+1}$ において

$p$

が原始元

$2\mathrm{b}$: $F_{2m+1}$ において$p$の位数が $m$ , かつ

式 (15a) は$F_{\mathrm{p}^{m}}$の基底を成すと共に,$2m+1\equiv 3\mathrm{m}\mathrm{o}\mathrm{d} 4$

次に示す正規基底と等価となることから TypeII ONB と呼ばれる.

(15b)$\{\beta,\beta^{\rho}, \cdots,\beta^{p^{m-1}}\}$

ここで,$\omega$である.

$\beta=\omega+\omega^{-1}$$\blacksquare$

TypeII ONB に関連して, 本論文では次に述べる性質に注目する. まず $2m+1$ が素数であることより,
は位数 $2m+1$ の元であり, 式 (9a) のような相異なる $2m$ 個の元の集合を考えることができる. 3.2 で紹介したように, 上述の条件 1 および$2\mathrm{a}$なわち TypeI ONB を成獣 そして,$\omega$が満たされるときは,

この集合は$F_{p^{2m}}$の擬多項式基底であり, すに対して成り立つ式 (10) の前者の関係を踏まえれば,(16)$\omega^{-1}=\omega^{2m}$が成り立ち, 条件あるいは$2\mathrm{a}$$2\mathrm{b}$のいずれの場合に対しても, 式 (9a) に示される元の集合は, その順序も含めて以下の集合と等価となる.
(17)$\{\omega,\omega^{2}\cdots,\omega^{m}, \omega^{-m}, \cdots,\omega^{-2},\omega^{-1}\}\}$

加えて Typell ONB は, 式 (15b) に示されるように正規基底であり,フロベニアス写像 {ごは,様に加算や乗算といった計算は必要としない

332

TypeII AOPF の定義

TypeII AOPF は, 以下のように定義される拡大体$\cdot$$F_{p^{m}}$である.

標数 $p:n$ が計算機のワードサイズ未満である擬メルセンヌ素数 $p=2^{n}\pm c,$法多項式 : $2m$ 次多項式 $(x^{2m+1}-1)/(x-1)$
基底 : 法多項式の零点$\omega$

による TypeII ONB :$\lfloor n/2\rfloor\geq 1o\mathrm{g}_{2}c$

AOPF と同190(18)$\{\omega+\omega^{-1},\omega^{2}+\omega^{-2}, \cdots,\omega^{m}+\omega^{-m}\}$

TypeII AOPF において重要な点は, TypeII ONB を用いていることであり, それに伴って定義 2 の条件がTypeII ONB を構成する元
満たされなければならない. また, 上記の法多項式は既約である必要はな
を零点にもっという意味で記している. 加えて $m$ が素数ならば, 素数次数の拡大体の構成法となる.
$\text{く},$$\omega$

自己相反元と TypeII AOPF の元333

32 でも触れたように, CVMA に対しては必ずしも $2m$ 次 AOP が既約である必要はない. ここで重要
なことは,

$2m$

次 AOP の零点$\omega$により式$(.9\mathrm{a})$のように与えられる元の集合を用いて, $2m$ 次のベクトル表現を盛ることである. ここでは, 32 で紹介した自己相反元と TypeII ONB によりベクトル表現される

TypeII AOPF の元との関係をみる. まず TypeII AOPF

$F_{p^{m}}$の任意元 $X$ は式 (18) の TypeII ONB を用いて次式のように表すことができる.
$X= \sum x_{i}(\omega^{\dot{1}}m+\omega^{-i})$,$x_{i}\in F_{p}$(19a), where $m\geq i\geq 1$ .

$i=1$上式のように表されることに加え, 式 (9a) と式 (17) は順序も含めて等価であり, 式 (16) を踏まえて, TypeII

AOPF$F_{p^{m}}$の任意元が 32 で紹介した自己相反元として次式のように取り扱えることが分かる.
十 $x_{m}\omega^{l}+x_{m}\omega^{m+l}+\cdots$ 十 $x_{2}\omega^{2m-1}+x_{1}\omega^{2m}$$X=x_{1}\omega$ 十 $x_{2}\omega^{2}+\cdots$

なお, 定義 2 の条件 1 および$2\mathrm{a}$$m$331 にも述べたように式 (9a) は TypeI ONB となるとにおける自己相反元との基底を成すことから, AOPF

を満たす場合は,いうことに加え, 32 で紹介した AOPF

はその部分体である瑞(19b)$F_{p^{2m}}$$F_{\mathrm{p}^{2m}}$の元である [4].

CVMA を改良して用いた TypeII AOPF における乗算

334

333 に述べた自己相反元と TypeII AOPF の元との関係を踏まえた上で, 式 (10) の関係を用いれば,の元 $Y$ を考え,
TypeII ONB を用いた CVMA を考えることができる, 式 (19) と同様に TypeII AOPF
$F_{p^{m}}$$Y= \sum_{i=1}^{m}yi$

2 元 $X,$$X,$ $Y$

$Y$

が式

(

$\omega^{i}$十$\omega^{-i}$),$y_{i}\in F_{\mathrm{p}}$, where$m\geq \mathrm{i}\geq 1$

.

(20)

の積 $Z$ を式 (12) および式 (13) に示す CVMA を用いて考える. まず式 (13a) で $q0$ を求めれば,$(19\mathrm{b})_{t}$(20) に示すように共に自己相反元であることより $q_{0}=0$ のようになる. すなわち,計算する必要はない. 続いて,

$X,$ $Y$が自己相反元であることにより,$m\geq j\geq 1$$q_{0}$

はとして, 式 (11) に対して次式が成り鍵っことから,$x_{j}=x_{(-j\rangle}=x_{2m+1-j}$,

式 (13a) に対し $qj=q\langle-\mathrm{j}\rangle=q2m+1-j$ が成り立つ.

$y_{j}=y_{\langle-j)}=y_{2m+1-j}$

これに$q\mathit{0}=0$$z_{j}=z_{\langle-j\rangle}=z_{2m+1-j}$

,

(21)

を踏まえ, 式 (12) に対して次式を得る.

(22)

191
すなわち,

自明な性質ではあるが, 自己相反元である TypeII AOPF

相反元となる. この結果, TypeII AOPF

$F_{\mathrm{p}^{m}}$$F_{p^{m}}$の 2 元 $X,$ $Y$ の積 $Z$ もまた自己における任意の 2 元 $X,$ $Y$ の積 $Z$ を, CVMA を用いて求める計算式として次式を得る.
$\chi j=\sum_{k=1}^{[] n}\{(x\{2^{-1}j-k\rangle-x\langle 2^{-1}j+k\rangle)\cdot(y(2^{-1}j+k\rangle-y\langle 2^{-1}j-k\rangle)\}$

.

(23)

, where $m\geq j\geq 1$

ここで。は, を $F_{2m+1}$ で計算をした結果であり, 式 (23) の計算は, 式 (21) の関係を用いて行うことに注意する. TypeII AOPF における CVMA を用いた乗算の一例として, 拡大次数を $m=2$ の場合を考える.
$\cdot$2 元 $X,$$Y$

を以下のように表せば,$X=x_{1}(\omega+\omega^{-1})+x_{2}(\omega^{2}+\omega^{-2})$

,

(24)

$Y=y_{1}(\omega+\omega^{-1})+y_{2}(\omega^{2}+\omega^{-2})$

式 (23) を用いて, その積 $Z$ が次式のように求まる.
$Z=z_{1}(\omega+\omega^{-1})+z_{2}(\omega^{2}+\omega^{-2})$(25a)$z_{1}=(x_{1}-x_{2})(y_{2}-y_{1})-x_{1}y_{1}$(25b)$z_{2}=(x_{1}-x_{2})(y_{2}-y_{1})-x_{2}y_{2}$(25c)細かいことではあるが, 式 (25b) および式 (25c) にみられる $(x_{1}-x_{2})(y_{2}-y_{1})$ の計算結果は共用し, それぞれで別途に計算するようなことはしない.

乗算,

34

フロベニアス写像に要する計算コストの比較

本章では, OEF, AOPF, および TypeII AOPF における乗算, およびフロベニアス写像の計算コスト
具体的について, それぞれに必要となる素言上の加算 (減算) および乗算の回数という観点から比較する.
内の数字は, 左から素吊上の加算 (減算) およ
なお, 表 2 においてには 6 次拡大体について比較する.

$()$

び乗算の回数である. 逐次拡大法については, 文献 [9] を参照していただきたい.
表 2: 6 次拡大体

表 3 は, gff 的に P\pi ‘

理時間を
用い

.

$\sim$$\Rightarrow\Rightarrow\}^{\backslash }\mathrm{p}ffi\backslash \mathrm{t}\mathrm{J}$$\mathbb{P}_{\mathrm{B}}\text{号を}$し$_{arrow}^{-_{\mathrm{Y}}^{J}\beta_{0}}$

‘’

$p$

を

果である.

$F_{p^{6}}$における乗算およびフロベニアス写像の計算コスト

それぞれの 6 次拡大体において乗算 1 回にかか一算処を用いた. これらデータから, XTR をには PentiumIII$2^{24}-3\#.-\vec{\frac}\dot{\alpha}\hat{k}\mathrm{n}$し,$(800\mathrm{M}\mathrm{H}\mathrm{z})$$\mathrm{C}\mathrm{P}\mathrm{U}$高\‘iE 実噂する場合には, AOPF や TypeII AOPF が適して$\mathrm{b}^{\mathrm{a}}$るとうことができる.

$\mathrm{O}\mathrm{E}\mathrm{F}$とであるかにあり, それぞれの特徴がある.

AOPF の大きな違いは, その乗算方法が Karatsuba 法か CVMA
また並列実装例えば CVMA であれば, 拡大次数が小さい方が性能がよく,文献 [5] を参照していただきたい.

$\mathfrak{j}_{f}\mathrm{a}$$\}_{\mathrm{L}}^{^{\backslash }}\ovalbox{\tt\small REJECT}$している.

$\yen^{1}\overline{\overline{\emptyset}}$

細こついては

192
表 3:$F_{p^{6}}$における乗算の計算処理時聞の比較$\mathrm{u}\mathrm{n}\mathrm{i}\mathrm{t}:\mu \mathrm{s}$$ffl_{\backslash }.\ovalbox{\tt\small REJECT}$:$f\mathfrak{F}\Re\ae$$\not\in\backslash \backslash \mathscr{L}:\mathrm{g}\ni$

TypeII OEF$\mathrm{n}24$$n$$\overline{z}^{--}-.3$$\not\in\backslash \theta\backslash \mathrm{i}ffi\star$

TypeII AOPF$\dagger_{\omega}$

1.47$(x^{13}-1)/(x-1)$

1.46

1.46

$(x^{7}-1)/(x-1)arrow(x^{5}-1)/(x-1)$

1.29

TypeII OEF.

$x^{6}-2$$x^{3}-2arrow x^{2}-\omega^{\dagger}$

TypeII AOPF$\not\in\backslash \grave{\{}kffl \mathrm{X}$

is a zero of $x^{3}-2$ that is the modular polynomial of*CPU:PentiumIII,

4.

$\Phi\ovalbox{\tt\small REJECT} \mathbb{H}$$\ovalbox{\tt\small REJECT}_{8}5$$F_{p^{3}}$.

$800\mathrm{M}\mathrm{H}\mathrm{z}$まとめ

XTR を用いた暗号の高速実装という観点から, 従来より知られている拡大体の高速な実装手法である OEF (Optimal Extension Field), AOPF (All One Polynomial Field), TypeII AOPF (TypeIIAll One Polynomial Field) の性能を, とくに乗算に必要な計算コストについて比較した.
本論文では,

参考文献[1] A.Menezes, Elliptic Curve Public Key Cryptosystem , Kluw er Academic Publishers, 1993.
$\mathrm{s}$[2] A.Lenstra and E.Verheul, “The XTR Public Key System,” Crypto 2000, LNCS 1880, PP. 1-20, 2000.

[3] D.B.Bailey and C.Paar, “Optimal Extension Fields for Fast Arithmetic in Public-Key Algorithms,”

Proc. Asiacrypt2000, LNCS 1976, pp.248-258, 2000.
[4], and Y.Morikawa, “Finite Extension Field with Modulus of All-One Polynomialand Expression of Its Elements for Fast Arithmetic Operations” The International Conference on
Fundamentals of Electronics, Communications and Computer Sciences, PP.IO-15(R18), 2002.
$\mathrm{Y}.\mathrm{N}\mathrm{o}\mathrm{g}\mathrm{a}\mathrm{m}\mathrm{i},\mathrm{A}.\mathrm{S}\mathrm{a}\mathrm{i}\mathrm{t}\mathrm{o}$[5] S.Shinonaga, Y.Fujii, Y.Nogami, and Y.Morikawa,” TYPE-II All-One Polynomial Field,” Symposiumon Cryptography and Information Security 2004, pp.377 to 382, 2004.
[6] D.Knuth, The Art of Computer Programming, vo1.2, Addison-Wesley, 1981.
[7] I.Blake et[8] S.Lim et$\mathrm{a}1$$\mathrm{a}1$, Elliptic Curves in Cryptography, LNS 265, Cambridge Univ. Press, 1999.

, “XTR Extended to $GF(p^{6m}),$ ”SAC2001, LNCS2259, pp.301-312, 2001.

[9] T.Kobayashi, K.Aoki, and F.Hoshino, “OEF Using a Successive Extension,” Proc. The 2000 Sym-

posium on Cryptography and Information Security, no.B02, 2000, in Jopanese.