帶有加法 ElGamal 的負數
我正在嘗試使用附加的 ElGamal 公鑰加密系統來實現 Private Set Intersection。我編寫的程式碼可以使用 ElGamal 系統加密和解密數字，到目前為止一切都很好。添加和乘以密碼也可以。或者至少，它適用於正數。
據我了解模算術負數可以通過以下方式考慮： $ x + a = 0 \mod q $ 在哪裡 $ a $ 是一個負數。因此，如果我將組訂單設置為 8009 減去一罐是 8008，因為 $ 1 + 8008 = 0 \mod 8009 $ .
現在我注意到，無論我使用哪種發電機，當我使用 power-mod 時 $ g^{q-1} \mod q $ 結果總是 1。我還沒有深入研究加密的數學，但它似乎是一個一致的結果。 $ 2^6 = 1 \mod 7 $ , $ 1151^{8008} = 1 \mod 8009 $ 等等。這給我帶來了一個問題。由於使用了指數，整個“加法”部分就應運而生了，這樣 $ g^x g^y = g^{x+y} $ 但這在模算術中是真的嗎？ $ g^{-1} g^{+1} \mod q $ 應評估為 1 以具有 $ x + y = -1 + 1 = 0 $ , 但如果 $ g^{-1} \mod q $ 總是 1 然後結果 $ 1 * g $ 將只是 $ g $ ，所以我會落後一個。事實上， $ g^{-1} \mod q $ 總是一，但隨後 $ g^0 \mod q $ 也是1。這是怎麼回事？我真的很困惑。
現在我注意到，無論我使用哪種發電機，當我使用 power-mod 時，
g^(q-1) mod q結果總是1恭喜，你剛剛重新發現了費馬小定理，它說對於所有素數 $ p $ 和所有非零整數 $ a $ 不是的倍數 $ p $ , 它認為 $ a^{p-1}\bmod p=1 $ .
因此，如果我將組訂單設置為 8009 減去一罐是 8008，因為
1 + 8008 mod 8009 = 0.確實，這就是簡單加法的工作原理 $ \bmod 8009 $ ，但是您似乎實際上並沒有這樣做，實際上是在使用提升的 ElGamal，即加密為 $ (g^k \bmod p,g^m\cdot y^k\bmod p) $ （因為標準 ElGamal 只有乘法同態）。
但那時你不再添加 $ m+m’ $ 但你改為添加 $ g^m\cdot g^{m’}=g^{m+m’} $ 事實證明，這些指數在組中不起作用 $ \mathbb Z_p $ （IE $ \bmod p $ ) 而是在組中 $ \mathbb Z_{\operatorname{ord}(g)} $ ， 在哪裡 $ \operatorname{ord}(g) $ 是最小的非零整數 $ q $ 這樣 $ g^q\bmod p=1 $ . 如果您使用的是安全的素數 $ p $ ，即素數 $ p $ 這樣 $ (p-1)/2=q $ 也是素數，那麼 $ \operatorname{ord}(g) $ 可以恰好取 4 個值： $ 1,2,q,2q $ （由拉格朗日定理和乘法階數為 $ p-1 $ 為素數）。