拡張二進GCD法のハードウェアによる高速化について

カテゴリ: 部門大会

論文No: MC3-1

グループ名: 【C】平成24年電気学会電子・情報・システム部門大会講演論文集

発行日: 2012/09/05

タイトル(英語): Hardware Acceleration of Modular Inverse Algorithm based Binary GCD Method

著者名: 石田 努(青森大学)

著者名(英語): Tsutomu Ishida(Aomori University)

キーワード: 逆元計算|公開鍵暗号|Inversion|Public key cryptosystem

要約(日本語): RSA暗号や楕円曲線暗号などの公開鍵暗号系では、暗号鍵の生成、メッセージの暗号化、復号化の過程で、大きな素数pを法とする有限体GF(p)上での演算が必要となる。それらの演算のなかで、特に除算、乗法の逆元を求める演算が最もコストが高い。近年、公開鍵暗号の実装が期待されているICカードのような少ない計算資源しか持たない計算システムおいて、その効率的な実装が求められている。本論文では、逆元を計算するアルゴリズム拡張二進GCD法を改良したワードベース法を組込みシステム上に実装しその性能を解析した。さらに、アルゴリズムの一部である多倍長整数の更新処理を、単精度整数をベースとしたハードウェア演算器をFPGA上に実装することで、更新処理の計算負荷を軽減し、逆元計算の処理性能を向上させた。ここでは、多倍長整数更新処理のハードウェア実装法とその性能およびコストについて報告する。

PDFファイルサイズ: 4,110 Kバイト