作为一个非密码学家，我总有一件让我印象深刻的事情：为什么使用素数如此重要？是什么让它们在密码学中如此特别？
有没有人有一个简单的简短解释？（我知道有很多入门书，应用密码学是圣经，但正如所说：我不打算实现自己的密码算法，而我发现的东西让我的大脑爆炸了——没有 10 页的数学公式请 ：））
感谢所有的答案。我接受了那个让我最清楚实际概念的那个。
Michael Stum
问问题
192515 次
14 回答
215
最基本和一般的解释：密码学都是关于数论的，所有整数（除了 0 和 1）都是由素数组成的，所以在数论中你会处理很多素数。
更具体地说，一些重要的加密算法（如RSA ）严重依赖于大数的素数分解需要很长时间这一事实。基本上，您有一个“公钥”，由用于加密消息的两个大素数的乘积组成，以及一个由用于解密消息的这两个素数组成的“秘密密钥”。您可以公开公钥，每个人都可以使用它来加密给您的消息，但只有您知道主要因素并可以解密消息。考虑到目前数论技术的现状，其他人都必须考虑这个数字，这需要很长时间才能实现。
于 2009-01-13T17:19:17.977 回答
138
简单的？是的。
如果你将两个大素数相乘，你会得到一个只有两个（大）素因子的巨大非素数。
分解该数字是一项不平凡的操作，而这一事实是许多密码算法的来源。有关详细信息，请参阅单向函数。
附录：只是多一点解释。两个素数的乘积可以用作公钥，而素数本身可以用作私钥。对数据所做的任何操作都只能通过知道这两个因素之一来撤消，这对于解密来说并非易事。
于 2009-01-13T17:15:21.727 回答
46
这是一个非常简单和常见的例子。
安全商务网站中常用的RSA 加密算法基于这样一个事实，即取两个（非常大的）素数并将它们相乘很容易，而反之则非常困难 - 意思是：取一个非常大的数，给定它只有两个质因数，然后找到它们。
于 2009-01-13T17:15:03.477 回答
16
重要的不是素数本身，而是使用素数的算法。特别是，找到一个数字（任何数字）的因数。
如您所知，任何数字至少有两个因素。素数具有独特的性质，因为它们恰好有两个因数：1 和它们自己。
因式分解如此重要的原因是数学家和计算机科学家不知道如何在不尝试所有可能组合的情况下对数字进行因式分解。也就是说，首先尝试除以 2，然后除以 3，再除以 4，以此类推。如果你试图分解一个素数——尤其是一个非常大的素数——你必须尝试（基本上）在 2 和那个大素数之间的每一个可能的数字。即使在最快的计算机上，也需要数年（甚至数百年）来分解密码学中使用的素数种类。
事实上，我们不知道如何有效地分解大量数字，这使得密码算法具有强大的实力。如果有一天，有人想出了如何做到这一点，那么我们目前使用的所有加密算法都将过时。这仍然是一个开放的研究领域。
于 2009-01-13T17:35:19.253 回答
13
因为没有人知道将整数分解为其素数的快速算法。然而，很容易检查一组素因数是否乘以某个整数。
于 2009-01-13T17:19:52.390 回答
12
有一些很好的资源可以增加加密货币。这是一个：
从该页面：
在 Ron Rivest、Adi Shamir 和 Len Adleman 于 1977 年发明的最常用的公钥密码系统中，公钥和私钥都是根据一个相对简单的数学公式从一对大素数中导出的。理论上，可以通过倒推公式从公钥中推导出私钥。但只有大素数的乘积是公开的，将这种大小的数分解为素数非常困难，即使是世界上最强大的超级计算机也无法破解普通的公钥。
Bruce Schneier 的《应用密码学》一书是另一本。我强烈推荐那本书；阅读很有趣。
于 2009-01-13T17:17:35.110 回答
9
为了更具体地了解 RSA 如何使用素数的属性，RSA 算法严重依赖于欧拉定理，该定理指出，对于相对素数“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 非常困难。
更抽象地说，许多加密协议使用各种陷门函数，这些函数易于计算但难以反转。数论是此类陷门函数（例如大素数的乘法）的丰富来源，而素数绝对是数论的核心。
于 2009-01-13T20:23:32.597 回答
7
我会推荐这本书A Mathematical Journey In Code。这本书有一种很好的脚踏实地的感觉，这令人惊讶，因为它是关于密码学的。这本书总结了 Sarah Flannery 从小时候学习拼图到 16 岁时创建 Cayley-Purser (CP) 算法的历程。它对单向函数、数论和素数以及它们与密码学。
使这本书对您的问题更加具体的原因是莎拉试图使用矩阵实现一种新的公钥算法。它比使用素数要快得多，但发现了一个可以利用它的漏洞。事实证明，她的算法更适合用作私有加密机制。这本书很好地证明了使用素数进行加密，因为它经受住了时间的考验和非常聪明的人的挑战。
于 2009-10-02T17:00:44.183 回答
6
为您提供更多资源。 立即安全！第 30 集（约 30 分钟的播客，链接是成绩单）讨论了密码学问题，并解释了为什么素数很重要。
于 2009-01-13T18:12:38.883 回答
6
我不是数学家或神秘主义者，所以这是外行人的外部观察（没有花哨的方程式，抱歉）。
整个线程充满了关于如何在密码学中使用素数的解释，很难在这个线程中找到任何人以简单的方式解释为什么使用素数......很可能是因为每个人都认为这些知识是理所当然的。
只有从外面看问题，才会产生这样的反应；但是如果他们使用两个素数的和，为什么不创建一个任何两个素数可以生成的所有可能和的列表呢？
在这个网站上有一个455,042,511 个素数的列表，其中最高的素数是9,987,500,000（10位数字）。
已知最大的素数（截至 2015 年 2 月）是2 的 257,885,161 - 1 次方，即17,425,170位。
这意味着保留所有已知素数的列表是没有意义的，更不用说它们所有可能的总和了。取一个数字并检查它是否是素数更容易。
计算大素数本身就是一项艰巨的任务，因此逆向计算已相乘的两个素数密码学家和数学家都会说已经够难了……今天。
于 2015-03-18T13:20:50.630 回答
4
密码算法的安全性通常依赖于“难题”。大多数现代算法似乎都使用非常大数的因式分解作为他们的难题 - 如果将两个大数相乘，计算它们的因式是“困难的”（即耗时）。如果这两个数字是素数，那么只有一个答案，这使得它变得更加困难，并且还保证当你找到答案时，它是正确的，而不是恰好给出相同结果的其他答案。
于 2009-01-13T17:19:00.800 回答
4
我认为密码学中重要的不是素数本身，而是素数分解问题的难度
假设你有一个非常大的整数，已知它是两个素数 m 和 n 的乘积，那么要找到 m 和 n 是不容易的。诸如 RSA 之类的算法取决于这个事实。
顺便说一句，有一篇关于算法的已发表论文可以使用量子计算机在可接受的时间内“解决”这个素数分解问题。因此，当量子计算机出现时，密码学中较新的算法可能不再依赖质数分解的这种“困难”了:)
于 2009-01-13T17:27:13.950 回答
3
因为分解算法在找到每个因子后都会大大加快速度。将两个私钥设为素数可确保找到的第一个因素也是最后一个因素。理想情况下，两个私钥的价值也几乎相等，因为只有较弱密钥的强度很重要。
于 2017-07-24T20:47:34.857 回答
-1
素数主要用于密码学，因为它会花费大量时间来确定给定数是否为素数。对于黑客来说，如果任何算法需要花费大量时间来破解代码，它对他们来说就变得毫无用处
于 2013-06-19T09:21:19.403 回答