|
ここ数日の日記に案1～案4を書いています。
案5、楕円曲線のスカラー倍算を断念してRSA 7680bit(2048bit)とDSA 7680bitの２つの公開鍵暗号に対応。
RSAの安全の根拠は素因数分解の困難性、DSAは離散対数問題の困難性を安全の根拠としています。
楕円曲線は楕円曲線上の離散対数問題の困難性を安全の根拠としています。
DSAも量子コンピュータによって解読が懸念される公開鍵暗号です。
案5のメリット 楕円曲線のスカラー倍算を断念することでICチップのマイクロコード量と
レジスタを大幅に削減して製造コスト削減。
楕円曲線を完全にスキップした数学コスト削減。
DSAはICF3(1999年)
でも対応した実績があるため開発コストが小さい。従来マイナンバーカードで使われているRSA 2048bitも可能。
案5のデメリット 新たに対応できる暗号アルゴリズムはべき乗剰余演算とモンゴメリ乗算を
使ったマイクロコードとレジスタの少ないアルゴリズムに限定される。
米国NISTのFIPS186-5でDSAが推奨からはずされました。
NISTからはずされた理由は、調べていませんが、EdDSAなどの新しい標準を追加したため保守コストの低減か？
日本のCRYPTRECではDSAを推奨している。
耐量子暗号が十分に安定するまでRSA 7680bit、DSA 7680bitのみで持ちこたえる判断ができれば、
RSA 7680bitに対応できるICカードの中では低コスト。
案6は、案5に米国NISTで新規に追加されたEdDSAをSnakeCubeの入出力担当のMCUで演算させる案。
EdDSAに詳しくないですが、非力なMCUでもEdDSAなら演算できるかも。
案7は、案5にCRYSTALS-Dilithiumのハードを後付け。CRYSTALS-Dilithiumが
動作するハードがあれば、楕円曲線を演算できる可能性はある。
ICチップのハードは最も高価なクラスになるが、安全を重視するなら、案7も可能性はるかもしれない。
僕が次期マイナンバーカードタスクフォースに呼ばれていないので、マイナンバーカードの要求仕様がわからないのですが、
ICカード内で鍵生成をする機能はコストが高いため避けられるなら、避けた方がいいかも。
事前に予備の鍵を１つ工場で入れて鍵生成しているフリが安価。
鍵が失効するトラブルが発生した場合、製造工場で新しい鍵を再度、入れる運用。
案5の開発はICチップの入れ物にハードを入れること以外、僕のわかる範囲内がほとんどですが、
案6、案7は他にわかる人が必要。
案5が選択できるなら開発期間も短くて、お薦め。
ただしRSA 7680bit、DSA 7680bitの双方が解読された場合の計画は必要。
RSA、DSAが解読されても僕は責任を持ちません。
RSAだけだと、RSAが解読されそうというニュースがある度に、辛くなるけど、DSAがあれば心配がなくなる。
日本のCRYPTRECのDSA保守のコストは、あるかもしれない。
参考までに言えば、ICF3(1999年)のDSAのマイクロコードはIBMの仕様(恐らくFIPS186-4と同じ)を元に僕が開発したもの。
僕が2018年に発明した高周波数動作のモンゴメリ乗算器は暗号プロセッサSnakeCubeとして
2020年に試作が完成しています。
これと競合するSPL(Southern Programmable Logic Conference)の論文(2011年)が発見されたので比較をしてみます。
Montgomery Modular Multiplication on Reconfigurable Hardware: Systolic versus Multiplexed Implementation
https://www.hindawi.com/journals/ijrc/2011/127147/
著者のGuilherme Perinさん、Daniel Gomes Mesquitaさん、Joao Baptista Martinsさんは、ブラジルの大学の所属のようです。
この論文のSystolic演算器をSPL2011、僕の発明をSnakeCube2020とします。
SPL2011もSnakeCube2020も同じXilinxのFPGAに実装されているため比較しやすい。
[SPL2011]
プロセス : 65nm (Virtex-5)
DSP48E最大周波数 : 450～550MHz
DSP48E : 130個
[SnakeCube2020]
プロセス : 28nm (Artix-7)
DSP48E1最大周波数 : 464MHz
DSP48E1 : 45個 ( 1032bitのモンゴメリ乗算１個分 )
DSP48Eの最大周波数から、同程度の能力を持つFPGAデバイスと推定します。詳しい人があれば、教えてください。
SPL2011はVirtex-4時代の設計のためDSP48Eの乗算器24x17を16x16として使っているため130個ですが換算すると87個。
DSP数の比較からSnakeCube2020はSPL2011の半分のトランジスタ数と推定。
[SPL2011]
RSA 1024bit(wo/CRT Decrypt) : 3.23ms
周波数 : 130MHz
モンゴメリ乗算1回のサイクル数 : 384 (Square and Multiply)
[SnakeCube2020]
RSA 1024bit(wo/CRT Decrypt) : 1.74ms
RSA 2048bit(w/CRT Decrypt) : 1.74ms(モンゴメリ乗算器2個なので)
周波数 : 236MHz
モンゴメリ乗算1回のサイクル数 : 339 (Square and Multiply)
3.23 ÷ 1.74 ≒ 1.86倍
結論
SnakeCube2020はSPL2011の半分のトランジスタ数で1.86倍の性能。
SnakeCube2020はSPL2011の3.7倍効率が高い。
FPGAによる比較なのでASICでは誤差があると思われます。
ここ数日の日記に案1～案3を書いています。
案4は、安くないとSnakeCubeが導入されない問題を対策するため。
対応する公開鍵暗号を楕円曲線とRSA 2048bit(低速 wo/CRT)に絞ります。
オプションでマルチ・プライム RSA 3072bit(w/CRT 3 prime)、RSA 4096bit(w/CRT 4 prime)、
RSA 8192bit(w/CRT 8 prime)も可能と思われます。
案3のSnakeCubeのモンゴメリ乗算器を2個から1個に減らして、モンゴメリ乗算器も基数を変更して軽量化をします。
過度な軽量化は効率を悪化させるので、あまり軽量化はできないかもしれません。
従来マイナンバーカードと互換性を保つためのRSA 2048bitは低速ですが実際に使えるレベルだと思います。
現行のマイナンバーカードのシステムで3秒以上待たされることもあります。
これが5秒になっても、それほど大きな問題にはならないでしょう。
案4のメリットは既存のICチップの中身を知らないので、確かなことは言えませんが、
発明のモンゴメリ乗算器の効率が高いため、既存の楕円曲線とRSAの双方に対応するICチップよりも
(物質的な)製造コストは安い可能性があります。
案4のSnakeCubeを開発しておけば、他ではできない高性能化が容易なアーキテクチャなのでRSA 7680bitや、
要求性能が高い新しい耐量子暗号に、すぐに対応できる。
将来、世界でSnakeCube以外に要求性能をクリアできるICカードが無いという場合に備えられる。
楕円曲線も、将来的には1024bitに近い鍵長になることに備え、今後のICカードは1024bitの演算器を装備すべきと思われます。
過去のRSA 1024bitのために既に多くのメーカーで1024bitの演算器は開発されています。
しかし1024bitの演算器ではRSA 2048bit(wo/CRT)は演算できません。
(高速な汎用CPUを搭載していれば、そちらで演算は可能ですけれども)
案4のSnakeCubeは低速ながらRSA 2048bit(wo/CRT)を演算できます。
案4のSnakeCubeを開発する価値はあるように思われます。
8月25日 7:25PM 追記
モンゴメリ乗算のビット幅が実行時にスケーラブルなモンゴメリ乗算器の論文はあるようです。
楕円暗号とRSA暗号の双方で使える演算器。ただスケーラブルな機構にもリソースが
必要なので演算効率は低下するはず。
昨日の日記「SnakeCubeを成功させる別解(案3)」の補足です。
CRTによる脆弱性の無い低速なRSA 2048bitが実際に使える性能になりそうか？と思った人はあると思います。
結論を先に言えば、少なくとも互換モードのために遅いという認識があれば使えると思います。
性能予測は難しいのですがICチップにした場合、RSA 2048bit 1回、0.5～1.5秒程度には、演算できる予想。
予想の根拠となるICF3(1999年)のマイクロコードを次のURLで公開しています。
モンゴメリ乗算器を使わないモンゴメリ乗算をするマイクロコード(RSA 4096bit)などがあります。
ウェブ上のICF3シミュレータで動作しますが、遺跡巡りをする感覚で見てください。
https://openicf3.idletime.tokyo/soft/impstatus.html
SnakeCube(2020年)はFPGAによる実装なのでASICの
ICF3(1999年)との違いを考える必要があります。
SnakeCube(2020年)のプロセッサと演算器のクロック周波数比は1:8ですがICF3(1999年)は1:2なのです。
同じ1024bit幅の演算器を持っていますけど。
ICF3(1999年)はビッグエンディアンですがSnakeCube(2020年)はリトルエンディアンなのでICF3のマイクロコードに慣れると、
SnakeCubeのマイクロコードで混乱するかも
8月21日の日記で案1、案2を説明しました。
案3も、案1と同じマイナンバーカードにSnakeCubeを導入する方法です。
案3は楕円曲線をメインとしてRSAと耐量子暗号(同種写像系)をバックアップにします。
メイン 楕円曲線
バックアップ1 RSA 2048bit(高速 w/CRT あるいは 低速 wo/CRT)
バックアップ2 RSA 8192bit(w/CRT、8 primes)
バックアップ3 耐量子暗号(同種写像系)
案3のメリットは楕円曲線を準備してきた人たちのために向いていること。
2020年の試作がほぼそのまま使えること。
1032bitのモンゴメリ乗算器２個を１つのプロセッサに接続するアーキテクチャなので、
ICチップに必要なトランジスタ数が少ない。
耐量子暗号(同種写像系)を1032bitのモンゴメリ乗算器、2個を使って独立した2つの演算を並列に計算可能。
案3のデメリットは従来マイナンバーカードと互換性を保つためのRSA 2048bitを演算できるものの、
演算方法にCRTを使う場合は脆弱性がある。ただ普通の人が利用する多くのサーバーが楕円曲線に移行していれば、
大きな問題にならない可能性が高い。性能が遅くても良い場合はCRT無しで演算することもできます。
その場しのぎの対策になりますがマルチ・プライムのRSA 8192bitも考えられます。
サーバーから見れば普通のRSA 8192bitと違いはありませんが素数の大きさがRSA 2048bitと同じ1024bitなので、
通常のRSA 8192bitと比較してかなり暗号強度は落ちます。
耐量子暗号のCRYSTALS-DilithiumをサポートしませんがICカード向けの耐量子暗号も
複数存在したほうがいいため日本のマイナンバーカードがその役目を果たすことになります。
同種写像系の耐量子暗号に要求される性能に合わせて開発します。
RSA 7680bitをサポートしませんが案2から案3に移行するケースでは、
案2でRSA 7680bitのICカードは製品化されることになります。
案2、案3と続けて開発をするため開発効率は良い。
案3のSnakeCubeは1024bitのべき乗剰余を2並列に実行することが最も得意なので、
それに適した耐量子暗号を考えると効果的。
これまで楕円曲線をスキップすることを言ってきましたが、案３ではスキップしないため、
全額分の楕円曲線コストがかかります。
しかし演算器のbit幅が7680bitから1032bit×2になるのでICチップの製造コストは下がる予想。
僕が2018年に発明した高周波数動作のモンゴメリ乗算器は暗号プロセッサSnakeCubeとして
2020年に試作が完成しています。
これと競合するIEEEの論文(2013年)が発見されたので購入(5,542円)して調べました。
A novel fast modular multiplier architecture for 8,192-bit RSA cryposystem
https://ieeexplore.ieee.org/abstract/document/6670320
著者のWei Wangさん、Xinming Huangさんは米国のウースター工科大学の人みたいですが中国人のようです。
この論文の説明は簡単で一言で説明できます。
モンゴメリ乗算の公式で基数を最大値にすると剰余算が乗算３回に変換され、変換された乗算をFFTで高速に演算する方法。
この方法をIntelに買収されたAlteraのFPGAに実装して評価したものが、この論文です。
僕は、上記の論文が正しいのかは、判断できませんが論文に記載されている数字を信用することにして
大雑把な比較をします。
SnakeCube 2020年のRSA 2048bitの試作からRSA 8192bitの性能とトランジスタ数を予想したものと比較。この予測は比較的、精密です。
僕のSnakeCubeの高周波数動作のモンゴメリ乗算器は低基数です。
そして最下位ビットからのブロッドキャストのクリティカルパスを短くすることに成功しました。
中国論文はモンゴメリ乗算の公式で乗算３回に変換しているので、そもそも最下位ビットからのブロッドキャストが存在しない。
ただし途中で２倍のビット幅に膨れるため恐らく配線実装に手間取ります。
SnakeCubeは演算中、ずっと等幅なので配線実装が容易です。
中国論文はRSA 8192bitを演算した場合、SnakeCubeと同程度か、それ以下かの性能です。トランジスタ数は3倍～5倍の予想。
感覚的な説明をするとICカードのICチップに実装した場合の製造コスト、SnakeCubeなら100円、中国論文だと300円以上。
この発明(SnakeCube)を使えばRSA暗号を延命できます。
そして社会インフラを支える現在運用されている公開鍵暗号が楕円曲線１つになる問題を対策できます。
この発明(SnakeCube)を、どのようにして成功させるか２つの案を考えてみました。
案1
次期マイナンバーカードに導入する。全世界では多くの国が楕円曲線、CRYSTALS-DilithiumのICカードを製造すると予想される中、
日本のマイナンバーカードはRSA 7680bit、同種写像暗号系などの耐量子暗号のICカードになるので、楕円曲線やCRYSTALS-Dilithiumが
解読された場合に世界に貢献できる。税負担も大きいけど成果も大きい。
案1は、お薦めではあるけどマイナンバーカード反対勢力が強いことが問題。
デジタル庁の大臣、河野太郎氏に無視されている問題が大きい。健康保険証をマイナンバーカードに統一することによる反対も大きいが、
マイナンバーカードを２枚組にして１つを健康保険証専用にすれば反対する人が減ると思われます。
案2
次期マイナンバーカードへの導入は反対が多いため、マイナンバーカード以外に導入することを考える。
まずETCカード。対応する暗号アルゴリズムをRSA 7680bitに限定することで開発費は極めて小さくなる。
これでも社会インフラを支える現在運用されている公開鍵暗号が楕円曲線１つになる問題を対策できる。
少ない税負担で日本の未来に残せるものは大きいことは重要。
ETCカードを利用する国土交通省は、コンピュータの進歩に伴なう暗号解読リスク向上のための費用を考えているはずで、
案2であればICF3(1999年)の暗号プロセッサ
を開発した実績のある僕がいれば、多くのことを知っているので、非常に小さいコストで開発が可能です。
ただしICチップへの実装につての知識は、あまり無いので、補える人が必要です。
高性能暗号技術なので国内の企業でも政府の規制対象になる場合があるため、
国土交通省と経済産業省に案2を推進するプロジェクトが出来ないかと考えています。
案2で進めながら、案1へ移行することもできるので税金が投下されそうな工場の方は、ご協力ください。
もちろん日本の未来を考える国民の方も。
昨日のニコニコ生放送、【河野太郎のLIVE配信】たろうとかたろう をもう一度、見ました。
僕のコメント「マイナカードの暗号アルゴリズムの話も」が削除されています。
昨日の画像と比較すると、コメントが削除されたことがわかります。
画像をマウスでクリックすると拡大されます
8月13日 21:00からデジタル相の河野太郎氏のLIVE配信がありました。
LIVE配信では事前質問を受け付けていたため、質問を送ってみました。
[質問] 次期マイナンバーカードではデジタル化の根幹をなす公開鍵暗号が揺らいでいる問題を考える必要があります。新技術の高周波数動作のモンゴメリ乗算器を採用すれば互換性を保ったまま従来より大きな鍵に対応することができて、しかも複数の公開鍵暗号に対応できます。ご存知でしょうか。
LIVE配信の時間内に多数の質問を答えなければならない都合を考えて、
ひとこと回答をすればいい質問にしていたのです。
事前質問はGoogleフォームを使っていました。Googleに不都合と判断され、質問が削除された可能性もありますが、
一応、デジタル庁のスタッフと大臣が回答をしなかったと考えます。
つまり日本国の大損が確定してることが判明したのです。
今、国民は大声でデジタル庁に次期マイナンバーカードではデジタル化の根幹をなす
公開鍵暗号が揺らいでいる問題を考えるように言うべきです。
僕がSNSで、このLIVE配信を宣伝したので、僕を知る人も何人か、いたようです。
相変わらず、暗号のようなコメントで、僕にしかわからないものばかりですが。
LIVE配信はYouTubeとニコニコ生放送の同時配信でしたが、僕は両方の配信を見ていました。
コメントもYouTube 2回、ニコニコ生放送 2回しています。
YoTube【河野太郎のLIVE配信】たろうとかたろう
ニコニコ【河野太郎のLIVE配信】たろうとかたろう
画像をマウスでクリックすると拡大されます
暗号プロセッサSnakeCube
の発明の名前があったほうがいいように思ったので命名します。
ナオキのアルゴリズム / naoki algorithm
ナオキを漢字にすると「直紀」
まずは普通の乗算について。
高速な乗算器は非常に多くのトランジスタ数が必要です。
ブースのアルゴリズム
はトランジスタ数を削減するなどの効果があるため、乗算器の実装では良く使われています。
ナオキのアルゴリズムはブースのモンゴメリ乗算バージョンです。
従来のモンゴメリ乗算の実装法よりも、高い周波数で動作して、演算器の幅を無限に大きくしても周波数が落ちない。
僕の2019年のブログに少し詳しく説明があります。
「わかりやすいICF3-Fのモンゴメリ乗算器の説明」
暗号プロセッサSnakeCubeは、最初はICF3-Fという名前で開発を進めていましたが、
オープンソースと間違われそうなので改名しました。上記ブログのICF3-FはSnakeCubeです。
参考まで、ブログの最後の「ICF3-Fの性能を2倍にする」に書かれてあることが2020年のSnakeCubeに実装されています。
ナオキのアルゴリズムはマイナンバーカードなどのICカードのICチップで効果的です。
ICチップの製造コストが1個 300円だったものが100円になれば、1億枚で200億円の削減になるのです。
将来、世界の大学の計算機工学(科学)の教科書にナオキのアルゴリズムが掲載されることになれば、
日本人として偉業を達成することになります。
参考ブログ
暗号半導体チップにおける『ナオキの法則』
ZOOMで第71回 ISSスクエア水平ワークショップに参加しました。
テーマ：「サイバーセキュリティ・IoT時代におけるトラストの基点～ICカード、そしてセキュアコンポーネント・デバイス～」
発表者にDNPの人がいてICカードのタンパー機能についてプレゼンをしていました。
DNPの人「ICカードは偽造防止の役目も大事なのでICカードに電磁波攻撃でCPUに誤判定をさせて
秘密鍵を推測できる情報を読み出す攻撃に耐える必要がある。」
CPUを誤判定させるほどの電磁波攻撃を検出できる機能があれば良いのかもしれないけど、
難しいかもしれない。
RSA暗号なら中国人剰余定理を使わずに計算すれば、マイクロコード無しに専用演算器のみで演算できる。
RSA暗号の秘密鍵の読み出しは専用演算器に直結させることが可能。
マイクロコード(CPU)無しに高速な実装が可能な公開鍵暗号はRSA暗号くらいではないだろうか?
つまりRSA暗号が最も電磁波攻撃に耐性があるのではないだろうか？
そしてSnakeCubeは電流解析などのサイドチャネル攻撃にもアーキテクチャレベルで耐性を持っている。
次期マイナンバーカードでは従来カードとの互換性を含めRSA暗号の延命かもしれない。
僕は、RSA暗号が解読されないことは一切保証しませんけど。
|
