Discrete-Logarithm
如何防止離散對數問題的解被意外以碰撞方式找到
假設有一個流行的系統被大量的人廣泛使用。它的安全協議為有限群提供了一個生成器 $ g $ ，並且使用者需要選擇一個隨機數 $ r $ 併計算 $ h=g^r $ 在某個階段。這在許多方案中很常見。
由於這個系統被很多人廣泛使用，兩個使用者選擇相同的可能性 $ r $ 可能不可忽視。在這種情況下，使用者可能會意外發現他人使用的隨機數，從而導致一些安全問題。
這個問題值得考慮嗎？如果是這樣，有什麼辦法可以防止它？或者，我錯了，發現這種碰撞的可能性實際上可以忽略不計？
即使所有使用者都知道 $ h $ 所有其他值，避免碰撞並不難，你只需要確保機率可以忽略不計。
我們只需要確保有限群的大小明顯大於使用次數的平方。
我們通常在 Prime 欄位上執行此操作 $ Z_p $ 或過橢圓曲線。在前者中，我們使用數千位，而在後者中，典型大小為數百位。
即使是一個有秩序的謙虛團體 $ 2^{200} $ 即使經過數十億次嘗試，也不會提供碰撞。如果我們有 $ 2^{33} $ 嘗試，為地球上的每個男人女人和孩子進行一次嘗試，我們會考慮可能與有秩序的群體發生碰撞的平方 $ 2^{66} $ 如果我們去稍微大一點的機率仍然是可能的，但機率較低。當我們達到數百位時，這個機率變得可以忽略不計。
我們可以用以下公式近似碰撞機率： 1 - e -k 2 /2 n+1 當我們有 k 個元素和一組大小為 $ 2^n $ 顯然這會迅速收縮 $ n $
因此，對於您的問題，安全加密實現通過使用足夠大的組來防止意外衝突，即使在大量使用的情況下，衝突的機率也完全可以忽略不計。