暗号計算機屋のブログ

なにか思いついたことを不定期に更新。

暗号プロセッサ ICF3の日本のオリジナリティ

20年前の暗号プロセッサICF3

ICF3はモンゴメリ乗算というアルゴリズムを実装したLSIです。「なんだ海外のアルゴリズムを実装しただけじゃん」と思った人もいるかもしれません。そういう人のために。

ICF3 https://openicf3.idletime.tokyo/

Wikiモンゴメリ乗算を調べると『特に時間のかかる除算を実質的に行うことなく、乗算・加減算・シフト演算のみで、高速に整数の積の剰余を求めることのできるアルゴリズム化』と書かれています。 LSIに簡単に実装できそうな日本語ですが、、、RSA暗号などの公開鍵暗号はビット長がとても長く、最下位ビットでの桁あふれが、最上位ビットにまで影響するので、分割して演算できません。 このためLSIの2次元平面上にどうやって回路を分割して配置するのかが難しい。

モンゴメリ乗算はPeter Montgomeryさんが1985年に考えたものです。このアルゴリズムには比較して減算をする処理があり、難しい処理ではありませんが、効率的に実装するとなると話は違います。 1998年にC.C. Yangさんによってこの比較減算処理をなくした改良モンゴメリ乗算が論文発表されました。

1999年に製品化されたICF3は、改良型ではなくPeter Montgomeryさんのモンゴメリ乗算を使っています。ゼロに近い追加回路の比較減算回路を発明して実現されています。RSA暗号の演算をするにはモンゴメリ乗算以外の処理も必要です。モンゴメリ乗算以外の処理は、専用演算器では効率的に実装するのが難しいためCPUに任せてしまう場合が多く、暗号プロセッサとしたい場合には、回路規模が大きくなってしまう問題がありました。 ちなみに1999年頃に製品化されていたIBMメインフレームの暗号LSIや、SSLアクセラレータとして数多くの製品に組み込まれたFastMapというLSIには、モンゴメリ乗算は使われていませんでした。そしてFastMapはCPUと専用演算器という構成でした。

ICF3は比較減算処理とモンゴメリ乗算以外の処理を非常にコンパクトな回路に収めることに成功したことが日本のオリジナリティです。 コンパクトなわりに、プログラムによって、いろいろな演算が可能で楕円暗号もなんとか計算できるほどでした。

プログラムによってRSA 2048bitや楕円暗号が可能なことから、現在のIoTデバイス向けの暗号プロセッサとして、再び活躍できそうなのです。 もともとRSA 1024bitを演算するための回路ですが、RSA 2048/4096などの現在のIoTの要求仕様をピッタリ満たしているためICF3は20年前よりも価値が上がっているという不思議を起こしている。

詳しくは

「20年前のLSIがなぜ役に立つのか」

2017年6月5日 6:30AM 追加 1998年のC.C.Yangによる改良型で比較減算処理を不要にしても、結局、大型加算器が残ってしまう場合が多く、それなら、C.C.Yangやめて、大型加算器を、ほんの少し改良して比較減算回路にしたほうがいい。 C.C.Yangは鍵長のビット数より演算器のビット長を2ビット長くする必要があったり、それにともなってモンゴメリ乗算の処理時間が長くなる。b=2nのケースでは2cyc長くなるのだが、これは大型加算器による比較減算1cycと同じ時間だ。C.C.Yangでは鍵長より1bit大きくなるためCPUで例えるなら33bitアーキテクチャとか65bitアーキテクチャになり、実装が煩雑になるので、このことは楕円暗号では改良型にとって厳しい問題となる。

2017年6月5日 7:00AM 追加 RSA暗号のみでいい場合には次の論文が参考になるがCRT(中国人剰余定理)をどうしても使いたくないケースでは役に立つかもしれない。実際にはCRTが許容できないケースは稀だと思うので、実用性としては乏しい。ICF3のようにCRTを使って演算器の2倍の鍵長が演算できるほうが、いろいろな他の演算もできることも含めて、回路規模的にICF3のほうが有利。

A New Modular Exponentiation Architecture for Efficient Design of RSA Cryptosystem - IEEE Journals & Magazine

2017年6月5日 7:30AM 追加 ICF3の比較減算回路はゼロに近い回路で回路規模が小さいということも、そうだがむしろ、比較減算回路のおかげで大型加算器に密着しているレジスタの数を減らし、RSA暗号の演算がやりやすくなっている効果が大きい。

2017年6月5日 7:45AM 追加 モンゴメリ乗算のアルゴリズムを題材にした論文は多い。C.C.Yangのようにアルゴリズム自身に改良を加えた「改良型」もあるが、オリジナルのアルゴリズムの範囲内でパラメータ(基数)を、いろいろ変更したものがある。しかもパラメータによって回路が全く異なるものに変化する。この両者を区別できてない人は、いるかもしれない。ICF3は基数として2を選択しているが、最近の論文では高基数(2の10乗とか2の20乗など)のものが多い。しかし高基数は乗算器のところでブースのアルゴリズムが使えるので理論的な効率は、あがるものの実際に実装してみるとRSA暗号を全体を演算させるとレジスタ制御論理が膨れ上がって実用化が厳しい場合が多い。それでも高性能が要求されるサーバーでは高基数の需要があるかもしれない。回路規模の効率を改善することができても絶対規模を小さくするのが難しいと予想している。したがってIoTやモバイルなどの用途では、そこまで高性能は要求されないので回路規模が小さく、簡素な回路で移植性が高い、ICF3が優位だと考えます。モバイルでは単価が高いので暗号プロセッサの選択は技術以外の要因で決まるかもしれない。またICF3の高い移植性はIoTでは有利だがモバイルでは、それほど有利にはならない可能性がある。ICF3の優位性についてはIoTで考えてほしい。