楕円曲線暗号における マルチスカラー倍算の前計算での モンゴメリトリックの使用 桶屋 勝幸 （株）日立製作所 櫻井 幸一 九州大学 2/21 概要 動機 問題 成果 ECDSAの検証でマルチスカラー倍を用いる [ANSI] スカラー倍からマルチスカラー倍への 変換法の存在 [GLV01] マルチスカラー倍の高速化 約3倍 前計算の効率化により マルチスカラー倍の高速化を達成 3/21 内容 マルチスカラー倍 問題設定 解決策 計算量比較 4/21 マルチスカラー倍 スカラー倍 k P 整数 楕円曲線上の点 スカラー倍 k回 マルチスカラー 倍 k, l P, Q 整数 楕円曲線上の点 kP P P P マルチスカラー倍 kP lQ P P P k回 Q Q Q l回 5/21 計算法 独立計算法 ウィンドウ法 [Knu81, CMO98] Comb 法 [LL94] 同時計算法 Shamir’s trick [Elg85, HHM00] 高速化手法 [Aki01, Moe01] 二つのスカラー倍を独立に計算 k, P l, Q スカラー倍 スカラー倍 kP 加算 kP lQ lQ 二つのスカラー倍を同時に計算 k, P l, Q マルチスカラー倍 sP tQ 加算 P, Q, P Q kP lQ 6/21 計算プロセス 前計算 ステージ 実計算 ステージ テーブル作成 実際の計算 入力 出力 sP tQ k, P l, Q O P 2P 3P Q P Q 2 P Q 3P Q 2Q P 2Q 2 P 2Q 3P 2Q 3Q P 3Q 2 P 3Q 3P 3Q 前計算テーブル 加算 2 P 3Q テーブ ル kP lQ 7/21 ターゲット 独立計算法 前計算ステージ 実計算ステージ 高速 低速 [CMO98] [CC87, MO90, LL94, CMO98, …] 多くの人が考察 同時計算法 高速 低速 [Aki01, Moe01, Sol01] あまり考察されてなさそう だ 議論の余地あり！ 8/21 何が高速化を阻んでいるのか？ 障害 逆元演算が必要 （1点につき1回） 求める点の数が多い 実計算ステージでは 用いない点の存在 マルチスカラー倍固有の問題 9/21 何が高速化を阻んでいるのか？ 障害 理由 逆元演算が必要 （1点につき1回） アフィン座標で計算するため 求める点の数が多い 実計算ステージでの計算 高速化のためにはアフィン 座標で格納する必要がある 実計算ステージでは 用いない点の存在 マルチスカラー倍固有の問題 アフィン座標の演算は 逆元演算を必要とする 10/21 何が高速化を阻んでいるのか？ 障害 理由 逆元演算が必要 （1点につき1回） 求める点が2次元 uP vQ u, v 0,1, 求める点の数が多い O 実計算ステージでは 用いない点の存在 マルチスカラー倍固有の問題 P 2P 3P Q P Q 2 P Q 3P Q 2Q P 2Q 2 P 2Q 3P 2Q 3Q P 3Q 2 P 3Q 3P 3Q 11/21 何が高速化を阻んでいるのか？ 障害 理由 逆元演算が必要 （1点につき1回） 前計算ステージ 計算する点の数：６４点 求める点の数が多い 実計算ステージ 使用する点の数：５４点 実計算ステージでは 用いない点の存在 160ビット・ウィンドウサイズ3 マルチスカラー倍固有の問題 12/21 とりあえず単純な改良 P ( x, y) P ( x, y) 逆元の共通化 Qの x 座標が等しい PQ 計算の省略 P Q P Q ｙ座標の値の反転 13/21 モンゴメリトリック 入力 a1, a2 , a3 ,, an 出力 a11, a21, a31,, an1 a2 a11 [Coh93] 楕円曲線法による 因数分解の高速化 に用いられた M a1a2 a3 a1a2 1 M a21 3n 1M I 計算量 M a1 [Coh93] M M a1a2 a3 I a1a2a3 1 M a31 M：乗算 I：逆元演算 14/21 モンゴメリトリックの適応例 （スカラー倍の前計算高速化） モンゴメリトリックと用いると複数の逆元演算を 1回の逆元計算で計算可能 前計算テーブル作成 P 2倍算 2P 加算 2倍算 2べき点との加算で使用 3P 4P 加算 7P 加算 5P 2倍算 8P モンゴメリトリックを用いて逆元計算 加算 [CMO98] 15/21 複数加算の逆元共通化 （マルチスカラー倍） モンゴメリトリックと用いると複数の逆元演算を 1回の逆元計算で計算可能 前計算テーブル作成 P 2倍算 加算 Q 2倍算 2P PQ 2Q 加算 3P Q 加算 2 P 2Q 加算 モンゴメリトリックを用いて逆元計算 計算する点が2次元のため複雑 加算 16/21 前計算テーブル作成 前計算テーブル O P 2P 3P Q PQ 2P Q 3P Q ステップ 0 ステップ1 ステップ2 2Q P 2Q 2 P 2Q 3P 2Q 3Q P 3Q 2 P 3Q 3P 3Q 各ステップでは モンゴメリトリックを用いて逆元共通化する ステップ 3 17/21 前計算テーブル作成 （計算しなくてよい点がある場合） 前計算テーブル O P 2P 3P Q PQ 2P Q 3P Q ステップ 0 ステップ1 ステップ2 2Q P 2Q 2 P 2Q 3P 2Q 3Q P 3Q 2 P 3Q 3P 3Q ステップ2で計算できなくなった 計算の順序を考える必要あり ステップ 3 18/21 前計算テーブル作成手順の簡略化 前計算テーブル O P 2P 3P Q PQ 2P Q 3P Q ステップ 0 ステップ1 ステップ2 2Q P 2Q 2 P 2Q 3P 2Q 3Q P 3Q 2 P 3Q 3P 3Q uP, vQ を先に計算し テーブル真中は最後に計算 ステップ 3 19/21 前計算テーブル作成 （計算しなくてよい点がある場合） 前計算テーブル O P 2P 3P Q PQ 2P Q 3P Q ステップ 0 ステップ1 ステップ2 2Q P 2Q 2 P 2Q 3P 2Q 3Q P 3Q 2 P 3Q 3P 3Q 他に影響を与えないので問題なし ステップ 3 20/21 計算量比較 160ビット 前計算 ステージ 実計算 ステージ 計 独立計算法 336.8Ｍ 2809.8Ｍ 3146.6Ｍ [CMO98] 既存法 1011.6Ｍ 1655.5Ｍ 2667.1Ｍ [HHM00] [Moe01] 提案法 279.2Ｍ 1655.5Ｍ 1934.7Ｍ 同時計算法 21/21 まとめ 問題 マルチスカラー倍の高速化 解決策 モンゴメリトリックを用いた逆元共通化 前計算テーブル作成手順の簡略化 成果 結果 約3倍 前計算の効率化により マルチスカラー倍の高速化を達成 ECDSAの検証の高速化 マルチスカラー倍高速化による スカラー倍計算の高速化
© Copyright 2025 ExpyDoc
