暗号計算機屋のブログ

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

暗号半導体チップにおける『ナオキの法則』

背景

半導体業界ではムーアの法則が有名ですが、ムーアの法則集積回路上のトランジスタ数は「2年ごとに倍になる」という指標のような経験則です。似たような法則として平山 直紀(Naoki Hirayama)が2018年に発明したSnakeCubeから、後世の人に役立つ指標になるナオキの法則(Naoki's law)を提案します。発明直後に、この法則が言えることを確信していたのですがSnakeCubeの実装に奔走していたため、後回しにしてきました。この法則が学会、産業界で、大いに活用してもらえるように、ここで発表します。

概略

SnakeCubeはRSAなどの公開鍵暗号の演算で良く使われるモンゴメリ乗算器とプロセッサの構成法のことです。デバイスに依存しない数学のアルゴリズムに近いものです。ざっくり言うと演算器、単体で3倍以上、性能を4倍にできる中国人剰余定理も併用可能なため、従来研究の3×4=12倍の高速化を達成しました。演算器単体でも10倍あるかもしれないデータもあるため革命的な発明ではないかと思われます。モンゴメリ乗算を使わないアルゴリズムにはSnakeCubeよりも高速なサバンジュ大学の論文があります。ただ量子コンピュータによる解読問題を緩和するためには、鍵長を長くする必要があるのですが、その方法は鍵長を大きくすることが実装上非常に困難であるため、僕はSnakeCubeが世界最高の暗号プロセッサであると考えています。移植の容易性や、鍵長を長くするのが、とても容易なこと。鍵長を長くしても効率が落ちない。マルチチップに実装することが容易であること、IPにしやすいなど、SnakeCubeは良い点が多いのです。

トルコにあるサバンジュ大学の論文

次の論文は「鍵長2倍で計算時間2倍」を理論的に説明した論文。米アマゾンとイーサリアム財団ら、賞金10万ドルのFPGAデザインコンテストを優勝した論文です。

f:id:icf:20220127035927p:plain

理論的に美しい論文ですが、鍵長が長くなるにしたがって、効率が下がり、実装が急激に(経済的にも)困難になっていくため、量子コンピュータの暗号解読が懸念される、現在では、論文の成果が薄れています。

暗号プロセッサSnakeCube

SnakeCubeは、平山 直紀(Naoki Hirayama)が2018年に発明した暗号プロセッサ。 次のURLにある説明を読むとわかるかも。

snakecube.idletime.tokyo

icf.hatenablog.com

icf.hatenablog.com

ナオキの法則 (Naoki's law)

RSA暗号は鍵長が2倍になると計算量が8倍になるのです。 サバンジュ大学の論文は、わかりやすく説明すると、理論的にRSA暗号性能が「鍵長2倍で計算時間2倍」を説明した論文ですが、ナオキの法則は「鍵長2倍で計算時間4倍」です。 サバンジュ大学の論文のほうが勝っていますが、これは鍵長を2倍にした場合、トランジスタ数を4倍にして計算時間2倍を成り立たせています。ただし前述のように実際の製品にしていくには鍵長が大きくなるしたがって、劇的に困難になります。一方、ナオキの法則はSnakeCubeによって、だいたい保証されそうだということが、わかってきています。つまり、あるプロセスのデバイスでデータを取るとナオキの法則を使って、そのデバイスで鍵長を大きくした場合の精密な性能が予測できるのです。

SnakeCubeは世界最高の暗号プロセッサ

SnakeCubeよりもレイテンシ性能の高いプロセッサを開発することは可能だと思います。しかしデバイス毎に大きな設計コストが要求されると予想されるため、SnakeCubeが世界最高の暗号プロセッサであり続けると考えています。これは、これまで設計にお金をかけるよりデバイスにお金をかけて性能を向上することを優先する場合が多かったこと。概略で書いたとおりSnakeCubeの良い点が、多数あるため。

まとめ

今後、世界でSnakeCubeよりも高速な暗号プロセッサの開発を考えることはあると思います。ナオキの法則は、それを評価する上で便利な指標となるため、広く利用されるように考えます。量子コンピュータの進歩によりRSA暗号の安全性が危ぶまれている状況ですが、2048bitの鍵長を、いっきに大きくして、量子ビットを同時に多数安定化する技術が限界に達するところまで、もっていけば、RSAも、まだしばらくは安全だと楽観的に考えることもできるように思います。またSnakeCubeはRSA暗号専用のプロセッサではなくて、巨大な整数の四則演算器なので、今後、新しい公開暗号を高速化するためにも役に立ちます。

ナオキの法則は、人類史に残る法則となるかもしれない。

巨大整数用四則演算プロセッサSnakeCubeが高速である秘密

2020年9月12日、訂正 SnakeCubeの周波数は3倍になるという予測を2倍に。 またUiからT0iの区間を1サイクルと書いていましたが2サイクルに。

はじめに

2020年3月30日、コンピュータサイエンスに関する米国の学会ACM(Association for Computing Machinery)が、 コロナ感染拡大を受けて同学会の論文が6月30日までオープンアクセスになったようです。 早速、僕が発明したSnakeCubeより優れたものがあるのか調べたところ、 電通大の崎山先生の論文(2007年)が検索でヒットしたのでSnakeCubeと比較をしてSnakeCubeが高速であることを説明します。 崎山先生の論文は、ベルギーのルーヴェンカトリック大学との共同研究のように見えています。 崎山先生は僕と同時期に日立製作所に勤務されていましたが事業部が違ったので、一度も連絡が取れたことはありません。 以後、「電通大演算器」と呼ばせていただきます。

注意! SnakeCubeはオープンソースではなく商用開発しているものです。

SnakeCubeとは

ICF3-Fと呼んでいたことがありましたがオープンソースと間違われそうなのでSnakeCubeに改名しました。 1999年 RSA暗号の性能で世界一だった暗号LSI ICF3をベースに高速化した巨大整数用四則演算プロセッサです。 汎用演算プロセッサと暗号専用演算器のセットです。僕はICF3の汎用演算プロセッサの唯一の設計、開発者です。 この汎用演算プロセッサに2018年に僕が発明した暗号専用演算器(モンゴメリ乗算器)を追加したもの。

icf.hatenablog.com

電通大演算器

米国の学会ACMの次の論文にある演算器のこと。SnakeCubeの演算器に近いところがあります。

「Efficient Pipelining for Modular Multiplication Architectures in Prime Fields」 GLSVLSI’07, March 11-13, 2007, Stresa-Lago Maggiore, Italy. Copyright 2007 ACM 978-1-59593-605-9/07/0003

演算器の構造について

大雑把な両者の演算器アーキテクチャの話をします。 モンゴメリ乗算のループ処理では、巨大整数の乗算を2回するのですが、 SnakeCubeは1個の演算器で直列に2回乗算します。 電通大は1/4個の演算器を2個を使って4回乗算します。

このことから同じ周波数であれば理論的にはSnakeCubeのほうが2倍性能が出ます。 後で説明しますが予想ではSnakeCubeのほうが高い周波数で動作します。

つまり2倍の周波数だとするとSnakeCubeは電通大演算器の4倍高速ということになりますが、 電通大演算器が毎サイクル乗算器を使っているのに対しSnakeCubeでは5サイクルに4回なので、 最終的に3.2倍高速ではないかという予測です。 SnakeCubeの最下位ビットからのブロッドキャストの工夫により、 鍵長が大きくなるにしたがってこの差が、さらに大きくなっていきます。

SnakeCubeが高周波数で動作する秘密

この説明を完全理解するには電通大演算器の論文を読む必要があると思いますが、 このタイプのモンゴメリ乗算器のクリティカルパスは最下位ビットからのブロッドキャストです。 電通大演算器は、このクリティカルパスのために周波数が上がりません。 電通大の論文に書かれている図では、UiからT0iの区間のことで2サイクルになっています。

SnakeCubeでは、このクリティカルパス3サイクルピッチの4サイクルディレイとなるような工夫をしています。 正しくは3サイクルピッチの4、5・・・nサイクルディレイです。 鍵長が大きくなるにしたがってnが大きくなっていきます。 鍵長が大きくなっても周波数が落ちません。

このため電通大演算器の1.5倍の周波数を見込めるのです。 3サイクルピッチなのですが電通大のUiからT0iに相当するのは4サイクルなので2倍の周波数。

クリティカルパスが3サイクルあるため乗算器は3回に1回しか利用されていないのかというと、 別の演算を1回入れているので、乗算器を3回に2回利用しています。さらに2スレッドにして クリティカルパスの遅延をオーバーラップさせ5サイクルに4回、乗算器を使うということをします。

まとめ

SnakeCubeは電通大演算器に対して方式性能2倍、周波数2倍。 電通大演算器は乗算器の利用率100%ですがSnakeCubeは80%です。 最終的にSnakeCubeは2×2×0.8 = 3.2倍高速という予想ができました。 また鍵長が大きくなるにしたがってこの差が、さらに大きくなっていきます。

大きなモンゴメリ乗算器は実装できるのか?

はじめに

前回のブログ「わかりやすいICF3-Fのモンゴメリ乗算器の説明」で途方もなく大きなモンゴメリ乗算器を実装できるということ書きました。ここではICF3-Fは複数チップを接続したものでも実装できるのか?という話をしてみたいと思います。そして、そこから何が言えるのか?を考えてみたいと思います。

巨大なモンゴメリ乗算器は実装できる

当たり前のような気もしますが、演算器の周波数を落とさず、演算器の大きさに比例した性能を出すことができる実装ができるという意味です。 RSA暗号をCPUで計算した場合、おおよそ鍵長が2倍になると計算時間は8倍になります。僕が書いた次の記事が参考になると思います。

RSA 8192bitの性能を測定するソースコード - Qiita

ICF3-Fは鍵を大きくしていっても鍵長2倍で計算時間4倍のまま、ほとんど効率は低下しません。

複数チップ上に実装しても効率は下がらないのか

現在の設計では、複数チップ間の遅延時間にもよりますが、演算器の周波数が全く下がらないような設計をしています。現時点(2019年11月6日)では設計までで検証はできていませんけれども。隣接するDSP間の通信が3サイクルあっても、周波数を下げずに動作することができます。もちろんチップ間の遅延時間が大きければ周波数は下がりますが、チップ間の遅延時間が1サイクルに入る限りは大丈夫です。DSPからチップのI/Oピン、チップ間、チップのI/OピンからDSPというぐあいに3サイクルで転送させます。

言えることは

電子投票などの準同型暗号システムや、SSLを使ったシステムを設計する上で、量子コンピュータの解読脅威のため、可能な限り大きな鍵の公開鍵暗号(RSA暗号など)を使いたい。システムに必要な要求性能は、わかっている。ICF3-Fの、あるFPGAの実装から「鍵長2倍で計算時間4倍」法則を使って、システムの鍵長を考えることができる。またICF3-Fは演算器の最下位ビットから最上位ビットまで、一筆書きのように、並べるだけの実装なので開発コストが小さく、見積もりが容易。 サバンチ大学の剰余乗算のFPGA実装は米アマゾンのFPGAコンテストの結果からも言えるように美しい理論はあるものの実際には実装してみないと性能が、わからないところがある。そして鍵長が大きくなるにしたがって効率が、どんどん下がっていく。ICF3-Fの「鍵長2倍で計算時間4倍」が理論のように見えてくるのかも。

わかりやすいICF3-Fのモンゴメリ乗算器の説明

はじめに

米アマゾンとイーサリアム財団らがFPGAコンテストをするそうです。簡単に言うとA×A mod N (A,N: 1024bit)をできる限り速く演算するというコンテスト。コンテストのサイトで紹介されているサバンチ大学の論文「Low-Latency Modular Multiplication Algorithm - Erdinc Ozturk」にはXilinxFPGAで剰余乗算器、A×B mod N(A,B,N: 512bit)を実装した結果がある。巨大な剰余乗算器で、ICF3-Fの剰余乗算器(=モンゴメリ乗算器)よりも、かなり高速な演算器です。コンテストで1024bitのものが実装できれば、ですが。コンテストで1024bitの性能の結果が出たようです。詳しくはコンテストのサイトほうへ。

ご注意! ICF3-Fはオープンソースではありません。

目的

サバンチ大学の論文には128bit、256bit、512bitの結果があるので、そこから1024bitのDSPの数を予想すると4225個。一方、ICF3-Fは44個×2です。 サバンチ大学の論文の方法で1024bitのものが実装されてもICF3-Fは、RSASSLアクセラレータの用途など、実際に利用される用途では負けていないということを言いたいのですが、 あまり細かいことを書きたくなかったので、わかりやすいICF3-Fのモンゴメリ乗算器の説明になりました。ICF3-Fとの違いで大きなものはNの入れ替え。 ICF3-Fは演算毎にNを入れ替えられるが、Nの入れ替えに時間がかかると思われます。つまりサバンチ大学の論文では複数のSSL証明書を運用したい場合、運用が難しい。周波数も考慮しないといけないのですがICF3-Fの約100倍のDSPを使うので100倍以上の性能が出ないとコストパフォーマンスが悪い。100倍以上としたのは、ICF3-FはリダクションもDSPで演算していますが、サバンチ大学の論文では巨大なLUTとBRAMを必要としている点があります。サバンチ大学の論文では小型のSSLアクセラレータを作れないであろうとか。

ICF3-Fのモンゴメリ乗算器(1024bit版 DSP 44個)

f:id:icf:20190812212327p:plain
ICF3-Fのモンゴメリ乗算器
1ループ=3サイクルで17bit分のモンゴメリ乗算。1024×1024bitをするには61ループ(183サイクル)。DSP内のレジスタに入力データを設定、ループ終了後、DSP内のレジスタに答えが格納されている。 uのブロッドキャスト以外は、隣接するDSPしかデータ転送がなくデータのローカリティが高いアーキテクチャ。k番目のDSPは、k-1番目のDSPとk+1番目のDSPと通信するのみで配線実装しやすい。 3サイクル中、乗算は2回行われる。乗算のうち、ひとつはuの値がないと演算できないためDSPが2倍あっても、あまり高速化できない。1つのDSPでuの値が不要な乗算を先に行い、その後、uの値を使う乗算を行う。DSPは乗数を17bitづつシフトする用途にも使われている。サバンチ大学の論文では乗算にRNSを使っているためXilinxDSPの24×17の乗算器を16×16として使っているがICF3-Fでは乗算にRNSは使っていないので24×17として使えている。つまり(24×17)÷(16×16) = 1.59倍、効率良く乗算器を使っている。

このようにループさせるだけでモンゴメリ乗算が正しく演算できることの証明はモンゴメリ乗算の累積加算における分割加算の証明にあります。

大きなモンゴメリ乗算器が実装できる仕組み

f:id:icf:20190812212444p:plain
大きなモンゴメリ乗算器が実装できる仕組み
乗算器が大きくなっていくとuのディレイが間に合わなくなってくる。そこでuのブロッドキャストに中継FFを入れる。 kからk+1のデータはFFで中継。k+1からkのデータを1サイクル早く作る。ここがポイント。このときディレイが心配になるが、それでもクリティカルパスはu生成になると思うので、ここはクリティカルパスにならない。このため、途方もなく大きなモンゴメリ乗算器を実装できる。途方もなく大きな乗算器になってもクリティカルパスが、長くなることはない。つまりDSP当たりの演算効率は、ほとんど下がらない。

ICF3-Fの性能を2倍にする

RSA暗号SSLアクセラレータにおいて、RSA暗号の鍵長が大きくなるとサバンチ大学の論文では実装できなくなるし、ICF3-Fも実装できても性能が遅すぎる問題がでてくる。そこで2個のICF3-Fを連結して中国人剰余定理を使って、性能をほぼ2倍にする方法が、現実可能だということです。

僕の分割加算と準同型暗号

目的

僕の考えた分割加算が準同型暗号を使ったシステムで役に立ちそう。

分割加算とは

大きな数のモンゴメリ乗算を高速に演算するアルゴリズム。僕が考えたもの。 詳しくは「モンゴメリ乗算の累積加算における分割加算の証明」

準同型暗号とは

暗号化されたまま加算や、乗算が行える暗号。RSA暗号など、いくつかの公開鍵暗号がある。僕はアルゴリズムや安全性については詳しくない。 電子投票電子マネーでの応用が期待されている様子。具体的に社会実装するという動きもあるようです。

分割加算は使えるか?

RSA暗号はもちろん。Paillier暗号でも、使えると思われます。 分割加算では基数2n(nは、17~64程度)なので 使えるかどうかは暗号アルゴリズムにあるmod xのxがgcd(2,x)=1であること。すなわちxが奇数かどうかになります。 準同型暗号を使ったシステムで、どのくらいモンゴメリ乗算を使うかによって、実際に分割加算を実装したFPGAなどのハードデバイスが役に立つかが決まります。

分割加算はFPGAに向いている

分割加算を使った暗号プロセッサICF3-FはASICのみならずFPGAでも効率的に実装できる。 ICF3-Fの元となっているICF3は、オープンソースハードウェアとして公式サイトがある。 ただし、まだライセンスの整備が十分でない。 構想の話ですが、ICF3-FとICF3の命令セットを、なるべく共通化して、オープンソースのICF3で広く普及させ、 真に性能が必要なシステムでは、ICF3-Fが売れる。その利益によってオープンソースのICF3が整備されるというような、、、。