超高速代数曲線公開鍵暗号-大阪大学大学院理学研究科数学専攻.pptVIP

公開鍵暗号系 公開鍵暗号系の例 群とは 群の例 離散対数問題の例 楕円曲線 楕円曲線離散対数問題 １．楕円曲線Eで点Pを決める ２．Pを何回加えると楕円曲線Eの点Qになるか 楕円曲線暗号の課題 ①暗号化の問題（群演算の高速化） 従来より安全だが、楕円曲線の導入により演算が複雑 ②安全性の確保の問題 どんな暗号も、解かれない保証はない。ナップザック暗号、一部の格子暗号など、有望とされながら解かれた暗号は山のようにある。 ③特許の問題 新規に参入しても、多くの要素技術が特許化されていて、それ以上の技術力が必要。 楕円曲線暗号化から代数曲線暗号へ 代数曲線暗号導入のメリット ①暗号化の高速化 広い代数曲線のクラスに、高速群演算を可能にする曲線が存在。 ②安全性の保障の問題 広い代数曲線のクラス全ての曲線に対して暗号が解かれる可能性が低い。 ③特許上の問題 代数曲線暗号で特許を取得すれば、楕円曲線暗号で特許になっていても、特許使用の問題は回避できる。 原澤?鈴木方式の概要 NEC方式との比較 NEC方式：グレブナ基底検索法に基づく 原澤?鈴木方式：パウルスの最小基底検索 に基づく 計算量に関する比較 情報セキュリティ国際会議、主要ジャーナル採択状況 ?J.Silverman and J.Suzuki Elliptic Curve Discrete Logarithms and the Index Calculus, Lecture Notes in Computer Science No. 1514, Advances in Cryptology-Asiacrypt98, 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-Eurocrypt99, pages 189-204, Springer-Verlag, 1999年5月. （MOVアタックとFRアタックの理論的性質を比較するとともに、FRアタックをはじめて実装した） * 超高速代数曲線公開鍵暗号 大阪大学大学院理学研究科数学専攻 鈴木研究室 　　　　　 助教授 　 　D2 鈴木 譲 　　原澤隆一 {suzuki, harasawa}@math.sci.osaka-u.ac.jp 大阪大学大学院工学研究科 電子情報エネルギー工学専攻 北山研究室 M1 桶谷賢吾 oketani@m.eng.osaka-u.ac.jp 公開鍵暗号系の原理 各ユーザの公開鍵は“電話帳”で公開 野村 桧山 和田 坪井 復号鍵 暗号鍵 氏名 タイガースネット名簿 ?野村は坪井に“盗塁”というメッセージ（平文）を送るとき、 坪井の暗号鍵 （盗塁）で暗号化する。 ?同じメッセージを和田には （盗塁）と暗号化して送信する。 ?坪井は復号化鍵 を持っていて （盗塁） ＝ 盗塁 と、受信する。 から を計算して求めるのに、 最高速計算機でも一年かかる。 ?それまでには、野村はタイガースにいない…….。 ? 暗号化 復号化 平文 平文 解読 平文 暗号文 暗号文 暗号化鍵 ： 復号化鍵 : 計算量膨大 ①因数分解 ②離散対数問題 3 2 1 0 4 4 2 1 0 4 3 3 1 0 4 3 2 2 0 4 3 2 1 1