加密協議中的隨機抽樣與遞增隨機性
作為我的問題的一個例子，我發布了 ECDSA 簽名算法以供參考（來自wikipedia）來簽署消息 $ m $ :
- 計算 $ e = H ( m ) $ .
- 選擇一個隨機整數 $ k \in [ 1 , n − 1 ] $
- 計算曲線點 $ ( x_1 , y_1 ) = k × G $
- 計算 $ r = x_1 $ 反對 $ n $ . 如果 $ r = 0 $ , 回到第 2 步。
- 計算 $ s = k ^{− 1} ( z + r d_A ) $ 反對 $ n $ . 如果 $ s = 0 $ , 回到第 2 步。
- 簽名是對 $ ( r , s ) $
我的問題如下。當第 4 步或第 5 步失敗時，即 $ r=0 $ 或者 $ s=0 $ 該算法需要循環並採樣一個新的隨機數 $ k $ （儘管這種可能性很低，因為訂單 $ n $ 該組的 $ G $ 很大）。但是在那種情況下，為什麼算法需要做一個新的隨機抽樣呢？增加不是更有效嗎 $ k $ 反而？我以 ECDSA 為例提出了這個問題，但這也適用於其他加密協議，我看到到處都重新採樣隨機性而不是遞增。從安全的角度來看，增加隨機性不應該有所作為。
從安全的角度來看，增加隨機性不應該有所作為。
“回去”而不是做一些特殊的邏輯有兩個原因。
第一個原因是減少“難以測試”的專用程式碼的數量。任何“增加”的方式 $ k $ ’ 將涉及極少執行的程式碼（並且很難為其設計單元測試）。任何此類難以觸摸的程式碼都是未檢測到的編碼錯誤的肥沃場所，因此應盡可能避免。相比之下，返回並重新執行本質上相同的過程更不容易出錯。
另一個原因是重用被認為“不可接受”的數據可能會洩漏。
例如，假設攻擊者能夠檢測到這種增量何時發生（例如，通過密切監視生成這種簽名所花費的時間），並且它確實發生了，因為 $ s=0 $ . 如果是這樣，我們剛剛洩露了私鑰。
這是如何發生的：在第一次迭代中，我們計算 $ s = k^{-1}( z + rd_A ) $ 並發現它是 0。所以，我們這樣 $ r’ = ((k+1)G)_x $ 而是輸出（並繼續計算 $ s’ $ ，此攻擊不使用）。
攻擊者可以做的是重建點 $ (k+1)G $ 從我們剛剛給他的 x 座標（實際上，這是兩點之一；這只是意味著他都嘗試了）；然後允許他重新計算 $ kG $ ，因此原來的 $ r $
現在，他知道了 $ k^{-1}(z + rd_A) = 0 $ ， 現在 $ k^{-1} \ne 0 $ （逆從不為零），所以 $ d_A = -r^{-1}z $ ; 他知道 $ z $ （來自已簽名的消息）和 $ r $ ，這給了他私鑰 $ d_A $ .
現在，如果我們選擇一個完全隨機的 $ k $ 每次，我們都不必擔心像這樣不明顯的攻擊。
現在，在實踐中，這 $ s=0 $ 條件基本上永遠不會發生（它發生的機率與對私鑰的隨機猜測恰好是正確的機率相同），所以看起來我們似乎不需要擔心它。我仍然相信不易出錯且更安全的方法，即使它需要更多時間（如果它幾乎不會發生，它所花費的時間通常是無關緊要的）。