講演名 2010-09-16
可変ワード長をもつ再構成可能プロセッサによる有限体演算(カスタムプロセッシング)
柴田 裕一郎, 原澤 隆一, 小栗 清,
PDFダウンロードページ PDFダウンロードページへ
抄録(和) 本稿ではFPGAなどのリコンフィギャラブルデバイス上に構成するソフトプロセッサにおいて,楕円曲線暗号システムに用いられる標数2の有限体GF(2^m)の還元処理を高速化する手法について議論する.GF(2^m)における還元アルゴリズムに要する演算回数は,既約多項式の形とプロセッサの演算ワードサイズの関係に左右されるという性質が知られている.そこで本稿ではリコンフィギャラブルデバイスの柔軟性に着目し,与えられた既約多項式に応じてワードサイズを変化させることで還元処理を高速化する手法を提案し,その効果に関する初期検討の結果を示す.標準既約多項式を用いた評価実験の結果,ワードサイズを縮小する方向に変化させた場合でも,標準的なワードサイズと比較して最大約18%の演算ステップ数を削減できることが分かった.また,ワードサイズに10%の拡張を許せば最大で約25%,さらに既約多項式も自由に選択した場合には最大で約61%の演算を削減効果が得られることが明らかになり,本手法の有効性に関して一定の見通しを得ることができた.
抄録(英) This paper discusses a speedup technique of the reduction process for finite fields with characteristic 2 (GF(2^m)), targeting for elliptic curve cryptography executed on soft processors configured with reconfigurable devices such as FPGAs. It is already known that the number of arithmetic operations required for the reduction algorithm for GF(2^m) is largely influenced by the relation between the irreducible polynomial and the word size of the processor. Inspired by this fact and making the best use of the flexibly that reconfigurable devices offer, we propose an approach to speeding up the reduction process by changing the word size according to a given irreducible polynomial and perform some experiments to discuss its effectiveness. The primary evaluation reveal that a processor with the variable word size can reduce the required arithmetic cost by up to 18% compared to standard size processors without increasing the word size. The evaluation results also show that 25% and 61% arithmetic reduction can be achieved by allowing increase in the word size by up to 10% and by selecting favorable irreducible polynomials, respectively, suggesting positive prospects for the effectiveness of the proposed method.
キーワード(和) 既約多項式 / GF(2^m) / 還元アルゴリズム / 可変長ワード / リコンフィギャラブルデバイス
キーワード(英) irreducible polynomial / GF(2^m) / reduction algorithm / variable size word / reconfigurable device
資料番号 RECONF2010-21
発行日

研究会情報
研究会 RECONF
開催期間 2010/9/9(から1日開催)
開催地(和)
開催地(英)
テーマ(和)
テーマ(英)
委員長氏名(和)
委員長氏名(英)
副委員長氏名(和)
副委員長氏名(英)
幹事氏名(和)
幹事氏名(英)
幹事補佐氏名(和)
幹事補佐氏名(英)

講演論文情報詳細
申込み研究会 Reconfigurable Systems (RECONF)
本文の言語 JPN
タイトル(和) 可変ワード長をもつ再構成可能プロセッサによる有限体演算(カスタムプロセッシング)
サブタイトル(和)
タイトル(英) Finite Field Arithmetic on a Reconfigurable Processor with Variable Word Size
サブタイトル(和)
キーワード(1)(和/英) 既約多項式 / irreducible polynomial
キーワード(2)(和/英) GF(2^m) / GF(2^m)
キーワード(3)(和/英) 還元アルゴリズム / reduction algorithm
キーワード(4)(和/英) 可変長ワード / variable size word
キーワード(5)(和/英) リコンフィギャラブルデバイス / reconfigurable device
第 1 著者 氏名(和/英) 柴田 裕一郎 / Yuichiro SHIBATA
第 1 著者 所属(和/英) 長崎大学工学部情報システム工学科
Department of Computer and Information Sciences, Faculty of Engineering, Nagasaki University
第 2 著者 氏名(和/英) 原澤 隆一 / Ryuichi HARASAWA
第 2 著者 所属(和/英) 長崎大学工学部情報システム工学科
Department of Computer and Information Sciences, Faculty of Engineering, Nagasaki University
第 3 著者 氏名(和/英) 小栗 清 / Kiyoshi OGURI
第 3 著者 所属(和/英) 長崎大学工学部情報システム工学科
Department of Computer and Information Sciences, Faculty of Engineering, Nagasaki University
発表年月日 2010-09-16
資料番号 RECONF2010-21
巻番号(vol) vol.110
号番号(no) 204
ページ範囲 pp.-
ページ数 6
発行日