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

Presentation on theme: "代数体上で定義された楕円曲線の 素因数分解への応用"— Presentation transcript:

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

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

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

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

5 公開鍵暗号の例 素因数分解問題型 離散対数問題型 CRYPTORECプロジェクト ＲＳＡ暗号 ＥＰＯＣ その他 楕円曲線暗号 etc…

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

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

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

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

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

11 ねじれ部分群の構造 定理（Mazur） 定理（Kamienny-Kenku-Momose）

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

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

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

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

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

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

18 d=36 となる曲線の構成

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

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