暗号計算機屋のブログ

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

IT業界で数学の才能が何の役に立つか

取り合えず僕に数学の特技があると思って聞いてもらえるといいと思います。😉

1999年の暗号LSI ICF3の開発で僕がモンゴメリ乗算を採用することに反対した理由を説明すれば、数学の才能が役に立つということが、わかるように思います。

ICF3を開発した部署は、ハードウェアの開発部なので電気・電子系の学科の人が多いのですが、現在の教育のようにRSAの数学について、知っている人は、いませんでした。研究所とは異なり頭を空っぽにして、全力で、最小限の工数で、開発を達成させることが仕事なのです。特に隣の大型コンピュータの開発部隊と異なり1年に1機種を開発するという無謀なことをやっていました。隣では4年に1機種というペースでやっています。なので勉強なんてさせてもらえず成果だけ出すという苦しいことをやらされます。1年に1機種が可能なのは、それなりの学歴の年配の方々が控えていて、できなければ、切り捨てられてしまうからです。

そんな中、新規にRSA暗号LSIを開発することになった。検討を進めて方式が決まりそうになったところで日立のシステム開発研究所から海外の暗号の教科書がFAXで送信されてきた。22ページだけ抜き取ったものでした。モンゴメリ乗算を使ってRSAを実装できないかということだった。研究所の人が必要だと思った、バラバラの箇所の22ページで、最後の2ページにモンゴメリ乗算の式が、書かれていた。「14.3.2 Montgomery reduction」のところです。 そこから2日かけてRSA暗号の計算方法を、作り上げたわけです。実は教科書のアルゴリズム14.94にRSA暗号の計算方法があったのですがFAXには入っていませんでした。研究所の人は、ちゃんと読んで送っているのか、疑いました。😀 ただし、ハードウェアでは14.94の方法では難しくて、どのみち自身でRSA暗号の計算方法を作り上げる必要がありました。

モンゴメリ乗算の公式14.36 --- x・y・R-1 mod m

R-1は、引く1ではなくてマイナス1乗です。RSA暗号の計算で、R-1が消えるように、計算していけば、答えがでるだろうと予測して、C言語で、試してみたところ、正解が得られました。

ここで数学の才能の有無によって、判断に違いが出てくるのです。R-1という記号が、自分が知っている-1なのか、あらゆる値で、正しい答えが計算できるのか、教科書の読んでないところに、特異点が存在するみたいなことが書かれてないか。

大学1年のときの数学で整数論を習っていたのを思い出した。10年前に習ったことで、加減、乗除を定義して、それが閉じるのか、どうか、という講義だった。モンゴメリ乗算という定義が、閉じているのか、それを確認する必要があった。

ただコンピュータを作りたいと思う電気工学科が、整数論を、しっかり覚えていたわけではなく、特異点が存在しないか、おろおろ、やっていた。最初、感覚的に問題を感じ、自分がわかっていないことが、わかったのだが、徐々にわかっていないところが、何なのか、明らかになり整数論にたどり着いた。

ソフトウエアの開発では、間違いがあれば、バージョンアップをすればいいという考え方もありますが、ハードウェアの開発では、1回の間違いが致命的な損害になることもあり、数学の才能はIT業界で役に立つということになると思います。

以下はFAXで送信された教科書です。サンプル無料とありますが、全部あるようです。

cacr.uwaterloo.ca

2018年4月19日追記

この話は「車輪の再発明」ではなくて、なんかやってみたら正しい答えになるから大丈夫だと勘違いをしている可能性があることを問題として認識できるか?という点です。 自身で計算方法を作っていますから、公式が、正しい条件で運用されているかを、厳格に考えなければならない。 割算(÷)の記号が使われていても、実際の演算はユークリッド互除法だったり、べき乗剰余演算だったりするのです。大学の数学は。

ついでの話になりますが、この国には自分で考えたほうが、海外よりも、できる回答になる人がいることを、頭の中に入れてもらえないかと思うのです。

1997年 東大の「疑似非同期式マイクロプロセッサ」

僕は1994年に日立 中央研究所 超高速プロセッサ部に入ったが、次の年には超高速プロセッサ部は無くなった。プロセッサを作るやつは「犯罪者」であり受刑者のような雰囲気だったのは確かだ。そして僕はIBMのCPUを買うための仕事にとりかかった。

1996年、大学などの研究機関向けにVDECが設立されLSIの試作、研究が行えるようになったようです。VDECの年報、1996年と1997年を読みました。東大のプロセッサのための研究が、いくつか掲載されています。 この頃は、パイプライン段数を増やす、スーパーパイプラインという思想で、周波数を上げる技術の研究が盛んだったようです。加算器をパイプライン化する研究や、加算する値によって計算時間が異なることを利用し、1~3サイクルで加算をする「疑似非同期」というアイディアがあったようです。

僕のICF3-Vの「疑似パイプライン」は面積当たりの性能を向上させるためパイプライン段数を削減しつつ、パイプライン効果を得る方法なのだが、それは、おいておいて、実は「疑似非同期」も検討していた。

東大の疑似非同期の対象は加算器で、入力値によって変化する終了検出が必要だった。僕の疑似非同期は、除算が対象。除算支援ハードのために全体の周波数が落ちているのだ。除算演算をする場合、32bitの2命令を1サイクルとするみたいな、決まり事を作るだけ。値による終了検出はしないので、簡単。除算の性能が下がるが、決まり事を作るだけでハードウェアの変更の必要はない。同一のハードで、除算の性能が下がっても、周波数を上げたい場合、ソフトウェアのほうで対応する。

VDECの年報は基本的には教育を含め、学生が短期間に試作しているものだが、中には、興味あるものもあるかもしれませんね。 1998年以降も、ちょっとみてみようかな。

http://www.vdec.u-tokyo.ac.jp/REPORT/vdecreport.html

MicroBlaze性能評価

目的

手っ取り早く自作CPUの性能を評価するためMicroBlazeと比較できるようにする。ベンチマークは自作CPUの性能を測るプログラムを簡単にするため、あまり意味はなく四則演算や論理演算、シフト命令が適当に入るような小さいものを自作した。FPGAの経験は浅いので結果についての取り扱いは注意されたし。

MicroBlazeの構成

FPGAバイス : Artix-7 35T Arty

性能型 面積型 最小型 MCS型
Predefined
Configuration
microcontroller Minimum Area Minimum Area -
implementation
optimization
PERFORMANCE AREA AREA AREA
クロック 166MHz 166MHz 166MHz 166MHz
WNS 0.04 ns 0.01 ns 0.02 ns 0.01 ns
Debug Module
Enable
Barrel Shiffter
×
FPU × × × ×
Integer Multi MUL32 MUL32 × ×
Integer Divider × ×
Optimaization PERFORMANCE AREA AREA -
Enable Branch
Target Cache
× × × ×
S-RAM 32KB 32KB 32KB 32KB
追加IP AXI GPIO
AXI Uartlite
AXI GPIO
AXI Uartlite
AXI GPIO
AXI Uartlite
-

GPIOはArtix-7 35Tの基板上のLED 4個と接続されている

実装面積

性能型 面積型 最小型 MCS型
LUT 1742 1512 1401 985
FF 1582 1274 1142 747
BRAM 8 8 8 8
DSP 3 3 0 0
LUTRAM 140 218 216 203

測定結果

パラメータ 性能型 面積型 最小型 MCS型
ループ数10000000
除算割合 10
7.9 秒 10.5秒 41.7 秒 51.0 秒

ベンチマーク プログラム

#include <stdint.h>
#include "xparameters.h"
#include "xil_printf.h"

#pragma GCC optimize("O2")

uint32_t xor(void) {
  static uint32_t y = 2463534242;
  y = y ^ (y << 13); y = y ^ (y >> 17);
  return y = y ^ (y << 15);
}

uint32_t xors(int loop,int div) {
    int i;
    uint32_t a,b,c;
    uint64_t w;
    uint32_t r;

    r = 0;
    for(i=0 ; i<loop ; i++) {
        do {
            a = xor();
        } while(a==0);
        do {
            b = xor();
        } while(b==0);
        do {
            c = xor();
        } while(c==0);

        w = a*b;
        if(i%div==0) w /= c;
        r += w;
    }
    return r;
}

#pragma GCC optimize("O0")

int main() {

    xil_printf("START!\n");
    uint32_t r = xors(10000000,10);
    xil_printf("%08X\n",r);

    return 0;
}

ベンチマークの演算結果

gccのオプションでハードウェア乗算器、除算器、バレルシフタの有無の設定ができる。MicroBlazeの構成をもとに正しくgccのオプションを設定する。乗算器がない構成で乗算命令を行うと演算結果が0になる。正しい演算結果になっているか確認する。測定したパラメータでは 次のような値になる。 0x3EEF270E

乗算の部分は32bit×32bit = 64bit のつもりで作成したが64bitにキャストしていなかったため32bit × 32bit = 32bitというようにCコンパイラは解釈するみたいです。結果の性能は32bitのままデータの再収取はしませんが、64bitにキャストした場合の期待値は

0xFC3BB111

Intel CPUとの比較

Intel Celeron E7500(2.93GHz)では0.13秒

2930 ÷ 166.667 ≒ 17.58倍 E7500の周波数を166.667MHzに換算した場合は2.3秒

考察

乗算器、除算器がある場合、性能は格段に向上する。乗算器のゲート数はASICでは大きなものになるはずだがFPGAではDSPで実装されるため注意する。性能型はパイプライン段数5で面積型はパイプライン段数3なので、性能型のほうが周波数が高くてもいいはずなのだが、今回は同じ166MHzだった。Xilinxのサイト見ても周波数の差は少ないので合っているものとも思われる。乗算命令とシフト命令のレイテンシが性能型と面積型で異なることが、今回の測定結果に反映されたのかもしれない。乗算命令のレイテンシは性能型で1、面積型で3。シフト命令のレイテンシは性能型で1、面積型で2。 MCS型はMicroBlaze MCSのこと。機能固定で面積をさらに小さくしたものと思われる。機能面では最小型とバレルシフタの有無が異なる。この結果、同じ周波数だが、バレルシフタがある最小型のほうが高性能になっているものと思われる。

追記 2018年4月14日 次のURLでMicroBlazeの乗算性能についての説明があって参考になります。

qiita.com

ICF3とICF3-Vの違いと、何ができそうかという話

ICF3をオープンにして2年近くになっています。そしてICF3が、これからどんな用途に使えるのか説明してきました。ネットワーク監視カメラのセキュリティに有用だと言った気がします。ICF3は1999年のLSIですが、世界一の高性能であったこともあり、廉価なIoTで使うにはゲート規模が大きかったかもしれない。そこで昨年、ICF3の1024bitの演算器を32bitにした小型のICF3-Vをフォークさせています。ICF3-Vは暗号プロセッサとしても使えますが、汎用マイコンとしても使えます。ICF3-Vの、だいたいの設計は、できていますが、現在、実装をFPGAでして検証を行なおうとしています。

ICF3-Vは家庭用ルータやセンサーデバイスをネットワークに接続する目的で効果的なんだと思っています。暗号演算に必要最低限の命令と疑似パイプラインによってゲート数を少なくすることができて製造原価を下げることが可能(予定)だからです。疑似パイプラインは従来のパイプラインアーキテクチャと異なるアーキテクチャ

ICF3-Vはハード制御信号を命令セットアーキテクチャになるようにしている。すべての命令をハードで処理するには、ゲート規模が大きくなるので、複雑な命令はマイクロコードで処理する方式。ハード制御信号の命令とマイクロ実装の命令を、同一命令ストリーム上で処理する方式。32bitのハード制御信号は、制御情報とオペランドを含む、冗長なものになるため、オペランドが短い。これがマイクロ実装の16bit命令でのオペランドに一致させることを容易にした。性能が必要な場合はハード制御信号の命令コードによる、疑似パイプラインで、高速化。メモリを節約するためには16bit命令を利用する。16bit命令は、ユーザーが自由にプログラム可能で、アプリで必要なものだけ実装すれば良く、少し手間がかかるが、製造原価を下げる目標には、適しているように思う。

これが現状のマイコンの効率を上回っていると仮定する。

今後、これを上回る効率のものが考えだされなければ、ICF3-VのセンサーIoTは、1度作れば、半永久的に売れるみたいなことはあるのではないだろうか? 例えばバッファローのBBR-4MGは、販売開始から、10年くらい経過していると思いますが、現役みたいですし。

openicf3.idletime.tokyo

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はコストパフォーマンスに優れる暗号プロセッサ。