RSAタイミング攻撃をSquareに適合させ、右から左への乗算と左から右への乗算

Question

Kocherによるかなりよく知られているRSAタイミング攻撃を再構築しようとしています。シミュレートされたタイミングデータを使用しているので、完全にノイズのない「測定」ができます。私の攻撃は、「右から左へ」の二乗と乗算の方法、つまり次のようなアルゴリズムを使用している限り、指数の推測に成功します（R = b ^ d mod m、dはwビット）。

R = 1
for i from 0 to w-1:
  if getbit(d, i) == 1:
    R = R * b mod m
  b = b * b mod m

攻撃は、私のシミュレーションで使用しているモンゴメリモジュラー演算を使用する場合の条件付き削減に依存します。各ビットについて、2つのパス（ビットは0/1）をシミュレートし、追加の削減が実行されたかどうかによって測定値をグループ化します。グループ間の平均の差が大きいパスを選択します。うまく機能するもう1つの基準は、正方形+マルチ対正方形だけの時間を差し引いたときに、どのパスがすべての測定値の経験的分散を減らすかを確認することです。

今、私は攻撃を左から右の正方形に適応させて乗算しようとしています：

R = 1
for i from w-1 to 0:
  R = R * R mod m
  if getbit(d, i) == 1:
    R = R * b mod m

ビットを繰り返し推測するときに、2つのパスから選択するための適切な基準を見つけることができないようです。押して、間違って推測されたビットを修正しながら進むと、攻撃は引き続き下位ビットで機能しますが、最初は上位ビットでは完全に間違っています（常に1を推測します）。この種の二乗および乗算アルゴリズムに攻撃を適応させる方法についての情報源は見つかりません。

Answer 1

私はついに攻撃に適応することができました。解決策は、次のビットの二乗の削減を2つのグループ間の識別器として使用することです。我々はその二つの経路、すなわちに分割される(R^2 mod m)^2 mod mと(R^2*b mod m)^2 mod m。パスごとに、最終的なmodに追加の削減があるかどうかによって2つのグループを作成します。最後に、右から左へのバリアントのように、どちらの2つのグループの平均の差が大きいかを確認します。これは、前と同じように分散の違いをチェックすることで簡単に解決できる最後のビットを除いて、非常にうまく機能します。