DLP和DH的超級基礎問題
這是一個超級基本的密碼學，我不明白。我的教授只是在非常抽象的層面上向我們解釋了它，我沒有質疑就同意了。
DLP 說計算 a^x 很容易，但如果使用循環群，用對數求 x 並不容易。循環組背後的想法是對數字進行洗牌。如果你不這樣做，你可以猜測指數的方式，因為數字是有序的，你知道如果你得到一個兩個高或兩個低的數字，你可以猜測正確的方向。
太抽象了，我明白了。但非常具體，我不知道。
我不明白 我的意思是，DH Alice 發送 g^x 和 g，Bob 發送 g^y。所以邪惡的人得到了g、g^x和g^y。她想找到給她 x 的 log_g(g^x)。她的問題是什麼？她知道 g 並且她知道數字 (g^x) 是什麼。
我的意思是，我不知道如何在計算器上輸入這個，因為我們只使用了 log_e（也稱為 ln）和 log_10（只是登錄我的計算器）。如果我拿起我的計算器並輸入 log(100)，即 log_10(100)，我得到 2。這是我要查找的數字。為什麼夏娃不能這樣做？
對不起，這是一個非常愚蠢的問題，但我太羞於問除了你以外的任何人^^
感謝這個問題的批判性思維。保持這種態度！
夏娃想找到 $ \log_g(g^x) $ 這給了她 $ x $ . 為什麼會出現問題？她知道 $ g $ 她知道號碼是多少 $ g^x $ 是。
此報價中所述的問題以及 $ g $ 在集合中 $ \mathbb Z $ （整數）是僅限於整數的對數問題，確實很容易。只看大小 $ g^x $ （十進制的位數），很容易知道有多大 $ x $ 是。例如，如果 $ g $ 是 $ 11 $ , $ g^x $ 會有點過 $ x $ 十進制數字。更一般地說， $ x $ 是 $ \log(g^x)/\log(g) $ , 在實數上用任何底數的對數計算。
在離散對數問題中， $ g^x $ 不是通過正常整數乘法計算的。它是在具有群結構的有限集中計算的。 $ g^x $ 被約束在與 $ g $ 是，無論多大 $ x $ . 這有很大的不同，因為 Eve 總是得到一個很小的值，因此基於大小的技術 $ g^x $ 將不再工作。
最簡單的可用群是乘法群以安全素數為模 $ p $ . 在這個組中， $ uv $ 被定義為歐幾里得除法的餘數 $ u\cdot v $ 經過 $ p $ ， 在哪裡 $ u\cdot v $ 是普通產品。 $ g^x $ 像往常一樣定義：$$ g^x=\underbrace{gg\ldots g*g}_{x\text{ terms}} $$ 其中每個 $ * $ 是有限集中的一個操作。注意 $ g^x $ 可以用計算 $ \approx1.5\log_2(x) $ 模乘法，而不是顯而易見的 $ x-1 $ .
為了說服你事情很艱難，試試 $ p=31469 $ （足夠小， $ u\cdot v $ 適合 9 位小數）， $ g=3 $ , $ g^x=11292 $ . 你怎麼獲得 $ x $ ?
一種簡單的方法是嘗試所有 $ x $ 依次，有成本 $ \Theta(p) $ （請注意，我們可以移動到下一個冪 $ g $ 單模乘法）。一個更好的方法是baby-step/giant-step，它有成本 $ \Theta(\sqrt p) $ 在工作和記憶中。然而，一種更好的（機率）方法是Pollard 的 rho，它也需要 $ \Theta(\sqrt p) $ 工作，但減少記憶體需求 $ \Theta(1) $ ，並且可以在很大程度上並行化。
因為我們使用了一個特別簡單的組，所以還有更好的方法。但是，對於橢圓曲線組，我們不知道在我們所知道的電腦上工作的更好方法。因此，如果我們使用具有足夠元素的合適組（例如，按 $ 2^{256} $ )，我們知道的最好的方法 $ x $ 需要按順序 $ 2^{128} $ 在我們所知道的電腦上進行分組操作。