Sliding window法からの漏洩情報を用いた秘密鍵復元攻撃の改良

摘要

暗号のアルゴリズムを実装した際に，物理的に秘密鍵に関する情報の一部が漏洩することがある．公開鍵暗号の一種であるCRT-RSA 暗号は復号する際にべき乗を行うが，ある実装ではSliding window 法を使用する．Sliding window 法はwindow サイズw を決め，2 乗算（S）と掛け算（M）を繰り返すことにより行われる．Sliding window 法の際，S とM の実行履歴（SM 時系列）が漏洩することが知られている．2017 年に，Bernstein [1] らはSM 時系列から秘密鍵のビットを部分的に復元するルールを提案するとともに，SM 時系列に基づいた，CRT-RSA 暗号の秘密鍵dp; dq の復元実験を行った．しかし，これ以上ビットの復元ができない最適性証明は与えられていない．本研究では，新たにビット復元ルールを提案し，最適性を証明した．比較するために， 改めて実装したBernstein らのルールと，提案したルールの双方について，実験を行った．その結果，w = 4 では，秘密鍵復元の成功率が18%から29%まで向上した．さらに，秘密鍵d のSM 時系列も漏洩した時，w = 6 まで鍵全体の復元が可能であることを実験で示した．