Home

欧州の論文の方法と比較(1)

電通大の崎山先生が欧州(ベルギー)と共同研究でRSA暗号高速化の論文(米国学会ACM 2007年)を出しているようです。
「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
以前、僕のブログで解説したものです。
もう少しわかりやすい説明をしてみることにします。
欧州の論文のタイトルを、わかりやすい日本語にすると、 「素数ベースの数を除数とした剰余演算の効率的なパイプライン・アーキテクチャ」
数式でいうと
A × B mod C (C: 素数ベースの数)
RSA暗号では、この計算式を連続して行うのですが、計算が終わらないと、次の計算ができないので、 A,B,Cのbit長と同じ大きさの演算器を用意しても、 準備計算(u)が入るため演算器が連続的に利用できず、効率が悪いのです。
1 A×B mod C
2 uの計算1
3 uの計算2
4 uの計算3
5 A×B mod C
6 uの計算1
7 uの計算2
8 uの計算3

uの計算は最下位の1桁だけ、わかれば、計算を開始できます。 そこで欧州の論文は4分の1のサイズの演算器を使ってパイプライン化して演算する方法をしています。
1 A×B mod C (1/4)
2 uの計算1 , A×B mod C (2/4)
3 uの計算2 , A×B mod C (3/4)
4 uの計算3 , A×B mod C (4/4)
5 A×B mod C (1/4)
6 uの計算1 , A×B mod C (2/4)
7 uの計算2 , A×B mod C (3/4)
8 uの計算3 , A×B mod C (4/4)

大雑把に言うと4分の一のトランジス数で同じ性能がでる効率のいい方法ということになるのです。

僕のSnakeCubeは、A,B,Cのbit長と同じ大きさの演算器を用意します。 そしてA×B mod Cを前半と後半の2回にわけて演算します。大雑把な説明なので、厳密には違うのですが、だいたいこんな感じ。 uの計算は後半の演算が開始されるまでに終わっていればいいというところがポイント。
1 A×B mod C 前半
2 A×B mod C 後半
3 uの計算1
4 uの計算2 A×B mod C 前半
5 A×B mod C 後半
6 uの計算1

SnakeCubeは欧州方式の2倍のトランジスタ数を使っていますがuの計算による演算器の空き時間が小さいのです。 さらにRSA暗号ではA×A mod CとA×B mod Cの計算が連続するためAとCのレジスタを共用しながら、 同時にA×A mod CとA×B mod Cの計算をさせることで「uの計算による空き」がなくなるようにします。
1 A×A mod C 前半
2 A×A mod C 後半
3 A×B mod C 前半 u1の計算1
4 A×B mod C 後半 u1の計算2
5 A×A mod C 前半 u1の計算3 u2の計算1
6 A×A mod C 後半 u2の計算2
7 A×B mod C 前半 u3の計算3 u1の計算1
8 A×B mod C 後半 u1の計算2

SnakeCubeは欧州方式の2倍のトランジスタ数を使っていますが、演算器がuの計算で空きになることがありません。 効率的に演算できています。またSnakeCubeではuの計算結果を配送する 遅延時間を短くする技術で欧州方式よりも高周波数で演算器が動作します。 さらに、欧州方式では鍵を大きくしていくとu配送の遅延時間が大きくなるため、効率が下がっていくのですが、 SnakeCubeでは、鍵が大きくなっていってもu配送の遅延時間が変わらないので鍵が大きくなっていくと差が大きくなっていきます。
両者をXilinxのFPGAで比較するとSnakeCubeのほうが約2倍の周波数で動作します。
つまり理論的な性能でSnakeCubeは欧州方式の4倍の性能です。


欧州の論文の方法と比較(2)

欧州論文の実装で使われているXilinxのDSPはDSP48E1です。 これは僕が昨年、SnakeCubeを Artyに実装したものと同じなので比較しやすいです。 仮に欧州論文の方法をSnakeCubeと同じArtyに実装した場合、SnakeCubeが何倍速いのかを予測します。
SnakeCubeはプロセッサがついているのでCRTが使えて演算器は1024bit×2個になります。 欧州論文にはプロセッサがついていないのでCRTが使えないため2048bitの演算器になります。 このためArtyには1個しか入らないと予想します。 SnakeCubeは1つのRSA2048bit(decrypt crt)の計算に2個の演算器を並列動作させて演算できるので2倍速い。
CRTを使うので理論的に4倍速いのですが演算器の幅がSnakeCubeは半分なので2倍速い。
昨日の結論から方式性能4倍ですが、ブログのほうの結論を使うと3.2倍。
2×2×3.2 = 12.8倍
同じArtyでSnakeCubeのほうが12.8倍速い、ということがあり得る。圧倒的かも。


暗号プロセッサ OpenICF3