暗号計算機屋のブログ

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

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

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

はじめに

XilinxFPGA(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の大型加算器でも使えるので、かなり効果があるかも。

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です。面積的にはスライス2個分といったところでしょうか。 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

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

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

はじめに

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

子供の頃

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

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

大学時代

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

研究室時代(大学院)

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

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

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

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

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

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

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

いいたかったこと

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

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

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

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

背景

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

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

設計開始

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

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

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

XilinxFPGAに実装開始

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

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

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

補足1

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

補足2

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

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

暗号プロセッサの周波数と演算器の周波数は普通2倍以上違うが、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様の協力があれば製品化は実現可能だと思います。

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が実際の生活に役に立つあたりも、いいと思っている点です。

FPGAを使ったSSLアクセラレータのICF3-F

これから設計して性能が出そうなら売れるものになるのかも、という話で具体的な計画があるわけではないです。 1999年の暗号LSI ICF3をベースとしてFPGAに特化したSSLアクセラレータを考えていきます。これまでFPGASSLアクセラレータでは性能が出せず商売にならないと思っていたのですが、FPGADSPを多数もっていることを知り考えが変わりました。

演算器の性能でいえばGPUのほうがはるかに上なのですが複数のSSLの演算を同期しなければならず利用ケースは限られます。FPGAではモンゴメリ乗算をうまく使うことで多数のDSPを効率的に使用できるはずなので小規模なサーバーでも効果があることを見込める。

これまで、そういう研究は10年以上前からありましたが商用化に成功しているものは、あまり見当たらない。あまり探していないので、もうあるかもしれないですが。商用化を困難にしている原因のひとつは、SSLの演算の全てをFPGAだけで処理することが難しいからではないかと「勝手に」思います。

そこでICF3をベースにFPGAに特化したSSLアクセラレータを作れば、FPGAだけで処理できるようになる。FPGAだけで処理できるようになるとUBS接続の安価なFPGAでも小規模サーバーのSSLに貢献できるようになり商業化が可能になるかもということです。

実際にやってみて性能が出れば。ですが。(^^;; うーん、ICF3-Fとして検討してみるか。

2018年4月23日 19:35追記

実際にやってみないと、わからないところはある。技術的な説明をすると、ICF3は基数2で幻のICF4は高基数に振り切っている。FPGAではDSPのビット長にあわせて基数を2から、もう少し大きくする。基数2にない面倒なことが起きるかもしれないが、そのくらいならICF3のように全体を閉じることができないかと考えている。 これが可能になっているのは僕が、ハード、ソフト、暗号を1人でできるからなのだと思う。仕様変更も頭の中で3秒くらいで完了するし。

IT業界で数学の才能が何の役に立つか

取り合えず僕に数学の特技があると思って聞いてもらえるといいと思います。😉

1999年の暗号LSI ICF3の開発で僕がモンゴメリ乗算を採用することに反対した理由を説明すれば、数学の才能が役に立つということが、わかるように思います。

ICF3を開発した部署は、ハードウェアの開発部なので電気・電子系の学科の人が多いのですが、現在の教育のようにRSAの数学について、知っている人は、いませんでした。研究所とは異なり頭を空っぽにして、全力で、最小限の工数で、開発を達成させることが仕事なのです。特に隣の大型コンピュータの開発部隊と異なり1年に1機種を開発するという無謀なことをやっていました。隣では4年に1機種というペースでやっています。なので勉強なんてさせてもらえず成果だけ出すという苦しいことをやらされます。1年に1機種が可能なのは、それなりの学歴の年配の方々が控えていて、できなければ、切り捨てられてしまうからです。

そんな中、新規にRSA暗号LSIを開発することになった。検討を進めて方式が決まりそうになったところで日立のシステム開発研究所から海外の暗号の教科書がFAXで送信されてきた。22ページだけ抜き取ったものでした。モンゴメリ乗算を使ってRSAを実装できないかということだった。研究所の人が必要だと思った、バラバラの箇所の22ページで、最後の2ページにモンゴメリ乗算の式が、書かれていた。「14.3.2 Montgomery reduction」のところです。 そこから2日かけてRSA暗号の計算方法を、作り上げたわけです。実は教科書のアルゴリズム14.94にRSA暗号の計算方法があったのですがFAXには入っていませんでした。研究所の人は、ちゃんと読んで送っているのか、疑いました。😀 ただし、ハードウェアでは14.94の方法では難しくて、どのみち自身でRSA暗号の計算方法を作り上げる必要がありました。

モンゴメリ乗算の公式14.36 --- x・y・R-1 mod m

R-1は、引く1ではなくてマイナス1乗です。RSA暗号の計算で、R-1が消えるように、計算していけば、答えがでるだろうと予測して、C言語で、試してみたところ、正解が得られました。

ここで数学の才能の有無によって、判断に違いが出てくるのです。R-1という記号が、自分が知っている-1なのか、あらゆる値で、正しい答えが計算できるのか、教科書の読んでないところに、特異点が存在するみたいなことが書かれてないか。

大学1年のときの数学で整数論を習っていたのを思い出した。10年前に習ったことで、加減、乗除を定義して、それが閉じるのか、どうか、という講義だった。モンゴメリ乗算という定義が、閉じているのか、それを確認する必要があった。

ただコンピュータを作りたいと思う電気工学科が、整数論を、しっかり覚えていたわけではなく、特異点が存在しないか、おろおろ、やっていた。最初、感覚的に問題を感じ、自分がわかっていないことが、わかったのだが、徐々にわかっていないところが、何なのか、明らかになり整数論にたどり着いた。

ソフトウエアの開発では、間違いがあれば、バージョンアップをすればいいという考え方もありますが、ハードウェアの開発では、1回の間違いが致命的な損害になることもあり、数学の才能はIT業界で役に立つということになると思います。

以下はFAXで送信された教科書です。サンプル無料とありますが、全部あるようです。

cacr.uwaterloo.ca

2018年4月19日追記

この話は「車輪の再発明」ではなくて、なんかやってみたら正しい答えになるから大丈夫だと勘違いをしている可能性があることを問題として認識できるか?という点です。 自身で計算方法を作っていますから、公式が、正しい条件で運用されているかを、厳格に考えなければならない。 割算(÷)の記号が使われていても、実際の演算はユークリッド互除法だったり、べき乗剰余演算だったりするのです。大学の数学は。

ついでの話になりますが、この国には自分で考えたほうが、海外よりも、できる回答になる人がいることを、頭の中に入れてもらえないかと思うのです。