檢查此密碼系統是否安全

讓 $ G $ 是可以快速執行組運算以及找到元素的逆的任何組，但離散對數問題很困難。考慮以下密碼系統：

1. Alice 選擇一個元素 $ g ∈ G $ ， 一個消息 $ m ∈ G $ , 和一個整數 $ k_A $ .
2. 愛麗絲計算 $ s = mg^{k_A} $ 並發送 $ s $ 給鮑勃。
3. Bob 選擇一個整數 $ k_B $ , 計算 $ t = sg^{k_B} $ , 並發送 Alice $ t $ .
4. 愛麗絲計算 $ u = tg^{−k_A} = mg^{k_B} $ 並發送 $ u $ 給鮑勃。
5. Bob 計算 $ ug^{−k_B} = m $ 並恢復消息。

這個密碼系統安全嗎？我注意到夏娃有 $ s $ , $ t $ ， 和 $ u $

並且它們都可以被m整除。這是否意味著它不安全？或者我錯過了什麼？

幫助表示讚賞

這是非常不安全的。離散對數是一條紅鯡魚 - 問題中沒有任何地方與離散對數相關的困難，因為任何一方都沒有使用他們的私人指數知識（計算 $ g^{-k} $ 給定 $ g^{k} $ 不需要知識*_* $ k $ ，所以如果逆數很快找到，知道一個很快就會給你另一個）。這意味著我們可以忽略求冪；你所擁有的只是愛麗絲採摘 $ a\in G $ 和鮑勃採摘 $ b\in G $ ， 所以 $ s=ma $ ， 然後 $ t=mab=sb $ ， 然後 $ u=ta^{-1}=mb $ . 夏娃攔截 $ s,t,u $ , 併計算 $ s^{-1} $ ， 然後 $ s^{-1}t=b $ ， 然後 $ b^{-1} $ ， 然後 $ ub^{-1}=m $ . 問題不在於它們都可以被除以 $ m $ , 是你靠保持 $ a $ 和 $ b $ 私人但隨後發送 $ s $ 和 $ sb $ 通過公共渠道（這意味著攻擊者可以輕鬆恢復 $ b $ 因此 $ m $ ).

在實際的 ElGamal 中，您實際上使用了您的私有指數。而不是必須保持 $ g^{k_A} $ 和 $ g^{k_B} $ 秘密，你相信愛麗絲（誰知道 $ g^{k_B} $ 和 $ k_A $ ) 可以計算 $ g^{k_Ak_B} $ 而攻擊者不能。要使用離散對數的安全性，您必須做一些對知道指數的人來說容易但對其他人來說很難的事情；找到倒數並不是什麼。

引用自：https://crypto.stackexchange.com/questions/22884