關於離散對數的問題 - 為什麼一個攻擊者不能解決 g 但兩個共謀者可以？
我正在閱讀 Fiat 和 Naor 的論文中描述的廣播加密，我截取了下面的相關部分。我的問題本質上是：
如果有秘密：
$ g^{abc} $ $ mod $ $ A $ （在哪裡 $ A=PQ $ （兩個足夠大的素數））
為什麼一位使用者知道：
$ g^d $ $ mod $ $ A $ , $ a $ , $ b $ , $ c $ , $ d $ ， 和 $ A $
無法計算 $ g^{abc} $ $ mod $ $ A $ 但是當您添加第二個知道 $ g^e $ $ mod $ $ A $ ， 和 $ e $ ，然後他們可以串通計算 $ g^{abc} $ $ mod $ $ A $ ?
上下文提供如下。
完整的論文可以在這裡找到
該論文指出，一個不在特權集中的使用者無法計算秘密，但兩個合謀的使用者可以（因此他們將方案評為 1-resilient）。
這個想法是，一個只知道的人 $ g^d \bmod N $ 和 $ d $ ，他們無法計算 $ g $ （因為他們不知道分解 $ N $ ; 因此這是 RSA 問題）；但是，如果他們知道 $ g^d \bmod N $ 和 $ d $ 和 $ g^e \bmod N $ 和 $ e $ , 那麼（假設 $ gcd(d, e) = 1 $ ），他們可以（並且一旦他們擁有 $ g $ , 他們可以計算 $ g^{abc} \bmod N $ ).
那是因為，既然他們知道 $ d $ 和 $ e $ , 他們可以計算兩個整數 $ s $ 和 $ t $ 這樣 $ sd + te = 1 $ （這就是假設 $ gcd(d, e) = 1 $ 進來; 如果那不是真的，那麼沒有這樣的 $ s $ , $ t $ 將存在）。一旦有了這兩個整數，他們就可以計算 $ (g^d)^s \times (g^e)^t = g^{sd + te} = g^1 = g $ , 恢復 $ g $ . 之一 $ s $ 和 $ t $ 將是負面的；這不是問題，因為我們可以對多個未知因式分解取模計算逆。