RSA加密
概述
RSA就是一个例子公开密匙加密假设Alice想要送给Bob一颗有价值的钻石,但是如果没有担保,钻石就会被偷。Alice和Bob都有各种各样的挂锁,但他们拥有的不是一样的,这意味着他们的钥匙不能打开对方的锁。
爱丽丝是怎么把钻石送给鲍勃的?
解决方案:
- 鲍勃首先发送给爱丽丝一把未上锁的挂锁。注意鲍勃会给
任何人一把没有锁的挂锁,因为它唯一的用处就是给鲍勃送点东西。 - Alice添加Bob的锁并将包发送给Bob,然后
- 鲍勃打开了锁,打开了包裹。
这个示例演示了公钥密码学背后的思想,尽管概念实际上略有不同。在公钥密码学中。Alice使用Bob的公钥加密她的消息,而该公钥只能由Bob的私钥解码。
在RSA中,公钥由两个大的数字相乘生成质数
而且
私钥是通过涉及的不同过程生成的
而且
.然后,用户可以分发他的公钥
,任何希望向用户发送消息的人都将使用公钥加密他们的消息。出于各种实际目的,即使是计算机也不能将大数分解成两个质数的乘积,就像手工分解414863这样的数几乎是不可能的一样。然而,
当用户收到加密的消息时,他们使用私钥对其解密,并可以读取原始文本。下一节将给出更详细的技术解释。
该算法
RSA的实现大量使用模运算,欧拉定理,欧拉totient函数.注意,算法的每一步只涉及乘法,所以计算机很容易执行:
- 首先,接受者选择两个大的质数 而且 .他们的产品, ,将是公钥的一半。
- 接收者计算 然后选择一个数字 互质来 .在实践中, 是经常选择的吗 ,尽管它可以小到 在某些情况下。 将是公钥的另一半。
- 接收器计算模块化的逆 的 模 .换句话说, . 是私钥.
- 接收方分发公钥的两个部分: 而且 . 是保密的。
现在已经生成了公钥和私钥,可以根据需要经常重用它们。要传递信息,请遵循以下步骤:
首先,发送者将他的消息转换成一个数字 .一种常见的转换过程使用ASCII字母:
一个 B C D E F G H 我 J K l 米 65 66 67 68 69 70 71 72 73 74 75 76 77 N O P 问 R 年代 T U V W X Y Z 78 79 80 81 82 83 84 85 86 87 88 89 90 例如,消息“HELLO”将被编码为7269767679。重要的是 ,否则取模时消息将丢失 ,那么如果 是比信息小的,它会被发送成碎片。
- 发送方然后计算 . 是密文,或加密的讯息。除了公钥之外,这是攻击者能够窃取的唯一信息。
- 接收者计算 ,从而检索原始数字 .
- 接收者翻译 回到信件,检索原始信息。
注意,第三步使用了欧拉定理。
欧拉定理告诉我们 .从接收者的第三步,我们刻意选择 这 注意,这样的 存在的定义 .这意味着存在一个整数 令人满意的 .然后
例如,假设接收者选择了质数 而且 ,连同 .
- 接收者计算 ,即公钥的一半。
- 接收者也会计算 . 也被选中了。
- 接收者计算 ,自此 自
- 接收端分发他的公钥: 而且 .
现在假设发送方想要发送消息“HELLO”。自 是如此之小,发送者将不得不一个字符一个字符地发送他的消息。
- 'H'在ASCII中是72,所以消息文本是 .
- 发送方计算 ,生成密文 .同样,这是攻击者能够获得的唯一信息,因为攻击者没有私钥。
- 接收者计算 ,从而得到的信息 .
- 接收器把72翻译成“H”。
其余的信件以同样的方式发送。
应用程序和漏洞
由于破解RSA非常困难,它几乎被普遍应用于任何需要加密的地方:密码交换、银行、网上购物,甚至有线电视。RSA也被用来确保网站是合法的,因为只有真正的网站才会有它的私钥。因此,它避免了中间人攻击,在这种攻击中,攻击者拦截一个连接,并几乎完全向用户展示一个令人信服的假连接。总而言之,RSA中的一个漏洞将会造成灾难性的安全后果,因此已经尝试了各种攻击。
RSA的强度是用密钥大小来衡量的,也就是密钥中的比特数 .512位(155位)的RSA不再被认为是安全的,因为现代暴力攻击可以在短短几个小时内提取私钥,而类似的攻击在2010年能够提取768位(232位)的私钥。截至2016年,1024位(309位)密钥被认为是有风险的,大多数新生成的密钥是4096位(1234位)密钥。
一种常见的RSA攻击会完全绕过算法。计算可以快速计算出两个数的最大公约数欧几里得算法,因此攻击者可以在两个公钥上运行此算法。如果它们的最大公约数是
其他攻击也类似,利用的是糟糕的随机数生成。如果 而且 靠得太近, 小到 ,或者私钥太小,则攻击者可以有效地确定私钥。
另一类攻击主要针对硬件。通过操纵计算机的功率水平并导致电源故障,密歇根大学的研究人员仅使用标准硬件[1]就能解码1024位的私钥。类似地,通过研究计算机运行时发出的声音,以色列研究人员能够在一小时内提取出4096位的私钥。
1994年,麻省理工学院数学家彼得·肖尔提出了一种理论算法量子计算机它分解数字的速度比现有算法快得多。然而,由于只建造了小型量子计算机,截至2016年,该算法只能分解16位数字(迄今为止最大的是56153)。
参考文献
密歇根大学。
特拉维夫大学。