Modular-Arithmetic
Paillier：在知道密碼和隨機數的情況下猜測消息
我無法理解這一點。
在 Paillier 中，密文是使用
$ c = g^m.r^n\ mod\ n^2 $
在哪裡 $ (n,g) $ 形成公鑰和 $ r $ 是一個隨機數 $ 0<r<n $ .
假設攻擊者知道 $ c $ , $ r $ , $ n $ . 和 $ g $ ，平均需要多少時間才能找到 $ m $ ?
不用猜，就能找到 $ m $ 當然。
如果你知道的話 $ c,r,n,g $ ，那麼你可以消除 $ r^n $ 從密文中得到 $ c’=g^m \bmod n^2 $ .
在 $ Z_{n^2}^* $ ， 我們有 $ (n+1)^x = 1+nx \bmod n^2 $ ( $ x\in Z_n $ ）。所以：
- 如果 $ g=n+1 $ 被使用，那麼 $ c’=g^m \bmod n^2 =1+mn $ ，那麼你可以找到 $ m=(c’-1)/n $ .
- 如果 $ g\ne n+1 $ , 因為順序 $ g $ 必須是的倍數 $ n $ ， 我們有 $ g= (1+n)^a=1+an \bmod n^2 $ 對於一些 $ a $ ，那麼我們可以找到 $ a=(g-1)/n $ . 然後 $ c’=g^m \bmod n^2 =1+amn $ ，我們可以計算 $ m=(c’-1)/an $ .
根據布魯諾的評論添加：一般論壇（適用於所有人 $ g $ ） 是 $ m=(c’-1)/(g-1) $ .