作为非密码学家，我总是感到一件事：使用素数为何如此重要？ 是什么使它们在密码学上如此特别？

有人有简单的简短解释吗？ (我知道有很多入门书籍，而《应用密码学》是圣经，但是正如我所说：我并不是要实现自己的密码算法，而我发现的东西却使我的大脑爆炸了-没有10页的数学公式 请 ：))

感谢所有的答案。 我已经接受了使我最清楚实际概念的那个。

最基本和最笼统的解释：密码学完全是关于数论的，所有整数(0和1除外)都由质数组成，因此您在数论中处理质数很多。

更具体地说，一些重要的密码算法(例如RSA)严重依赖于以下事实：大量的素数分解需要很长时间。基本上，您有一个"公用密钥"，由两个用于加密邮件的大素数组成；另一个"秘密密钥"，由两个用于加密消息的素数组成。您可以将公钥公开，每个人都可以使用它来加密给您的消息，但是只有您知道主要因素并可以解密消息。鉴于当前数论的最新水平，其他所有人都必须考虑这个数，这花了太长时间才实用。

简单？对。

如果将两个大质数相乘，则只有两个(大)质数会得到一个巨大的非质数。

将此数字分解是一项不平凡的运算，而这一事实是许多密码算法的来源。有关更多信息，请参见单向功能。

附录： 只是更多的解释。两个质数的乘积可以用作公钥，而质数本身可以用作私钥。仅通过知道两个因素之一就可以对数据进行的任何操作对解密来说都是不平凡的。

这是一个非常简单且常见的示例。

RSA加密算法通常用于安全的商务网站，其基于以下事实：很容易取两个(很大)质数并将它们相乘，而反之则非常困难-意思是：取一个给定它只有两个主要因素，并找到它们。

重要的不是素数本身，而是与素数一起工作的算法。特别是，找到一个数(任意数)的因子。

如您所知，任何数字至少都有两个因素。质数具有独特的属性，因为它们恰好具有两个因素：1和自身。

原因分解是如此重要，是数学家和计算机科学家不简单尝试每种可能的组合就不知道如何分解数字。也就是说，首先尝试除以2，然后除以3，再除以4，依此类推。如果尝试分解质数(尤其是很大的质数)，则必须(基本上)尝试2和该较大质数之间的每个可能数。即使在最快的计算机上，也要花费数年(甚至几个世纪)来考虑密码学中使用的素数的种类。

事实是，我们不知道如何有效地分解大量数据，这使得密码算法无处不在。如果某一天有人弄清楚该怎么做，那么我们当前使用的所有加密算法都将过时。这仍然是一个开放的研究领域。

因为没有人知道将整数分解为素数的快速算法。但是，检查一组素数是否乘以某个整数非常容易。

有一些很好的资源可以增加加密货币。这是一个：

从该页面：

In the most commonly used public-key cryptography system, invented by Ron Rivest, Adi Shamir, and Len Adleman in 1977, both the public and the private keys are derived from a pair of large prime numbers according to a relatively simple mathematical formula. In theory, it might be possible to derive the private key from the public key by working the formula backwards. But only the product of the large prime numbers is public, and factoring numbers of that size into primes is so hard that even the most powerful supercomputers in the world cant break an ordinary public key.

布鲁斯·施耐尔(Bruce Schneier)的书《应用密码学》是另一本。我强烈推荐那本书；阅读很有趣。

为了更具体地说明RSA如何使用质数的属性，RSA算法主要取决于Euler定理，该定理指出，对于相对质数" a"和" N"，a ^ e等于1模N，其中e是N的欧拉上位函数。

素数从何而来？为了有效地计算N的欧拉函数，需要知道N的素因数分解。在RSA算法的情况下，对于某些质数" p"和" q"，N = pq，则e =(p-1)(q -1)= N-p-q +1。但是，如果不知道p和q，则很难计算e。

更抽象地讲，许多低温照相协议使用各种活板门功能，这些功能易于计算但难以反转。数论是此类活板门函数(例如大质数的乘法)的丰富来源，并且质数绝对是数论的核心。

我建议写《代码中的数学之旅》一书。这本书具有与众不同的感觉，这令人惊讶，因为它是关于密码学的。这本书总结了莎拉·弗兰纳里(Sarah Flannery)从童年时期学习难题到16岁时创建Cayley-Purser(CP)算法的历程，它给出了关于单向函数，数论和质数以及它们之间的关系的惊人详细解释。加密。

是什么让本书更加针对您的问题，是Sarah尝试使用矩阵算法实现新的公共密钥算法。这比使用质数要快得多，但是发现了可以利用它的漏洞。事实证明，她的算法最好用作私有加密机制。这本书很好地证明了使用质数进行加密，因为它经受了时间的考验和聪明人的挑战。

我不是数学家或神秘主义者，所以这是外行人的外在观察(没有花哨的方程式，很抱歉)。

整个线程充满了关于如何在密码学中使用素数的解释，很难在此线程中找到任何人以简单的方式解释为什么使用素数的解释...最有可能的原因是，每个人都认为这是理所当然的。

仅从外部看问题会产生类似的反应。但是，如果他们使用两个素数之和，为什么不创建任何两个素数可以生成的所有可能总和的列表？

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

计算大素数本身是一项艰巨的任务，因此反向计算已经被密码学家和数学家相互乘以的两个??素数就足够了……今天。

为您提供另一种资源。立即安全！第30集(约30分钟的播客，链接至笔录)讨论了密码学问题，并解释了素数为何重要的原因。

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

假设您有一个非常大的整数，已知该整数是两个素数m和n的乘积，要找出m和n是不容易的。 RSA之类的算法取决于这一事实。

顺便说一句，有一篇有关算法的已发表论文，可以使用量子计算机在可接受的时间内"解决"这一素因分解问题。因此，当量子计算机出现时，新的密码学算法可能不再依赖于素数分解的这种"困难" ：)

密码算法通常出于其安全性而依赖于"困难的问题"。大多数现代算法似乎都将大数分解作为他们的难题-如果将两个大数相乘，则计算它们的因数是"困难的"(即费时)。如果这两个数字是质数，那么只有一个答案，这将使难度更大，并且还可以保证，当您找到答案时，它是正确的，而不是其他碰巧得出相同结果的答案。

因为分解算法对找到的每个因子都大大加快了速度。将两个私钥设为素数可确保找到的第一个因素也将是最后一个。理想地，两个私钥的值也将几乎相等，因为仅弱密钥的强度很重要。

质数主要用于密码术，因为它在确定给定数是否为质数时会花费大量时间。对于黑客来说，如果有任何算法花费大量时间来破坏代码，对他们来说就变得毫无用处