RNS表現によるMontgomery乗算の基本性能の評価モデル

摘要

RNS表現を用いて公開鍵暗号を実装する研究成果が2000年以降数多く発表されている．RNSとは整数の表現方法のひとつであり，互いに素なn個の整数を基底B = {m_1,…,m_n}として，整数xを基底要素で割った余りn個の組で表す方法である．その応用として公開鍵暗号の実装が注目されている．本稿では公開鍵暗号実装に多く用いられているMontgomery乗算について，通常のバイナリ表現で実装した場合とRNS表現で実装した場合に，両者の処理速度が選択パラメータによってどのように変わるかについて，FPGAやASICなどに具体的な実装をせずに評価するための，比較的単純なモデルを提案する．評価の結果，lazy reductionテクニックと組み合わせ可能な場合に，RNS表現がバイナリ表現より処理速度と消費電力で有利となりうることが分かった．