暗号実装の研究について
1 ：izuna五段：2016/06/17 20:50:30 (8年前) 0MONA/0人
暗号プロセッサのオープンソースハードウェア OpenICF3を公開したので
最新の暗号実装の研究動向を調べているけどOpenICF3よりも
すごい研究があれば、ここに投稿して議論しましょう。
OpenICF3
http://openicf3.idletime.tokyo/
2 ：izuna五段：2016/06/17 20:55:25 (8年前) 0MONA/0人
SCIS2016 2C4 暗号実装
「高基数モンゴメリ乗算器を用いたECDSA速度の最適化」
(東京大学大学院、他)
モンゴメリ乗算器の演算をパイプライン化することで、レジスタの面積オーバーヘッドのみで2倍のスループットを実現した。
3 ：izuna五段：2016/06/17 21:04:53 (8年前) 0MONA/0人
>>2
概要しか読んでないけど「高基数モンゴメリ乗算器」の演算をパイプライン化については1999年の暗号LSI ICF3の開発後、僕も、だいぶ研究した。
ICF3の監督だった東大卒(中央研究所出身)さんも、特許を書いていると思う。
OpenICF3と比較できると面白いかも。
ちなみにICF3は、低基数モンゴメリ乗算器でパイプラインしなくても高速化できるのが特徴かも。レジスタの面積のオーバーヘッドがないかわりに演算器自身のゲート効率はあまり良くない。
4 ：izuna五段：2016/06/17 21:19:54 (8年前) 0MONA/0人
>>3
> ICF3の監督だった東大卒(中央研究所出身)さんも・・・
ちなみに監督はICF3が持つ4っつの演算器の調停論理を担当していたので
ICF3のRSA演算器については監督業務のみ。
特許はICF3のRSA演算器の実装結果をもとに、ICF3の実装とは異なる論理を検討したのだと思う。
僕がいた当時も、ICF3の低基数(b=2)でなく低基数(b=3)とか、僕が正方乗算器がいいといえば、長方乗算器を研究するみたいな状態。
5 ：izuna五段：2016/06/17 21:31:23 (8年前) 0MONA/0人
SCIS2016 2C4 暗号実装
「並列化RNSアーキテクチャによる高速ペアリング実装に関する検討」
(横浜国立大学、他)
専用ハードウェア化が有望なアプローチであると捉え、ペアリング計算につき RNS(Residue Number System) の並列実装を含む高速化アーキテクチャを検討し良好な結果を得た
6 ：izuna五段：2016/06/17 21:36:20 (8年前) 0MONA/0人
>>5
RNSは東芝さんが、やっていたやつですか？
1999年のICF3の経験からRNSは、演算器の効率ばかりに、気をとられている感じで、暗号演算の最初から最後までの装置を考えると、大変だったような気がしている。
でも、良好な結果を得たと書いてあるね。解説できる人がいれば。
7 ：izuna五段：2016/06/17 21:59:09 (8年前) 0MONA/0人
>>2
> 「・・・を用いたECDSA速度の最適化」
ちなみにOpenICF3の速度調節は、２個あるモンゴメリ乗算器を
1個にしたり、0個にしたりすることでできる。
0個でも汎用演算器があるので暗号演算可能。
モンゴメリ乗算器をはずすのは簡単。
8 ：izuna五段：2016/06/18 01:21:27 (8年前) 0MONA/0人
2016年の東大の研究、SCIS2016 2C4 暗号実装 ( >>2 )
「高基数モンゴメリ乗算器を用いたECDSA速度の最適化」
抜粋
モンゴメリ乗算器の演算をパイプライン化することで、レジスタの面積オーバーヘッドのみで2倍のスループットを実現した。
1999年に暗号LSI ICF3を開発後、僕も高基数モンゴメリ乗算器の検討を「もう一度」した。 2016年の東大の研究の一文と合致する僕の当時の資料が見つかったので、公開します。 文章的には合致するけど、内容までは、どうだろう。
http://www.canal.mokuren.ne.jp/memo/icf4mont.html
9 ：izuna五段：2016/06/21 06:14:48 (8年前) 0MONA/0人
情報処理学会論文誌 Vol.51 No.9 1847-1858(Sep.2010)
■推薦論文■
RSA暗号プロセッサ自動生成システムの設計と評価
(ルネサス、日立中央研究所、東北大学)
高基数モンゴメリ乗算に基づくRSA暗号プロセッサアーキテクチャを提案し、
そのRSA暗号プロセッサを設計仕様に応じて自動生成するジェネレータの性能評価を示す
10 ：izuna五段：2016/06/21 07:02:56 (8年前) 0MONA/0人
>>9
PDFがインターネットからダウンロードできるので内容を詳しく読んだ。
「積和演算器の動作速度と回路面積の最適化」と書いてあるけど
制御ブロックも含めて最適化でないと物足りない気がする。
制御ブロックが演算器の２倍以上になる場合もある。
高基数のモンゴメリ乗算では逆数の計算があるが、専用回路を使うのか、どうかなどの情報がない。
基数が２、2^1024の評価がない。基数２は演算器の効率は悪いがパイプライン化しなくても高速なためトータルでは効率がいいのかもしない。
基数2^1024は自乗ケースでさらに効率を上げられるので自乗が多いRSAでは検討の必要がある。←これについては >>8 の資料をみるといい。
11 ：izuna五段：2016/06/21 07:16:55 (8年前) 0MONA/0人
>>9 その２
「積和演算器の動作速度と回路面積の最適化」と書いあったのは
この論文の前の資料だった。
基数を決めて、制御ブロックを最適化すると自動生成する場合よりも
回路面積が小さくなる可能性が気になる。
12 ：izuna五段：2016/06/21 07:32:26 (8年前) 0MONA/0人
>>9 その3
自動生成する論文よりは、基数２、基数２^8、基数２^128、基数2^1024の
４種類を全力で最適化して、その結果のほうが、いいような気がした。
性能をスケーラブルにする方法は、他にもあってICF3では
2個あるモンゴメリ乗算器を１個にしたり0個にすることで可能。
0個でも汎用演算器で暗号演算ができる。
13 ：izuna五段：2016/06/21 07:56:51 (8年前) 0MONA/0人
##################################################################
多少、攻撃的な口調になっていますが、本スレの趣旨の範囲ということで
##################################################################
このスレを立てた経緯のひとつに、16年前のICF3の技術など、とっくに
陳腐化しているという、批判を浴びたことがあるのです。
今、調べている範囲では、ICF3も、まだまだかなと感じています。
ぜひ、みなさんも、議論にご参加ください。
14 ：izuna五段：2016/06/23 20:45:54 (8年前) 0MONA/0人
日本の論文を調べているけど、あまりみつからない。
自薦、他薦は問いません。
これはと思う論文や製品があれば、こちらに投稿してください。
評価のポイントはSoCのCPUに追加できる暗号コプロで実際に製品化
できそうなもの。
公開鍵暗号の秘密鍵を守れることが必須です。
15 ：izuna五段：2016/06/24 09:10:29 (8年前) 0MONA/0人
IPSJ SIG Technical Reports 2006-CSEC-34(13) 2006/7/20
「コプロセッサの２倍のビット長をもつモンゴメリ乗算」
(日立製作所 システム開発研究所)
nビットのモンゴメリ乗算を実行するコプロセッサを用い、2nビットのモンゴメリ乗算を計算する手法を提案する。
16 ：izuna五段：2016/06/24 09:21:56 (8年前) 0MONA/0人
>>15
OpenICF3は1024bitのモンゴメリ乗算器を持っているので、この論文の方法を使えば2048bitのモンゴメリ乗算ができるかもしれない。
ただOpenICF3は汎用的なCPUのような機能はないので、できない可能性もある。
もし、この論文の方法で2048bitのモンゴメリ乗算を実装してRSA 4096bitを高速に演算できるようになるなら、OpenICF3が世界に普及していれば、マイクロコードの販売も、可能になるのかもしれない。
ただRSA 4096bitは、昨日、OpenICF3の汎用演算器を使って実装できてしまったので、これよりも、かなり速くないと、売れないだろう。
汎用演算器を使った場合、1999年のLSIの前提で約0.95秒
(中国人剰余定理を使用)
17 ：izuna五段：2016/06/26 13:17:35 (8年前) 0MONA/0人
東大の高基数モンゴメリ乗算器を用いたECDSAでないと、使いたくない
そういう人は、多いかもしれない。
ただIoT向けでは、性能よりも、いろいろできることのほうが重要かも。
東大の高基数モンゴメリ乗算器で、逆元の計算とか、中国人剰余定理とか、すべての実装を含めてどれくらいのゲート規模になるのか、わからないけど、あまり小さくならないような気がしている。
OpenICF3も、サーバー向けに開発したものだから、性能重視なんだけど、モンゴメリ乗算器２個を外しても、暗号演算可能だ。
モンゴメリ乗算器を外せば、実装面積が小さくなり、周波数があげられる。
汎用演算器を使ったモンゴメリ乗算でも、それなりに、性能が出るかもしれない。汎用演算器だから、逆数も、楕円も、RSAも、RSA 4096bitも、いろいろ可能だし、ゲート規模も小さいくて、コストパフォーマンスの、とても良いものになりそうな、気がしている。
18 ：izuna五段：2016/06/26 13:48:50 (8年前) 0MONA/0人
>>17 汎用演算器について
普通のCPUとの違いは、1024bitレジスタが4本とデータレジスタ16本で
約2命令で1024bitの掛け算とか、割り算とかが可能。
1命令が32bitだが、組み合わせで、いろいろな機能が実現できる
このため論理がシンプルでコード格納領域の効率がいい。
「汎用」だが、暗号演算に必要なものしかないため、非常に軽量な論理。
そして組み合わせで、いろいろなことが、できてしまう
という事実が開発後判明した。
19 ：izuna五段：2016/06/27 18:54:59 (8年前) 0MONA/0人
学会発表の実装が演算器の部分しか見えなくて足りないと
思っていたら、想定されている前提条件が違うのかもと思った
OpenICF3の元になったICF3はIBMのメインフレームのCPUの暗号コプロだった。IBMのCPUのコプロセッサ専用バスにICF3のLSIを接続するタイプだ。
このためCPUからの支援はなく暗号演算のすべてを自分で処理する必要があった。
ICチップのCPUのアクセラレータという前提であれば、モンゴメリ乗算だけできれば実用化が可能だということに、気が付いた。
「あまり意味のない結果ではないか」と疑ったことをお詫びします。
20 ：izuna五段：2016/06/27 19:03:34 (8年前) 0.00114114MONA/1人
>>20
スマフォとかタブレットとか、いろいろなアプリが動作するような環境
では、アクセラレータという機能だけでなく、やはり秘密鍵を守る機能が
欲しいところなので、暗号演算のすべてをCPUの支援なく、できることは
重要かもしれない。
21 ：izuna五段：2016/06/30 03:04:54 (8年前) 0MONA/0人
サイドチャネル攻撃に耐性のあるソフトウェア実装の論文がいくつかあるようです
ICカードのソフトウェア実装の話が多いですが、OpenICF3が普及すれば、OpenICF3のマイクロコードのソフトウェア実装の論文も出てくるのか？？？
22 ：izuna五段：2016/06/30 03:11:53 (8年前) 0MONA/0人
>>20 に関連して
CPUとアクセラレータで暗号演算する場合、CPUの分岐予測ミスの回数を
読み出して秘密鍵の解読の情報とするものがあるようです。
IntelのCPUだけかもしれないですが。
このタイプのサイドチャネルは、OpenICF3の暗号プロセッサを使えば
防ぐことができます。
23 ：izuna五段：2016/07/01 22:00:45 (8年前) 0MONA/0人
興味深い論文を発見
「べき乗剰余に適したモンゴメリ法による剰余乗算法とそれを実現するシストリックアレー」
一般社団法人電子情報通信学会 1993-08-20
古い論文で、概要しか読んでないが、ICF3のモンゴメリ乗算器はシストリックアレーに似ているかもしれないと思ったからだ。
【概要】
モンゴメリ法は除算を行うことなしに剰余乗算を演算する手法として知られており，モンゴメリ法を実行するシストリックアレーがいくつか提案されている．しかし，モンゴメリ法は出力のビット数が入力のビット数より大きくなる場合があるために，従来の手法はモンゴメリ法を実行するたびにその出力値の大きさを判定し補正する必要があり効率的ではなかった．そこで，本論文ではモンゴメリ法を行うたびの出力の補正を必要としないための条件を一般的に導き，その条件下でのモンゴメリ法を実行するシストリックアレーを提案する．
24 ：izuna五段：2016/07/01 22:21:54 (8年前) 0MONA/0人
>>23
> 出力値の大きさを判定し補正する必要があり効率的ではなかった
ICF3では、この補正を効率的に行うハードで解決されている。
四則演算ができる1024bit加算器を少し改造して1サイクルで処理する。
ICF3はデータパスも効率的に実装できていて
４つの1024bitのレジスタだけでA×BとA×Aの
２つのモンゴメリ乗算を並列に実行できるあたりも、
いいかもと思っている。
モンゴメリ乗算器がシストリックアレイのような感じで
パイプラインを必要としないから。
あまり比較できるものがないから、なんともだが。
25 ：izuna五段：2016/07/02 19:16:38 (8年前) 0MONA/0人
>>24
> ICF3では、この補正を効率的に行うハードで解決されている。
「信じられない」という人のために
暗号や数学の専門家は、計算機工学に明るくないのかもしれない。
計算機工学には、1つの変数を2つのレジスタで表現する技術があるのだ。
> 出力のビット数が入力のビット数より大きくなる場合がある
だから出力のビット数が入力のビット数より大きくならない。
計算中は2レジスタで表現して、最後に1レジスタにするときに
1回補正する。
26 ：izuna五段：2016/07/02 20:03:57 (8年前) 0MONA/0人
>>25
計算機工学を駆使して問題を解決した、、、ように見せかけたけど
本当のところは、高速化のために2レジスタ表現を使っていて
そのおかげで、たまたま補正するためのハードが簡潔なものとなった。
ということだったのだ。
27 ：izuna五段：2016/07/02 23:50:30 (8年前) 0MONA/0人
>>23 の論文も、シストリックアレイだから、もしかすると
２レジスタ表現を使っていて、単純に、補正するためのハードが
困難だと思っただけかもしれない。
28 ：izuna五段：2016/09/04 21:20:26 (8年前) 0MONA/0人
ICF3を開発したときに使った資料がインターネットで公開されていたので、ご連絡
http://icf.hatenablog.com/entry/2016/09/04/204806
29 ：izuna五段：2016/09/05 21:52:41 (8年前) 0MONA/0人
>>28
もう少し説明したほうが良かったか。
ICF3開発までの経緯とか、面白いと思うよ。
1998年9月11日、日立のシステム開発研究所から汎用コンピュータ事業部に送られたFAXの画像つき。
無料でPDFによるダウンロード可能(のようです)
http://icf.hatenablog.com/entry/2016/09/04/204806
30 ：七段教士：2016/09/05 22:03:39 (8年前) 0MONA/0人
公開されていたもなにも自分で公開しているんでしょ？
31 ：izuna五段：2016/09/05 22:05:54 (8年前) 0MONA/0人
>>30
いやいや、そうじゃないです。FAXの画像の英文の原書が、PDFでダウンロードできるのですよ。
32 ：七段教士：2016/09/05 22:07:00 (8年前) 0MONA/0人
そういうことね
ごめんごめん
お気に入り
新規登録してMONAをもらえた
本サイトはAsk Mona 3.0に移行しましたが、登録すると昔のAsk Monaで遊ぶことができます。