修 士 論 文 概 要 書
提出
2008
年2
月 学籍番号3606U120–9 CD
専門分野 情報・ネットワーク専攻
研究指導 マルチメディアシステム
氏 名
谷村 和幸
指 導
教 員
柳澤 政生 印
研 究 題 目
GF (2 n ) 及び GF (P ) における楕円曲線暗号向け スケーラブルモンゴメリ乗算器に関する研究
1 まえがき
通信の安全性を確保する公開鍵暗号の
1
つに楕円曲線暗 号がある．現在最も普及している公開鍵暗号であるRSA
暗 号の鍵長1024bits
の安全性は，楕円曲線暗号の鍵長160bits
の安全性と同等とされている．この鍵長が短い特長から，楕 円曲線暗号のハードウェア実装は，RSA暗号に比べて小面 積かつ高速になる．楕円曲線暗号の中で，最も支配的な演 算は剰余乗算であるが，一般的に剰余乗算にはモンゴメリ 乗算器が用いられる．ただし，暗号強度によって，モンゴメ リ乗算器のオペランドのビット幅は160bits
から256bits
も しくはそれ以上と可変で，スケーラビリティを持ったアー キテクチャが望まれる．加えて，楕円曲線暗号を用いた署名 方式であるEC-DSA
ではGF (P)
とGF (2 n )
の両方で標準 化規定があるため，モンゴメリ乗算器もGF (P )
とGF (2 n )
上の両方の値を扱える必要がある．GF (2 n )
上では正負の区 別をせず，その加算はビット同士の単純な排他的論理和で 定義される．桁上げの考慮の必要がないGF (2 n )
乗算器に 比べてGF (P )
乗算器は遅延時間が長く，暗号プロセッサの 動作周波数を落す要因となっていた．本論文では，GF(2 n )
及びGF (P)
における楕円曲線暗号向けスケーラブル双基 数ユニファイド型モンゴメリ乗算器の提案を目的とする．2 楕円曲線暗号
楕円曲線暗号は楕円曲線上に加法群を定義し，その離散 対数問題を解く困難性を安全性としている．楕円曲線暗号 の離散対数問題の攻撃法は指数時間を要する手法しか構築 されていないが，公開鍵暗号のデファクトスタンダードであ る
RSA
暗号は準指数時間の解法が存在する．その為，160 ビットの鍵長を持つ楕円曲線暗号の暗号強度は1024
ビット 鍵長のRSA
暗号と同等の暗号強度とされている．従って，特に高速化，低消費電力，バンド幅の縮小に向いており，プ ロセッサの処理能力やメモリ容量，面積が制限されている 環境に適している．
3 モンゴメリ乗算
剰余乗算では乗算結果を得た後に，除算を実行して剰余 を取る必要がある．対して，モンゴメリ乗算では剰余を取 りながら乗算の実行が可能である．
図
1
に楕円曲線暗号の階層図を示す．モンゴメリ乗算は 最下層に属するが，これを用いて上位層の計算が行われる ため，楕円曲線暗号の高速化にはモンゴメリ乗算器の高速化が最も効果的である．
Protocols (EC-DSA)
Point multiplication
Point addition and doubling Finite field arithmetic (ADD/SUB/XOR/MAC in GF(2n)/MAC in GF(P)) Layer-4:
Layer-3:
Layer-2:
Layer-1:
図
1:
楕円曲線暗号スキームにおける演算操作の階層.3.1
スケーラブルGF (P )
モンゴメリ乗算アルゴリズム“finely integrated operand scanning method”
によるGF (P )
におけるスケーラブルモンゴメリ乗算アルゴリズ ムを図2
に示す．ここで，nビットの入力はm
個のd
ビッ トのブロックに分割して表現するとする(n = m · d)．大文
字はn
ビットの多倍長の値を表し，小文字はd
ビットの1
ブロックを表す．入力A
はd
ビットごとに区切られている ので，nが変化したときはd
は固定したままm
を増減させ る．また，dは基数のビット幅を意味する．同様に，入力B
をw
ビットごとのe
個に区切り，wビット× d
ビット乗 算器を繰り返し使うことでスケーラビリティを得られる．n が変化したときはm
と同様にe
も増減させる(n = e · w)．
使用する他の主な記号の定義を表
1
に示す． モンゴメリ乗INPUT:A=
(
am−1,· · ·, a1, a0
)
2d INPUT:B=
(
bm−1,· · ·, b1, b0
)
2d INPUT:P=
(
pm−1,· · ·, p1, p0
)
2d(0≤A, B < P) INPUT:q=−P−1 mod 2d
OUTPUT:C=AB2−nmodP C:= 0
fori= 0 tom−1 z:= 0 ti:=
(
c0 +aib0
)
qmod 2d forj= 0 tom−1
S:=cj+aibj+tipj+z if (j6= 0) thencj−1 :=Smod 2d z:=S
/
2d cm−1 :=z
if (C > P) thenC:=C−P
図
2: GF (P)
におけるスケーラブルモンゴメリ乗算アルゴ リズム.算のアルゴリズム
(図 2)
では，ABの乗算結果に法であるP
の倍数を加算し，下位n
ビットを0
にすることで剰余演 算を不要にしている．3.2
スケーラブルGF (2 n )
モンゴメリ乗算アルゴリズムGF (2 n )
におけるスケーラブルモンゴメリ乗算アルゴリ ズムを図3
に示す．GF(2 n )
上でも図2
とほぼ同じ操作で 演算できる．ただし，GF(2 n )
ではGF (P )
と異なり，桁上表
1:
表記法パラメータ 意味
A,B モンゴメリ乗算のオペランド
ai,bi A,Bを構成するi番目のdビット(wビット)のブロック P モンゴメリ乗算の法
q q=P−1 modr S モンゴメリ乗算中の部分積 C モンゴメリ乗算結果 n A,B,及びPのビット長 r 基数(r= 2d) d dビットブロックのビット長 m dビットブロックの数(m=dn/de) w wビットブロックのビット長
e wビットブロックの数(e=dn/we)
げ作業が無いために，最終ステップで減算が必要になる可 能性がない．
INPUT:A(x) =
(
am−1,· · ·, a1, a0
)
xd INPUT:B(x) =
(
bm−1,· · ·, b1, b0
)
xd INPUT:P(x) =
(
pm−1,· · ·, p1, p0
)
xd INPUT:q(x) =P(x)−1 modxd
OUTPUT:C(x) =A(x)B(x)x−nmodP(x) C(x) := 0
fori= 0 tom−1 z(x) := 0 ti(x) :=
[
c0 (x) +ai(x)b0 (x)
]
q(x) modxd forj= 0 tom−1
S(x) :=cj(x) +ai(x)bj(x) +ti(x)pj(x) +z(x) if (j6= 0) thencj−1 (x) :=S(x) modxd z(x) :=S(x)
/
xd cm−1 (x) :=z(x)
図
3: GF (2 n )
におけるスケーラブルモンゴメリ乗算アルゴ リズム.4 提案モンゴメリ乗算器
入力ビット幅の等しい
GF (P )
乗算器とGF (2 n )
乗算器 では，GF(P )
乗算器の遅延時間の方が長くなる．GF(P )
乗算器とGF (2 n )
乗算器の遅延時間差を図4
に示す．図4
は，VHDLを用いて記述したGF (P)
とGF (2 n )
の両乗算 器を，Synopsys
社のDesign Compiler
で論理合成した結果 によるものである．ライブラリにはSTARC90nm
プロセス 用ライブラリ1
を用いている．図4
では，この時のGF (P )
とGF (2 n )
の遅延時間差を削減できれば，両フィールドを 扱うときに分周器などで複数の動作周波数対応させること を考慮する必要がなくなる．d= 64
のときのGF (2 n )
乗算 器による遅延時間とほぼ同じGF (P )
乗算器の遅延時間のd
の値は16
のときである．そこで，GF (P )
乗算器とGF (2 n )
乗算器の遅延時間差削減のために，基数2 16
で4
並列化し たGF (P )
部分と基数2 64
のGF (2 n )
部分を1
つに統合し た乗算アーキテクチャを提案する．小さい基数をGF (P)
に 用いて双基数化するために増加するサイクル数を並列化に より削減する．提案手法の
GF (2 n )
におけるクロックサイクル数見積も りを式(1)
に，GF (P )
におけるクロックサイクル数を式(2)
に表される．式(2)
は図2
の最終ステップで減算が行われ た最悪の場合である．2m 2 + 5m + 3 (1)
m 2
2 + 3m + 6 (2)
1STARC90nmプロセス用ライブラリは東京大学大規模集積システム設計教育研究センターを通し株式会社 半導体理工学研究センターの協力で作成されたものである．
k GF(P) GF(2^n)
2 0.13 0.07 1.857143 4 0.28 0.12 2.333333 8 0.67 0.33 2.030303 16 1.27 0.59 2.152542 32 2.52 0.85 2.964706 64 4.77 1.27 3.755906
0.0 1.0 2.0 3.0 4.0 5.0
0 10 20 30 40 50 60 70
d bits
Delayns
GF(P) GF(2^n)
図
4: GF (P )
乗算器とGF (2 n )
乗算器の遅延時間差.64-bit GF(2n) Multiplier
／64 ／64
GF(P) Multiplier
／16 ／16
／32 GF(P) Multiplier
／16 ／16
／32 GF(P) Multiplier
／16 ／16
／32 GF(P) Multiplier
／16 ／16
／32
／128 MUX
／128 ／128 GF(2n) Product
図
5:
双基数ユニファイド型乗算器.5 論理合成結果
提案するスケーラブル双基数ユニファイド型モンゴメリ乗 算器を含む
ALU
部(積和器，加減算器，排他的論理積器を含
む)，レジスタファイル部，コントローラ部をVerilog-HDL
で記述し，図4
のときと同様に論理合成を行った．表
2
に提案手法と既存手法によるモンゴメリ乗算実行時 間の比較を示す．ただし，表2
中の256
ビットMM
時間は256
ビットモンゴメリ乗算実行時間を意味する．表2
にお いて，提案手法によるGF (2 n )
及びGF (P)
におけるモン ゴメリ乗算の演算実行時間は，既存手法の中で最速であっ た文献[1]
の手法に比べても短い．特にGF (P )
では提案手 法が文献[1]
の手法に比べ1.3
倍高速である．表
2:
モンゴメリ乗算器の性能比較文献 テクノロジ 動作周波数 フィールド 基数 256ビットMM時間
Ours 90 nm CMOS 641M Hz GF(P) 216 0.28µs
Ours 90 nm CMOS 641M Hz GF(2n) 264 86ns [1] 0.13µmCMOS 137.7M Hz GF(P) 264 0.48µs [1] 0.13µmCMOS 510.2M Hz GF(2n) 264 98ns
6 むすび
本論文で提案した
GF (2 n )
及びGF (P )
における楕円曲 線暗号向けスケーラブルモンゴメリ乗算器を用いることに よって，様々なセキュリティレベルの楕円曲線暗号を，よ り高速に暗号化及び復号することが可能となる．今後の課題としては，チップ試作に向け，ゲートレベル での動作検証や配置・配線が挙げられる．
参考文献
[1] A. Satoh and K. Takano, “A Scalable Dual-Field Elliptic Curve Cryptographic Processor,” IEEE Transactions on Computers, Vol.52, No.4, pp.449-460, April 2003.
研究業績
査読付論文誌
