Cylinder

Size: px

Start display at page:

Download "Cylinder"

あいりやがい
5 years ago
Views:

1 第 14 回情報セキュリティシンポジウム 2012 年 12 月 20 日 ( 木 ) - 講演 2- 次世代公開鍵暗号楕円曲線暗号とその適切な活用に向けて日本銀行金融研究所情報技術研究センター清藤武暢本発表は横浜国立大学の四方順司准教授との共同研究の成果に基づく 1 本発表に示されている意見は発表者個人に属し日本銀行の公式見解を示すものではない

2 本発表の概要 2 ATM 取引やインターネットバンキングにおいてデータの保護や通信相手の認証等のために暗号アルゴリズムが利用されている現在主流の暗号アルゴリズムである RSA 暗号に代わる暗号アルゴリズムとして楕円曲線暗号が注目されている RSA 暗号 : 鍵長が長く計算機性能が制限された環境 (IC カードや組込み機器 ) での利用が厳しくなる楕円曲線暗号 :RSA 暗号より短い鍵長で同程度の安全性を保証でき暗号処理の面で有利安全に利用するためにはそれなりの知識が必要楕円曲線暗号の安全性評価に関する研究動向を中心に紹介するとともに利用する際の留意点等を示す

3 本発表の流れ 3 I. 楕円曲線暗号の概要 II. 楕円曲線暗号とRSA 暗号 III. 楕円曲線暗号の安全性評価の動向 IV. 楕円曲線暗号の適切な活用に向けておわりに

4 I. 楕円曲線暗号の概要 4

5 金融業界における暗号アルゴリズムの利用 5 IC カードの真正性確認通信内容の保護 ATM 利用者 PC インターネット通信内容の保護通信相手の認証金融機関のホストシステム暗号アルゴリズムの種類 : 暗号アルゴリズムの種別共通鍵暗号トリプル DES AES 代表例公開鍵暗号 RSA 暗号 ( 現在主流 ) 楕円曲線暗号 (ECDH ECDSA など ) ECDH:Elliptic Curve Diffie-Hellman Scheme ECDSA:Elliptic Curve Digital Signature Algorithm FISC の安対基準において参照が推奨されている電子政府推奨暗号リストに含まれている暗号アルゴリズム次期リスト案にも含まれる

6 公開鍵暗号のフレームワーク 6 公開鍵 : 秘密鍵 : 公開鍵 1 公開鍵リスト公開鍵 2 受信者 4 暗号文送信者 5 3 復号暗号化メッセージ暗号文暗号文メッセージ秘密鍵公開鍵公開鍵暗号の安全性 : 公開鍵から秘密鍵を求めることの難しさに基づく公開鍵秘密鍵

7 RSA 暗号の現状 7 RSA 暗号 : 現在主流で用いられている公開鍵暗号安全性と鍵長 : 暗号アルゴリズムの安全性は経年劣化する安全性のレベルを維持するために鍵長を長くしていく必要がある 1,024 ビット (10 進数で 300 桁程度 ) 更新 2,048 ビット (10 進数で 600 桁程度 ) 更新暗号処理の性能低下が懸念計算機性能 ( 計算能力メモリ ) が制限されている環境 (IC カードや組込み機器 ) での利用が今後厳しくなることが予想される短い鍵長で同程度の安全性を達成できる公開鍵暗号への移行が検討されている一部では既に利用

8 楕円曲線暗号 8 楕円曲線暗号 : 楕円曲線離散対数問題( 後述 ) を利用した公開鍵暗号の総称楕円曲線暗号の利点 : RSA 暗号と比較して短い鍵長で同等の安全性を保証可能暗号処理を高速に行うことが可能計算機性能 ( 計算能力メモリ ) が制限されている環境 (IC カードや組込み機器等 ) での利用に適している約 10 分の 1 RSA 暗号では脆弱な鍵を発行する運用上のリスクがあるのに対し楕円曲線暗号ではそうしたリスクは相対的に低い RSA 暗号に代わる公開鍵暗号として注目

9 楕円曲線暗号の利用状況 9 楕円曲線暗号 : 現在既に利用されており次世代の主流としても有力身近な利用例 : デジタル放送における映像コンテンツの著作権保護 AACS(Advanced Access Control System) ブルーレイディスクで採用されているコンテンツの著作権保護技術機器 ( テレビや録画機 ) の認証やコンテンツの正当性確認において楕円曲線暗号 (ECDH ECDSA) が利用 DTCP(Digital Transmission Content Protection) 地上波 /BS/CS 放送で配信された映像コンテンツを家庭内ネットワーク等で伝送するときの著作権保護技術機器認証等で楕円曲線暗号 (ECDH ECDSA) が利用

10 楕円曲線暗号の利用状況 10 市販製品における楕円曲線暗号の採用実績 (2012 年 6 月時点 )[1] 分類市販製品 (206 製品 ) 楕円曲線暗号 (ECDSA) 採用実績 - 署名 RSA 暗号 (RSASSA-PKCS#1-v1.5) 28.2% 80.6% 分類市販製品 (213 製品 ) 楕円曲線暗号 (ECDH) 採用実績 - 守秘鍵共有 RSA 暗号 (RSAES-PKCS#1-v1.5) 23.9% 47.9% 市販製品の例 : オペレーションシステム暗号化ツールキット / ライブラリカードストレージハードウェアセキュリティモジュール等市販製品においても楕円曲線暗号が利用されている [1]CRYPTREC, CRYPTREC 暗号リスト ( 案 ) に係る意見募集について 2012 年

11 楕円曲線暗号の利用状況 11 米国安全保障局 Suite B Cryptography 米国安全保障局より2005 年に発表された機密情報保護のために利用する暗号アルゴリズムのリスト鍵交換暗号電子署名とハッシュ関数のアルゴリズムが規定鍵交換と電子署名のアルゴリズムには楕円曲線暗号のみ指定鍵交換 :ECDH 電子署名 :ECDSA RSA 暗号の記載はなし EMV 仕様 EMVCoが規定管理しているクレジットカード等の国際デファクト標準 EMVCo Common Contactless Terminal Roadmap (2009 年 ): 安全性向上を目的とした楕円曲線暗号の将来的な利用が明記インターネットの暗号通信プロトコル :SSL/TLS SSL/TLSプロトコルを規定しているIETF RFC4492, 5246 等 : 利用可能な暗号アルゴリズムに楕円曲線暗号 (ECDH ECDSA) が含まれている主要なWebブラウザ (Microsoft Internet Explorer Google Chromeや Mozilla FireFox 等 ) も楕円曲線暗号への対応が進められている本シンポジウム講演 1 の講演資料 p.23,28 を参照

12 楕円曲線暗号の設定手順 12 楕円曲線暗号 : 公開パラメータの決定が重要! 公開パラメータの決定 ( 利用者共通の設定 ) 利用する楕円曲線を決める ( 楕円曲線のタイプ曲線の係数 a,b) 曲線上の 1 点 (G) を選ぶ全ての利用者に公開 ( タイプ a b G) 鍵の設定 ( 利用者ごとの設定 ) 秘密鍵 s を選ぶ公開鍵 T=s G を計算する s の長さ ( ビット長 ): 楕円曲線暗号の鍵長暗号で利用する楕円曲線タイプ 1( 素体上の楕円曲線 ) y 2 =x 3 + ax + b タイプ 2(Binary Field 上の楕円曲線 ) y 2 + xy=x 3 + ax 2 + b 楕円曲線のイメージ y 2 = x 3 +1

13 II. 楕円曲線暗号と RSA 暗号 13

14 公開鍵暗号の安全性 14 公開鍵暗号の安全性 : 公開鍵から秘密鍵を求めるのが困難数学的問題により保証公開鍵暗号を破る主な攻撃手法安全性の根拠となっている数学的問題を解く安全性低下の要因計算機性能の向上 ( ムーアの法則 ) 問題を解く攻撃手法の進歩公開鍵秘密鍵公開鍵暗号の安全性は適用可能な攻撃手法のうち最も効率のよい攻撃手法により評価最も効率の良い攻撃手法を適用したとしても一定の安全性が確保されていれば安全な公開鍵暗号といえる

秘密鍵例 : ( 鍵長 2 桁 ) 33 3 11 ( 鍵長 3 桁 ) 989 43 23 ( 鍵長 5 桁 ) 73,903 263 281

15 楕円曲線暗号 RSA 暗号素因数分解問題 : 安全性の根拠となる数学的問題楕円曲線暗号と RSA 暗号の違い 15 楕円曲線離散対数問題ある数 g の x 乗の値 (g x ) から x を求める問題の一種素因数分解問題合成数 N から素数 P Q を求める問題 N(=P Q) 公開鍵困難容易素数 P,Q 秘密鍵例 : ( 鍵長 2 桁 ) ( 鍵長 3 桁 ) ( 鍵長 5 桁 ) 73, 桁数が大きくなるほど難しい ( 推奨桁数 :600 桁程度 ) 桁数を大きくした時に増加する難しさの程度は数学的問題により異なる増加する難しさの程度が大きいほど本質的に難しい問題といえる

16 楕円曲線暗号と RSA 暗号の違い 16 楕円曲線暗号の安全性の根拠楕円曲線離散対数問題 32 2 x 点 T(=s 点 G) 困難整数 s 答え x=5 連続値 ( 実数 ) の世界公開鍵容易秘密鍵離散値 (mod p) の世界楕円曲線の世界 ( イメージ図 ) 現時点では楕円曲線離散対数問題は素因数分解問題よりも相対的に解くのが難しい

17 楕円曲線暗号と RSA 暗号の鍵長 17 < 攻撃時間と鍵長の関係 ( イメージ )> 問題を解くのに要する時間 ( 攻撃時間 ) 楕円曲線暗号 ( 楕円曲線離散対数問題 ) 一定の時間内で解ける桁数が楕円曲線離散対数問題の方が短い ( 問題がより難しい ) 楕円曲線暗号の方が短い鍵長で同程度の安全性を達成可能現時点で利用可能な攻撃時間 RSA 暗号 ( 素因数分解問題 ) 鍵長 1 < 鍵長 2 鍵長 ( 桁数 )

18 楕円曲線暗号と RSA 暗号の鍵長 18 楕円曲線暗号と RSA 暗号の鍵長比較 : 攻撃時間を基準として等価な安全性を有する鍵長の対応関係が明らかにされている RSA 暗号楕円曲線暗号タイプ 1 タイプ , , , , , ( 単位 : ビット ) 鍵長が 1,024 ビットの RSA 暗号同じ安全性鍵長が 133 ビットの楕円曲線暗号 [2] 森川下山暗号等価安全性電子情報通信学会誌, 2011 年 [3] Yasuda, M., T. Shimoyama, T. Izu, and J. Kogure, On the Strength comparison of ECC and RSA, SCN2012

鍵生成時に起こり得る問題 19 公開鍵暗号 : 鍵生成時に素数を利用 RSA 暗号 : 異なる利用者で同じ値の素数を使い回すと第三者により当該利用者の秘密鍵が容易に求められてしまう主な原因 [4][5]: 運用面 : 鍵生成における管理者の丌注意や手抜き技術面 : 生成される素数に偏りが発生楕円曲線暗号 : 上記のような問題による安全性への影響は低い管理負担が低い [4]

19 鍵生成時に起こり得る問題 19 公開鍵暗号 : 鍵生成時に素数を利用 RSA 暗号 : 異なる利用者で同じ値の素数を使い回すと第三者により当該利用者の秘密鍵が容易に求められてしまう主な原因 [4][5]: 運用面 : 鍵生成における管理者の丌注意や手抜き技術面 : 生成される素数に偏りが発生楕円曲線暗号 : 上記のような問題による安全性への影響は低い管理負担が低い [4] Lenstra, Arjen, K., J. P. Hughes, M. Augier, J. W. Bos, T. Kleinjung, and C. Wachter, Publik Keys, CRYPTO2012 [5] Heninger, N., Z. Durumeric, E. Wustrow, J. A. Halderman, Mining Your Ps and Qs:Detection of Widespread Weak Keys in Network Devices, Usenix Security Symposium2012

20 III. 楕円曲線暗号の安全性評価の動向 20

楕円曲線暗号の安全性 21 楕円曲線暗号に対する攻撃 : 目的 : 安全性の根拠楕円曲線離散対数問題を解く利用する公開パラメータのタイプがある一定の条件を満たすときより簡単な問題に変換して解けることが知られている既存の攻撃手法 : 公開パラメータに依存しない攻撃手法 (

21 楕円曲線暗号の安全性 21 楕円曲線暗号に対する攻撃 : 目的 : 安全性の根拠楕円曲線離散対数問題を解く利用する公開パラメータのタイプがある一定の条件を満たすときより簡単な問題に変換して解けることが知られている既存の攻撃手法 : 公開パラメータに依存しない攻撃手法 ( 全ての公開パラメータに適用可能 ) Baby-Step Giant-Step(BSGS) 法 Pollard ρ 法公開パラメータに依存する攻撃手法 ( 一部の公開パラメータに適用可能 ) MOV 帰着 FR 帰着 SSSA 法 GHS 法指数計算法公開パラメータ楕円曲線のタイプ係数 a b 曲線上の点 G

22 楕円曲線暗号の攻撃手法に関する研究動向 22 楕円曲線暗号に対する攻撃 : 攻撃手法の強さ ( 多項強式時間 ) ( 準指数中関数時間 ) ( 指数関弱数時間 ) 近年一定の条件を満たす公開パラメータを対象とした攻撃手法の提案が主流攻撃が適用できる条件は明らかになっている公開パラメータに依存しない攻撃手法 BSGS 法 (1971) Pollard ρ 法 (1978) 年々進歩公開パラメータに依存する攻撃手法 MOV 帰着 (1991) FR 帰着 (1994) SSSA 法 (1998) GHS 法 (2000) 指数計算法 (2004) 提案された年

23 要件 1: 強力な攻撃手法が適用できない公開パラメータ推奨される公開パラメータ 23 楕円曲線暗号 : 公開パラメータの選び方により安全性が低下する性質がある安全な公開パラメータの選択 : 以下の2つの要件を満たす公開パラメータを選ぶ必要がある要件 2: 公開パラメータに依存しない攻撃手法では解けない程度の鍵長 Pollard ρ 法 Bad ( 攻撃手法が適用できる公開パラメータ ) 公開パラメータ全体 Not Bad 新たな攻撃手法により Not Bad の公開パラメータが Bad になる可能性あり NIST や SECG が推奨される公開パラメータを公表

24 推奨される公開パラメータ 24 推奨公開パラメータを公開している組織 NIST( 米国標準技術研究所 ) 米国政府内で利用する暗号技術等の標準規格やガイドラインを策定 15 個の推奨公開パラメータを規定 [6] SECG(The Standards for Efficient Cryptography Group) 楕円曲線暗号の商用的な標準仕様策定を行っている国際コンソーシアム主な会員 :NIST VISA 等 20 個の推奨公開パラメータを規定 [7] 例 :NIST の推奨公開パラメータ P-192(p,n:10 進数表記 b,gx,gy:16 進数表記 ) p = n = a = -3 b = e59c80e7 0fa7e9ab feb8deec c146b9b1 曲線の係数曲線のタイプ ( タイプ 1) Gx = 188da80e b03090f6 7cbf20eb 43a18800 f4ff0afd 82ff1012 Gy = 07192b95 ffc8da ed 6b24cdd5 73f977a1 1e 点 G の座標 (Gx, Gy) [6] NIST, FIPS186-3 Digital Signature Standard, FIPS186-3, 2009 [7] SECG, SEC2:Recommended Elliptic Curve Domain Parameters, 2010

25 推奨される公開パラメータ 25 NIST と SECG の推奨公開パラメータの種類および対応タイプ1 タイプ2 鍵長 NIST SECG 鍵長 NIST SECG 192 P-192 secp-192k1 163 K-163 secp-192r1 224 P-224 secp-224k1 B-163 secp-224r1 223 K-223 secp-256k1 B P-256 secp-256r1 384 P-384 secp-384r P-521 secp-521r1 楕円曲線のタイプタイプ 1: タイプ 2: y 2 =x 3 + ax + b y 2 +xy=x 3 + ax 2 + b K-283 B-283 K-409 B-409 K-571 B-571 sect-163k1 sect-163r1 sect-163r2 sect-233k1 sect-233r1 sect-239k1 sect-283k1 sect-283r1 sect-409k1 sect-409r1 sect-571k1 sect-571r1

26 楕円曲線暗号の安全性検証状況 26 安全な公開パラメータ選択の要件の一つ : 要件 2: 公開パラメータに依存しない攻撃手法では解けない程度の鍵長 Pollard ρ 法により解読された鍵長 [8][9] 鍵長評価の基準解読日鍵長のサイズ 1997 年 12 月年 1 月年 3 月年 10 月年 7 月 112 高性能な家庭用ゲーム機を 200 台以上用いて解読 ( 単位 : ビット ) [8] Certicom, Certicom ECC Challenge, 2009 [9] Bos, Joppe, W., M. E. Kaihara, T. Kleinjung, A. K. Lenstra, and P. L. Montgomery, Solving a 112 bit prime elliptic curve discrete logarithm problem on game consoles using sloppy reduction, IJACT, 2012

楕円曲線暗号の安全性に関する最近の動き 27 新たな攻撃手法 : 指数計算法の改良版 (2012 年 5 月提案 )[10] 特徴 : 攻撃対象 : 曲線タイプ 2 の公開パラメータ全体攻撃手法の強さ ( 多項強式時間 ) ( 準指数中関数時間 ) ( 指数関弱数時間 ) 攻撃手法の強さ : 中公開パラメータに依存しない攻撃手法 BSGS 法 (1971) 公開パラメータに依存する攻撃手法

27 楕円曲線暗号の安全性に関する最近の動き 27 新たな攻撃手法 : 指数計算法の改良版 (2012 年 5 月提案 )[10] 特徴 : 攻撃対象 : 曲線タイプ 2 の公開パラメータ全体攻撃手法の強さ ( 多項強式時間 ) ( 準指数中関数時間 ) ( 指数関弱数時間 ) 攻撃手法の強さ : 中公開パラメータに依存しない攻撃手法 BSGS 法 (1971) 公開パラメータに依存する攻撃手法 Pollard ρ 法 (1978) MOV 帰着 (1991) SSSA 法 (1998) FR 帰着 (1994) 適用できる公開パラメータの範囲が広い GHS 法 (2000) 指数計算法 (2004) 改良版指数計算法 (2012) 提案された年 [10] Petit, Christophe, and Juean-Jacques Quisquater, On Polynomial Systems Arising from a Weil Descent, ASIACRYPT2012

28 IV. 楕円曲線暗号の適切な活用に向けて 28

29 改良版指数計算法の安全性への影響 29 改良版指数計算法の楕円曲線暗号の安全性への影響について分析する主な分析項目 : 安全性に対して脅威となる時期の予測推奨公開パラメータへの影響今後楕円曲線暗号を利用する際の留意点について説明する

30 安全性に対して脅威となる時期の予測 30 改良版指数計算法と Pollard ρ 法の計算量を比較 ρ 法よりも強力な攻撃手法となるのは鍵長が 2,000 ビット以上の場合 Pollard ρ 法改良指数計算法攻撃時間 Pollard ρ 法が最も効率が良い改良版指数計算法が最も効率が良い 2, 鍵長 ( ビット ) ) 楕円曲線暗号の鍵長が 2,000 ビット以上となる時期はいつか?

31 安全性に対して脅威となる時期の予測 31 楕円曲線暗号 ( 曲線タイプ 2) の鍵長と危殆化時期を文献 [2][3] のデータに基づき予測 3150 危殆化時期 ( 年 ) 危殆化予想時期 3031 年 1950 鍵長 2,000 ビットビットの鍵長が危殆化する時期は 3031 年と推定される 2012 年時点では直ちに脅威とはならないと考えられる [2] 森川下山暗号等価安全性電子情報通信学会誌, 2011 年 [3] Yasuda, M., T. Shimoyama, T. Izu, and J. Kogure, On the Strength comparison of ECC and RSA, SCN2012 該当する鍵長が世界最高のスーパーコンピュータを用いて 1 年間計算するとほぼ解読できると予想される時期鍵長 ( ビット )

32 推奨公開パラメータへの影響 32 NIST や SECG の推奨公開パラメータへの影響について改良版指数計算法の攻撃条件 : 条件 1: 曲線タイプ 2 の公開パラメータを利用条件 2: 鍵長が 2,000 ビット以上推奨公開パラメータを見てみると曲線タイプ 1: 攻撃の適用範囲外曲線タイプ 2 に該当する公開パラメータ : NIST(10 個 ) SECG(12 個 ) 各公開パラメータの鍵長は約 160~570 ビット攻撃条件が成立しないため現時点では影響なし

33 楕円曲線暗号と RSA 暗号の強度比較 33 RSA 暗号に対する攻撃手法 ( 数体ふるい法 ) 改良指数計算法 2 つの攻撃手法を比較 Pollard ρ 法攻撃の強さ : 中改良指数計算法攻撃時間攻撃時間には大きな差がある RSA 暗号への攻撃 ( 数体ふるい法 ) 2, 鍵長 ( ビット ) 適切に鍵長を選択すれば引き続き RSA 暗号よりも短い鍵長で同程度の安全性を達成可能と考えられる

34 改良版指数計算法の今後の影響 34 攻撃手法の研究が進み改良版指数計算法がさらに改良されると Pollard ρ 法改良指数計算法攻撃時間しきい値の変化攻撃時間の削減 RSA 暗号への攻撃 ( 数体ふるい法 )? 2, 今後の研究動向について引き続き注視する必要あり鍵長 ( ビット )

35 RSA 暗号に代わる公開鍵暗号 : 楕円曲線暗号おわりに 35 RSA 暗号と比較して短い鍵長で同程度の安全性を保証できる鍵長が短いため暗号化処理も高速に行うことができるデジタル放送等において既に利用されている ICカード (EMV 仕様 ) や暗号通信プロトコル (SSL/TLS) 等金融分野と関連の深い技術において楕円曲線暗号の利用に向けた動きが進んでいる楕円曲線暗号を利用する際の留意点 : 楕円曲線の公開パラメータを適切に選ぶ必要がある NIST や SECG の推奨公開パラメータの利用鍵長の適切な選択の指針の利用今後も引き続き楕円曲線暗号の安全性評価に関する最新の研究動向に注視する必要がある [2] 森川下山暗号等価安全性電子情報通信学会誌, 2011 年 [3] Yasuda, M., T. Shimoyama, T. Izu, and J. Kogure, On the Strength comparison of ECC and RSA, SCN2012

36 補足資料 : 楕円曲線暗号と RSA 暗号の処理速度比較金岡による測定結果 [11] 安全性 ( ビット ) OpenSSLにおける楕円曲線暗号 (ECDSA) とRSA 暗号 (RSASSA-PKCS#1- v1.5) の処理速度を測定測定環境 : CPU:Intel Core i7 920, RAM:8GB, OS:Linux(CentOS5.6) 速度の測定 :speedコマンドを利用し一秒間当たりの署名生成検証回数を測定使用した楕円曲線 : タイプ1( 素体上の楕円曲線 ) 鍵長 ( ビット ) 楕円曲線暗号 (ECDSA) 署名生成 / 秒署名検証 / 秒鍵長 ( ビット ) RSA 暗号 (RSASSA-PKCS#1-v1.5) 署名生成 / 秒署名検証 / 秒署名生成 : 楕円曲線暗号の方が速い署名検証 :RSA 暗号の方が速い [11] 金岡楕円曲線暗号の整備動向 + 楕円暗号の実装状況 PKI Day, 2011 年

暗号方式委員会報告（CRYPTRECシンポジウム2012）

暗号方式委員会報告（CRYPTRECシンポジウム2012）暗号方式委員会活動報告安全性実装性能評価リスト入りまでの基本的な流れ事務局選出暗号公募暗号技術現リスト掲載暗号次期リスト電子政府推奨暗号リスト推奨候補暗号リスト運用監視暗号リスト現リストのカテゴリ技術分類公開鍵暗号共通鍵暗号その他署名守秘鍵共有 64ビットブロック暗号 128 ビットブロック暗号ストリーム暗号ハッシュ関数擬似乱数生成系現リスト : 公開鍵暗号技術分類