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

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


当前回答

最基本和一般的解释:密码学都是关于数论的,所有的整数(除了0和1)都是由质数组成的,所以你在数论中要处理很多质数。

More specifically, some important cryptographic algorithms such as RSA critically depend on the fact that prime factorization of large numbers takes a long time. Basically you have a "public key" consisting of a product of two large primes used to encrypt a message, and a "secret key" consisting of those two primes used to decrypt the message. You can make the public key public, and everyone can use it to encrypt messages to you, but only you know the prime factors and can decrypt the messages. Everyone else would have to factor the number, which takes too long to be practical, given the current state of the art of number theory.

其他回答

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

我不是数学家或密码学家,所以这里有一个外行的观察(没有花哨的方程,抱歉)。

这整个线程充满了关于如何在密码学中使用质数的解释,很难在这个线程中找到任何人以简单的方式解释为什么使用质数…很可能是因为每个人都认为这些知识是理所当然的。

只有从外部看问题才能产生这样的反应;但是如果他们使用两个质数的和,为什么不创建一个列表,列出任何两个质数可以产生的所有可能的和呢?

在这个网站上有一个455,042,511个质数的列表,其中最高的质数是9,987,500,000(10位数字)。 已知的最大素数(截至2015年2月)是2的257,885,161 - 1次方,即17,425,170位数字。这意味着保留所有已知质数的列表是没有意义的,更不用说所有它们可能的和了。取一个数并检查它是否是质数更容易。

计算大质数本身就是一项艰巨的任务,所以密码学家和数学家都会说,反向计算两个相互相乘的质数已经足够困难了……今天。

因为没有人知道一个快速的算法把一个整数分解成质因数。然而,检查一组质因数是否乘以某个整数是非常容易的。

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

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

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