暗号計算機屋のブログ

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

ICF3-Fのモンゴメリ乗算器が高速である仕組み

ICF3-Fは1999年のICF3FPGAに実装するために設計を、はじめたバージョンです。

MITの研究者が公開鍵暗号の高速化を可能にする乗算器を発明したとか、そういう話題を、たくさん輸入しはじめていると感じたので、僕が海外のパクリではないことを証明するために、僕のICF3-Fの種を明かすことにします。 ただ成功すれば商品化をしようかと考えているので、その辺りは考えてください。

基本原理は1999年のICF3と同じです。ICF3は、この教科書の「14.36 アルゴリズム モンゴメリ乗算」を実装しています。サンプルとしてFreeでダウンロード可能なので確認してみてください。

cacr.uwaterloo.ca

このアルゴリズムは基数(b)がパラメータになっています。1999年のICF3では基数をb=2としています。ICF3-Fでは、これをFPGAの持つ乗算器に合わせます。XilinxのDSP48E1は18x25bitの乗算器なので基数 b=218にします。基数が小さいうちは、小さい演算ブロックをいっぱい並べるような感じでICF3のb=2と同じように実装ができます。 ただしb=2よりも大きい基数を使うと逆数を演算する必要がでてくるため、少し複雑になります。ICF3-FではDSP48E1を1個利用して逆数専用の演算器を用意することになりそうです。またuiの生成も、それなりに複雑になるのでDSP48E1を1個利用してui生成専用の演算器を用意します。RSA 2048bitではCRTを使うことで1024bitのモンゴメリ演算器で演算が可能です。1024bitのモンゴメリ乗算器を24bit間隔で分割して小さいブロックにします。 1ブロックは1個のDSP48E1で構成されます。

ICF3では1024bitのモンゴメリ乗算器を2個装備するので使用するDSP48E1の個数は

( 1 + 1 + (1024÷24 ) ) × 2 = 90個

つまりXilinxFPGA秋葉原秋月電子通商で1個 9,800円 (2018年5月8日現在)で販売されているCmod A7-35Tに実装できるかもしれないということです。

14.36のアルゴリズムの話に戻します。恐らく14.36の2.2の式

A ← ( A + xi・y + ui ・m) / b

Aは約1024bit長なので、この加算キャリーに時間がかかって性能がでないと思った人が多かったのかもしれません。過去のIEEEの論文では、ASICの乗算器と同じような実装で、加算キャリーの問題を回避しているものが多いです。ポイントはAは加算されていきますが途中で参照されるのはAの最下位の桁だけということです。つまり基数b=218であれば、Aの最下位の18bit分だけ計算が完了していればいい。

余談になりますが、1999年のICF3が優秀なのは、この加算キャリーの対策の他、3の式

If A ≧ m then A ← A - m

を、非常に少ないゲート数で実装できたことなどの理由があります。そしてCRTや楕円暗号が1999年の製品で、動作するということです。

モンゴメリ乗算をFPGAに実装する場合、ASICと全く同じ方法では、性能はともかく、リソースの消費が大きくなると、予想されるので、式2.2のWallace Treeで実装する部分をブロックごとに全加算します。するとブロックは24bit幅ですが、18bit×24bitの乗算があるので、ブロックの演算結果は44bitになる。18bit右シフトして、ブロックから上位にはみ出す2bitを上位ブロックに送り、下位にはみ出す18bitを下位に送る。当ブロックでは、上位からはみ出してきた18bitと、下位からはみ出してきた2bitをマージして24bitのレジスタに入れる。次のサイクルで当ブロックの演算結果24bitと加算するとブロック内のAは25bit 1レジスタとなる。

もう一度、説明すると25bit + 18×24bit + 18×24bit = 44bitになり、延々、ブロック内のAは25bitで足りる。

この結果、加算キャリーは上位1ブロックまでで1024bitの加算キャリーを毎サイクル必要とすることはなくなり、並列に高速に演算できるようになるのです。 (2018年5月14日 公開初日の説明が、少し甘かったので修正しましたが、結論に違いはないように思います。 ASICだと自由に設計できるので解がユニークに決まってくるのですが、FPGAだとDSPに合わせる都合、いろいろになって少し戸惑いました。ブロック毎に全加算して楽をしようと思ったところとか。DSP48E1だと17bitシフタがあるからそれを有効に利用するなら218よりも217になるし、変数Aを48bitのCレジスタに割り当てることができれば25bit幅でも良くなる。)

結論

ICF3-Fは、ほぼ1999年に発明されたいた。真に難しいのは演算器を並列動作させることよりも、演算の全工程が可能である実装、暗号プロセッサの発明が重要であること。 FPGAに実装してみたら、かなり効率的に実装できそうなので、ASIC並みの性能が期待できる。FPGAは需要に応じてRSA 4096bit対応させてたり、楕円対応で256bitに変更できるので、FPGAのハードウェアを効率的に運用できるのでASICを超える可能性すらある。ASICではRSA 4096bitと楕円256bitを同時にできないといけないので無駄が生じる。

インターネットは、昨年から常時httpsが必須となりSSL演算処理のコストが増加したが、Cmod A7-35TをUSBに刺すだけで、処理能力が向上するため、性能向上分のWebサーバーのコストが浮く。常時httpsで使われるopensslが非同期処理に対応しているので現在販売されているUSB型のFPGAでいけそう。つまり

浮いたサーバーコスト >  Cmod7-35T を含めた販売価格

であれば商売が可能だということです。FPGAが実際の生活に役に立つあたりも、いいと思っている点です。