はじめに

この記事では，A Timing Attack against RSA with the Chinese Remainder Theoremの論文を解説し，なぜタイミング攻撃が脅威となるのかを説明したいと思います．この論文では，RSA暗号システムにタイミング攻撃を仕掛け，公開鍵 $n=pq$ を多項式時間で素因数分解する手法を提案しています．

なお，この記事ではRSA暗号の詳しい説明については省略させていただきます． RSA暗号についてはこちらの記事を参考にしてください．

www.tomonori4565.com

RSA暗号の説明で登場する変数の説明

本記事で登場する変数を簡単に説明します．

$c$ : 暗号文
$m$ : 平文
$n$ : 公開鍵( $n = pq$ を満たし， $p, q$ は素数である)
$e$ : 公開鍵
$d$ : 秘密鍵

その他の変数については，アルゴリズム中の記載を確認してください．

タイミング攻撃とは

暗号システムの復号処理時間を観測することにより，内部で使用されている秘密鍵を復元する攻撃をタイミング攻撃と呼びます．身近な例をあげると，暗号機能を内蔵したICカードなどが攻撃対象になりやすいです．復号するときの処理時間の差を繰り返し読み取ることによって，正しい秘密鍵を復元できる可能性があります．

秘密鍵と処理時間の関係

なぜ復号処理時間を観測することで秘密鍵に関する情報を取得できるのか説明します．まず，処理時間と秘密鍵には密接な関係があります．その関係について説明するために，RSA暗号の代表的な復号アルゴリズムである「バイナリ法」を以下に紹介します．

アルゴリズムに関する詳しい説明は省略しますが，ポイントなのは4, 5行目です． 4行目で秘密鍵 $d$ の $i$ 番目のビットが1であるかどうかをチェックし，もし1ならば5行目の処理を追加で実行します．追加で処理を行うということは，その分処理時間が長くなるということになります．したがって，「処理時間が長い $\Leftrightarrow$ 5行目の追加処理をたくさん実行している $\Leftrightarrow$ 秘密鍵 $d$ のビット列に1がたくさん含まれている」という関係が成立します． 処理時間を観測することによって，秘密鍵 $d$ のビット列に含まれている1の数を予想することができるのです．

このように，処理時間と秘密鍵には密接な関係が存在していることがわかりました．ですが， $d$ のビット列に含まれている1の数が分かったところで，あまりいいことはありません．例えば， $d$ の鍵長を1024ビットだとして，その中に1が500個含まれていると分かったとしましょう．さて，そのような条件を満たす $d$ は何通り存在するでしょうか？

数学が得意な人は簡単だと思いますが，おおよそ $\binom{1024}{500}$ 通りになります( $d$ のmost significant bitとleast significant bitは本来1であるはずなので，正確には $\binom{1022}{498}$ 通り程度になります)．かなり膨大な候補数になるので，全探索で正しい秘密鍵を見つけることは現実的に不可能です．

したがって，タイミング攻撃は以前まで脅威のある攻撃だとは認識されていませんでした．しかし，本日紹介する論文 A Timing Attack against RSA with the Chinese Remainder Theorem をきっかけに，タイミング攻撃が脅威であるという認識が広まりました．

論文の内容について

ここから論文の内容を説明します．論文自体はかなり数学的な議論をたくさんしておりますが，本記事では分かりやすさを重点において説明するため，なるべく数学的な議論を排除して解説します．そのため，厳密さには少し欠ける部分があるので，その点についてはご容赦願います．

CRT-ModBin法とは

この論文では，攻撃対象のRSA復号アルゴリズムとして「CRT-ModBin法」というものを採用しています． CRTは，Chinese Remainder Theorem (中国人の剰余定理)のことを指します． ModBinは，Montgomery Binaryの略で，Montgomery乗算という手続き(Montgomery Reduction)を利用したバイナリ法のことを指します．

詳しいアルゴリズムの説明については省略いたしますが，このアルゴリズム自体ものすごく数学的に面白い議論がされているので，興味がある方は一度調べてみてください．

なお，本記事を読み進めるにあたり，以下のアルゴリズムの詳細を理解していただく必要はありません．

Schindlerの提案手法のポイント

ここからの議論は，CRT-ModBin法の3行目を実行しているときを考えます(4行目は $p$ を $q$ に入れ替えるだけで，その他に変わりはありません)．なお，CRT-ModBin法の3行目と4行目が復号時間に大きな影響を与えていますが，それ以外は大きな影響を与えていないことに注意してください．

Schindlerは，ModBinアルゴリズム内の4, 6行目で利用されているMR(Montgomery Reduction)アルゴリズムの3行目(と6行目)に注目しました．説明を簡単にするために，MRアルゴリズムの6行目を「Extra Reduction」と呼ぶことにします．MRアルゴリズムの3行目がfalseである(つまり， $m_2 \geq n$ )場合，Extra Reductionが発生することになります．実は確率的な議論によって，ModBin法の4行目と6行目を実行した場合に，Extra Reductionが発生する確率をそれぞれ $p/(3r), c_p/(2r)$ と導出することができます．

ここで注目すべきポイントは，ModBin法の6行目においてExtra Reductionが発生する確率が $c_p/(2r)$ であるということです． $c_p = c \bmod p$ であり， $c$ は攻撃者が自由に復号システムに投入できる暗号文です． つまり攻撃者が投じる暗号文の種類によって，ModBin法の6行目においてExtra Reductionが発生する確率を変化させることができるのです．

ここで次のようなシナリオを考えましょう．

攻撃者は暗号文の値を繰り返し1インクリメントさせながら，復号システムに次々と投入します．暗号文が大きくなるにつれて，相対的に $c_p = c \bmod p$ の値も大きくなります．つまり，Extra Reductionの発生頻度が多くなるため，復号処理時間が長くなります．しかし， $c$ がpの倍数になった瞬間， $c_p = 0 \bmod p$ となります．この瞬間に，Extra Reductionはパタっと発生しなくなります．つまり，復号処理時間は急に短くなります．

攻撃者はこの処理時間の瞬間的な変化を観測した瞬間，「先ほど投入した暗号文 $c$ は $p$ の倍数だったんだな」と認識することができます． そして， $c$ が $p$ の倍数だと分かると，とても嬉しいことがあります． $c$ と $n(=pq)$ の最大公約数をユークリッド互助法等で導出すると，秘密鍵 $p$ が計算できるのです！ $p$ が分かると， $q=n/p$ より $q$ も導出できるので，公開鍵 $n$ が素因数分解できてしまいます．