暗号プロセッサ 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と競合するアイディアを、自身で、潰してしまうこと。既出なら、これ以上、追う必要なし。

HDD再生の研究

失敗は成功のもと

HDDを廃棄して都市鉱山の利用研究をするよりHDDを再生したほうが地球環境にいい。そんなことを考えている。そして再生したHDDによってお金の節約も狙う。個人でわかる範囲で調べているため、もっと詳しい人はいるだろうが、もっといい情報などあれば、コメントいただけるとうれしい。

利用環境はサーバーではなく普通の環境だ。BUFFALOのUSB HDD(320GB)の調子が悪くUSB 2.0で接続されているにもかかわらず転送速度が300KB/Secに落ちることがあるようになった。HDD-SCANを使って調べると32個のバッドセクタが見つかった。2007年のWestern Digital製なのだがバッドセクタは散在するため、パーティションでバッドセクタを避けると容量が激減するため、なんとかバッドセクタを修復する無料のソフトを探した。あるにはあったが実際にやってみると「これは修復できません」ということだった。そこでついにHDD Regeneratorを購入することにした。購入についての経験は次節で述べる。32個あったバッドセクタのすべてを修復したが、フォーマットをするとタイムアウトすることが多く結局、Western Digitalの320GBのHDDの再生には失敗した。 そこで先日、HDDレコーダから取り出した再生したHDDと交換した。

2016年9月10日 追加 HDD Regeneratorによるバッドセクタの修復(リカバリ)は32個所のすべてで成功している。過去にHDD Regeneratorの無料版で何度もバッドセクタの修復してHDDの再生に成功している。今回は、たまたまバッドセクタ以外の故障によるものと思われる。バッドセクタがあってもファイルシステムの機能を使ってHDDを利用可能にすることはできるが、HDDの運用を考えるとバッドセクタを修復してしまったほうが便利。

HDD Regeneratorの購入についての経験

購入のページに移動すると自動的に円で購入できるが、左上にあるセレクトボックスでUSドルに変更する。相場にもよるのかもしれないが10800円が10200円で購入できたので約600円くらい安く買えた。Windows10対応みたいな表記があるが2011年版のようである。シリアル番号が送られてくるが、シリアル番号の名前とシリアル番号を入力しないとアクティベートできない。シリアル番号の名前はPayPalで購入したせいかもしれないが漢字が自動入力されて文字化けで困った。購入する前によく調べたほうがいいです。

世界一のRSA暗号LSI ICF3のアルゴリズム

アルゴリズムの解説ではなく僕が1998年にICF3の開発を開始したときに渡された資料の公開です。学生の頃は情報系の科目をメインに取っていましたが電気工学科の卒業ということもあり会社に入ってすぐの頃は電子回路シミュレーションをしていました。次にIBMのLSIの配線データを日立のLSIの配線データに変換するエクセル作業、大型コンピュータの基板の配線長の計算、夜間勤務でクロック周波数のマージン測定、アメリカでFAXを受信するだけの仕事、暗号装置の線表管理と、雑用が続いた。その後、暗号LSI ICF1の改造、暗号LSI ICF2の改造をするのだが、論理設計の勉強など全くしないで改造作業をした。改造している時間は長かったが基本的なことを知らずに応用問題をやっていた感じで、技術が身についていくような感覚はなかった。このまま雑用係としていくのかと思えば1998年のある日、課長に呼ばれ「RSA暗号の論理設計をしてみないか？」と聞かれた「え、やっていいんですか？」と返答したのを覚えている。普通は論理の勉強のため7セグメントLEDとかのサンプル回路とか作り始めるのかもしれないが、そんな時間が与えられるはずもなく、いきなりRSA暗号の演算器の絵を描き始めた。CPUっぽいものだったので周囲からはポンチウムと笑われた。ポンチ絵+Pentiumの合成語。だが徐々に精度が上がっていき加算器4個を同時に動作させる演算器ができてきた。周囲には「4IPターボ」とか笑われた。IPとは、この部署固有の言葉でCPUの意味。本格的に4IPターボを作ろうとしたときに、日立製作所のシステム開発研究所から次のFAXが届いた。

原書がインターネットでFreeで公開されています。FAXは14章の１ページです。

僕が数学科の卒業なら有限体を勉強していたはずで、もしかすると楽に読めたのかもしれないが、2日間、考えてFAXにある14.36のアルゴリズムからRSA暗号の計算方法を思いつくことに成功した。後から聞いた話、２日間で理解したのは評判になるくらい速かったらしい。 つい先日、原書がインターネットで公開されているという情報を教えてくれた人と話をして14.36を使う以外の方法でもモンゴメリを使ったRSA暗号の計算ができることを知った。ハードウェアで実装する場合と、ソフトウェアで実装する場合とで、若干、有利な方法が違うのだろうと思う。

2019年7月16日追記 FAXで送られてきたのは原書から抜き取られた22ページ。今、見るとDES暗号についての説明もあって、どういう基準で抜き取られたものなのか、現在も知らない。しかし肝心のRSA暗号の計算方法が書かれたページが抜けていた。このため僕が14.36のアルゴリズムからRSA暗号の計算方法を考え出す必要が出てしまった。

廃棄するHDDレコーダからHDD 80GBを回収

日立製作所 2003年製のHDDレコーダを放置していたがHDDが足りなくなったので、HDDレコーダから回収することに。 中を開けてみると、でてきたHDDはSAMSUNG製(韓国)だった。

日立すら買わない日立のHDDを誰が買うのだと思いつつ、日本のHDD事業について調べてみた。縮小傾向だが東芝がまだやっているようだ。少し調べたくらいで、どうこう言えるほどではない。

しかし、一般的な話として、強く思うことはある。

経営者からしてみれば、海外の安いHDDを導入しHDDレコーダの価格を下げたほうが、いいのはわかる。しかし、その結果、将来、HDD事業を撤退することになった。

経営者に、将来日本が困るから、HDDを買い支えるよう、指示する仕組みは、あるのだろうか？ なければ、同じことが、繰り返される。 日本人が愚かな民だと思いたくはない。

海外製のHDDに、リモートでHDD上のファイルを改ざんしてウィルスが発生する仕組みがあるかもしれない。 海外のHDDの工場にいって、1台１台製造に付き合っていたら、トータルで、割高になってしまうとか、なりそうで怖い。 なにか事業をしようとして、HDDの信頼性の問題に気が付き、割高くらいでは、すまなくなって後悔しまくることにならないだろうか？