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

作为非密码学家,有一件事总是让我感到震惊:为什么使用Prime数字这么重要？是什么让他们在密码学方面如此特别？

有没有人有简单的简短解释？(我知道有许多引物,应用密码学是圣经,但正如所说的:我不打算实施我自己的加密算法,我发现的东西只是让我的大脑爆炸 - 没有10页的数学公式请 :))

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

1> Michael Borg..：

---

最基本和一般的解释:密码学是关于数论的,所有整数(0和1除外)都由素数组成,所以你在数论中处理了很多素数.

更具体地说,一些重要的加密算法,如RSA,关键取决于大数的素数分解需要很长时间的事实.基本上你有一个"公钥",包括用于加密消息的两个大素数的乘积,以及一个由用于解密消息的两个素数组成的"密钥".您可以公开公钥,每个人都可以使用它来加密给您的邮件,但只有您知道主要因素并且可以解密邮件.考虑到数论的当前现状,其他人都必须考虑数字,这需要太长时间才能实用.

---

@stujo:你大量过高估计了量子计算的状态.事实上,确实没有这样的计算机存在.使用Shor算法和量子硬件前沿研究工作所考虑的最大数字是21.这不​​是21位,而是数字21,素因子3和7.

---

当我们进入量子计算的时代时,似乎应该注意到使用量子计算机的素数因子分解可以在多项式时间内实现.使用Shor的算法https://en.wikipedia.org/wiki/Shor%27s_algorithm很可能是计算机已经存在,可以像RSA一样解密公钥加密

---

@juanmf:你对量子计算的理解是完全错误的.它与3个值完全无关,这完全没有意义.细节非常复杂,但效果是一些量子算法可以解决比非量子硬件上的"普通"算法更低的Big-O复杂性问题.

2> user54650..：

---

简单？对.

如果将两个大素数相乘,则得到一个巨大的非素数,只有两个(大)素因子.

将该数字分解是一项非常重要的操作,而这一事实是许多加密算法的来源.有关详细信息,请参阅单向函数.

附录:再解释一下.两个素数的乘积可以用作公钥,而素数本身可以用作私钥.对数据进行的任何操作只能通过了解这两个因素中的一个来撤消,这对于未加密是非常重要的.

---

将此解释与术语"单向函数"联系起来会很有帮助:http://en.wikipedia.org/wiki/One-way_function

---

另外值得注意的是,除了因子分解问题之外,许多现代加密也(或相反)依赖于离散对数问题.两者都是"单向"功能:很容易获取已知输入并计算答案,但很难回答并计算这些输入.

3> Yuval Adam..：

---

这是一个非常简单和常见的例子.

通常用于安全商务网站的RSA加密算法基于以下事实:很容易获取两个(非常大的)素数并将它们相乘,而相反则很难做到 - 这意味着:非常大的数字,只有两个主要因素,并找到它们.

---

仅供参考,你从两个素数乘以得到的数字称为半素数.

4> Barry Brown..：

---

重要的不是素数本身,而是与素数一起使用的算法.特别是,找到一个数字(任意数字)的因子.

如您所知,任何数字至少有两个因素.素数具有独特的性质,因为它们有两个因素:1和它们自己.

因子分解如此重要的原因是数学家和计算机科学家不知道如何在不简单地尝试每种可能的组合的情况下对数字进行分解.也就是说,首先尝试除以2,然后除以3,然后除以4,依此类推.如果你试图计算素数 - 特别是一个非常大的素数 - 你必须(基本上)尝试2和那个大素数之间的每个可能数.即使在速度最快的计算机上,也需要数年(甚至数百年)来计算密码学中使用的素数种类.

事实上,我们不知道如何有效地分解大量数字,从而为加密算法提供了强大的功能.如果有一天,有人想出如何做到这一点,我们目前使用的所有加密算法都将过时.这仍然是一个开放的研究领域.

---

实际上,您只需要测试素数到您想要考虑的数字的平方根.

---

@KartikChughヅ说`n`不是素数&'n = a*b`.如果`a> sqrt(n)`,`b`必须更小,反之亦然,否则'a*b> n`本身会否定我们的初始主张.所以要检查素数,我们只检查直到sqrt.

---

我知道.这是一个我以"简单"的名义"忽略"的细节.

5> nes1983..：

---

因为没有人知道将整数分解为其素因子的快速算法.然而,很容易检查一组素因子是否乘以某个整数.

---

没有人知道"在公共场合".世界各国政府的情报机构可能有他们不共享的技术.他们雇用了大量的数学毕业生.例如,美国国家安全局通过"双EC_DRBG"秘密推广随机素数,他们知道这是一个弱点,作为公共使用的标准加密方案的一部分.http://bits.blogs.nytimes.com/2013/09/10/government-announces-steps-to-restore-confidence-on-encryption-standards

6> Brian Clappe..：

---

有一些很好的资源可以加速加密.这是一个:

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

从该页面:

在由Ron Rivest,Adi Shamir和Len Adleman于1977年发明的最常用的公钥加密系统中,根据相对简单的数学公式,公钥和私钥都来自一对大质数.理论上,可以通过向后处理公式从公钥派生私钥.但只有大质数的产品才是公开的,将这个大小的数字分解成素数是如此之难,以至于即使是世界上最强大的超级计算机也无法打破普通的公钥.

Bruce Schneier的着作" 应用密码学"是另一本书.我强烈推荐这本书; 这很有趣.

7> 小智..：

---

为了更加具体地说明RSA如何使用素数的性质,RSA算法关键取决于欧拉定理,该定理指出对于相对素数"a"和"N",a e与1 模 N一致,其中e是欧拉的 N 的总函数.

素数在哪里？要有效地计算N的Euler函数,需要知道N的素因子分解.在RSA算法的情况下,对于某些素数"p"和"q",N = pq,则e =(p-1)(q - 1)= N - p - q + 1.但是在不知道p和q的情况下,e的计算非常困难.

更抽象地说,许多crypotgraphic协议使用各种陷门功能,这些功能易于计算但难以反转.数论是这种陷门函数的丰富来源(例如大素数的乘法),素数对于数论绝对是核心.

8> Jason Rowe..：

---

我会建议书中的数学之旅.这本书具有良好的脚踏实地的感觉,这是令人惊讶的,因为它是关于密码学的.这本书总结了Sarah Flannery从小时候学习谜题到在16岁时创建Cayley-Purser(CP)算法的过程.它给出了单向函数,数论和素数以及它们如何与之相关的惊人详细解释.加密.

是什么让本书更具体地针对您的问题,Sarah尝试使用矩阵实现新的公钥算法.它比使用素数快得多,但发现了一个可以利用它的循环孔.事实证明,她的算法最好用作私有加密机制.这本书是使用素数加密的一个很好的证明,因为它经受了时间的考验和非常聪明的个人的挑战.

9> Bill the Liz..：

---

还有一种资源供您使用. 现在安全!第30集(约30分钟播客,链接到成绩单)谈论加密问题,并解释为什么素数很重要.

10> 小智..：

---

我不是数学家或密码学家,所以这里是外行人的外部观察(没有花哨的方程式,对不起).

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

只从外面看问题就可以产生反应; 但如果他们使用两个素数的和,为什么不创建任何两个素数可以生成的所有可能总和的列表？

在这个网站上有一个455,042,511个素数列表,其中最高的素数是9,987,500,000(10位数).

已知最大的素数(截至2015年2月)为2,功率为257,885,161 - 1,即17,425,170位数.

这意味着没有必要保留所有已知素数的列表,更不用说所有可能的总和.拿一个数字并检查它是否是一个素数是更容易的.

计算大素数本身是一项艰巨的任务,因此反向计算密码学家和数学家之间相互成倍增加的两个素数就足够了 ......今天.

---

只有你的最后一段确实有效.对于任何复合数,也可以说和的参数(存在大范围[技术上无限大],所有和的存储是不可行的/愚蠢的).此外,素数的总和在密码学中并不具有那么多相关性,更重要的是(通常,如RSA的情况)是他们的产品.另外,通过**反向计算**你可能意味着**因子**.这可能对你的意思有所帮助.