モンゴメリ乗算のプログラミングテクニック
前提
モンゴメリ乗算はRSA暗号などの公開鍵暗号で良く使われています。今後、準同型暗号などの暗号応用分野でも広く使われることになると思われます。ただ乗算結果に$${R^{-1}}$$がついているために使い方に戸惑う人もある。そういう人のためのテクニックを紹介します。モンゴメリ乗算については説明を省略します。
モンゴメリ乗算
INPUT: 整数 p = ($${p_{n-1}}$$ , ・・・ , $${p_1}$$ , $${p_0}$$ )$${_b}$$
整数 Y = ($${y_{n-1}}$$ , ・・・ , $${y_1}$$ , $${y_0}$$ )$${_b}$$
整数 G = ($${g_{n-1}}$$ , ・・・ , $${g_1}$$ , $${g_0}$$ )$${_b}$$
0 ≦ Y,G < p
R=$${b^n}$$ ( gcd(p,b)=1 , $${p^\prime}$$ = $${-p^{-1}}$$ mod b )
OUTPUT: $${YGR^{-1}}$$ mod p
A×B mod pの計算
$${A_R}$$ = A × R mod p
$${B_R}$$ = B × R mod p
モンゴメリ乗算 $${A_R}$$ × $${B_R}$$ = $${ABR^1}$$ mod p
モンゴメリ乗算 ($${ABR^1}$$ mod p) × 1 = AB mod p
テクニック
A × R mod p は事前に計算できる$${R^2}$$ mod p を使えばモンゴメリ乗算で高速に演算ができる
A × R mod p = モンゴメリ乗算 A × $${R^2}$$ mod p
B × R mod p = モンゴメリ乗算 B × $${R^2}$$ mod p
まとめ
モンゴメリ乗算の乗算結果には$${R^{-1}}$$がついていますが、事前に計算できる$${R^2}$$ mod pを使うことで、剰余乗算の計算を含む、様々な暗号計算がモンゴメリ乗算で可能です。
モンゴメリ乗算の$${R^{-1}}$$についての数学的な意味について学んでおくことは、いいことかもしれない。
暗号プロセッサSnakeCube
SnakeCubeではA×BとA×Aの2つのモンゴメリ乗算を並列に実行します。これが高速なのはIntel ハイパースレッディングと同じ理屈。mod pのpが共用できるので、さらに効率的。RSA暗号では、この並列実行をフル活用して計算できます。楕円曲線暗号でも、多少、高速化できます。その他の暗号応用でも並列演算について考慮したアルゴリズムを開発すると、いいかもしれません。
参考までICF3(1999年)も同様に並列実行します。ハイパースレッディングではなくて専用演算器を完全に２個使った並列方式。(当時の日立のCMOS半導体のフリップ・フロップが比較的、ゲート数が多いために、この方式が有利になったという記憶)
SnakeCubeではRの大きさを変更することができるので乗算のサイズに応じた計算コストになります。
SnakeCubeにはA × R mod pを直接計算できる方法があるのでpの値が頻繁に変更されるような演算も可能です。
ASIC版のSnakeCubeは検討中ですがICF3(1999年)のマイクロコードに似たものになると思われます。ただし大型コンピュータ向けに開発されたICF3はビッグエンディアンなのでICF3のシミュレータでマイクロコードを開発してもSnakeCubeへ移植するには労力を必要とするため推奨ではありません。
2020年に開発されたFPGA版のSnakeCubeは２組の｛A×BとA×A｝の計算ができます。1つの暗号プロセッサに２組のモンゴメリ乗算器を接続することで、１組の場合よりも、プロセッサが共用できるためトランジスタ数当たりの性能が上がります。RSA暗号ではこの２組のモンゴメリ乗算器をフル活用できます。ざっくり４スレッドで演算器を使い切る効率の良さ。