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

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


当前回答

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

其他回答

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

如你所知,任何数字至少有两个因数。质数有一个独特的性质,它只有两个因数: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.

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

我建议你读《代码中的数学之旅》这本书。这本书有一种很好的接地气的感觉,这是令人惊讶的,因为它是关于密码学的。这本书总结了Sarah Flannery从一个孩子学习谜题到在16岁时创建Cayley-Purser (CP)算法的旅程。它对单向函数、数论、质数以及它们与密码学的关系给出了令人惊讶的详细解释。

让这本书更具体地回答你的问题的是Sarah试图使用矩阵实现一个新的公钥算法。它比使用质数要快得多,但发现了一个可以利用它的循环漏洞。事实证明她的算法更适合作为私人加密机制。这本书是使用质数进行加密的一个很好的证明,因为它经受住了时间的考验和非常聪明的人的挑战。

因为每找到一个因子,分解算法的速度就会大大加快。将两个私钥设置为素数可以确保找到的第一个因子也是最后一个因子。理想情况下,两个私钥的值也几乎相等,因为只有较弱的密钥的强度才重要。

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

这里有一个非常简单和常见的例子。

RSA加密算法通常用于安全的商业网站,它是基于这样一个事实:取两个(非常大的)素数并将它们相乘很容易,而做相反的事情则非常困难——这意味着:取一个非常大的数,给定它只有两个素数因子,并找到它们。