拡張2進GCD法を用いた道元演算の実装に対するサイドチャネル攻撃

摘要

暗号を安全に実装するにはデバイスの消費電力などを分析して秘密鍵を特定するサイドチャネル攻撃への対処が不可欠である．公開鍵暗号の実装への攻撃や対策は専らべき乗剰余演算を中心に検討されてきたが，他の演算に関する検討が不足しているように思われる．本論文ではRSA鍵生成などで必要となる道元演算へのサイドチャネル攻撃の適用可能性について検討する．具体的には道元演算法の一つである拡張2進GCD法に対し，消費電力などから漏えいする情報を特定し，逆元演算の入出力の全てを復元するアルゴリズムを構成する．この適用例として，RSA鍵生成中の消費電力などを分析して6ミリ秒以下で秘密鍵を特定できる場合を示す．このように逆元演算についてべき乗剰余演算と同様にサイドチャネル攻撃への対策が必要であることを指摘する．