为什么素数在密码学中很重要？
有一件事总是把我作为一个非密码学者：为什么使用素数这么重要？ 是什么让他们在密码学中如此特别？
有没有人有简单的简短的解释？ （我知道有很多引子，应用密码学就是圣经，但是正如我所说的：我并不是想要实现我自己的密码algorithm，而我发现的东西只是让我的大脑爆炸 – 没有10页的math公式请 ：））
感谢所有的答案。 我已经接受了使我的实际概念最清楚的那个。
最基本的和一般的解释：密码学是关于数论的 ，所有的整数（除了0和1）都是由素数组成的，所以你在数论中处理的素数很多。
更具体地说，诸如RSA的一些重要的密码algorithm关键取决于大数的素因子分解需要很长时间的事实。 基本上你有一个由用于encryption消息的两个大质数的乘积组成的“公钥”和由用于解密该消息的两个素数组成的“秘密密钥”。 您可以公开公钥，每个人都可以使用它来encryption邮件给您，但只有您知道主要因素，才能解密邮件。 考虑到数论的现有技术水平，其他人都必须考虑这个数字，这个数字需要很长时间才能实用。
简单？ 对。
如果你乘两个大的素数，你会得到一个巨大的非素数，只有两个（大）素因子。
分解这个数字是一个不平凡的操作，而这个事实是许多encryptionalgorithm的来源。 请参阅单向函数以获取更多信息。
附录：多一点解释。 两个素数的乘积可以用作公钥，而素数本身可以用作私钥。 对数据进行的任何操作，只有通过了解这两个因素之一才能取消，对于不encryption的数据将是不重要的。
这是一个非常简单和常见的例子。
在安全商业网站中常用的RSAencryptionalgorithm是基于这样一个事实，即容易得到两个（非常大的）素数并将它们相乘，而相反的做法则非常困难 – 这意味着：非常大的数字，因为它只有两个主要因素，并find它们。
因为没有人知道一个快速的algorithm来把一个整数分解成它的主要因素。 然而，检查一组素数因子乘以某个整数是非常容易的。
有一些很好的资源encryptionencryption。 这里有一个：
从该页面：
在1977年由Ron Rivest，Adi Shamir和Len Adleman发明的最常用的公钥密码系统中，公钥和私钥都是根据一个相对简单的math公式从一对大素数派生而来的。 从理论上讲，通过向后推导公式可以从公钥中推导出私钥。 但是只有大素数的产品是公开的，而且把这个大小的数字分解成素数是非常困难的，即使是世界上最强大的超级计算机也不能破坏普通的公钥。
布鲁斯·施奈尔（Bruce Schneier）的着作“ 应用密码学 ”（ Applied Cryptography）是另一本书 我强烈推荐这本书; 阅读很有趣
素数本身不是重要的，而是与素数一起使用的algorithm。 特别是find一个数字（任何数字）的因素。
如你所知，任何数字至less有两个因素。 素数有其独特的性质，因为他们有两个因素：1和他们自己。
math家和计算机科学家如果没有简单地尝试每一种可能的组合，都不知道如何分解数字，因此分解的原因非常重要。 也就是说，首先尝试除以2，然后除以3，然后除以4，等等。 如果你想要素数 – 尤其是非常大的 – 你必须尝试（基本上）所有可能的数字在2和那个大素数之间。 即使在最快的计算机上，也需要几年（甚至几百年）的时间来考虑密码学中使用的素数。
事实上，我们不知道如何有效地分解大量的密码algorithm。 如果有一天有人想知道如何去做，我们目前使用的所有encryptionalgorithm将会变得过时。 这仍然是一个开放的研究领域。
关于RSA如何使用素数的属性，RSAalgorithm关键取决于欧拉定理 ，该定理指出，对于相对素数“a”和“N”，a e与N的模一致，其中e是N 的欧拉函数 。
素数到底在哪里？ 为了有效地计算欧拉的N的总体函数，需要知道N的素数分解。在RSAalgorithm的情况下，对于一些素数“p”和“q”，其中N = pq，则e =（p-1） – 1）= N – p – q + 1但是不知道p和q，e的计算是非常困难的。
更为抽象的是，许多低温graphics协议使用各种陷门函数 ，这些函数易于计算但难以反转。 数论是这种陷门函数的一个丰富来源（如大素数的乘法），素数绝对是数论的核心。
再给你一个资源 安全现在！ 第30集 （约30分钟的播客，链接到成绩单）谈论密码学问题，并解释了为什么素数是重要的。
我会build议书“math之旅在代码” 。 这本书有一个很好的脚踏实地的感觉，这是令人惊讶的，因为它是关于密码学。 这本书总结了Sarah Flannery从小时候学习拼图到16岁时创buildCayley-Purser（CP）algorithm的过程。它给出了单向函数，数论和素数的一个非常详细的解释，以及它们与encryption。
是什么让这本书更具体到你的问题是萨拉试图实施一个新的公钥algorithm使用matrix。 使用素数的速度要快得多，但发现了一个可以利用它的循环漏洞。 原来她的algorithm更适合用作私人encryption机制。 这本书是使用素数进行encryption的一个很好的certificate，因为它经受了时间的考验和非常聪明的个人的挑战。
我不是一个math家或密码学家，所以这里是外行观察（没有花哨的方程式，对不起）。
这整个线程充满了有关密码学中使用素数的解释，很难在此线程中find任何人以简单的方式解释为什么使用素数…很可能是因为每个人都把这些知识视为理所当然。
只从外面看问题就会产生反应， 但如果他们使用两个素数的总和，为什么不创build任何两个素数可能产生的所有可能的总和列表？
在这个网站上有一个455,042,511的素数列表，其中最高的素数是9,987,500,000 （ 10位数字）。
已知最大的素数（截至2015年2月）是2的257,885,161 – 1 ，即17425,170位的数字。
这意味着保留所有已知素数的列表并不重要，更不用说所有可能的数目。 采取一个数字并检查它是否是一个主要数据更容易。
计算大质数本身就是一个不容忽视的任务，所以反向计算两个密码学家和math家之间相互倍增的素数，现在已经够难了 。
密码algorithm通常依靠他们的安全来解决“难题”。 大多数现代algorithm似乎使用大数的因子作为他们的难题 – 如果将两个大数相乘，计算他们的因子是“困难的”（即耗时）。 如果这两个数字是素数，那么只有一个答案，这使得它更加困难，而且还保证，当你find答案时，这是正确的答案，而不是其他答案，只是恰好给出了相同的结果。
我认为在密码学中重要的不是素数本身，而是素数分解问题的难点
假设你有非常大的整数，这个整数已知是两个素数m和n的乘积，要findm和n是不容易的。 像RSA这样的algorithm取决于这个事实。
顺便说一下，有一篇关于algorithm的发表论文 ，可以用量子计算机在可接受的时间内“解决”这个素数分解问题。 因此，当量子计算机进入城市时，密码学中更新的algorithm可能不再依赖于素数分解的这个“难度”:)
由于因子分解algorithm在find每个因子时都会显着加速。 使两个私钥都是主要的，确保find的第一个因素也是最后一个。 理想情况下，两个私钥的价值也几乎相等，因为只有弱密钥的强度才是重要的。
素数主要用于密码学，因为在确定一个给定的数字是否为素数时会耗费大量的时间。 对于黑客来说，如果有任何algorithm需要花费大量的时间来破解代码，那么对他们来说就没有用处了
