乗算器のない8bit CPUで高速にべき乗剰余演算するコード(改訂版)

乗算器のない8bit CPUで高速にべき乗剰余演算するコード(改訂版)

目的

軽量で非常に良くできた8bit CPUのオープンソースWZetaを普及させるためにRSA暗号や楕円暗号などの公開鍵暗号で使われるべき乗剰余演算のアセンブラコードをCC0ライセンス(パブリックドメインと同じ)で公開したことのお知らせ。

警告 CC0であるのは、べき乗剰余演算のWZetaのアセンブラコードのみ

WZetaとは

WZetaはトランジスタ数当たりの性能、命令セット内パリティ、ハードマクロ命令など8bit CPUにして新技術を多数持ち、常識を破る変則的な命令セットですが、高い効率であることが確認されつつあるCPU。

1024bitのべき乗剰余演算するコード

コードの貼り付けがうまくいかなかったのでアセンブラのファイルへの直リンクにします。

wzpowmod2022_06_10.zip

解説

wzpowmod.asm (事前定数有版)

y = g ^ x mod p ( r: R^2 mod p )

wzpowmod2.asm (事前定数無版)

y = g ^ x mod p

rはpの値によって決まるモンゴメリ乗算の事前定数。モンゴメリ乗算の基数2はICF3(1999年)でも使われていました。1024bitべき乗剰余演算のサブルーチンの入力パラメータは256バイトのブロック2個。powmod_grとpowmod_pxです。grは前半128バイトがg、後半128バイトがr。 pxは前半128バイトがp、後半128バイトがx。サブルーチンが終了するとrの場所に演算結果yが入っています。

実行環境

WZetaシミュレータで実際に演算させてみることが可能です。

> wzsim (アセンブラのファイル)

警告 シミュレータにはC言語実装のシミュレータとverilogのバイナリがあります。verilogでは1024bitのべき乗剰余演算に1週間以上かかることもあるので、ご注意ください。

実行結果

実行後、演算が終了すると演算結果に続いて期待値が表示されます。期待値はコードの最後にあるpowmod_expの値が、そのまま表示されます。

性能について

乗算命令が無いため8bitの加算器1個で演算しています。絶対時間では非常に遅いため軽量な楕円暗号か、数時間の演算時間が許容されるIoTシステムなどでの利用に向いています。BIOSを通してアプリを作成すればアプリを改変することなく超高速な暗号プロセッサSnakeCubeに置き換えられることを考えているため、性能が必要になったところで、暗号プロセッサSnakeCubeに置き換えることが可能になる予想です。シミュレータの実行終了後、命令数が表示されます。WZetaのSDogコアでは1命令4サイクルなので命令数を4倍して周波数を計算すると1024bitのべき乗剰余演算1回の時間が求まります。値に依存しますが、上記、サンプルコードでは666530315命令。CPUの周波数に8MHzを想定した場合、1サイクル125[ns]なので

666530315 × 4 × 125 ÷ 10^9 ≒ 333秒(512bitのべき乗剰余演算だと約42秒)

脆弱性対策

今回のコードは脆弱性対策の無い単純に最も高速なプログラムになっています。また最上位ビットを高速モードとして使っています。サイドチャネル攻撃を対策をするには値に依存しないようにダミーの計算時間を入れます。WZetaの命令セットはオペコードに依存せずメモリアクセスをするという低消費電力でない特性がありますが、これが電力解析などのサイドチャネル攻撃への耐性を高めることにもなっています。トランジスタ数が少ないのでオペコードに依存しない動作で0、1の切り替えが多くなったとしても、全体としての消費電力は少ないという予想です。

暗号資産で8bit CPU WZetaをどう使うのか?

CC0で公開したアセンブラのコードは1024bitのべき乗剰余演算ですが、これを応用してハードウォレットを開発すれば安価なものになる。性能は非常に遅いですが、規模が小さいCPUなので検証しやすく、安心できるハードウォレットを開発することが可能かもしれません。暗号資産を扱う小型のIoTデバイスの開発など。

Remaining : 0 characters / 0 images
100

Sign up / Continue after login

Related stories

Writer

仮想通貨よりハードウェアに詳しいエンジニア

Share

Popular stories

ハードウェアから見た暗号資産(仮想通貨)

91

オープンソースのCPUで8bitパソコン作った

39

RSAは終わらない - RSA 7680bitのICカードの実現可能性

24