为什么素数在密码学中很重要？

Question

作为一个非密码学家，有一件事总是让我印象深刻：为什么使用素数如此重要？是什么让它们在密码学领域如此特别？

有谁有 简单的 简短的解释？（我知道有很多入门读物，应用密码学就是圣经，但正如所说：我不想实现我自己的加密算法，我发现的东西让我的大脑爆炸 - 请不要写 10 页数学公式:))

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

Answer 1

最基本和一般的解释：密码学就​​是关于 数论, ，并且所有整数（除了 0 和 1）都是由素数组成的，因此在数论中会经常处理素数。

更具体地说，一些重要的密码算法，例如 RSA 关键取决于以下事实： 质因数分解 大量的数据需要很长时间。基本上，您有一个由用于加密消息的两个大素数的乘积组成的“公钥”，以及一个由用于解密消息的这两个素数组成的“秘密密钥”。您可以公开公钥，每个人都可以使用它来加密发送给您的消息，但只有您知道主要因素并可以解密消息。其他人都必须对这个数字进行因式分解，考虑到目前数论的技术水平，这需要很长时间才能实现。

Answer 2

简单？烨。

如果您乘两个大素数，你只有两个（大）一个巨大的非质数的质因子。

保理该号码是一个非平凡操作，并且该事实是很多的加密算法的来源。请参阅单向函数了解更多的信息。

附录： 只是有点更多的解释。两个素数的乘积可以作为公共密钥，而素数自己作为一个私钥。做数据的任何操作只能由知道这两个因素中的一个将是不平凡的，以解密方法复原。

Answer 3

下面是一个非常简单的和常见的例子。

在 RSA加密算法其通常在安全商务网站所使用的，是基于这样的事实，很容易采取两种（超大型）的素数和繁殖他们，而这是非常难做到的对面 - 意思是：它只有两个主要因素，采取了非常大的数字，给出的，并找到它们。

Answer 4

这是不是这么多的素数本身是重要的，但与素数的算法工作原理。特别是，发现了一些（任何数量）的因素。

大家知道，任何数量的具有至少两个因素。素数具有独特的属性，它们究竟有两个因素：1和自身

在保理业务的原因是如此重要的是数学家和计算机科学家不知道如何因素一批不只是想每一个可能的组合。即，首先尝试除以2，然后，通过如图3所示，然后，通过图4，等等。如果试图因素素数 - 尤其是一个非常大的一个 - you'll必须尝试（基本）每一个可能的2号和大素数之间。即使在最快的计算机，这将需要几年（甚至上百年）因式分解种加密使用的素数。

这是事实，我们不知道如何有效因素的大量，让加密算法自己的实力。如果有一天，有人计算出如何做到这一点，所有我们目前使用的加密算法将变得过时。这仍然是研究的开放区域。

Answer 5

由于没人知道的快速算法因式分解的整数到其首要因素。然而，这是很容易检查一组素因子乘以某一整数。

Answer 6

有一些很好的资源可以帮助您加强加密货币的发展。这是一个：

• http://research.microsoft.com/en-us/groups/crypto/firstcrypto.aspx

从该页面：

在1977年由Ron Rivest，Adi Shamir和Len Adleman发明的最常用的公钥加密系统中，根据相对简单的数学公式，公共钥匙和私钥都源自一对较大的素数。从理论上讲，有可能通过向后处理公式来从公共密钥中得出私钥。但是，只有大质数的产物才是公开的，并且将这些规模的数字分解成素数非常困难，以至于即使是世界上最强大的超级计算机也无法违反普通的公共密钥。

布鲁斯·施奈尔的书 应用密码学 是另一个。我强烈推荐那本书；读书很有趣。

Answer 7

为了更具体地了解 RSA 如何使用素数的属性，RSA 算法关键取决于 欧拉定理, ，其中指出对于相对素数“a”和“N”，a^e 与 1 全等 模数 N，其中 e 是 欧拉 totient 函数 的 N。

素数是从哪里来的呢？要有效计算 N 的欧拉 totient 函数，需要知道 N 的素因数分解。对于 RSA 算法，其中对于某些素数“p”和“q”，N = pq，则 e = (p - 1)(q - 1) = N - p - q + 1。但如果不知道 p 和 q，e 的计算就非常困难。

更抽象地说，许多加密协议使用各种 陷门函数, ，易于计算但难以求逆的函数。数论是此类陷门函数（例如大素数的乘法）的丰富来源，而素数绝对是数论的核心。

Answer 8

我建议书数学之旅代码。这本书有一个很好的脚踏实地的感觉，这是令人惊讶的，因为它是关于加密。该书总结了学习的困惑萨拉·弗兰纳里的旅程作为一个孩子，以创造在16岁的凯利 - 乘务长（CP）算法，它给出了一个单向函数，数论，并质数一个令人惊讶的详细说明，以及它们如何与加密。

是什么让这本书更具体到你的问题是萨拉试图用矩阵的实施新的公共密钥算法。这是更快然后用素数，但环孔被发现，可以利用它。原来她的算法是作为一个私有的加密机制，更好地利用。这本书是一个很好的证明了使用加密素数，因为它经受住了时间的考验，非常聪明的人所面临的挑战。

Answer 9

为你一个资源。 安全！第30集（〜30分钟播客，链接谈话）有关加密问题进行谈判，并解释了为什么素数是很重要的。

Answer 10

我不是数学家或cryptician，所以这里的通俗地说外部观察（没有华丽的方程，对不起）。

这整个主题是充满着对解释如何素数在密码学中，很难找到在这个线程在一个简单的方法解释为什么素数的人使用。 ..最有可能的，因为每个人都需要的知识是理所当然的。

只看着来自外部的问题可以生成反应等;但如果他们使用两个素数的总和，为什么不创造一切可能的和的列表中的任何两个素数可生成？

在此网站还有的 455042511 素数，其中一个列表最高的素数是的 9987500000 （适用的 10 位）。搜索结果 已知的最大素数（如2015年2月的）是的 2的功率257885161 - 1 其中是的 17425170 数字搜索结果，这意味着没有点。保留所有已知的素数的列表，更不用说他们的所有可能的和。它更容易采取一些并检查它是否是一个素数。

在本身计算大素数是一项艰巨的任务，这样的反向计算已乘以均彼此密码学家和数学家会说两个素数是够硬 ..今天。

Answer 11

加密算法一般依赖它们对具有“难题”的安全性。大多数现代算法似乎用非常大量的保理作为他们的难题 - 如果你乘两个大数字加在一起，计算他们的因素是“难”（即费时）。如果这两个数字是素数，那么就只有一个答案，这使得它更加困难，而且还保证，当你找到答案，这是正确的，不就是正好产生相同的结果一些其他的答案。

Answer 12

我觉得是很重要的密码不素数本身，而是它是在困难 质因子分解问题的

假如你有一个被称为是两个素数m和n产品非常非常大的整数，这是不容易找到什么是m和n。算法如RSA取决于这个事实。

顺便说，有一个上算法发表的论文其可以“解决“在可接受的时间这个因式分解问题用量子计算机。所以在加密算法更新可以不靠这个因式分解的“困难”了，当量子计算机来镇：）

Answer 13

由于分解算法与找到的每个因子大大加快。使得无论私钥首要确保发现也将是最后的第一因素。理想情况下，这两种私钥也将是因为只有较弱的键事项的强度值几乎相等。

Answer 14

素数主要用于加密，因为它会消耗相当多的时间在确定一个给定的数是否为素数或没有。对于黑客如果任何算法花费的时间很多，打破它变得无用为它们的代码