超高速代数曲線公開鍵暗号大阪大学大学院理学研究科数学専攻鈴木研究室助教授 D2 鈴木譲原澤隆一 {suzuki, harasawa}@math.sci.osaka-u.ac.jp 大阪大学大学院工学研究科電子情報エネルギー工学専攻北山研究室 M1 桶谷賢吾 [email protected] 公開鍵暗号系の原理各ユーザの公開鍵は“電話帳”で公開タイガースネット名簿氏名坪井和田桧山  野村暗号鍵 f f f a b c f f f 1 a 1 b 1 c   f 復号鍵 d f 1 d ・野村は坪井に“盗塁”というメッセージ（平文）を送るとき、坪井の暗号鍵 f a （盗塁）で暗号化する。・同じメッセージを和田には・坪井は復号化鍵 f 1 a  f 1 a f b （盗塁）と暗号化して送信する。を持っていて f （盗塁）＝盗塁 a と、受信する。・ f a から f 1 a を計算して求めるのに、最高速計算機でも一年かかる。・それまでには、野村はタイガースにいない…….。公開鍵暗号系平文暗号化暗号文復号化平文解読暗号化鍵： f 平文暗号文復号化鍵 : f 1 f　から f f : 公開 1 f 1 : 秘密 f  f 1  e (恒等写像) は数学的に求まる計算量膨大公開鍵暗号系の例 ①因数分解 f ( p, q)  pq････( p, q)をかけて pq f 1 ( p, q)  ( p, q)････ pqを因数分解して ( p, q) ( pと qは素数 ) ②離散対数問題 G  { 1, i ,  i ,  1}  i   G ,     のとき , を求める（   { 0,1, 2, 3}） f ( )   ････  の  乗 f 1 (  )  ････  が  の何乗か f は一方向性関数(計算量) 群とは Gは、かけ算＊について群をなす・ 1 G 1 a G ・ a G (a＊b)＊c  a＊(b＊c) ・ a, b, c  G Gは、たし算＋について群をなす・ 0G ・ a G  a G (a  b)  c  a  (b  c) ・ a, b, c  G 群の例 G  1, i,  i,  1 a + b (mod 5) ① a b ② G  0,1, 2, 3, 4 mod5 0 0 0 1 1 2 2 3 3 4 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 1 2 3 離散対数問題の例 ①G  1, i,  i,  1, ＊   i,   i を何回かけると  になるか ＊＊＊  1　位数 n4 ４回　 l   , 0    n  1　となる を求める ②G   0,1, 2, 3, 4,  (mod5)   2,   3 を何回加えると  になるか           0 (mod5) 位数 n  5    , 0    n  1　となる を求めるｎが大きいとき、 を求める計算量大楕円曲線 y 2  x 3  ax  b （ a, bは定数）････ (*)　を満たす ( x, y )の集合 E 楕円曲線の2点 P1 , P2の和 P3  P1  P2 P1 , P2が(*)を満足  P3も (*)を満足 y Eは  について群 P Q x PQ (座標の和ではない) 楕円曲線離散対数問題１．楕円曲線Eで点Pを決める２．Pを何回加えると楕円曲線Eの点Qになるか P  P ････  P  Q　を満たす を求める  楕円曲線離散対数問題は他の群より解くための計算が膨大 ⇒国際標準（セキュリティ上安全）楕円曲線暗号の課題 ①暗号化の問題（群演算の高速化）従来より安全だが、楕円曲線の導入により演算が複雑 ②安全性の確保の問題どんな暗号も、解かれない保証はない。ナップザック暗号、一部の格子暗号など、有望とされながら解かれた暗号は山のようにある。 ③特許の問題新規に参入しても、多くの要素技術が特許化されていて、それ以上の技術力が必要。楕円曲線暗号化から代数曲線暗号へ Cab曲線超楕円曲線楕円曲線楕円曲線： y 2＝( xの3次式）超楕円曲線： y 2＝( xの5次式） Cab曲線： y a＝( xの b次式）代数曲線暗号導入のメリット ①暗号化の高速化広い代数曲線のクラスに、高速群演算を可能にする曲線が存在。 ②安全性の保障の問題広い代数曲線のクラス全ての曲線に対して暗号が解かれる可能性が低い。 ③特許上の問題代数曲線暗号で特許を取得すれば、楕円曲線暗号で特許になっていても、特許使用の問題は回避できる。原澤・鈴木方式の概要・種数 g の代数曲線では、g個の点の組で群要素を表現 P , P 1 2 ,, P g R , R 1 2   Q , 1 ,, R g ・ｇ個の点を格子点の集合とみなす Q  2 ,  , Q g  NEC方式との比較 NEC方式：グレブナ基底検索法に基づく原澤・鈴木方式：パウルスの最小基底検索に基づく提案方式の演算時間実用サイズ (160 bit) 実行時間 [秒] 0.09 0.08 0.07 0.06 0.05 0.04 0.03 0.02 0.01 0 原澤・鈴木方式 100 200 300 400 鍵のサイズ [bit] 計算量に関する比較原澤・鈴木方式ＮＥＣ方式 2 O( g ) 3 O( g ) （ｇは代数曲線の種数）・原澤・鈴木方式では１変数の割り算のみ（ＮＥＣ方式２変数多項式の割り算が必要）情報セキュリティ国際会議、主要ジャーナル採択状況・J.Silverman and J.Suzuki "Elliptic Curve Discrete Logarithms and the Index Calculus", Lecture Notes in Computer Science No. 1514, Advances in Cryptology-Asiacrypt'98, pages 110-125, 1998年10月．（楕円曲線暗号にインデックス計算法を適用することがなぜ困難化を解析した) ・R.Harasawa, J.Shikata, J.Suzuki, H.Imai R. Harasawa, J. Shikata, J. Suzuki, H. Imai, "Comparing the MOV and FR Reductions in Elliptic Curve Cryptography", Lecture Note on Computer Science 1592, Advances in Cryptology-Eurocrypt'99, pages 189-204, Springer-Verlag, 1999年5月. （MOVアタックとFRアタックの理論的性質を比較するとともに、FRアタックをはじめて実装した）・J.Shikata, L.Zhen, J.Suzuki, H.Imai ``Optimizing the Menezes-Okamoto-Vanstone Algorithm for NonSupersingular Elliptic Curves", Lecture Note on Computer Science, Asiacrypt '99, 1999年 11月（MOVアタックは超非特異楕円曲線に適用可能であることを理論的に説明した）・R.Harasawa, J.Suzuki ``Fast Jacobian Group Arithmetic on Cab Curves", Lecture Note on Computer Science, the 4th Algorithmic Number Theory Sympojium, pages 359-376, 2000年7月. （Cab曲線に関して群演算を高速におこなう方法を提案し、NEC方式、ガルブレイスらの方式と比較して有利であることを示した）鈴木研究室代数曲線暗号グループ鈴木譲原澤隆一大阪大学大学院理学研究科助教授大阪大学大学院理学研究科博士課程２年（平成１３年度より、文部省特別研究員）桶谷賢吾大阪大学大学院工学研究科修士課程１年 (北山研究室) 学外共同研究者 Joseph.H.Silverman 米国Brown大学教授, NTRU設立者東京大学生産技術研究所教授今井秀樹四方順司東京大学生産技術研究所研究員山本芳彦大阪大学大学院理学研究科教授