Rsa
RSA 求冪中合適的視窗大小是多少？
我想使用 RSA 模冪運算的視窗方法。
由於旁道攻擊 (SCA)。
但我不知道合適的視窗大小是多少。
RSA 算法（如 OpenSSL）的許多實際實現的視窗大小（W ）與密鑰長度有關。例如，在openSSL庫中，對於不安全的 80 位密鑰，W是 4 或對於不安全的 320 位密鑰，W是 5，對於 1024 或2048 位密鑰（長度），W為 6。
注意：openSSL 庫中的最大視窗大小為“6”
A.Toumantsev 在他的評論中說“這取決於”是正確的；我會嘗試對此進行擴展。
首先，沒有一個“視窗方法”，有很多不同的變體，其中 $ w $ 最適合您將取決於您使用的確切版本。
用最基本的視窗方法，計算 $ a^e \bmod p $ ， 你：
- 計算 $ a^0 \bmod p, a^1 \bmod p, a^2 \bmod p, …, a^{2^w-1} \bmod p $ （使用 $ 2^w-2 $ 模乘法），
- 表示 $ e $ 作為基礎—— $ 2^w $ 整數為 $ e = d_n 2^{nw} + d_{n-1}2^{(n-1)w} + … + d_02^{0w} $
- 從…開始 $ d_n $ ，或者乘以 $ a^{d_i} \bmod p $ （查找您在步驟 1 中計算的表），並執行 $ w $ 模平方運算，以乘以結束 $ a^{d_0} $
這種非常基本的形式用於 $ k $ 位指數 $ e $ , $ 2^w-2 $ 乘法， $ k/w $ 數字的乘法，大約 $ k $ 平方運算（仔細程式可以減少少量）。
因此，“最佳”價值 $ w $ ，假設你的指數是 $ k $ 位長，是最小化的值 $ 2^w - 2 + k/w + k $ , 或 (刪除不涉及的項 $ w $ , $ 2^w + k/w $ .
如果您使用 CRT 執行 2048 位 RSA（因此在私鑰操作期間， $ e $ 將是一個 1024 位整數），然後一個簡單的計算表明 $ w=6 $ 將是可選的，並且 $ w=5 $ 只會稍微差一點。如果 $ e $ 是一個 2048 位整數，那麼 $ w=6 $ 顯然是最優的。
現在，警告幾句：
- 這種分析假定了非常基本的視窗方法。但是，如果您真的擔心旁道攻擊，則不太可能使用非常基本的方法，因為如果您不小心，它可能會洩漏很多。您更有可能使用一些變體；該變體的工作方式可能會修改分析。
- 實際上，使用不太理想的 $ w $ 並不是那麼昂貴（除非你使用一個太大的 $ w $ ); 其中最大的成本是重複平方，並且 $ w $ 並沒有做太多的事情來防止這種情況。你可能（比如說）決定使用一個固定的 $ w=4 $ ; 這需要更長的時間，但它可以簡化數字的計算 $ d_i $ ，並且這種簡化可能會超過小時間成本。