Home

このページは、SnakeCubeプロジェクトの開始から2019年9月までの記録を当時のまま残したもの



このICF3-FはFPGAに実装されるSSLアクセラレータです。サーバーの性能アップを売る商品です。 FPGAなので秘密鍵を守る機能は国家レベルの機関には通用しないと思われます。


1999年のICF3はRSA暗号の性能が世界一でしたがSSLアクセラレータとしても利用することが可能でした。 そのICF3をFPGAで実装しSSLアクセラレータとして特化したものをICF3-Fとして2018年4月25日フォークさせます。 フォークさせたICF3-Fは商用化を目指そうかと思うのでオープンソースではなくクローズドにしようと思います。

ブログのほうに、もう少し詳しいことを書いています。
「FPGAを使ったSSLアクセラレータのICF3-F」

一人で、あれこれ、やっているせいで、更新わすれてました。もう一つ詳しくかいてあるブログあります。
「ICF3-Fのモンゴメリ乗算器が高速である仕組み 」

2018年7月2日追加 「ICF3-Fのモンゴメリ乗算器が高速である仕組み 」 の設計図のRev0が完成したので公開します。 クローズドで公開する理由ですが、過去に不正アクセスで侵入された経験があり、 産業スパイによって盗まれていないことが保証できない。 産業スパイが海外のメーカーに持って行って逆輸入したり、特許を取得してしまうと、非常に問題になるため、 公開することにしました。

最後にふたつの24bitを加算して25bitの累積加算結果を計算する加算器と 1024bitの大型加算器を兼用することで性能向上と、実装容易性が増している。 実際に実装する段階で追加修正は、あると思います。

2018年7月2日 17:30追加 Rev0.1にバージョンアップします。 公開してすぐにバージョンアップとなりましたが、大型加算器との兼用をやめて、 簡潔にしただけなので、大きな影響はないと思われます。 これによってゲート数は増加しますがFPGAではターゲットデバイスに入りきれば、 煩雑な実装をする必要はなく、性能的にも若干優れるので、大型加算器の兼用しないバージョンを 優先させていきます。 DSP48E1のCの入力に接続される24bit加算器が性能を上げるのに役に立っています。


2018年7月4日 3:30追加 Rev0.2にバージョンアップします。 DSP48E1の内部の変更なのでバージョンアップをする必要は、なかったかもしれません。 これよりも高周波数を狙うバージョンも、今後、検討します。


2018年7月13日追加 17bit逆数演算器をバージョンアップ。
今回はシミュレーション結果のみ、演算終了後、自動的に止まる論理を追加しています。 (ちなみにRev0.2はバグっていて動かなかった)

画像をクリックすると拡大表示されます


2018年7月16日 2:00追加 Rev0.3にバージョンアップしました。
まだ公開するには、早い感じですが、産業スパイ対策なので。 DSP48E1のB1レジスタを有効にしたままBCIN-BCOUTをスルーで使うことができないことが判明したので BCIN-BCOUTを外部論理として外に出した。逆数演算器は、ページからはみだしたので、図面からなくなっています。 uを全ブロックに転送するため1cycを使っているが先頭2ブロックは0cycで転送してuの計算が1cyc早くなるようにした。 このためブロック1は1cyc遅れるブロック2と整合性をとりつつブロック0に合わせることが必要になり複雑になっている。 しかし4サイクルピッチだったのが3サイクルピッチで演算ができる。


2018年8月7日追加 Rev0.3をXilinxのシミュレータでの動作が検証できました。
7月16日に公開したRev0.3は多少バグがありましたが、根本的には変わっていません。 RSA 4096bitなどの鍵長が長い場合、XilinxのFPGAでは隣接するDSPが中央分離帯で分断されてしまう 場合がありますが、4サイクルから3サイクルに性能を向上させた技術を用いれば、DSPが離れていても 動作が可能です。


2018年8月8日 2:00追加 Rev0.4にバージョンアップしました。
XilinxのxsimでUNISIMライブラリのDSP48E1を使ってシミュレーションによる検証をしました。 RSAの演算を一通りした場合の演算の期待値をすべて作成し、シミュレーション結果とコンペアしています。 フリーのverilogシミュレータicarusでも検証しています。 RSAの乱数によるテストを行うとicarusのほうが約7倍高速でした。 ただし高速なUNIFASTライブラリのDSP48E1を使用しています。


2018年8月17日追加 Vivadoで実装してみた。
はじめてなので全く保証できないが演算器の最大周波数からRSA 2048の性能を算出した。 2011年のIEEE(広島大)論文ではDSP1個で277ms(447MHz)。これはDSP90個で3.2ms(125MHz)。 90個で約86倍。かなり高効率に並列化された感じ。実際に製品化できることを期待! 図はXilinxのFPGA、DSP48E1が90個並んでいる

画像をクリックすると拡大表示されます


2018年9月11日追加 暗号プロセッサのブロック図
だいたい、できたので公開してみます。見た目、1999年のICF3とあまり変わらない感じですが、 XilinxのFPGAに合わせて修正されています。 従来論理をそのまま実装するより、面積効率がいい実装になるように修正されています。 このため従来論理よりは不便になっているところがあります。 例えばAレジスタはデータレジスタから入力できなくなったり、データレジスタがデュアルポートから シングルポートになったりしています。反対に、32bitコードだったのが64bitコードになったことで 並列に動作させる命令が増えるケースもあります。また2個あるモンゴメリ乗算器を、 近い乗算器、遠い乗算器の2種類にして、遠い演算器はDレジスタから取り込むようになってます。 これはXilinx FPGAのカラムアーキテクチャに適するように修正されました。

画像をクリックすると拡大表示されます


2018年9月28日追加 ICF3-Fで使われる分割加算の証明をブログに公開
ビット長の大きな加算はキャリーによる遅延が大きくなるため、分割して並列に加算してキャリーによる遅延を低減し高速化する方法の証明です。キャリーの問題を冗長性を持ったレジスタを使って解決していますが、その計算方法が正しいことを証明しています。 これです。「モンゴメリ乗算の累積加算における分割加算の証明」


2019年7月28日追加 ICF3-Fの状況
このモンゴメリ乗算器の付いた暗号プロセッサにサーバーPCからの演算データを送受信するための回路を開発中。

2019年8月19日追加 Rev0.4は1ループ 3サイクルでしたが、 さらなる性能向上のため、1ループ 2サイクルにすることを検討。 乗数のシフトレジスタをDSPの外に出すため面積が増える。 このためICF3-Fの最初のバージョンでは1ループ 3サイクルになるかもしれません。


2019年8月25日追加(同日22:00 修正) 用途に応じた性能特性を考え複数のモデル(型番)を定義し、現段階での評価を行った。
型番の形式
1ループで17bitのモンゴメリ乗算を行う。1ループのサイクル数、1ループで処理するスレッド数などで分類する。

ICF3-F-[1ループのサイクル数][スレッド数][バージョン][特長を示す文字]

1ループのサイクル数

1文字の数字、1~9の数字

スレッド数

CPUのスレッドとは異なり、A×B mod Nの1つを演算するのか、A×B mod NとC×D mod Nの2つを演算するのかの違い。 1つ場合はS(シングル・スレッド)、2の場合はD(デュアル・スレッド)。DはデフォルトではA×B mod NとA×A mod Nを示す。A×B mod NとC×D mod Nが可能なものは特長を示す文字としてTTが追加される。

バージョン

1文字の数字、0~9の数

特長を示す文字

B2などの文字列。文字数に制限はない。ない場合は書かない。例えばDSPブロック間の転送のサイクル数などを示す。TTはTrue Threadの意味でA×B mod NとC×D mod Nが可能であることを示す。



以下、モデルの説明ですが、実際に実装してみると実装できないということはあり得ます。

ICF3-F-3S0

2018年8月に試作。uのブロッドキャストの中継の仕組みに特長があり、良くできている。

ICF3-F-2S0

2019年8月に検討。3S0よりクリティカルパスが長くなってしまうため、トータルの性能では、あまり変らない。 2S0は少しでも3S0の性能改善させる目的に向いている。カラムを横断した配置を重視するなら、これ。 3S0でも、カラムを横断した配置の性能は高く、2S0と同程度か、若干落ちる程度。

ICF3-F-4D0

2019年8月に検討。高周波数で高性能だが性能がRSAに偏る。 シフトレジスタをDSPの外部に出したので面積が大きくなる。カラムを横断した配置が厳しい。

ICF3-F-6D0

2019年8月に検討。高周波数で高性能だが性能がRSAに偏る。 シフトレジスタをDSPに入れたので面積が小さい。カラムを横断した配置を容易にする設計ができる余地が4D0よりも、やりやすいと思われる。

ICF3-F-3S1B

2019年8月に検討。シフトレジスタをファブリックで実装。3S0との違いは、あまりない。

ICF3-F-3S1C

2019年8月に検討。3S0は、シフトレジスタの初期設定をDレジスタに直接書いているが、AレジスタからPレジスタを経由させてDレジスタに。A×B mod Nの初回ループを実行するのが数サイクル遅れるが全モデル中最も面積が小さい。6D0も3S1C並みに小さい。


2019年8月27日追加 ICF3-F-5D0のモデルを追加

2019年9月3日追加 「RSA Doublerと命名」
RSA暗号はCRT(中国人剰余定理)のアルゴリズムによって専用演算器のビット幅の2倍の鍵長を計算できる。 つまり1024bitの演算器では2048bitのRSA暗号が計算できる。2030年にはRSA 2048bitよりも鍵長を長くする方向になっている。 演算器のビット幅を2倍にして対応してもいいのですが256bitの楕円暗号を計算するには無駄が多くなる。 そこで演算器のビット幅の2倍のモンゴメリ乗算を可能にするアーキテクチャを考える。 ICF3-Fでは、現在、5サイクル2スレッドの設計をしている。 1スレッド目で前半を計算、2スレッド目で後半を計算する。 もともとループ毎に最下位ビットの値を元にuを計算して ブロッドキャストする部分がディレイのクリティカルパスになるから2スレッドにして高速化をしている。 1スレッド目で前半を計算、2スレッド目で後半を計算するなんて、できるのか?という疑問があると思う。 僕は、今のところ実装できるように思っています。 そこで演算器のビット幅の2倍のモンゴメリ乗算を可能にする、このアーキテクチャを「RSA Doubler」と命名しておくことに。 従来の2倍の鍵長のRSA暗号を計算できる技術の名前としては、ぴったりかと。^^)
そういえばRAM Doublerというのが、昔、ありましたよね。Macintoshのメモリ・ユーティリティで、 実装されている物理メモリーを独自の技術によって、見かけ上、2倍の容量にするやつ。 仮想記憶ではなくて物理メモリを見せか上、倍の容量にする。



逆数演算の知財

RSA暗号の高速化に必要な逆数演算についてです。 詳細は、こちらのページ