为什么质数在密码学中很重要?

这里有一个非常简单和常见的例子。

RSA加密算法通常用于安全的商业网站，它是基于这样一个事实:取两个(非常大的)素数并将它们相乘很容易，而做相反的事情则非常困难——这意味着:取一个非常大的数，给定它只有两个素数因子，并找到它们。

简单的?是的。

如果你把两个大素数相乘，你会得到一个只有两个(大)素数因数的巨大非素数。

分解这个数字是一个非平凡的操作，这一事实是许多密码学算法的来源。更多信息请参见单向函数。

有一些很好的资源可以加强加密。这里有一个:

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

从那一页开始:

最常用的公钥 密码系统，由罗恩发明 里维斯特，阿迪·沙米尔，还有莱恩·阿德曼 1977年，不管是公立的还是私立的 键是由一对大键派生出来的 a的质数 相对简单的数学 公式。从理论上讲，可能是这样 可以派生私钥 方法从公钥中删除 公式向后。但只有 大素数的乘积是 公共的，因式分解 计算质数很难，甚至 最强大的超级计算机 这个世界不能打破一个平凡 公钥。< / p >

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

密码算法的安全性通常依赖于“难题”。大多数现代算法似乎都将非常大的数字的因式分解作为难题——如果你将两个大数相乘，计算它们的因式是“困难的”(即耗时)。如果这两个数是质数，那么答案就只有一个，这就更加困难了，同时也保证了当你找到答案时，它是正确的，而不是碰巧给出相同结果的其他答案。

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

更具体地说，一些重要的加密算法(如RSA)严重依赖于这样一个事实:大数字的质因数分解需要很长时间。基本上，您有一个“公钥”，由用于加密消息的两个大素数的乘积组成，以及一个由这两个素数组成的“秘钥”，用于解密消息。您可以将公钥公开，每个人都可以使用它来加密给您的消息，但只有您知道主要因素并可以解密消息。其他所有人都必须分解这个数字，考虑到目前数论的艺术水平，这需要很长时间才能实现。

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

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

假设你有一个非常非常大的整数，已知是两个质数m和n的乘积，要找出m和n是什么并不容易。RSA等算法就是基于这个事实。

顺便说一下，有一个发表论文算法可以在可接受的时间内使用量子计算机“解决”这个质因数分解问题。因此，当量子计算机问世时，新的密码学算法可能不再依赖质因数分解的“困难”:)

质数本身并不重要，重要的是处理质数的算法。特别是求一个数(任何一个数)的因式。

如你所知，任何数字至少有两个因数。质数有一个独特的性质，它只有两个因数:1和质数本身。

因式分解如此重要的原因是数学家和计算机科学家不知道如何在不尝试所有可能的组合的情况下进行因式分解。也就是说，首先试着除以2，然后除以3，然后除以4，以此类推。如果你试图分解一个质数——尤其是一个非常大的质数——你将不得不(基本上)尝试2和这个大质数之间的每一个可能的数。即使在最快的计算机上，也需要数年(甚至几百年)才能分解密码学中使用的各种质数。

事实上，我们不知道如何有效地分解一个大数字，这赋予了密码算法的优势。如果有一天，有人想出了如何做到这一点，我们目前使用的所有加密算法都将过时。这仍然是一个开放的研究领域。

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

为了更具体地说明RSA如何使用质数的属性，RSA算法主要依赖于欧拉定理，它表明对于相对质数“a”和“N”，a^e等于1 模 N，其中e是N的欧拉totient函数。

质数是怎么进来的?为了有效地计算N的欧拉totient函数，需要知道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试图使用矩阵实现一个新的公钥算法。它比使用质数要快得多，但发现了一个可以利用它的循环漏洞。事实证明她的算法更适合作为私人加密机制。这本书是使用质数进行加密的一个很好的证明，因为它经受住了时间的考验和非常聪明的人的挑战。

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

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

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

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

计算大质数本身就是一项巨大的任务，所以反向计算两个相互相乘的质数密码学家和数学家都会说足够努力…今天。

因为每找到一个因子，分解算法的速度就会大大加快。将两个私钥设置为素数可以确保找到的第一个因子也是最后一个因子。理想情况下，两个私钥的值也几乎相等，因为只有较弱的密钥的强度才重要。