作为一个非密码学家,有一件事总是让我震惊:为什么使用质数如此重要?是什么让它们在密码学中如此特别?

有人能简单解释一下吗?(我知道有很多入门知识,应用密码学是圣经,但如我所说:我不打算实现我自己的加密算法,我发现的东西只是让我的大脑爆炸-请不要十页的数学公式)。


当前回答

给你的另一个资源。现在安全了!第30集(约30分钟的播客,链接到文本)讨论了密码学问题,并解释了为什么质数很重要。

其他回答

给你的另一个资源。现在安全了!第30集(约30分钟的播客,链接到文本)讨论了密码学问题,并解释了为什么质数很重要。

素数主要用于密码学,因为确定一个给定的数是否是素数需要相当长的时间。对于黑客来说,如果任何算法都需要大量的时间来破解代码,那么它对他们来说就变得毫无用处

我认为在密码学中重要的不是质数本身,而是质因数分解问题的难点

假设你有一个非常非常大的整数,已知是两个质数m和n的乘积,要找出m和n是什么并不容易。RSA等算法就是基于这个事实。

顺便说一下,有一篇发表的算法论文可以在可接受的时间内使用量子计算机“解决”这个质因数分解问题。因此,当量子计算机问世时,新的密码学算法可能不再依赖质因数分解的“困难”:)

质数本身并不重要,重要的是处理质数的算法。特别是求一个数(任何一个数)的因式。

如你所知,任何数字至少有两个因数。质数有一个独特的性质,它只有两个因数:1和质数本身。

The reason factoring is so important is mathematicians and computer scientists don't know how to factor a number without simply trying every possible combination. That is, first try dividing by 2, then by 3, then by 4, and so forth. If you try to factor a prime number--especially a very large one--you'll have to try (essentially) every possible number between 2 and that large prime number. Even on the fastest computers, it will take years (even centuries) to factor the kinds of prime numbers used in cryptography.

事实上,我们不知道如何有效地分解一个大数字,这赋予了密码算法的优势。如果有一天,有人想出了如何做到这一点,我们目前使用的所有加密算法都将过时。这仍然是一个开放的研究领域。

Cryptographic algorithms generally rely for their security on having a "difficult problem". Most modern algorithms seem to use the factoring of very large numbers as their difficult problem - if you multiply two large numbers together, computing their factors is "difficult" (i.e. time-consuming). If those two numbers are prime numbers, then there is only one answer, which makes it even more difficult, and also guarantees that when you find the answer, it's the right one, not some other answer that just happens to give the same result.