特定形式的致盲值

我正在使用以下 C++ 程式碼為 RW 簽名創建致盲值的實現：

Integer r, rInv;
ModularArithmetic modn(m_n);

do {
   // Do this in a loop for people using small numbers for testing
   r.Randomize(rng, Integer::One() /*min*/, m_n - Integer::One() /*max*/);
   rInv = modn.MultiplicativeInverse(r);       
} while (rInv.IsZero() || (Jacobi(r % m_p, m_p) == -1) || (Jacobi(r % m_q, m_q) == -1));

添加了 Jacobi 測試以修復 Sidorov 的破壞 Rabin-Williams 數字簽名系統…和 ​​CVE-2015-2141。

儀器顯示循環可以執行 1 次到 10 或 12 次（我相信預期的平均值是 8 次）。

我覺得有一種方法可以加快循環的執行。我開始在 HAC 和 Google Scholar 中查找，但沒有找到相關的文章或論文。我嘗試了一些簡單的加速，但它們沒有產生預期的加速或限制更壞的情況。第一個是在範圍內生成一個隨機整數 $ [1, n - 1] $ 那是一致的 $ 3 mod 4 $ . 第二個是在範圍內生成兩個較小的整數 $ [1, p - 1] $ 和 $ [1, q - 1] $ （兩者一致 $ 3 mod 4 $ )，然後將它們相乘。

有什麼方法可以加快循環的執行速度，使致盲值 $ r $ 通常在 1 或 2 次嘗試後滿足條件？

或者上面的實現是否理想？

---

一個相關的問題是Rabin-Williams，Integer r 的致盲和大小？在這個問題中，我探索了較小的隨機整數來掩蓋操作。

您正在做的是以下內容：

1. 選擇一個隨機數 $ r $ 在 $ [1,2^n-1] $ .
2. 檢查是否 $ r $ 是可逆的 $ \bmod n $
   （應該有機率 $ \approx1-2^{-1000} $ ，因為隨機運氣你必須打 $ p $ 或者 $ q $ )，
   如果不是，請轉到 1。
3. 檢查是否 $ (\frac{r}{p})=(\frac{r}{q})=1 $
   ( $ (\frac{a}{n}) $ 表示雅可比符號），
   如果不是，則轉到 1。

因此，為了加快這一算法的速度，需要了解第 3 步的作用。

“它計算一些雅可比/勒讓德符號”太容易了。

此步驟可確保 $ r $ 是一個正方形 $ \bmod p $ 和 $ \bmod q $ . 因此，它確保 $ r $ 是一個正方形 $ \bmod n $ , 因為如果 r 是一個正方形 $ \bmod $ $ p $ 和 $ q $ 比它也是一個正方形 $ \bmod pq $ . 計算是分開的，而不是像 $ (\frac{r}{n}) $ 因為 $ (\frac{r}{n})=(\frac{r}{p})*(\frac{r}{q}) $ 而如果 $ (\frac{r}{p})=(\frac{r}{q})=-1 $ 然後 $ (\frac{r}{n})=1 $ . 所以這不適用於優化。

但還有另一種方式。

第 3 步確保我們確實有一個正方形 $ \bmod n $ , 那麼我們為什麼不構造 $ r $ 成為一個正方形 $ \bmod n $ ? 因此“新”算法看起來像這樣（抱歉，我忘記了 Crypto++ 的正確函式，請在評論中發布它們）

Integer r, rInv;
ModularArithmetic modn(m_n);

do {
   // Do this in a loop for people using small numbers for testing
   r.Randomize(rng, Integer::One() /*min*/, m_n - Integer::One() /*max*/);
   r = r*r%n; // square it, there was a better function for this IIRC
   rInv = modn.MultiplicativeInverse(r);       
} while (rInv.IsZero()); // we don't need the symbols because r is always a square

那麼這有什麼安全隱患呢？

我不確定，無論哪種情況，您都應該聯繫論文的作者並確保此解決方案有效。

的平方 $ r $ 不應該損害隨機性/不可預測性，就好像 $ r $ 是隨機的， $ r^2\bmod n $ 也應該是隨機的/不可預測的。

定時攻擊？我認為這不應該是一個問題，因為攻擊者可能只觀察一個平方，然後再觀察一個相關的平方，這使得它很難使用。（如果不是不可能的話）

還有什麼好說的？

您甚至可以儲存“舊” $ r $ 如果你需要“新”的平方根 $ r $ 在後面的步驟中。

新算法如下所示：

1. 選擇一個隨機數 $ r $ 在 $ [1,2^n-1] $ .
2. 放 $ r \gets r^2 \bmod n $
3. 檢查是否 $ r $ 是可逆的 $ \bmod n $
   （應該有機率 $ \approx1-2^{-1000} $ ，因為隨機運氣你必須打 $ p $ 或者 $ q $ )，
   如果不是，請轉到 1。

引用自：https://crypto.stackexchange.com/questions/26226