トルコの大学の論文「レイテンシ性能重視の回路実装に適したモジュラー乗算アルゴリズム」


SnakeCubeアーキテクチャ


INPIT証明書


WIPO証明書

WZetaプロジェクトのリーダ、平山 直紀は暗号プロセッサSnakeCubeをマイコンなどに接続できるBIOS仕様とソフトウェア「WZeta BIOS」を5月28日(土)に提供開始しました。

「WZeta BIOS」 URL: https://wzeta.idletime.tokyo/wzetabios.html


■概要
商用クローズドな暗号プロセッサSnakeCubeとオープンソースの8bit CPU WZetaを組合せることで様々な暗号演算が可能になります。どちらも同一設計者による独自の命令セットのプロセッサでありICカードやレイテンシ性能を追求するサーバー向けに最適ですが、これをWZeta搭載マイコンなどに接続するためのBIOS仕様とソフトウェアのみによる実装を公開。特別にI/Fを除いたものはCC0(パブリックドメインと同じ)で公開。


■WZeta BIOSの特徴
従来BIOSコールはソフトウェア割込み(INT命令)を利用することが多くあります。ソフトウェア割込み中に割込みを受け付けることができても多重割込みとなり煩雑になる傾向がありました。8bit CPU WZetaはハードマクロ命令を使ったBIOSコールのためBIOSファンクション実行中でも普通に割込みを受けられます。処理時間の長いBIOSファンクションの実装が容易にできるという特徴があります。このハードマクロ命令によるBIOSコールがマイコン技術の進化につながることがあり得るかもしれません。


■商用クローズドな暗号プロセッサSnakeCubeとは
革新的な性能のモンゴメリ乗算器を持つ暗号プロセッサSnakeCubeは2018年に平山 直紀(Hirayama Naoki)によって発明され2020年にFPGAによる実機で高性能かつ高効率であることが実証されました。デバイス依存が少なく廉価なFPGAでも性能を発揮するため多くのデバイスに実装できる経済性の高い暗号プロセッサ。SnakeCubeは巨大な整数演算を得意としていますがSHA-2などのハッシュ演算では多大な無駄が発生します。SnakeCubeは1999年にRSA暗号の性能で世界一だった大型コンピュータ(IBM互換機)の暗号装置に搭載された暗号プロセッサICF3の設計者によるものです。

記事の最後にSnakeCubeアーキテクチャの図があります。


■FPGAによる実機で2048bit RSA復号化1回、1.74[ms]を記録
2020年8月に暗号プロセッサSnakeCubeの完全版をFPGAに実装し実測した記録はYouTube動画として配信しています。
https://www.youtube.com/watch?v=beaFg0x8Qj8

FPGAボードの8個のLEDを使って演算結果を確認。設定したクロック周波数で動作していることを青色のLEDの点灯で確認しています。測定条件はFPGAボードはDIGILENTのArty、FPGAはXilinxのXC7A35TICSG324-1L コスト重視のArtix-7です。スピードグレード -1なので一番遅いもの。

RSA 2048bit 復号化(CRT有)の演算1回、1.74[ms]

Xilinxのホワイトペーパ「Zynq UltraScale+ MPSoCで暗号化処理を高速化」(WP512(v1.0) 2019年5月21日)の記録は12.846[ms]なので約7.4倍ですが実測したSnakeCubeの半導体プロセスは2ランクも格下なので同じなら10倍以上。XilinxのホワイトペーパにCRTの有無は記載されていませんが、LinuxとFreeRTOSの性能差が2倍あるあたりを考えるとCRT有と推測できます。

測定に使ったverilogのソースコードを独立行政法人工業所有権情報・研修館(INPIT)および世界知的所有権機関(WIPO)においてオンラインでタイムスタンプの証明書を取得しています。なお独立行政法人工業所有権情報・研修館(INPIT)のタイムスタンプ・サービスは2021年3月に終了していますが「アマノタイムスタンプサービス3161」は有効です。

記事の最後にINPIT証明書とWIPO証明書の画像があります。


■オープンソースの超軽量8bit CPU WZetaとは
WZetaは少ないトランジスタ数で構成され、40年以上前のIntel 8bit CPU 8080のトランジスタ数と同等で数倍(FPGA換算のため誤差有)の性能が出る新種の命令セットの8bit CPU。WZetaは2019年に期間限定公開されていましたが2021年2月にハードウェア開発コミュニティelchikaの「ハードウェア投稿作品キャンペーン」に応募、審査を通過したため本格的に開発を開始。同じ特長を持つ全く別のCPUになったという経緯があります。他のCPUではあまり見かけないハードマクロ命令は複数の命令を1命令にする機能でプログラムメモリを節約、高速なサブルーチン、仮想マシンなど画期的に便利でコンパイラに新世界をもたらします。8bitのデータ幅のメモリをプログラムとデータで共用できるためメモリ1個で動作します。
マイコンの製造コストを下げるのに役立ちます。各々の実装に依存しますが公式コアSDogは全命令4サイクルのためPWM制御に向いています。また暗号のサイドチャネル攻撃耐性があります。WZetaは全く独自のアーキテクチャでありオープンソースであることから世界的に普及することが期待できます。

16bit固定長の命令セットはオペランドの8bitだけで投機的に実行が開始できる命令セット。命令は8bit×2回の転送でCPUに送られます。このとき先に来た8bitのコードだけで動作が開始できます。これを命令セットとして一貫させています。AES暗号やRSA暗号などでは50~60%以上の命令でオペランド投機実行が成功して命令の実行時間を1サイクル早めることができます。
例えば次のADD命令

ADD [n],A ;[n] = [n] + A

RSAや楕円暗号など多くの演算でよく使われる命令です。オペランド投機実行がなければ[n]の読み出しが遅れるため 命令の実行に5サイクルかかりますが、オペランド投機実行をすると4サイクルになります。プログラムコードの読み込みに2回、命令の実行に[n]のリード1回、[n]のライト1回。合計4回のメモリアクセスが行われます。つまり、この命令は4サイクル以下にできません。

16bit固定長の命令セットの最上位ビットは、モードによって3種類の動作をします。「パリティモード」には2つのモードが存在。命令コードの1bitのパリティか、ハードマクロ命令のbitと合わせて2bitパリティとするモード。パリティ無しの安価なメモリでパリティの信頼性を得られるメリットがあります。

画像1: https://www.atpress.ne.jp/releases/310208/LL_img_310208_5.png
命令コード内パリティ

「高速モード」はレジスタを+1しながら命令を同時に実行することで高速化します。トランジスタ数当たりの性能向上率の高い機能。「デバッグモード」では動作を止めることなくトレースデータを取得する目的で使えます。実装依存の機能ですがリアルタイムでなければバグが再現できない場合などで活躍します。


■暗号半導体チップにおける『ナオキの法則』
半導体業界ではムーアの法則が有名ですが、ムーアの法則は集積回路上のトランジスタ数は「2年ごとに倍になる」という指標のような経験則です。似たような法則として平山 直紀(Hirayama Naoki)が2018年に発明したSnakeCubeから、後世の人に役立つ指標になるナオキの法則(Naoki's law)を提案します。
詳しくは次のブログにありますが、RSA暗号は鍵長が2倍になると計算量が8倍になります。
https://icf.hatenablog.com/entry/2022/01/27/074607

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

画像2: https://www.atpress.ne.jp/releases/310208/LL_img_310208_1.png
トルコの大学の論文「レイテンシ性能重視の回路実装に適したモジュラー乗算アルゴリズム」

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

一方、SnakeCubeは「鍵長2倍で計算時間4倍」を恐らく保証します。つまり、あるプロセスのデバイスでデータを取るとナオキの法則を使って、そのデバイスで鍵長を大きくした場合の精密な性能が予測できるのです。


■SnakeCubeの応用と今後
10万ビットのRSA暗号の演算をするため10万ビットの整数演算を1度に計算するSnakeCubeは実現可能です。このため量子コンピュータの量子ビット数の限界を鍵長が超えれば、ブレイクスルーがあるまで当面、RSA暗号でも安心できるかもしれません。楕円暗号の演算にも利用できますが楕円暗号は鍵を大きくする毎に安全性を考える必要があります。一方、RSA暗号は鍵長に依存しないため、鍵を大きくするだけで安全性を再考する必要がありません。このためRSAはシステムのコストを下げることに貢献する場合があります。量子コンピュータの進歩や解読アルゴリズムの発明により、すべての公開鍵暗号が崩壊することも考えられます。
そういう問題のために巨大整数を使った新しい公開鍵暗号を考えておくことは必要でありSnakeCubeは役に立ちます。また将来のアプリ、準同型暗号で活躍する可能性もあります。

次世代SnakeCubeでは量子コンピュータの解読に強い耐量子暗号をSnakeCubeに実装していきます。従来暗号も新暗号も演算可能となるようにしていきます。汎用的なSIMDプロセッサをRSA暗号に対応させたものでは十分に効率がでません。SnakeCubeを耐量子暗号に対応させたほうが効率的ではないかと考えるため耐量子暗号の国内の研究者とともに開発を進めていくことが期待されます。


■Webサイト
BIOS公開URL
https://wzeta.idletime.tokyo/wzetabios.html

暗号プロセッサSnakeCube公式サイト
https://snakecube.idletime.tokyo/
8bit CPU WZeta公式サイト
https://wzeta.idletime.tokyo/
暗号半導体チップにおける『ナオキの法則』
https://icf.hatenablog.com/entry/2022/01/27/074607

画像3: https://www.atpress.ne.jp/releases/310208/LL_img_310208_2.png
SnakeCubeアーキテクチャ
画像4: https://www.atpress.ne.jp/releases/310208/LL_img_310208_3.png
INPIT証明書
画像5: https://www.atpress.ne.jp/releases/310208/LL_img_310208_4.png
WIPO証明書

【本プレスリリースに関するお問い合わせ先】
平山 直紀
TEL : 090-8332-6208
MAIL: wzeta@idletime.tokyo

電話でアクセスしてからメールでご連絡をお願いいたします。
情報提供元: @Press