写于 2018-12-06 03:09:02| 云顶娱乐在线官网| 云顶娱乐在线官网

几天前在The Conversation上,我为自己设定了一个任务:捍卫所谓的“无用”数学的有用性今天,这种防御仍在继续,看看我上次完成的RSA算法,指出三位数学家--Ron Rivest,Adi Shamir和Leonard Adleman--于1977年创建了RSA算法,一举建立了现代世界中数论的实际应用所以,为了更仔细地看待这个想法,让我们绕道而行

爱丽丝和鲍勃的生活,两个虚构的人物彼此迷恋,尽管从来没有见过假设爱丽丝想给鲍勃发一张私信,概述她的情感她可以把它放在一个盒子里,在它上面挂上挂锁然后把它运走

问题显然是,如果没有Alice可以发送此密钥的密钥,这对Bob来说是无用的,但如果两者都被截获(可能是Bob的嫉妒的前妻,Eve)会有麻烦 - 事实上这可能发生意味着我thod并不是真正安全这个问题的一个解决方案与RSA算法并行运行Bob知道人们(特别是Alice)想要向他发送秘密消息,所以他出去买了一堆相同的挂锁,所有这些挂锁都打开了只用一把钥匙,他一直隐藏在他的左鞋中Bob解锁所有这些挂锁并让它们在Bunnings可用如果Alice想给Bob发送一条秘密信息,她只需要去Bunnings并获得其中一个挂锁,然后在她想要发送的盒子上使用它这将是一个安全的传输,看到Bob是唯一一个拥有密钥但是一个复杂的信息保护方式:人们接收秘密消息,他们需要公开挂锁可供所有人使用!这些天,当然,更多的人选择电子邮件而不是蜗牛邮件

那么我们怎么知道夏娃不会监视Alice和Bob的在线通讯

现在我们进入RSA算法,这是在线加密和解密信息的最有效方法

算法的设计和强度是数论中历史性结果的工作,其安全性由以下事实保证:它对于计算机来说很容易将两个大的素数相乘(谷歌将这样做而不会出汗)但是,假设你将两个大的素数相乘得到一个结果数:如果你把这个新数字给计算机并要求它告诉你什么素数数字乘以构造它,计算机会挣扎这个被称为陷门,意味着它很容易走向一个方向,但很难走向另一个两个素数我乘以得到194477

计算机可以很容易地解锁这个数字,但是如果我使用的素数要大得多,那么上述问题的数学难度就是确保加密(或锁定)的强度RSA算法的工作原理如下:首先,我发现两个巨大的(每个至少100个数字!)素数p和q,然后我将它们相乘以获得更大的数字NI也以不同的方式组合p和q以生成另一个数字e(下面的详细信息)I将这两个数字(N,e)公布为我的“公钥”,知道即使世界上最快的计算机将N分解为其构成素数原子p和q也存在巨大的困难

事实证明,数字N和e可以是人们使用加密信息发送给我,我可以使用我的秘密素数p和q解密为了说明这个美丽的数学,我们可以回到我们虚构的爱好者鲍勃希望加密并发送爱丽丝他的年龄 - 42当然,RSA算法处理s发送号码,但看到任何文本可以通过各种方式转换为数字,我们可以安全地传输任何类型的信息另外,我将在这个例子中使用小素数,只是为了简化计算1)爱丽丝知道鲍勃想要给她发一条消息,所以她选择两个素数让我们说她选择p = 17和q = 29(虽然实际上它们会大得多以确保更好的安全性)然后爱丽丝将p和q相乘得到数字N:pxq = 17 x 29 = 493所以Alice现在有N = 493 2)Alice还需要生成另一个数字e她首先通过减去每个素数p和q的1来创建这个数字她:p - 1 = 16 q - 1 = 28 Alice然后将这两者相乘得到:(p-1)x(q-1)= 448这个数字不是e 数字e被允许为任何数字,这与这个新数字没有共同点448为了看我的意思,我们可以将448分成一堆素数乘以:44​​8 = 2 x 2 x 2 x 2 x 2 x 2 x 7然后e是任何数字,当分解为素数时,不具有2或7作为因子所以有很多可能性让我们假设爱丽丝选择e = 5 3)Alice然后给出数字N = 493和e = 5如果鲍勃她甚至可以把它们放在当地的广告牌上

重要的是,N号应该很难让任何人分解成p和q我们只会假设数字493恐慌人们因此没有人试图分解它4)有了这两个数字N和e,鲍勃现在可以加密他的秘密信息,在这种情况下是他的年龄 - 42他开始把42赋予e的权力,他知道这只是意味着他将自己的年龄乘以五次:42 x 42 x 42 x 42 x 42 = 130,691,232 5)Bob现在已经半信半疑此时,他只需要使用N来完成加密过程他取上面的数字130,691,232并将其除以数字N = 493他对执行此除法时的余数感兴趣,即383所以Bob加密了42作为383,这是他发给爱丽丝的号码6)现在,凌乱的比特爱丽丝从鲍勃那里收到了383号码,她需要解密它以获得他的年龄她的第一步,是使用她的秘密素数p和q和公共号码e形成另一个号码d,她可以用来解密Bob的消息Alice再次考虑号码448,她在步骤3中通过乘以(p-1)乘以(q-1)Alice需要找到e = 5的倍数,这正好是448的倍数

数论理论认为这总是可行的,我们将展示一种繁琐但直截了当的做法,Alice列出了5:5,10,15的倍数, 20,25,30,35,40 ......和448:448,896,1344,1792,2240,2688的倍数......她需要在第一个序列中找到一个数字,这个数字正好是第二个序列中的一个数字

如果Alice在第一个序列中走得足够远 - 到第269个术语,即1345个 - 她可以看到这正好是一个超过1344,第二个序列中的第三个成功!请注意,它是找到数字d = 269,e的相关倍数的位置,这是该步骤的全部点7)最后,Alice可以通过一个大的计算解码消息她有Bob的加密号码,383,和她的新数字,d = 269事实证明鲍勃的年龄可以通过计算383到269的幂来解码,然后在除以N = 493时找到余数

这看起来像是一个非常讨厌的计算,但是有些工具数字理论可以在这里使用一旦Alice完成这个计算,余数将是42,这是Bob的年龄RSA是最好的公钥密码学类型,但由于涉及高计算,它通常不用于加密/解密简单的消息相反,它用于签名和协议协商,允许双方接收私钥用于他们的通信RSA算法只是许多系统中的一个,其中一组数学定理,通常来自数论,可以合成建立加密方案有一些优雅的数学在幕后进行,确保算法的成功当然,实际上,大质数保证了安全加密,而计算是由计算机执行的

重要的是,算法与物理情况相似使公开的挂锁可供公众使用数学上讲,我们的数字N和e形成开放的挂锁,我们的秘密素数p和q组合形成一个密钥,我们可以用它来检索锁定的信息但是如果有人提出了一个精彩的公式为了将数字分解为其主要因素(将挂锁转换为键),世界各地确实存在安全问题素数的固有随机性是当前阻止现有数量公式的力量数理论家处于这一知识的最前沿,但距离提出这样一个工具还有一段时间世界应该放心,因为问题得到解决d,创造了更多,这一进步不仅促进了技术的进步,而且赋予了数学家无尽的动力 仅仅因为某些东西没有真实世界的应用程序但并不意味着它将来不会有这样的结论我总结了我对无用数学有用性的辩护它是否有效

你确信吗

我有兴趣听听你的观点阅读阿德里安的上一篇文章:你的数字上升 - 无用数学有用的案例