ICF3のモンゴメリ演算器の図、初公開

1999年のICF3の開発で日立の研究報告書に掲載されたもの。僕が担当して書いた部分から引用しました。インターネット上では初公開だと思う。日立が別途、インターネット上で公開していなければですが。 山形大学 城戸淳二(早稲田 理工OBらしい)さんの白色有機ELがノーベル賞の候補に上がるようになったとのことだ。Web上の研究室の研究内容には次のように書かれている。

有機半導体はその分子構造により無限のバリエーションを持ち、新しい材料の登場によってデバイス性能が飛躍的に向上する。

モンゴメリ乗算も、基数(2とか、2の2048乗とかの数字)によって、多くのバリエーションを持つ。このため自動生成でRSA暗号プロセッサを作る論文もあったようだ。

情報処理学会論文誌 Vol.51 No.9 1847-1858(Sep.2010) ■推薦論文■ RSA暗号プロセッサ自動生成システムの設計と評価 (ルネサス、日立中央研究所、東北大学)

この論文、製品実装できるレベルのものが自動生成できているとは思えないし、自動生成しやすい実装になっている時点で、最高性能は期待できないと思っている。いくつかの基数に絞って、それに最適な実装を開発したほうが、いいのではないだろうか。

さて、モンゴメリ乗算は炭素に例えることができる。炭素はダイヤモンドになったり、グラファイトになったりするのだが、モンゴメリ乗算も基数によってダイヤモンドの結晶構造や、グラファイトの結晶構造になる。原子＝ANDゲートやORゲートなどの論理素子、と考える。論理素子の結合の仕方が、結晶に似ているという話。 昔、金沢大学だったろうか、２次元の結晶構造をもつRSA暗号演算器を研究していたように思うが、いろいろなところで、いろいろ研究されている。ICF3は１次元の結晶構造だが、これらをグラファイトに例えることができる。 一方、高基数のモンゴメリ乗算は３次元の結晶構造になりやすく、ダイヤモンドに例えることができるのです。高基数は理論的には高性能なのだが、実際にLSIの2次元平面状に配置して、RSA暗号の全工程を、計算させるには、非効率になる場合が多い。 IoTの暗号プロセッサとしてICF3のグラファイトの結晶構造が、今でも、有利だと思っているのです。

演算器の図を解説すると、これは4bit分のモンゴメリ乗算器。一番、左の1bit分の演算器が、少し他と違っている。2048bitの演算器を作っても、異なるのは、一番、左の1bitだけ。

IoTの原価を下げる暗号プロセッサICF3

背景

ICF3はIoTデバイスに搭載する暗号プロセッサとして1999年製ながら奇跡的にジャストミートしています。その理由については、これまでいろいろ説明してきました。ここではIoTデバイスの原価を下げる暗号プロセッサについての説明です。

要点は２つ

モンゴメリ乗算や中国人剰余定理などの海外の暗号演算アルゴリズムをなるべく使わないこと。海外の暗号演算アルゴリズムを使うと国産プロセッサとしての成果が海外に流れるので結果的に原価があがるということ。

ファームウェアの変更だけで暗号演算アルゴリズムを入れ替えて用途に応じた性能のアルゴリズムを選択できるようにする。
性能のコントロールだけでなくRSA暗号、楕円暗号の２つに対応すること。

IoTデバイスでは高性能な演算器、高性能なアルゴリズムよりも秘密鍵を漏洩させない暗号プロセッサが重要なのです。そしてCPUと比較して少ない資源、トランジスタ数で実装できること。

1999年製なのに、どうしていろいろ対応できるの？

ICF3は1999年製ですがメインフレーム向けに開発されたため複数のファンクションを格納できるプログラムエリア(32bit×512ワード)がありました。IoT製品では、そのIoTで使う１ファンクションだけ実装すればいいので、プログラムを駆使することで、様々なことができることが、その理由です。

ICF3の1命令は、A,B,Cの３っつの1024bit演算レジスタを連結して1bit左シフトしながらA-Dの演算をしてA>=Dなら結果をAに格納して、引き算したことをCレジスタの最下位bitに記憶しておけるというようなことが可能な命令セットで、一般のCPUの命令セットとは異なり、場合によってはかなり効率的です。一方で汎用レジスタのコピーには3命令が必要。コピーしながら他の処理は可能。特定の演算を高速化するための機能が、プログラマの技量次第では、別なことにうまく使えて、かなり短いコードが書ける。

アルゴリズムと性能値

性能値は1999年のICF3のLSIの実測値と完全に同じ値が計算できるシミュレータで計算したもの。シミュレーションしていない予測値もあります。(←それでも、かなり正しい数字)
ICF3は0.27μの設計プロセスでした1999年では高価でしたが、現在では安価になっていると思うので、この性能値はかなり参考になるものだと思います。

RSA 2048bit

暗号演算アルゴリズム	性能	試作コード有無
モンゴメリ乗算＋中国人剰余定理	13.4ms	○
中国人剰余定理	100ms
モンゴメリ乗算	473ms	○
海外アルゴリズム無し	980ms	○

RSA 4096bit

暗号演算アルゴリズム	性能	試作コード有無
モンゴメリ乗算＋中国人剰余定理	1000ms	○
中国人剰余定理	2000ms

モンゴメリ乗算や中国人剰余定理について

詳しく知りたい人はWikiのモンゴメリ乗算や中国人剰余定理を見て欲しいのですが、モンゴメリ乗算はアメリカ人のPeter Montgomeryさんが1985年に発表したものです。中国人剰余定理は、どうも中国人が大昔に発明していたものらしいです。中国人剰余定理がIoTの原価を上げるか？という疑問はあります。しかしながら中国人剰余定理を使うと、実質的には、ほとんど影響しませんが、計算できないケースがあるので、使わない選択はあると思います。

まとめ

ICF3は海外アルゴリズム無しでもRSA 2048bitで1秒を切る性能がでるのでICF3は純国産の暗号プロセッサとしても考えることができて、原価の安い暗号プロセッサです。ファームを入れ替えるだけで性能やアルゴリズムを変更できるため、これ１つで様々なIoTデバイスに対応できます。その結果、IoTの原価が下がる。

2017年6月13日 22:10 追加
性能値はファームウェアの改善で性能があがる場合があります。
ICF3は1024bitのモンゴメリ乗算器が2個ついています。簡単に取り外せます。場合によってはモンゴメリ乗算器をはずしたICF3も考えられると思います。モンゴメリ乗算のアルゴリズムを使っていてもモンゴメリ乗算器を使っているとは限りません。モンゴメリ乗算器を使っているのは表のうち一番上の13.4msのものだけです。

モンゴメリ乗算のアルゴリズムを使わないICF3

背景

ICF3はモンゴメリ乗算器を搭載した暗号プロセッサで1999年に製品化、RSA暗号の性能で世界一でした。 現在、IoTデバイスに入れる電子証明書の秘密鍵を暗号プロセッサ内で演算させ秘密鍵を漏洩させないことでセキュリティを向上させたいという需要が沸いてきています。 運よく過去のICF3が、そのまま使えるという状況ですが、IoTデバイスの価格を抑えるためモンゴメリ乗算などのアルゴリズムを使いたくない、そういう需要もあるかもしれません (海外の技術に頼らず日本だけの技術の暗号プロセッサがいいというような)。 またIoTデバイスの価格を抑えるには楕円暗号よりはRSA暗号が有利であるためRSA暗号ができないといけない。 そういう条件をICF3は、満たすことが可能なのです。

https://openicf3.idletime.tokyo/

２つの選択

ICF3は暗号プロセッサなのでモンゴメリ乗算器を使わなくてもRSA暗号などの公開鍵暗号の演算が可能です。もちろん性能は落ちます。 まだマイクロコードの実装はしていませんが、おおよそRSA 2048bitで100ms弱の性能です。IoTデバイスの用途では、この性能で許容できるものは多いと思われます。 一つ目の選択はモンゴメリ乗算器を取り外したICF3を開発すること。もう一つの選択はハードウェアはそのままで、マイクロコードだけ変更してモンゴメリ乗算を使わない方法。 どちらの選択が有利になるのかは、時と場合によるのかもしれないので、有利になる方法を選択します。

モンゴメリ乗算器はプロセッサ部に食い込んだ実装になっていないので、取り外しは容易です。

モンゴメリ乗算がないと他の暗号プロセッサより性能低いのでは？

確かにICF3はモンゴメリ乗算器を使うことを前提とした暗号プロセッサなので、他の暗号プロセッサより性能が落ちることはあるかもしれません。 しかし現在のIoTデバイスで沸いた需要は暗号プロセッサ内で演算させることで秘密鍵を漏洩させないことなので、性能が必要ない場合が多いのです。 用途によっては、シビアなレスポンスが必要になって性能が要求される場合もあると思います。 そういう場合には、モンゴメリ乗算器を使ってRSA 2048bitを13.4msで演算させることができます。

ICF3の暗号プロセッサってCPUなの？

まずICF3の暗号プロセッサにはパイプラインはありません(フェッチ、デコード、実行みたいなステートがない)。またメモリもなくて16本の汎用レジスタを使って演算します。 もうそれだけでCPUの技術のほとんどが関係なくなっていると思います。 ICF3は32bitの命令セットのようですが、実は、制御信号の集合体なだけで、CPUのような命令コードが単一の意味をもつ命令セットとは異なります。 少ない制御信号で、様々な演算が可能であることが、ICF3の特長であり、CPUの技術とはあまり関係していないということです。

2017年6月5日 3:20PM 追加

次のURLにモンゴメリ乗算器 0個(汎用演算器で演算)の性能がありますが、これはモンゴメリ乗算器は使っていないものの、マイクロコードでモンゴメリ乗算のアルゴリズムを使っている場合の性能値になります。 この投稿で言っているモンゴメリ乗算のアルゴリズムを使わない性能値とは異なるので、注意してください。 モンゴメリ乗算のアルゴリズムを使わないRSA 2048bit(中国人剰余定理)は前述しましたが、100ms弱の予想です。

https://openicf3.idletime.tokyo/soft/impstatus.html

暗号プロセッサ ICF3の日本のオリジナリティ

20年前の暗号プロセッサICF3

ICF3はモンゴメリ乗算というアルゴリズムを実装したLSIです。「なんだ海外のアルゴリズムを実装しただけじゃん」と思った人もいるかもしれません。そういう人のために。

ICF3 https://openicf3.idletime.tokyo/

Wikiでモンゴメリ乗算を調べると『特に時間のかかる除算を実質的に行うことなく、乗算・加減算・シフト演算のみで、高速に整数の積の剰余を求めることのできるアルゴリズム化』と書かれています。 LSIに簡単に実装できそうな日本語ですが、、、RSA暗号などの公開鍵暗号はビット長がとても長く、最下位ビットでの桁あふれが、最上位ビットにまで影響するので、分割して演算できません。 このためLSIの２次元平面上にどうやって回路を分割して配置するのかが難しい。

モンゴメリ乗算はPeter Montgomeryさんが1985年に考えたものです。このアルゴリズムには比較して減算をする処理があり、難しい処理ではありませんが、効率的に実装するとなると話は違います。 1998年にC.C. Yangさんによってこの比較減算処理をなくした改良モンゴメリ乗算が論文発表されました。

1999年に製品化されたICF3は、改良型ではなくPeter Montgomeryさんのモンゴメリ乗算を使っています。ゼロに近い追加回路の比較減算回路を発明して実現されています。RSA暗号の演算をするにはモンゴメリ乗算以外の処理も必要です。モンゴメリ乗算以外の処理は、専用演算器では効率的に実装するのが難しいためCPUに任せてしまう場合が多く、暗号プロセッサとしたい場合には、回路規模が大きくなってしまう問題がありました。 ちなみに1999年頃に製品化されていたIBMのメインフレームの暗号LSIや、SSLアクセラレータとして数多くの製品に組み込まれたFastMapというLSIには、モンゴメリ乗算は使われていませんでした。そしてFastMapはCPUと専用演算器という構成でした。

ICF3は比較減算処理とモンゴメリ乗算以外の処理を非常にコンパクトな回路に収めることに成功したことが日本のオリジナリティです。 コンパクトなわりに、プログラムによって、いろいろな演算が可能で楕円暗号もなんとか計算できるほどでした。

プログラムによってRSA 2048bitや楕円暗号が可能なことから、現在のIoTデバイス向けの暗号プロセッサとして、再び活躍できそうなのです。 もともとRSA 1024bitを演算するための回路ですが、RSA 2048/4096などの現在のIoTの要求仕様をピッタリ満たしているためICF3は20年前よりも価値が上がっているという不思議を起こしている。

詳しくは

「20年前のLSIがなぜ役に立つのか」

2017年6月5日 6:30AM 追加 1998年のC.C.Yangによる改良型で比較減算処理を不要にしても、結局、大型加算器が残ってしまう場合が多く、それなら、C.C.Yangやめて、大型加算器を、ほんの少し改良して比較減算回路にしたほうがいい。 C.C.Yangは鍵長のビット数より演算器のビット長を2ビット長くする必要があったり、それにともなってモンゴメリ乗算の処理時間が長くなる。b=2ⁿのケースでは2cyc長くなるのだが、これは大型加算器による比較減算1cycと同じ時間だ。C.C.Yangでは鍵長より1bit大きくなるためCPUで例えるなら33bitアーキテクチャとか65bitアーキテクチャになり、実装が煩雑になるので、このことは楕円暗号では改良型にとって厳しい問題となる。

2017年6月5日 7:00AM 追加 RSA暗号のみでいい場合には次の論文が参考になるがCRT(中国人剰余定理)をどうしても使いたくないケースでは役に立つかもしれない。実際にはCRTが許容できないケースは稀だと思うので、実用性としては乏しい。ICF3のようにCRTを使って演算器の２倍の鍵長が演算できるほうが、いろいろな他の演算もできることも含めて、回路規模的にICF3のほうが有利。

A New Modular Exponentiation Architecture for Efficient Design of RSA Cryptosystem - IEEE Journals & Magazine

2017年6月5日 7:30AM 追加 ICF3の比較減算回路はゼロに近い回路で回路規模が小さいということも、そうだがむしろ、比較減算回路のおかげで大型加算器に密着しているレジスタの数を減らし、RSA暗号の演算がやりやすくなっている効果が大きい。

2017年6月5日 7:45AM 追加 モンゴメリ乗算のアルゴリズムを題材にした論文は多い。C.C.Yangのようにアルゴリズム自身に改良を加えた「改良型」もあるが、オリジナルのアルゴリズムの範囲内でパラメータ(基数)を、いろいろ変更したものがある。しかもパラメータによって回路が全く異なるものに変化する。この両者を区別できてない人は、いるかもしれない。ICF3は基数として2を選択しているが、最近の論文では高基数(2の10乗とか2の20乗など)のものが多い。しかし高基数は乗算器のところでブースのアルゴリズムが使えるので理論的な効率は、あがるものの実際に実装してみるとRSA暗号を全体を演算させるとレジスタや制御論理が膨れ上がって実用化が厳しい場合が多い。それでも高性能が要求されるサーバーでは高基数の需要があるかもしれない。回路規模の効率を改善することができても絶対規模を小さくするのが難しいと予想している。したがってIoTやモバイルなどの用途では、そこまで高性能は要求されないので回路規模が小さく、簡素な回路で移植性が高い、ICF3が優位だと考えます。モバイルでは単価が高いので暗号プロセッサの選択は技術以外の要因で決まるかもしれない。またICF3の高い移植性はIoTでは有利だがモバイルでは、それほど有利にはならない可能性がある。ICF3の優位性についてはIoTで考えてほしい。

nhira型モンゴメリ乗算アルゴリズム

とりあえず

この証明だけは、まだ、役に立つかも。というところ。

はじめに

RSA暗号を高速化するためのアルゴリズムとしてモンゴメリ乗算が有名だが、その改良型がC.C.Yang(IEEE 1998)によって論文発表された。それをもとにDesign Wave MagagineのRSA暗号コンテスト(2008年)で実装されたものが記事になっていた。それをヒントに、この参考文献の14.36のモンゴメリ乗算を改良したnhira型モンゴメリ乗算のアルゴリズムを説明する。自身が作ったアルゴリズムだがC.C.Yangと同じかもしれない。C.C.Yangの論文を取り寄せる前に自身で証明できてしまったため、C.C.Yangの論文を読む必要がなくなった。

ちなみにDesign Wave Magagineはモンゴメリリダクションを使ったモンゴメリ乗算にC.C.Yangを導入した感じだが、これは乗算とリダクションを同時に行うモンゴメリ乗算にC.C.Yangを導入した感じだと思っている。

nhira型モンゴメリ乗算

【解説】　

xの範囲は2m-1までなのでは必ず0。　わかりやすくするためb=2として説明する。 　Forループで0≦i≦n のとき0≦A＜3m-1 とした場合、次のAの値の範囲は、2.2の式から　(3m-2 + 2m-1 + m) / 2 = (6m-3) / 2 = 3m-1.5 以下なので0≦A <3m-1 の範囲になる。　Aの初期値は0なのでi=nのループ終了時のAは0≦A＜3m-1　となる。Forループでi=n+1 のとき0≦A＜3m-1なので、次のAの値の範囲は 2.2の式から(3m-2 + m ) / 2 = 2m-1 以下、すなわち0≦A≦2m-1

【解説２】(2017年2月26日 追加)

オリジナルの14.36に対してx,yがmを超える値となっていて正しい結果になる理由は、14.36は14.32のモンゴメリリダクションと同じ計算しかしていないということ。14.32でを求めるタイミングまでにx×yを計算させて、最初からA=x×yであったのと同じ状態であればいい。14.32の定理でR=をR=とすればx,yが2m-1以下の範囲であれば正しい結果が得られる。

【参考文献】

Design Wave Magagineのコンテストの応募原稿にあった参考文献。(私は、読んでない)

(2017年2月27日 追加)

詳しく読んでないが、ここで説明するアルゴリズムを使って、やりたかったことが2008年のIEEEの論文になっていました。
↓↓↓これです↓↓↓

A New Modular Exponentiation Architecture for Efficient Design of RSA Cryptosystem - IEEE Journals & Magazine

(2018年2月25日 追加)

証明はだいぶ、省略して説明しているけど、問題ないはず。 こんな証明をした目的はOpenICF3と競合するアイディアを、自身で、潰してしまうこと。既出なら、これ以上、追う必要なし。