尾崎 友哉
通信の安全性を確保する上でデータの秘匿化は不可欠であり, その具体的な実装手段として暗号技術が用いられる. なかでも, 解読の計算量的困難性を安全性の根拠とする公開伴暗号方式は, 現代の通信基盤を支える主要な暗号化方式の一つである. 公開伴暗号の例として RSA 暗号や楕円曲線暗号, 同種写像暗号などが挙げられるが, その計算過程で必要となるモジュラ逆元計算は, 他の論理演算と比較して計算時間が多くかかるため実装におけるボトルネックとなっている. 公開伴暗号そのものが数学的に安全であると証明されていても, 実装において同様の安全性が担保されるとは限らない. 実システムへの実装での脅威の一つが, 計算時間の変動から秘密伴を特定するタイミング攻撃などのサイドチャネル攻撃 (SCA) である. この攻撃に耐性を持たせるためには, 入力値に依存せず実行時間を一定にする定数時間実装が不可欠である. しかし, 定数時間を担保するには最も計算コストがかかる入力に合わせたアルゴリズムが必要となり, 平均的なケースで冗長性が生じるため, 効率的な実装手法の確立が課題となる. 本研究では, 定数時間モジュラ逆元計算 (CTMI) で注目されている Bernstein-Yang の divstep アルゴリズムおよび改良手法として提案されている Jin-Miyaji の手法 (JM) , Kuramoto-Miyaji の手法 (KM), Pornin の手法 (Pornin) に対し, アルゴリズムの反復回数と 1 回の反復にかかるコストを解析する. その結果得られた知見に基づき, まず 1 つ目に JM, KM に対するより厳密な反復回数の証明を与える. 2 つ目に, 定数時間性を保持しつつ既存手法のボトルネックを改善し新たな CTMI アルゴリズムを提案する. このアルゴリズムは実験環境である 13th Gen Intel Core i7-1360P @ 2.2Ghz において KM より 93.12%, divstep より 21.52%, Pornin より 9.70% 計算時間が削減されたことを確認している.
