暗号計算機屋のブログ

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

ICF3のRSA 4096bitの性能改善アイディア

背景

1999年のICF3でもRSA 4096bitは演算可能だが、ICF3が持つ専用演算器(モンゴメリ乗算器)は1024bitなので使うことができない。 このためRSA 4096bitの1演算の処理時間は800msと、かなり遅い性能です。 この性能でもIoTデバイスでは、使える場合も、多いと考えています。 しかしながらICF3はRSA 4096bitの性能が遅いからダメと考えている人がいると問題かと思い、RSA 4096bitの性能を改善できないか考えてみました。(というより、ふと思いついた)

前置き

このRSA 4096bitの性能改善アイディアの実現可能性は不明だが、可能性はあると思っている。

改善方法

ICF3は1024bitのモンゴメリ乗算器を2個持っている。 これを連結して2048bitのモンゴメリ乗算器として動作するモードを追加しようというもの。 連結なんて、できるのか?というのが、普通の反応だろう。 ICF3は基数2(低基数)のモンゴメリ乗算器なので連結するだけで2048bitのモンゴメリ乗算器になる。 あとは、他の論理のつじつまを合わせるのだが、回路規模は、ほとんど大きくならない。

RSA 4096bitの性能

約10倍の80ms程度になる見込み。あまり正確な数字は出せないが、それでもある程度、正しい予測値だと思っている。

まとめ

ICF3のハードウェアにほんの少し回路を追加するだけでRSA 4096bitの性能が10倍になるかもしれない。

2017年6月8日 9:10PM 追加

この方法だと配線の総数は、それなりに増える。 分散されているので、それほどでもないと思うが、配線の問題で実装できないことがあるなら、次のことを考える。 モードによって1024bit×2個、2048bit 1個に変更することをあきらめて2048bit 1個のモンゴメリ乗算器とすれば、現状の実装難度と同程度になるので、ほぼ実装できるのではないかと思う。 マイクロコードが完全互換でなくなるデメリットはある。