模冪的定時攻擊
眾所周知，計算 $ a^x \bmod N $ 需要 $ O(|x| + \mathrm{pop}(x)) $ 乘法模 $ N $ ， 在哪裡 $ |x| $ 是位數 $ x $ 和 $ \mathrm{pop}(x) $ 是數量 $ 1 $ 位（漢明權重）。這表明通過測量求冪的執行時間來進行側通道攻擊。
可數 $ 1 $ 位是從執行時派生的，它能否以某種方式加快查找 $ x $ 如果 $ a $ 和 $ N $ 是已知的（假設沒有使用對策）？
可以採取哪些對策？
針對函式的定時攻擊 $ f_k $ 一般需要兩件事：
- 攻擊者可能會觀察目標執行 $ f_k(x) $ 對於大量足夠多樣化的已知輸入 $ x $ .
- 對於每個 $ k $ , 有輸入 $ x $ 和 $ x’ $ 這樣 $ f_k(x) $ 和 $ f_k(x’) $ 預計以不同的速度執行。
現在，讓我們假設 $ f_k $ 是 Diffie-Hellman 或 RSA 的私鑰操作，即 $ k $ 是目標的（固定）私有指數，並且輸入是例如 2048 位整數值。通常，執行操作 $ f_k(x) = x^k \mod p $ 是這樣的，它執行完全相同數量的 CPU 指令，而不管 $ x $ ，因此不會有時間差異可觀察（假設 CPU 以固定數量的時鐘週期執行例如 MUL 或 DIV）。
然而，有一些事情需要注意。如果有些 $ x $ 顯著小於 2048 位的最大大小，並且模乘的實現經過優化以考慮到這一點，一些最低或最高有效位 $ k $ 可能會洩漏，具體取決於求冪實現是從右到左迭代指數的位還是相反。由於中間結果呈指數增長，因此在最不利的情況下，這只會顯示最多 11 位的指數 $ x=2 $ .
為了防止這種洩漏（再次假設 CPU 以固定數量的周期執行 MUL 指令等，與操作數的值無關），防止這種洩漏所需要做的就是證明所有輸入的大小與取冪函式實現開始時的模數。
現在，在下一個案例中，假設攻擊者能夠反复減慢系統速度，此時目標將執行模乘，因為私有指數的相應位 $ k $ 是 $ 1 $ ，或者不執行模乘，因為該位是 $ 0 $ . 可以說，如果模冪運算是由例如多執行緒應用程序中的 CPU 執行的，那麼如果攻擊者可能以某種方式控制 CPU 執行的其他內容，無論是被動的還是主動的，這都能以某種統計準確性完成。
即使在這種情況下，使私鑰不可見的一種簡單方法是始終生成一個新的隨機整數 $ z $ 這是可逆的 $ \mod q $ 在哪裡 $ q $ 是順序的倍數 $ x $ （例如 $ p-1 $ 如果訂單未知）。而不是計算 $ f_k(x) = x^k \mod p $ , 你會計算
- $ k’ = kz \mod q $
- $ y = x^{k’} \mod p $
- $ w = y^{z^{-1}\mod q} \mod p $
- 返回 $ f_k(x) = w $
這裡唯一依賴於私有指數的步驟是第一步，必須假設它的執行時間不會根據 $ k $ . 該方法的成本平均為 2 倍，假設模逆 $ Z_q $ 可以在微不足道的時間內計算出來。
另一種技術是使模乘的數量完全獨立於私有指數的位，例如通過使用滑動視窗技術。這意味著一個表 $ 2^m $ 建構整數，並為每個選擇其中一個值 $ m $ 私有指數的二進製表示的位。但是應該注意，這種技術可能會使事情變得更糟，例如，如果從表中選擇一個整數的時間取決於該元素的索引。
還應該注意的是，雖然有人提倡對輸入值進行盲化 $ x $ to-be-raised，而不是私有指數，這將對獨立於操作數的值執行 MUL 的 CPU 沒有影響，並且對測量相對時間差的被動和主動定時攻擊都沒有影響正在處理指數中的哪個位位置。
存在有效的恆定時間取冪算法。例如，可以如下計算一個序列： 給定 $ a^{k}, a^{k+1} $ 計算 $ a^{2k+2}, a^{2k+1} $ 或者 $ a^{2k}, a^{2k+1} $ . 兩種計算的不同之處僅在於哪個值是平方的，哪個是相乘的，這使得它們易於使用單個條件交換作為唯一的區別特徵來實現。選擇從哪個開始 $ 1, a $ 將取決於指數的高位。這些方法用於橢圓曲線密碼學：查找蒙哥馬利階梯等。