代数体上で定義された楕円曲線の 素因数分解への応用

Slides:



Advertisements
Similar presentations
私情協 授業情報技術講習会 個人情報の取扱い 慶應義塾大学理工学部 山本 喜一 授業情報技術講習会 2 個人情報の定義 JIS Q : 1999 個人情報とは、個人に関する情報であって、 当該情報に含まれる氏名、生年月日その他の 記述、または個人別に付けられた番号、記号.
Advertisements

情報セキュリティ 第3回 現代暗号の基礎数理. 脅威と暗号技術 セキュリティに対する脅威 脅かされる特性 暗号技術 機密性 正真性 認証 否認不可能性 盗聴 (秘密が漏れる) 改竄 (情報が書き換えられる) なりすまし (正しい送信者のふりをする) 否認 (後から私じゃないと言う) 共通鍵暗号 公開鍵暗号.
1 前回の練習問題 F 29 = {1, 2,…, 28} において, g = 11 が生成元であることを確 かめ, F 29 の元とその離散対数との関係を図示せよ. x = 1,..., 28 に対し, g x mod 29 を計算すればよい
効率的に計算可能な 加法的誤りの訂正可能性 安永 憲司 九州先端科学技術研究所 SITA 2012 @ 別府湾ロイヤルホテル
素数判定の効率性について 東邦大学理学部情報科学科卒業研究発表会 指導教員 白柳 潔 提出者 後藤 雄大.
暗号技術の国際動向について ー AES 秘密鍵暗号, 楕円公開鍵暗号- 三菱電機株式会社情報技術総合研究所 松井 充.
Y - 座標復元を伴うモンゴメリ型 楕円曲線上のスカラー倍計算方法と 楕円曲線暗号における効率性の解析 桶屋 勝幸 (株)日立製作所 櫻井 幸一 九州大学 All Rights Reserved, Copyright © 2001, Hitachi, Ltd.
電子社会設計論 第12回 Electronic social design theory 中 貴俊.
駒澤大学 経営学部 情報セキュリティ B 公開鍵暗号による 認証つきの秘匿通信 ―― 鍵に注目して ――
2001/10/10 PSEC-KEM NTT 小林 鉄太郎 CRYPTREC 2001
2000年 3月 10日 日本電信電話株式会社 三菱電機株式会社
情報工学科 06A2055 平塚 翔太 Hiratsuka Shota
黒澤 馨 (茨城大学) 情報セキュリティ特論(4) 黒澤 馨 (茨城大学) 2017/3/4 confidential.
Q q 情報セキュリティ 第6回:2005年5月20日(金) q q.
黒澤 馨 (茨城大学) 情報セキュリティ特論(6) 黒澤 馨 (茨城大学) 2017/3/13 confidential.
「まめだくん Ver.1.0」 特徴と利用方法.
第2章 第1節 情報通信の仕組み 4 暗号技術と情報の保護 5 コンピュータとネットワークの管理
共通鍵と公開鍵 暗号のしくみ 情報、数学ハイブリッド版.
数論幾何学セミナー タイトル:楕円曲線の平均階数と数の幾何
数 学 の か た ち 第3講 暗号を作ろう 早苗 雅史 数学とソフトウエア
黒澤 馨 (茨城大学) 情報セキュリティ特論(7) 黒澤 馨 (茨城大学)
ネットワークでかわる社会 第2節 ネットワークのしくみ②
暗号技術 ~公開鍵暗号方式の仕組み~ (3週目)
第10回 情報セキュリティ 伊藤 高廣 計算機リテラシーM 第10回 情報セキュリティ 伊藤 高廣
黒澤 馨 (茨城大学) 情報セキュリティ特論(5) 黒澤 馨 (茨城大学)
博士たちの愛する素数 徳山 豪 東北大学 Prime numbers that professors love
2001/10/10 PSEC-KEM NTT 小林 鉄太郎 CRYPTREC 2001
Q q 情報セキュリティ 第3回:2005年4月28日(金) q q.
Q q 情報セキュリティ 第3回:2005年4月22日(金) q q.
数論システム NZMATH の 開発と応用 巨大な自然数の高速計算に すぐ使えるプログラム 理工学研究科 数理情報科学専攻
数学のかたち 暗号を作ろう Masashi Sanae.
Copyright © 2014 JOPS AWS Working Group, All rights reserved.
Q q 情報セキュリティ 第12回:2006年7月7日(金) q q.
Q q 情報セキュリティ 第5回:2005年5月13日(金) q q.
黒澤 馨 (茨城大学) 情報セキュリティ特論(1) 黒澤 馨 (茨城大学) 2018/12/8 confidential.
情報セキュリティ  第4回 メッセージ認証コード.
第二章 インターネットで やり取りする情報を守る
PGP インターネットで 広く使われている暗号技術
実用的暗号通信ソフトウェア 「まめだくん」の開発 Shiota Laboratory
情報セキュリティ  第11回 デジタル署名.
Linux リテラシ 2006 第5回 SSH と SCP CIS RAT.
情報セキュリティ  第8回 RSA暗号.
2章 暗号技術 FM15002 友池 絲子.
5.RSA暗号 素因数分解の困難性を利用した暗号.
Selfish Routing and the Price of Anarchy 4.3
Q q 情報セキュリティ 第12回:2007年7月6日(金) q q.
Q q 情報セキュリティ 第8回:2005年6月3日(金) q q.
Q q 情報セキュリティ 第7回:2006年6月2日(金) q q.
暗号技術 ~暗号技術の基本原理~ (1週目) 情報工学科  04A1004 石川 真悟.
Q q 情報セキュリティ 第6回:2007年5月25日(金) q q.
暗号技術をとりまく最近の話題 ーAES秘密鍵暗号,楕円公開鍵暗号-
生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング
「情報セキュリティ論」 2-4 公開鍵暗号の原理とRSA暗号
情報科学演習III --- 計算代数とその応用 ---
香川大学創造工学部 富永浩之 情報数学1 第1-3章 素数と素因数分解 香川大学創造工学部 富永浩之
Diffie-Hellman 鍵共有 ElGamal 暗号 楕円曲線暗号,量子コンピュータ
構造的類似性を持つ半構造化文書における頻度分析
Q q 情報セキュリティ 第5回:2006年5月19日(金) q q.
Q q 情報セキュリティ 第12回:2004年6月25日(金) の補足 q q.
4.プッシュダウンオートマトンと 文脈自由文法の等価性
ネット時代のセキュリティ3(暗号化) 2SK 情報機器工学.
Q q 情報セキュリティ 第6回:2005年5月26日(金) q q.
Q q 情報セキュリティ 第8回:2004年5月28日(金) の補足 q q.
暗号技術・セキュリティ 情報工学科  04A1004 石川 真悟.
香川大学創造工学部 富永浩之 情報数学1 第2-2章 合同式の逆元と応用 香川大学創造工学部 富永浩之
情報生命科学特別講義III (3)たたみ込みとハッシュに 基づくマッチング
Q q 情報セキュリティ 第7回:2005年5月27日(金) q q.
創造都市研究科 都市情報学 情報基盤研究分野
2012年度 情報数理 ~ ハミング距離 ~.
弾力性 労働経済学.
Presentation transcript:

代数体上で定義された楕円曲線の 素因数分解への応用 2019/5/2 仙台数論小研究集会2000 東北大学 2000年12月1日(金) 代数体上で定義された楕円曲線の 素因数分解への応用 (株)富士通研究所 セキュアコンピューティング研究部 伊豆 哲也

概要 楕円曲線法の効率化手法 ある代数体上でねじれ部分群が既知な楕円曲線を構成し、その曲線を楕円曲線法へ適用する。 素因数分解と楕円曲線法 Z/4Z×Z/4Z に同型なねじれ部分群を持つ楕円曲線の構成 Z/6Z×Z/6Z に同型なねじれ部分群を持つ楕円曲線の構成 楕円曲線法への適用

素因数分解 素因数分解問題: 主な素因数分解法と分解記録 入力された合成数の(素)因数を見つける問題 2019/5/2 素因数分解問題: 入力された合成数の(素)因数を見つける問題 主な素因数分解法と分解記録 二次篩 QS C129(P64) 1994年4月 RSA129 一般数体篩 GNFS C155(P78) 1999年8月 RSA155 特殊数体篩 SNFS C233(P93) 2000年11月 2773+1 楕円曲線法 ECM (P54) 1999年12月 (643-1)42-1

公開鍵暗号 公開鍵暗号の原理 平文 暗号文 関数の例:素因数分解問題・離散対数問題 公開鍵から簡単に計算できる 落とし戸付き 一方向性関数 2019/5/2 公開鍵暗号の原理 公開鍵から簡単に計算できる 落とし戸付き 一方向性関数 平文 暗号文 公開鍵を知っていても簡単には計算できない (秘密鍵を知らなければ計算できない) 関数の例:素因数分解問題・離散対数問題

公開鍵暗号の例 素因数分解問題型 離散対数問題型 CRYPTORECプロジェクト RSA暗号 EPOC その他 楕円曲線暗号 etc… http://www.ipa.go.jp/security/enc/CRYPTREC/index.html

楕円曲線法 (ECM) アルゴリズムの概要 Input : 合成数 Output : 素因数 (1) で定義される楕円曲線 (2) 任意の点 に対し (3) の倍数 に対し (4) のかわりに で考える 途中で計算不能になったときに が現れる で定義される楕円曲線 p-1 法の拡張として Lenstra Jr. により提案(1987年)

ECMによる計算例 (1) フェルマー数 (39桁) (17桁)

ECMによる計算例 (2) (114桁) (114桁) (51桁) 2000年5月14日発見 (Izu, ECMによる発見記録の第5位)

パラメータの設定 ECMが素因数を見つける条件は? の設定(多くの約数を持って欲しい) の設定 は smooth であって欲しい

楕円曲線の生成 どのように楕円曲線を生成するか? はランダムに動くので制御が難しい となる曲線を使用すればランダムに ふるまう部分は になる となる生成法が良く用いられている

ねじれ部分群の構造 定理(Mazur) 定理(Kamienny-Kenku-Momose)

ねじれ部分群 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 1 20 24

楕円曲線の構成 Kubert-form elliptic curve Division polynomial

d=16 となる曲線の構成 命題(Izu) は 上で に同型なねじれ部分群 を持つ

d=18 となる曲線の構成 定理(Yoshimura) 上の無限位数の点 について とする。 とおけば は 上で に同型なねじれ部分群を持つ。

命題 (Izu) 命題(Izu) (1) は に同型なねじれ部分群を持つ。 (2) は に同型なねじれ部分群 を持つ。

d=36 となる曲線の構成 命題(Izu) とすると, は に同型なねじれ部分群を持つ。

d=36 となる曲線の構成

ECMへの適用 の適用 1/2 の確率でしか にならない 従来の なる曲線の方が効果的 の適用 1/4 の確率でしか にならない

All Rights Reserved, Copyright (C) FUJITSU 2000 FUJITSU logo