2018-09-26

モンゴメリ乗算の累積加算における分割加算の証明

はじめに

今年の4月にFPGAをはじめたときにFPGAにDSP(乗算器)が多数あることを知った。これでモンゴメリ乗算が高速化できるわけだがアルゴリズムをそのまま実装するとビット長の大きな累積加算が、ビット長とともに周波数が下がり性能がでない。そこで分割して加算しても、正しい加算結果になるような方法を考えた。これを使ったSSL アクセラレータ ICF3-F(商用版)の実装を急いでいるところだが、証明もしておかないと、いけないかと思って、急いで公開することにしました。産業スパイによる海賊版を抑止する目的です。ちなみに他にも応用ができる方法ではないかと思います。この証明にコメントしたい方が、いらしゃるのかわかりませんが、もしあれば公開日(2018年9月26日)の２日後、28日の午後12時からでお願いします。とりあえず、その記録は残すようにします。

問題

非負の整数の変数Aを2進数表現すると、最下位ビットからrビットづつ区切ってs個のブロックに分割して表現できる。

$\displaystyle A = \sum_{k = 0}^{s-1} a_k \cdot 2^{r k}$

$a_k$ がrビットの場合はAはr×sビットの数を表現可能だが、 $a_k$ が(r+1)ビットあってもr×sビットの数を表現できる。最上位ビットを $e_k$ 、それ以外を $f_k$ とすると $a_k = e_k \cdot 2^r + f_k$ になるが

$\displaystyle A = \sum_{k = 0}^{s-1} e_k \cdot 2^{r (k+1)} + \sum_{k = 0}^{s-1} f_k \cdot 2^{r k}$

として全加算してやればAは冗長性がなくなりr×s+2個のビットの数になる。このような冗長性をもったAを考える。

$A = (A + t \cdot B + u \cdot C ) \div 2^{n}$ --- (1)

$r \geqq n + 2$ --- (2)

t,uはnビットの数。B、Cはr×s-2ビットの数。 $\displaystyle B = \sum_{k = 0}^{s-1} b_k \cdot 2^{r k}$ 、 $\displaystyle C = \sum_{k = 0}^{s-1} c_k \cdot 2^{r k}$ と表す。

式(1)の右辺を計算した結果、任意のA、B、C、t、uにおいて、同じ冗長性、すなわち $a_k$ が(r+1)ビットある左辺Aに正しく格納できることを証明せよ。

証明

式(1)右辺のカッコ内は

$A + t \cdot B + u \cdot C$

$\displaystyle = \sum_{k = 0}^{s-1} a_k \cdot 2^{r k} + t \times \sum_{k = 0}^{s-1} b_k \cdot 2^{r k} + u \times \sum_{k = 0}^{s-1} c_k \cdot 2^{r k}$

$\displaystyle = \sum_{k = 0}^{s-1} a_k \cdot 2^{r k} + \sum_{k = 0}^{s-1} t \cdot b_k \cdot 2^{r k} + \sum_{k = 0}^{s-1} u \cdot c_k \cdot 2^{r k}$

$\displaystyle = \sum_{k = 0}^{s-1} ( a_k \cdot 2^{r k} + t \cdot b_k \cdot 2^{r k} + u \cdot c_k \cdot 2^{r k} )$

$\displaystyle = \sum_{k = 0}^{s-1} ( a_k + t \cdot b_k + u \cdot c_k ) \cdot 2^{r k}$

ここで $p_k = a_k + t \cdot b_k + u \cdot c_k$ とする。t,uがnビットであるから $p_k$ は最大でもr+n+2ビット。 $p_k$ の最上位ビットから2bitを $px_k$ 、最上位ビットから2ビット、最下位ビットからnビットを除いたrビットを $py_k$ 、最下位ビットからnビットを $pz_k$ とする。

$p_k = px_k \cdot 2^{r+n} + py_k \cdot 2^{n} + pz_k (0 \leqq k \leqq s-1)$ --- (3)

(1)の右辺は

$\displaystyle \sum_{k = 0}^{s-1} p_k \cdot 2^{r k} \div 2^{n}$

(3)より

$\displaystyle = \sum_{k = 0}^{s-1} ( px_k \cdot 2^{r+n} + py_k \cdot 2^{n} + pz_k ) \cdot 2^{r k} \div 2^{n}$

k=0の項をシグマの外に出して整数にすると

$\displaystyle = px_0 \cdot 2^{r} + py_0 + \sum_{k = 1}^{s-1} ( px_k \cdot 2^{r+n} + py_k \cdot 2^{n} + pz_k ) \cdot 2^{r k} \div 2^{n}$

$\displaystyle = px_0 \cdot 2^{r} + py_0 + \sum_{k = 1}^{s-1} ( px_k \cdot 2^{r} + py_k ) \cdot 2^{r k} + \sum_{k = 1}^{s-1} pz_k \cdot 2^{r k - n}$

$\displaystyle = px_0 \cdot 2^{r} + py_0 + \sum_{k = 1}^{s-1} ( px_k \cdot 2^{r} + py_k ) \cdot 2^{r k} + \sum_{k = 1}^{s-1} pz_k \cdot 2^{r(k-1) + r-n}$

$\displaystyle = py_0 + pz_1 \cdot 2^{r-n} + \sum_{k = 1}^{s-2} ( px_{k-1} + py_k + pz_{k+1} \cdot 2^{r-n} ) \cdot 2^{r k} + ( px_{s-2} + py_{s-1} ) \cdot 2^{r (s-1)} + px_{s-1} \cdot 2^{r s}$

ただしB、Cがr+n-2ビットなので必ず $px_{s-1} =0$ 。

$\displaystyle = py_0 + pz_1 \cdot 2^{r-n} + \sum_{k = 1}^{s-2} ( px_{k-1} + py_k + pz_{k+1} \cdot 2^{r-n} ) \cdot 2^{r k} + ( px_{s-2} + py_{s-1} ) \cdot 2^{r (s-1)}$

ここで式(2)の条件からr-nは2以上。 $w_k = px_{k-1} + pz_{k+1} \cdot 2^{r-n} (1 \leqq k \leqq s-2)$ とすると $w_k$ はrビットの記憶素子を持つ1つの変数としてまとめられる。

$\displaystyle = py_0 + pz_1 \cdot 2^{r-n} + \sum_{k = 1}^{s-2} ( py_k + w_k ) \cdot 2^{r k} + ( px_{s-2} + py_{s-1} ) \cdot 2^{r (s-1)}$

これは(1)左辺のAとして次にようになる。

$\displaystyle A = \sum_{k = 0}^{s-1} a_k \cdot 2^{r k}$

$a_k = \left\{ \begin{array}{} py_0 + pz_1 \cdot 2^{r-n} ( k = 0) \\ py_k + w_k ( 1 \leqq k \leqq s-2 ) \\ ( px_{s-2} + py_{s-1} ) ( k = s - 1) \end{array} \right.$

$py_k$ 、 $w_k$ ともにrビットの数なので加算してもr+1ビットの数である。k=0、k=s-1も同様にr+1ビット。式(1)の右辺を計算した結果、同じ冗長性、すなわち $a_k$ が(r+1)ビットある左辺Aに正しく格納できる。

補足

実際の実装では最後に、全加算を行って冗長性をなくしてr×sビットのレジスタに格納します。このとき桁あふれが発生する可能性がありますが、一般のCPUのレジスタと同じで桁あふれはアルゴリズム側の責任。モンゴメリ乗算では最終的な計算結果はCの2倍以下になるので全加算後、r×sビットのレジスタに必ず格納できます。計算過程においても、上記証明によって、桁あふれすることなく計算できていることがわかります。この問題では積和の数が２個の場合ですがn個にした証明など一般化できるように思います。いづれまた。

2018-09-19

FPGAで加算器を共有して面積を小さくする

このページで説明する加算器を共有して面積を小さくするテクニックは勝手に使っていいのかという質問がありました。勝手に使っていただいて大丈夫です。

はじめに

XilinxのFPGA(Artix-7)でDSPを使用せずにLUTで加算器を作る場合、加算器の入力を構成するLUTに余裕があり、共有するためのセレクタを詰め込んでも面積は増えない。そのテクニックが、現在、開発中のICF3-Fの制御部で使うことができそうで、効果がありそう。

論理合成ツール

XilinxのVivado 2018.2です。評価ボード Artyの(Artix-7 XC7A35T-L1CSG324I)の設定で合成しています。合成オプションは、面積、最優先(Flow_AreaOptimaized_high)です。

対象となる論理

ICF3-Fは商用だがブロック図(2018年9月11日追加)を公開していいる。図の左側にループ制御用の16bitレジスタI,Jがある。その部分の論理について加算器を共有させて面積を小さくする。レジスタI,Jは即値(n)を代入すること、分岐命令(BI命令、BJ命令)のときには値を-1にする論理です。 BI命令とBJ命令は同時に来ることはないので-1をする加算器の共用化が可能です。

対象となるverilogコード

module subij(
    input CLK,
    input CEI,
    input CEJ,
    input BI,
    input BJ,
    input [15:0] n,
    output INOR,
    output JNOR);

    always @(posedge CLK) begin
        I<= BI ? I-1 : CEI ? n : I;
        J<= BJ ? J-1 : CEJ ? n : J;
    end

    assign INOR = ~|I;
    assign JNOR = ~|J;

Iレジスタにnを代入するにはCEIを1にします。分岐命令のBI命令の場合はCEIとBIが1になります。Jレジスタも同様。このコードでは、論理合成ツールはBIとBJが同時にくる可能性のために加算器を共用できません。少しコードを変更して加算器が共用できるコードに変更します。

module subij(
    input CLK,
    input CEI,
    input CEJ,
    input BI,
    input BJ,
    input [15:0] n,
    output INOR,
    output JNOR);

    always @(posedge CLK) begin
        I<= CEI ? (BI ? I-1 : n) : I;
        J<= CEJ ? (BI ? n : J-1) : J;
    end

    assign INOR = ~|I;
    assign JNOR = ~|J;

これ以外のコードも試しましたが、シミュレーションすると誤った結果となってしまいました。

論理合成ツールによる結果

38LUT 32FFで約10スライスの面積。加算器の共有ができていません。 f:id:icf:20180919033431p:plain

人間による結果

22LUT 32FFで8スライスの面積。まだLUTが8スライス内に入りそうです。加算器を共有する論理をLUT,CARRY4,FFで作りスライスの場所を固定しました。固定したものはオレンジ色になるようです。 f:id:icf:20180919033804p:plain

まとめ

実際のケースで加算器を共有する方法をやってみました。加算器を共有化を確実にするにはLUT、CARRY4、FFをスライスに固定するなど少々、手間がかかりますが面積を小さくすることはできるようです。これ、ICF3-Fの1032bitの大型加算器でも使えるので、かなり効果があるかも。

2018-09-15

Xilinxの論理合成ツールと勝負してみた

はじめに

論理合成ツールは、これまでほとんど使ったことがなく、論理合成ツールの性能がどのくらいなのか、ちょっとだけ試してみた。もちろん人間が作った論理と比較して、人間が勝ったから、ブログに投稿しているわけで、この初戦の結果だけで判断しないようにお願いします。

論理合成ツール

XilinxのVivado 2018.2です。評価ボード Artyの(Artix-7 XC7A35T-L1CSG324I)の設定で合成しています。合成オプションは、面積、最優先(Flow_AreaOptimaized_high)です。

論理合成対象

次のverilogのコード。使用するリソース、面積が最小となるように論理を作ります。

module s2add(
    input SW,
    input [3:0] A,
    input [3:0] B,
    input [3:0] C,
    input [3:0] D,
    output [3:0] O);
    assign O = SW ? A+B : C+D ; 
endmodule

論理合成ツールの結果

7 LUTです。面積的にはスライス２個分といったところでしょうか。 f:id:icf:20180915051140p:plain

人間の結果

4 LUTです。面積的にスライス 1個に収まっています。(シミュレーションで正しい答えになることは確認しています) f:id:icf:20180915051255p:plain

まとめ

論理合成ツールに人間が勝ちました。ちょっと試してみただけの結果なので、これだけで判断しないようにお願いします。

追記

4bitの加算では人間が勝ちましたが8bitにすると論理合成ツールも人間と同じ結果を生成しました。

追記2

現在、開発中のICF3-Fはループ制御用に2本の16bitレジスタがあります。同時にデクリメントすることはないので、この論理合成対象のように加算器を共有できます。しかしならが共有できるようなverilogの記述をしても、うまく共有されず、論理合成ツールのほうが大きな面積となりました。人間だと8スライスに収まりますが、論理合成ツールでは10スライスくらいになります。 verilogの記述を操作して共有できるようなコードを探すとなると、時間がかかるし、論理を追加していくうちに、再び共有されなくなる心配も考えるなら人間がやってしまったほうがいいように思いました。人間がやるためにはLUTのデータを自分で作成する必要がありますが、FORTHライクな言語を自作しました。様々なLUTデータを簡単に作れます。

結局、最初の結論の通り、「論理合成対象のコードは、良くあるケースのように思うので、この結果は使えるのではと思います。」であります。

　追記3

追記２の話を詳しくブログにしました。「FPGAで加算器を共有して面積を小さくする」

2018-09-11

論理設計はどうやって学んだのか？

はじめに

僕の経歴を見ると早稲田の電気工学科を1992年3月に卒業し、同大学の大学院の計算機工学科を1994年3月に修士を卒業。日立の中央研究所の超高速プロセッサ部に1994年4月に入社と、CPUとか暗号プロセッサとかを開発するのに最適な経歴です。ところが奇跡的に論理設計を教えてもらえることが、全くなかったという話です。普段は、この経歴、便利だったりもするのですが、不都合なこともあるので、本当の話をすることにしました。興味がない人は、読まないほうがいい内容です。

子供の頃

中学、高校と大阪に住んでいました。小学校５年のときにはCASIOのプログラム電卓 FX-502Pで良く遊んでましたが、中学１年生ときはナイコン族でした。パソコンを持っていなかった。雑誌には紙に印刷されたキーボードの付録があって、それで練習するという時代。中学２年生のときにSHARP MZ-2000を買ってもらった。 CPUはZ80でしたがBASICでプログラムを書いても、とても遅くマシン語に興味を持ったのです。なんとか高速化できないかOSを調べてBREAKキーをポーリングしているサブルーチンを発見し、そこに1バイトのC9 ( RETURN )をパッチしてみた。1分かかった計算が、58秒になったことが、うれしかった。その後、WICSという整数型BASICコンパイラを買ってもらった。うちが計算機の英才教育していたのかというと、家族は、むしろ文系なみにコンピュータを知らない。中学２年生の普通の子供は、みなゲームに夢中だったが、科学にとても興味を持った変わった子供だったと思う。

大阪の日本橋は東京の秋葉原みたいな電気街なのだが、当時の僕は、デジットというジャンクパーツ屋が気に入ったようで、行ってみて、できそこないの150円のジョイスティックとか買って帰ることが多かった。古いテレビとかを分解した部品が売られていて、トグル式のスイッチを買って帰ったことがあった。それには目的があって加算器を作ることだった。スイッチは１ボタンで混線しないスイッチが多数あるので配線のみの加算器を作ることができた。すでにゲートディレイゼロの超高速加算器を発明していたのだ。(爆笑)

大学時代

パソコンを自分で作ってみたいという思いから電気工学科に入った。サークルはコンピュータサークルには入らないように親に言われていたので、鳥人間コンテストとかやっているサークルに入った。１年の頃は、ファインマンの電磁気学の本を読んでまじめに勉強した。夏休みに大阪に帰省したときに、自宅が大阪大学に近かったのでファインマンの光、熱、波動の本を買いにいったら、早稲田の大学生協のカードを見せても１割引きしてもらえなかった。当時の電気工学科で論理設計を教えてもらえる先生は１人で門倉先生でした。しかし門倉先生の授業は、ほとんどサボりました。なぜか？鳥人間コンテストの人力飛行機のプロペラ作りを、ほぼ１人でやっていて、全く余裕がなかった。門倉先生の授業は論理回路の授業というよりは歴史的なマシンLGP-30の説明で、あんまり役に立ちそうにないと思ったのは、そうですが、それよりもプロペラ作りが忙しく、役に立つとか、考える前に、サボるしかなかった。

研究室時代(大学院)

現在、IEEEの会長で超有名な笠原先生の研究室に入りました。コンピュータのハードウェアの研究室に入りたかったのだが、門倉先生は引退してしまって、コンパイラの研究室に入ったのです。わかりやすくいうとソフトウェアの研究室だった。つまり論理設計のカケラもないところでした。

日立中央研究所超高速プロセッサ部

CPUを研究する部署でしたが、僕が入った次の年には、名前が変わって別の部署になってます。日立の大型コンピュータのCPUのパイプラインのシミュレーションをする仕事をしましたが、中の論理をのぞかせてもらったわけではありません。 CISCの転送命令が、ちゃんと性能が出ているかを確認する仕事で、東京女子大卒のおねーさんと２人で、さびしくやってました。おねーさんのほうは基本命令の性能確認だったと思います。

日立メインフレーム開発部時代

東大卒の人がいっぱいの部署でしたが、僕は仲間に入れてもらえず、壁すらない隣の部屋で大型コンピュータのCPUを開発していたようですが、僕だけ隔離された環境で仕事してました。ちなみに隣の部屋のCPU開発部には、笠原研の同期がいたのです。卒業後、その同期と話しをしたことはないですから、この会社の隔離システムが、いかにすごいか、わかるのではないでしょうか。話すことはいっぱいあるのですが、ここでは全部省略して、要するに、全然、ここまで論理設計を勉強したことはなかった。

ところが、このことは会社の経営者にとっては好都合で、僕にいきなり暗号LSIを設計するように業務命令が出た。僕が開発すれば社内外の左に払う必要がないし、僕が潰れてもおいしいのだ。

そして僕に才能があったおかげで、システム開発研究所からFAXで送られてきたモンゴメリ乗算のアルゴリズムを元に、いきなり開発して世界一の性能の暗号LSIを開発してしまった。論理設計は、ANDとかORとか、すごく単純なものの組み合わせだけなので回路図を読むだけなら、ほとんど勉強しなくても読める。勘がいい人間なら、いきなりできることもある。

いいたかったこと

オープンソースハードウェアとして1999年世界一だった暗号LSIの論理図面を公開していますが、僕に先生は、いなくて、僕１人で設計している。僕１人で公開できるのは、そういうことだからなのです。

2018-09-03

ICF3-Fの技術と今後について

2018年9月5日補足1、補足2を追加

2018年9月4日修正: ICF3-Fは鍵長が2倍になると処理時間が2倍強と書きましたが4倍強の間違いでした。すいません。それでも内容に大きな影響はないと思います。

背景

結論を先に言うとICF3をFPGAでSSL アクセラレータにしたICF3-Fは鍵長の長いRSA暗号が得意なのだが常時httpsのサーバー負荷増大は楕円暗号(ECDSA証明書)に移行しても対策できる。 ICF3-Fは、それほど売れないということ。しかし、その技術は楕円暗号が先に危殆化した場合など必要。ですので今後とも、よろしくお願いします。

事の発端。数か月前にFPGAを使い始めた。LSIの設計経験がありながら今頃になったのは暗号LSIでは秘密鍵が漏洩しないことが重要であるためFPGAでは困難だと考えていたから。使い始めてみるとFPGAにはDSP(乗算器モジュール)が多数あることを知った。SSLの性能はDSPの占める割合が支配的であり、DSPはASICに近い性能がでるはずなので、FPGA全体として ASICを凌ぐコスパが実現されそうだという予感がした。乗算器の数と性能では、はるかにGPUが上だが、１つのSSLを計算するにもGPU全体を動作させなければならないなど、GPUではあまりうまくないと思われた。

設計開始

SSLで使われるRSA暗号や楕円暗号などの公開鍵暗号はハードウェアが苦手な除算を乗算のような演算に変換するモンゴメリ乗算を利用する場合が多い。モンゴメリ乗算のアルゴリズムは基数をパラメータとして持っているためFPGAの乗算器のサイズに最適な基数を選択できる。ただし1024ビット以上のビット幅の大きい加算のキャリーが性能の足かせになる。 ASICではキャリーセーブアダーによる方法で回避するのだがDSPの乗算器は全加算をしてしまうため、気づけなかった人が多かったのかもしれない。 1024bitをDSPに合わせてブロックに分割する。ブロック毎に全加算をする方法では~~ブロックの合計を保存するレジスタが加算を繰り返すうちに溢れてしまう問題を解決することが必要だった。~~ ブロックに、どういう冗長性を持たせれば加算を繰り返しても正しい答えになるのか考える必要があった。 (発明なのかな? そのときのブログ)

シミュレーションで正しい結果に

f:id:icf:20180903134157p:plain 2018年8月初旬、4サイクルピッチで正しい結果が出た直後、失明しかかる事故が発生し大騒ぎになった。以前、左耳がほぼ完全に聴こえなくなった。このとき医者に3分の一くらい治らないこともあると言われたが、６～7割程度回復した。日常の会話では、ほとんど問題ないが音楽鑑賞には全く耐えない。失明の話に戻るが、治らないこともあるかと、数日、慌てふためいた。その後、ほとんど回復したが、元々、既に動体視力が劣化していた。並みのエンジニア以下の思考力に低下したが3サイクルピッチに改善することに成功した。

XilinxのFPGAに実装開始

設計の段階でディレイを最大限考慮しているが、シミュレーションではディレイは反映されないため、実際にインプリメントして、どの程度の周波数で動作するのか、XilinxのVivadoを使って確かめてみた。Vivadoは初めてなので保証できる値ではないのですが125MHzで動作することがわかった。これは演算器の性能なので、そこからRSA 2048bitの性能を計算するとDSP 90個で3.2ms程度になった。評価ボード ArtyのXC7A35T-L1CSG324Iにインプリメントしています。これはCPUに比べてかなり低消費電力なのでは？とも思った。 f:id:icf:20180903134217p:plain

鍵長が大きくなっても演算器の周波数が下がらない特長の発見

4サイクルピッチから3サイクルピッチに性能改善するときに1サイクル遅れたブロックと接続する技術を開発した。この技術を使えば鍵長が大きくなっても周波数が下がらないことに気づいた。モンゴメリ乗算のアルゴリズムは劇的に改造しないかぎり最下位ビットから演算器全体にブロッドキャストすることになり、低基数ではハードウェア実装において鍵長の増加に伴い周波数を低下させる原因となっていた。 CPUでは鍵長が２倍になると、おおよそ7倍～9倍性能が低下する。 RSA 2048bitでは0.62msでも、RSA 16384bitでは400msになるためとてもSSLの実装として許容できる性能ではない。この技術を使った場合の予想では、鍵長を２倍しても、演算器の幅を２倍にすることで性能低下は4倍強にとどまる。仮に4.2倍とするとRSA 2048bitで3.2msだったのがRSA 16384bitでは237msとなるためぎりぎり現実的な性能といえる。

補足1

「RSA 16384bitの性能なら俺のほうが勝っている」と言う人もあるかもしれません。 5nmプロセスとか、Virtex UltraScale+みたいなハイエンドデバイスとか、デバイスの前提条件が考慮されているか確認してください。こちらの前提はArtix-7で、比較的ローエンドなデバイスです。もちろん必要ならハイエンドデバイスも考えます。

補足2

理論的にはRSAの鍵長が２倍になると演算量は8倍です。ICF3-Fは鍵長が２倍になると演算器を２倍にできるアーキテクチャなので処理時間が４倍ですがCPUでは並列性を抽出できず８倍になると思います。もしできても無駄が多く消費電力が厳しくなる。鍵長がさらに大きくなればCPUとの差はもっとでると。

暗号プロセッサの開発開始

暗号プロセッサの周波数と演算器の周波数は普通２倍以上違うが、3倍になるのか、4倍になるのか。BRAMのタイミングと合わせて検討を始めた。実際には、暗号プロセッサの開発と並行して、ICF3-Fが売れるのかも調べた。

ICF3-Fは、どれくらい売れるのか？

現時点でのSSL証明書はRSAが大半で、まずはRSAのことだけを考えていた。 ICF3-Fは楕円にも対応可能であるため楕円に移行しても問題がないと考えていたからだ。今後、普及していくと思われるTLS 1.3は当然、楕円に対応している。 RSAはサーバー側が非常に重く、クライアント側が軽いが、楕円はクライアント側よりもサーバー側のほうが軽く、サーバー側に負荷がかからないということを、さっき知った。つまり楕円暗号に抵抗のないサーバー管理者はSSL アクセラレータを買うより、可能な限り楕円に切り替える。無料のSSL証明書 Let's Encryptも楕円に対応したものが発行できる。 「ICF3-Fは、買えば得をする商品になる」といったが、あまり正しくなかった。 ただSSL証明書の購入が、お客である場合も多いので、お客が楕円暗号に抵抗があったり、RSA証明書のほうが安価ということでRSAを選択する場合もある。クライアント側が重い楕円はモバイルではバッテリーの消耗が大きい。そういうことを重視する場合は、やはりRSAの証明書を選択することもあるだろう。ちなみに楕円P-256だけ、かなり最適化が進んでいる感じで楕円P-384の性能はかなり下がるということがあるようだ。なんと楕円P-521よりも性能が悪いのだ。 P-256よりも安全な証明書を選択したい場合、P-384かRSA 4096になるが、opensslの性能評価でクライアント側の処理は、RSA 4096のほうが約8倍くらい軽い。 RSA 4096を選択したくなるケースはあるかもと思った。

まとめ

背景の最初に書いた通りだが、楕円暗号の離散対数問題を効率的に解く方法が発見されたり、量子コンピュータの進歩によって量子ゲート数が増えて鍵長の短い楕円暗号のほうが先に解読されるということになれば、とても長い鍵長の専用演算器をハードウェア実装可能なICF3-Fの技術は、今とても役に立つということではないが、なくてははならないものではないかと思っています。従来の専用演算器はモンゴメリのアルゴリズム的に鍵長を長くすると低基数では性能劣化が大きくなる問題があった。高基数ではCPUと同じ状況になるだろう。詳しく理解していないが改良型である冗長モンゴメリは、もしかすると鍵長が長くなっても性能劣化が小さいかもしれない。しかし理論は美しいが、最初から重い実装なので、感覚的だがICF3-Fのほうがいいと思われる。量子コンピュータについても勉強不足だが、現在、ざっと調べてもショアのアルゴリズム以外は検索で見つからない。最悪のケースでは鍵長を長くしてもRSAや楕円暗号を延命することはできないということは考えていなければならない。しかし量子コンピュータは量子ゲート型だけではなくて量子イジングモデル方式も多く開発が進んでいる。解読されても鍵長を長くすることで延命できるケースも考えられるかもしれない。鍵長が長くなるとCPUのコアを増やす方法ではSSLに必要な絶対性能を満たすことができず、ICF3-Fの専用演算器が必要となります。 IEEEなどの論文を調べても、学術的な価値も1999年に世界一のRSA性能だったICF3を含めて、とてもあるように思っています。 ICF3-FはFPGAを使って開発をするので、かつてASIC LSIの開発経験がある僕にとっては、ほとんどお金がかからず開発が進み、 Cmod A7などの評価ボートを、そのまま使って製品とするようなことをすれば、ある程度、Xilinx様の協力があれば製品化は実現可能だと思います。

はじめに

問題

証明

補足

はじめに

論理合成ツール

対象となる論理

対象となるverilogコード

論理合成ツールによる結果

人間による結果

まとめ

はじめに

論理合成ツール

論理合成対象

論理合成ツールの結果

人間の結果

まとめ

追記

追記2

追記3

はじめに

子供の頃

大学時代

研究室時代(大学院)

日立 中央研究所 超高速プロセッサ部

日立メインフレーム開発部時代

いいたかったこと

背景

設計開始

シミュレーションで正しい結果に

XilinxのFPGAに実装開始

鍵長が大きくなっても演算器の周波数が下がらない特長の発見

補足1

補足2

暗号プロセッサの開発開始

ICF3-Fは、どれくらい売れるのか？

まとめ

　追記3

日立中央研究所超高速プロセッサ部