Multiprecision Integer Arithmetic Algorithms for Public Key Encryption

IPSJ

Bibliographic Information

Other Title
  • 公開鍵暗号のための多倍長整数計算アルゴリズム

Search this article

Description

公開鍵暗号方式は、500~2000ビット程度の長さの整数計算を利用すると、実際上解読不可能な程度の難しさとなる。しかし、そのように長い整数の計算には、秘密情報を知っての暗号化/復号化にも、かなりの計算時間がかかる。特に、多倍長整数乗算の速度が全体の性能を決めることになるため、その高速化は重要である。多倍長整数乗算のアルゴリズムとして、単純な二乗時間のアルゴリズム、そのKaratsubaの方法による高速化、高速フーリエ変換による対数時間のアルゴリズム等が知られており、計算量のオーダーとしては後者ほど勝れているが、公開鍵暗号方式に必要な程度の長さの場合には、その差は微妙なものとなる。そこで、最近の一般的なCPU上での実際のインプリメンテーションに関して、各種アルゴリズムの速度を比較、検討してみる。最近のCPUでは、レジスタ間での加算や乗算は高速であり、条件判断やデータの転送のほうに多くの時間をとられていることに注意する必要がある。最近のCPUでは、各実行サイクルで、浮動小数点加算、浮動小数点乗算、を同時に実行できる。これに比べて整数の乗算は極めて遅いため、多倍長のデータは、適当なビット数に区切って複数の浮動小数点数にわけ、浮動小数点演算回路を利用して計算するのが効率的である。演算と並行して、さらに、浮動小数点のロードも各サイクルにl回実行できる。しかし、浮動小数点のストアに関しては、演算とは並行できるものの、ロードとは並行せずに2サイクルに1回しか行えないのが普通である。さらに多重度の大きなCPUでも、この演算とロード/ストアの性能の比率はほぼ同様である。高速化のためにはレジスタを活用し、ロード/ストアを減らすことが重要である。公開鍵暗号のための多倍長整数計算ではそれほど大きなデータ量を扱わないので、すべてのデータは一次キャッシュに入ると考えてよい。本稿では、こうした要因を考慮しつつ、公開鍵暗号のための多倍長整数計算アルゴリズムの高速なインプリメンテーションについて、クロック速度99MHz理論最大性能198MFLOPSのHP9000/755上で、640ビット、2000ビットの二つの桁数について、各種方法を比較考察する。一つの浮動小数点レジスタには20ビットを格納することとする。

Journal

Details 詳細情報について

Report a problem

Back to top