為 RSA-KEM 生成 r 的按位方法
看來RSA-KEM有一個很麻煩的生成秘鑰的方法 $ r $ . 看來隨機值需要在範圍內 $ 0 \le r \le {n - 1} $ .
現在大多數加密環境都沒有生成這些數字的隨機數生成器。通常它們只提供一個輸出完整字節的種子 DRBG。對字節執行各種整數運算可能會導致這些環境中的主密鑰洩漏。特別是 $ \bmod $ 在這方面，操作似乎很棘手。
有沒有一種已知的好方法來生成 $ r $ 處理 $ \bmod $ 操作和可能的循環？
例如，我可以考慮建構 $ r $ 作為
00 | R
|操作當然是串聯。在這個建築 $ R $ 然後是一個由（偽）隨機字節組成的八位字節字元串。 $ r $ 由
00 | R用作大端無符號整數時的值組成。它可以直接用作大多數庫實現的原始“RSA 加密”的輸入。這將提供 $ \operatorname{len}(R) * 8 $ KDF 的熵位。我認為那將是 $ \lfloor (log_2(n) - 1) / 8\rfloor \cdot 8 $ 根據模值測量時的熵位 $ n $ .
當然，否則該計劃將保持不變；不會對 $ r $ 在解密期間。
這是否足以作為一種安全的建構方案？ $ r $ 而不是執行整數計算和檢查以達到 $ 0 \le r \le {n - 1} $ ?
這裡有幾個選項。我包括模組化減少和拒絕抽樣，因為我懷疑它們的成本比您擔心的要低。
- 您的建議大致是：選擇 $ r $ 均勻地在 $ {0, 1, 2, \dots, 2^{\lfloor\log_2 n\rfloor} - 1} $ .
如果存在具有成功機率的 IND-CCA2 或 NM-CCA2 對手 $ p $ 針對 RSA-KEM $ r $ 統一在 $ {0, 1, 2, \dots, n - 1} $ , 同一個對手的成功機率不能超過 $ 2p $ 因為我們要刪除的可能空間不到一半 $ r $ . 如果 $ 2p $ 太高了，那麼 $ p $ 幾乎可以肯定已經太高了。如果按照您的建議將高字節設置為零，那麼您將刪除更多的輸出空間並且它是 $ 256p $ 而不僅僅是 $ 2p $ .
理論關注點：RSA 問題的標準安全簡化$$ 1 $$，它展示瞭如何將 IND-CCA2 攻擊者轉變為計算程序 $ e^{\mathit{th}} $ 根模 $ n $ , 將不再適用，因為保證不會覆蓋不到一半的空間。很難想像一般的RSA 問題很難，但如果將其限制在這個域中就會變得容易；但是，您消除的空間越多，減少與證明安全性的關係就越不相關，因此將高位設置為零比按照您的建議將高字節設置為零更好。 2. 模組化減少：挑選 $ r $ 均勻地在 $ {0, 1, 2, \dots, 2^{\lfloor\log_2 n\rfloor + k} - 1} $ 在哪裡 $ k $ 是，比如說，64 或 256，如果你是偏執狂或 $ \lfloor\log_2 n\rfloor $ 如果你真的很偏執，減少模數 $ n $ .
您不需要通用除法常式：您可以輕鬆地減少 $ r $ 模組 $ n $ 如果您預先計算，只需使用兩次乘法和一次減法即可在恆定時間內使用 Barrett 減少 $ 2^{\lceil\log_2 n\rceil}/n $ （在恆定時間內進行逐位長除法，如果 $ n $ 永遠是秘密的），只要 $ r < n^2 $ .
這並沒有給出均勻的分佈，但它非常接近——比選項 (1) 更接近，如果沒有其他原因，它沒有完全排除任何 $ \mathbb Z/n\mathbb Z $ 像（1）一樣。（讀者練習：量化模偏差，比如說，總變異距離——這對 IND-CCA2 或 NM-CCA2 對手與真正均勻分佈的優勢進行了類似的限制。） 3. 拒絕抽樣：Pick $ r $ 均勻地在 $ {0, 1, 2, \dots, 2^{\lceil\log_2 n\rceil} - 1} $ ，並重新開始，如果 $ r \geq n $ .
自從 $ 2^{\lceil\log_2 n\rceil}/2 < n < 2^{\lceil\log_2 n\rceil} $ , 試驗次數按機率幾何分佈 $ p < 1/2 $ ; 預期的試驗次數剛剛超過 1 次，遠低於 2 次。顯然，試驗次數永遠不會超過 128 次——對於 4096 位 RSA 模數，您需要生成遠少於 4096 KB 的數據。
這保證了均勻分佈 $ r $ 在 $ {0, 1, 2, \dots, n - 1} $ .