暗号計算機屋のブログ

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

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

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

f:id:icf:20160904202228p:plain

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

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

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