Number-Theory
質數在密碼學中的位置是什麼？
我對散列和加密的理解相當有限。我當然不理解這些算法中的數學公式。話雖如此，質數在密碼學中扮演什麼角色？
當我在大學時，我的一位教授告訴我，沒有公式可以預測素數（除了嘗試它們），這使得許多加密方案（如 PGP）如此安全，因為不可能在任何合理的時間內猜測用於公鑰/私鑰的數字。那是對的嗎？
不，沒有已知的僅產生素數的實用公式這一事實並沒有真正發揮作用。如果有人明天發現了一個，那不會有任何加密含義。
您可能想了解非對稱加密是如何工作的？線; 簡短的回答是，對於公鑰操作，公鑰和私鑰必須相關，但不是以明顯的方式相關。這意味著使用的任何方案都有一些數學結構。數論是我們發現“相關但不是顯而易見”的數學結構的地方，而質數在數論中是相當錯誤的。
素數的具體使用方式取決於所使用的非對稱算法；在 RSA 中，我們利用了這樣一個事實，給定 $ M^e \mod N $ （和 $ e $ 和 $ N $ )，沒有已知的恢復方法 $ M $ 在不知道主因數的情況下 $ N $ （但有了這些資訊，這很容易）。在 DH/DSS 中，我們利用了以下事實： $ G^x \mod p $ （和 $ G $ 和 $ p $ )，沒有已知的恢復方法 $ x $ （我們有 $ p $ 是素數，因為如果有人找到分解，複合模的問題會變得容易得多）。在橢圓曲線密碼學中，我們利用了恢復的難度 $ k $ 給定 $ kG $ （在哪裡 $ G $ 是一個已知點）；涉及素數是因為橢圓曲線僅定義了一個域，並且唯一的有限域（即具有有限元素集的域）具有大小 $ p^N $ , 對於素數 $ p $ （和正整數 $ N $ ).
現在，您偶爾會看到對稱加密中使用的素數；它幾乎沒有那麼常見（而且這些素數也不是秘密）。