Presentation is loading. Please wait.

Presentation is loading. Please wait.

楕円曲線暗号における マルチスカラー倍算の前計算での モンゴメリトリックの使用

Similar presentations


Presentation on theme: "楕円曲線暗号における マルチスカラー倍算の前計算での モンゴメリトリックの使用"— Presentation transcript:

1 楕円曲線暗号における マルチスカラー倍算の前計算での モンゴメリトリックの使用
桶屋 勝幸 (株)日立製作所 櫻井 幸一 九州大学

2 ECDSAの検証でマルチスカラー倍を用いる
概要 動機 ECDSAの検証でマルチスカラー倍を用いる [ANSI] スカラー倍からマルチスカラー倍への 変換法の存在 [GLV01] 問題 マルチスカラー倍の高速化 成果 前計算の効率化により マルチスカラー倍の高速化を達成 約3倍

3 内容 マルチスカラー倍 問題設定 解決策 計算量比較

4 マルチスカラー倍 スカラー倍 整数 スカラー倍 楕円曲線上の点 マルチスカラー倍 整数 マルチスカラー倍 楕円曲線上の点

5 計算法 独立計算法 二つのスカラー倍を独立に計算 同時計算法 二つのスカラー倍を同時に計算 [Knu81, CMO98] [LL94]
ウィンドウ法 スカラー倍 [Knu81, CMO98] 加算 Comb 法 スカラー倍 [LL94] 同時計算法 二つのスカラー倍を同時に計算 Shamir’s trick マルチスカラー倍 [Elg85, HHM00] 高速化手法 加算 [Aki01, Moe01]

6 計算プロセス 前計算 ステージ 実計算 ステージ 入力 出力 テーブル作成 実際の計算 加算 前計算テーブル テーブル

7 ターゲット 前計算ステージ 実計算ステージ 独立計算法 高速 低速 多くの人が考察 同時計算法 低速 高速 議論の余地あり!
[CMO98] [CC87, MO90, LL94, CMO98, …] 同時計算法 低速 高速 議論の余地あり! あまり考察されてなさそうだ [Aki01, Moe01, Sol01]

8 何が高速化を阻んでいるのか? 障害 逆元演算が必要 (1点につき1回) 求める点の数が多い 実計算ステージでは 用いない点の存在
マルチスカラー倍固有の問題 求める点の数が多い 実計算ステージでは 用いない点の存在

9 何が高速化を阻んでいるのか? 障害 理由 逆元演算が必要 アフィン座標で計算するため (1点につき1回) 実計算ステージでの計算
高速化のためにはアフィン 座標で格納する必要がある マルチスカラー倍固有の問題 求める点の数が多い 実計算ステージでは 用いない点の存在 アフィン座標の演算は 逆元演算を必要とする

10 何が高速化を阻んでいるのか? 障害 理由 逆元演算が必要 (1点につき1回) 求める点が2次元 マルチスカラー倍固有の問題
求める点の数が多い 実計算ステージでは 用いない点の存在

11 何が高速化を阻んでいるのか? 障害 理由 逆元演算が必要 (1点につき1回) 前計算ステージ 計算する点の数:64点
マルチスカラー倍固有の問題 実計算ステージ 使用する点の数:54点 求める点の数が多い 実計算ステージでは 用いない点の存在 160ビット・ウィンドウサイズ3

12 とりあえず単純な改良 逆元の共通化 の 座標が等しい 計算の省略 y座標の値の反転

13 楕円曲線法による因数分解の高速化に用いられた
モンゴメリトリック [Coh93] 入力 計算量 出力 M M M I M I M [Coh93] M:乗算 楕円曲線法による因数分解の高速化に用いられた M I:逆元演算

14 モンゴメリトリックの適応例 (スカラー倍の前計算高速化)
[CMO98] モンゴメリトリックと用いると複数の逆元演算を1回の逆元計算で計算可能 前計算テーブル作成 2倍算 加算 加算 2倍算 加算 加算 2べき点との加算で使用 2倍算 モンゴメリトリックを用いて逆元計算

15 複数加算の逆元共通化 (マルチスカラー倍)
モンゴメリトリックと用いると複数の逆元演算を1回の逆元計算で計算可能 前計算テーブル作成 2倍算 加算 加算 加算 加算 加算 2倍算 モンゴメリトリックを用いて逆元計算 計算する点が2次元のため複雑

16 モンゴメリトリックを用いて逆元共通化する
前計算テーブル作成 前計算テーブル ステップ0 ステップ1 ステップ2 ステップ3 各ステップでは モンゴメリトリックを用いて逆元共通化する

17 前計算テーブル作成 (計算しなくてよい点がある場合)
ステップ0 ステップ1 ステップ2で計算できなくなった ステップ2 ステップ3 計算の順序を考える必要あり

18 前計算テーブル作成手順の簡略化 前計算テーブル ステップ0 ステップ1 ステップ2 ステップ3 を先に計算し テーブル真中は最後に計算

19 前計算テーブル作成 (計算しなくてよい点がある場合)
ステップ0 ステップ1 ステップ2 ステップ3 他に影響を与えないので問題なし

20 計算量比較 前計算 ステージ 実計算 ステージ 計 160ビット 独立計算法 336.8M 2809.8M 3146.6M 同時計算法
[CMO98] 同時計算法 [HHM00] 既存法 1011.6M 1655.5M 2667.1M [Moe01] 提案法 279.2M 1655.5M 1934.7M

21 まとめ 問題 マルチスカラー倍の高速化 解決策 モンゴメリトリックを用いた逆元共通化 前計算テーブル作成手順の簡略化 成果 約3倍
前計算の効率化により マルチスカラー倍の高速化を達成 結果 ECDSAの検証の高速化 マルチスカラー倍高速化による スカラー倍計算の高速化


Download ppt "楕円曲線暗号における マルチスカラー倍算の前計算での モンゴメリトリックの使用"

Similar presentations


Ads by Google