暗号計算機屋のブログ

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

1999年のICF3で楕円暗号を実装した社内資料の完全公開

f:id:icf:20171220073556j:plain 以前から、1ページ目だけ公開していたのですが全ページを公開しました。ICF3でビットコインなどに使われているECDSAを実装するのに、あると便利な資料だと思います。

著作権は平山 直紀にあります。 以下のURLからダウンロードできます。

http://openicf3.idletime.tokyo/summary.html#ICF3EC

1999年 ICF3 暗号プロセッサ ゲートレベルの全設計図 初公開!

f:id:icf:20171212061247p:plain

暗号プロセッサ ICF3は1999年に日立のメインフレームの暗号装置として世界に製品出荷されたLSIです。 当時、RSA暗号の性能で世界一でした。 ICF3の暗号プロセッサのゲートレベルの全設計図を初公開しました。 18年前、LSIのゲートレベルの設計での開発の様子が良くわかるのではないかと思います。

著作権は平山 直紀にあります。 以下のURLからダウンロードできます。

http://openicf3.idletime.tokyo/gatelevel.html

ICF3にはモンゴメリ乗算器が搭載されていました。以下のURLが参考になると思います。

http://icf.hatenablog.com/entry/2017/08/19/091112

最近はRTLレベルの設計が主流になっているのかもしれませんが、ゲートレベルの設計は、もう少し低レベルで難しいですが、すべてを人の手で制御し、高性能を得る感覚が、いいと思っています。 RTLレベルでの設計を極めることを好む方も、いらしゃると思いますけど。

SSLサーバー証明書の秘密鍵を調べてみた

暗号プロセッサ ICF3の用途は、IoT小型コンピュータであるが、さくらインターネットなどの専用サーバー(物理サーバー)も便乗できるのではないかと考えています。専用サーバーを利用する客はセキュリティを重要視する客であるためSSL証明書秘密鍵は、暗号プロセッサによって守られることが望ましいからだ。ただICカードのICチップの外付けでも実現は可能な範囲だからCPUのSoCに暗号プロセッサが収まるメリットがどのくらいあるかということになるか。 ICF3はコストパフォーマンスの良い暗号プロセッサだが、現在、主流となっているSSL 2048bitの、すべてのケースを高速に演算することはできない。 セキュリティ重視で性能が低くてもいい場合は、どんなSSL 2048bitも演算は可能だ。 暗号プロセッサ ICF3で2048bitを高速に演算するためには2つの素数が、どちらも1024bit以下である必要がある。そこでSSLサーバー証明書を調べてみた。

Let’s Encrypt 高速演算可能(2つの素数のいづれも1024bit以下)

AlphaSSL 高速演算可能(2つの素数のいづれも1024bit以下)

調べ方は、opensslコマンドを使って秘密鍵のファイルを解析します。こんな感じ

openssl asn1parse -in key.txt

key.txtがDER形式だとDER形式を指定する必要がありますし、場合によっては -offset で秘密鍵の位置を指定する必要があります。

Let’s Encryptは将来にわたって高速演算可能である保証はない。高速に演算できない場合の性能でも不都合がないシステムを構築すれば安全だと思う。1999年に製造したLSIをベースにした性能値だが、高速に演算できる場合は1演算 13.4ms。それ以外の場合は 379ms。

コストパフォーマンスに優れるICF3を使うには、高速に演算できるSSL証明書を確保する方法でもいい。 専用サーバーを利用するようなセキュリティが必要な人は認証レベルの低いLet’s Encryptを使うことはなくて、認証レベルの高い有料のSSL証明書になる場合が多いのではないだろうか。有料だと高速に演算できる形式のSSL証明書を発行してくれる場合が多いと思うし、恐らく、現状、多くのSSL証明書は高速に演算可能なものだと思う(多分) ということなら、あまり心配することも、ないのかもしれない。

まとめ、ICF3はコストパフォーマンスに優れる暗号プロセッサ。

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

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

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

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

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

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

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

f:id:icf:20170819090233p:plain

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

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

背景

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

要点は2つ

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

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

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

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

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

ICF3の1命令は、A,B,Cの3っつの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は純国産の暗号プロセッサとしても考えることができて、原価の安い暗号プロセッサです。ファームを入れ替えるだけで性能やアルゴリズムを変更できるため、これ1つで様々なIoTデバイスに対応できます。その結果、IoTの原価が下がる。

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

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個のモンゴメリ乗算器とすれば、現状の実装難度と同程度になるので、ほぼ実装できるのではないかと思う。 マイクロコードが完全互換でなくなるデメリットはある。

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

背景

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

http://openicf3.idletime.tokyo/

2つの選択

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弱の予想です。

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