Modular-Arithmetic
工作小組從∗p從p∗mathbb{Z}^*_p在實踐中
據說,給定一組 $ \mathbb{Z}^_p $ ,我們總是可以有一個階為素數的子群。為此,為了一個安全的總理 $ p=2q+1 $ , 計算 $ x_i^2 \bmod p $ 對全部 $ x_i \in \mathbb{Z}^_p $ .
問題:
- 我們是否只需要處理該子組中存在的值(其順序為素數)?
- 如果我們需要一些子組中不存在的值,但它們在 $ \mathbb{Z}^*_p $ ?
- 為了研究子群的元素,我們做 $ \bmod q $ ?
因為這種方式限制了我們對元素的選擇,我們不能處理任何任意值。
當使用任何依賴於決策 Diffie-Hellman 假設的密碼系統(例如,ElGamal、ECIES、Diffie-Hellman 密鑰交換等)時,您需要一組素數。注意 $ \mathbb Z_p^* $ 在哪裡 $ p $ 是素數有秩序 $ p-1 $ . 然而,如果 $ p=rq+1 $ 在哪裡 $ q $ 也是一個大素數,那麼你有一個子群 $ \mathbb Z_p^* $ 有秩序的 $ q $ . 如果你拿 $ r=2 $ , 那麼這些就是所謂的安全素數(曾經認為對於 RSA 最好使用這些類型的素數,這就是為什麼它們被稱為“安全”的原因;然而,今天,人們認為最好只選擇RSA 的隨機素數)。為了得到一個訂單子組 $ q $ ,確實你只取正方形。
回答您的具體問題:
- 對於我上面提到的密碼系統,是的,您必須在子組中工作。
- 您需要將所需的任何值映射到子組中。您可以通過平方來映射 1 和 q-1 之間的任何值。
- 不,你不這樣做 $ \bmod q $ 在元素上(你做 $ \bmod q $ 處理指數中的值時)。
我建議你讀一本書,提供加密所需的數論背景……