Rsa
為什麼在 RSA 組的子組 QR(n) 中工作從∗n從n∗Z^*_n?
我有時在論文中讀到（子）組生成器 $ g $ 取自 $ \mathrm{QR}(n) $ 代替 $ \mathbb{Z}^*_n $ ， 在哪裡 $ n = p \cdot q $ 和 $ p $ 和 $ q $ 是素數。是否有一個原因？有什麼屬性 $ \mathrm{QR}(n) $ 有？它是一個特別大的子群嗎？
嗯，特定加密對象需要在特定子組中工作的原因可能與該對象的詳細資訊以及它需要來自子組的加密屬性有關。
一種明顯的可能性是他們需要避免通過雅可比符號洩露資訊。這是一個易於計算的函式，將值映射到 $ Z^*_n $ 進入集合中的值 $ {1, 0, -1} $ ; 這很有趣，因為 RSA 操作保留了它； $ Jacobi(x) = Jacobi(RSA(x)) $ （在哪裡 $ RSA $ 是公共或私人運營，並且 $ Jacobi $ 隱式依賴 $ n $ ).
根據您正在執行的操作，此屬性可能允許人們跟踪哪些輸入引用了哪些輸出（例如，如果您通過加密它們來隨機排列值，然後隨機排列它們）。確保此類事情不會導致問題的一種方法是指定所有輸入值都在 $ QR(n) $ ; 所有這些值都有雅可比符號 1，因此沒有洩漏。
在中創建隨機值也很容易 $ QR(n) $ ; 選擇一個隨機數 $ r $ 與 n 互質，併計算 $ r^2 \bmod n $ ; 這是一個隨機值 $ QR(n) $
至於大小 $ QR(n) $ ，好吧，那就是 $ (p-1)(q-1)/4 \approx N/4 $ ; 顯然，這是一個相當大的群體。