RSA 这俩世纪最重要的算法之一No.91

本文大概1000字,读完共需5分钟

Diffie–Hellman加密算法的劣势

上一篇文章我们聊到 Diffie–Hellman key exchange 这个算法。(密钥交换有点不安全 No.89),虽然可以安全地交换密钥从而使用 AES,DES 等对称加密算法进行加密,但是却有一个天大的问题。就是他娘的,跟一个人通讯就要保存一个密钥,跟一百个人通讯就要保存一百个密钥,A 迟早会崩溃。

密钥崩溃中

RSA 算法的来历

所以科学家就思考,能不能减少密钥的个数呢??这时候大佬就想到了,街头上的邮筒。

邮筒是一个公开的地方,所有人都可以往里面投递信件(传递信息),但是只有拥有邮筒的邮筒管理员才能打开这个邮筒进行信件的揽收(信息获取)。

虽然这个例子举得不是很恰当啊。但是是大概是这么一个意思,就是能不能将一个公开的加密的密钥分发给其他人,其他人用这个密钥进行加密,而只有拥有私钥的人才能进行解密呢?

来来来 RSA 算法了解一下。

RSA

RSA是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

但是呢,其实 RSA 算法并不是1977年被发明的,早在1973年,英国国家通信总局的数学家 Clifford Cocks 就发现了类似的算法,他的研究一被发现,立马被列为绝密,直到1998年才得以公诸于世。

RSA应用

说 RSA 加密算法是上世纪和本世纪最重要的算法之一绝不为过,RSA 是一种基于大数因式分解为保证的非对称加密算法,广泛应用在数字签名、数据加密等领域,是第一个同时能够数据签名以及数据加密的算法。所以其实公钥和私钥是一个相对的概念,大家不要纠结了,这个算法是双向的,用公钥加密的数据,只能用私钥解密。用私钥加密的数据,只能用公钥解密。这样一来一回呢,公钥加密就的数据传输的应用就变成了加密(加密在不安全信道中的数据传输),私钥加密的数据应用就变成了数据签名(检验某个数据是不是真的来自A)。

RSA的工作过程

好了,为了表达我是真的自己搞了一遍,证明过程了解一下。

算法分为五步。

1、选择 p、q两个比较大的质数

2、令n = p * q。取 φ(n) (欧拉函数自行度娘),

3、取 e ∈ 1 < e < φ(n) ,( n , e )为公钥对

4、令 ed mod φ(n) = 1,取得d,( n , d ) 为私钥对。

5、销毁 p、q。密文 = 明文 ^ e mod n , 明文 = 密文 ^ d mod n

嗯,算法就是这么简单。但是其实可以很简单证明。

(明文 ^ e mod n)^d mod n = (明文 ^ d mod n)^e mod n

RSA如何保证安全?

如何破译?算法如何保证安全?

我们可以看到,经过上面的过程,出现了 p、q、n、φ(n)、e、d 这么多数字。那么如何破解d这个私钥呢??

step1:e*d mod φ(n) = 1。

如果知道了φ(n),而e又是公开的,那么d就被解密了。

step2:φ(n) = φ(p * q) = φ(p) * φ(q) = (p-1)(q-1)

好如果知道了 pq,那么φ(n)也是可以计算出来的。

step3:如何知道p、q呢?n = p * q。

将公开数据 n 进行因式分解就可以得到 p、q了。但是现在大数因式分解都是一个世界大难题。所以RSA只要密钥不泄露,那么信息就是安全的。

RSA为什么可以被加解密?

下面证明一下为什么上边的算法可以进行加解密。假设明文为 m(message),密文为 c (crypted)。

加密过程

c = m ^ e mod n

解密过程:

m

= c ^ d mod n(代入c)

= (m ^ e mod n)^ d mod n(进行模计算变换)

= m ^ (e * d) mod n

∵ e * d mod φ(n) = 1

∴e * d = k * φ(n) + 1 (k为整数)

m

= m ^ (k * φ(n) + 1) mod n

= m ^ (k * φ(n)) * m mod n

若m与n互质,那么m ^ (k * φ(n)) mod n = 1 (欧拉公式)

那么上式子 可得直接等于 m。原题得证。RSA 原始论文也只讨论了m与n互质的情况,但是阮一峰老师还证明了另外一种情况,就是 m与n 如果不互质呢??这种情况我上面也证明了,感兴趣的小伙可以了解一下。

原文发布于微信公众号 - 一名叫大蕉的程序员(DaBananaTalk)

原文发表时间:2018-03-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏上善若水

011各种加密算法比较

算法选择:对称加密AES,非对称加密: ECC,消息摘要: MD5,数字签名:DSA

2453
来自专栏小工匠技术圈

【Java小工匠聊密码学】--对称加密--IDEA

  国际数据加密算法(IDEA)是[上海交通大学]教授来学嘉与瑞士学者James Massey联合提出的。它在1990年正式公布并在以后得到增强。这种算法是在[...

902
来自专栏码神联盟

敲一天代码了,轻松下吧,精彩 !看人潮如海

先来首歌曲,耶耶耶..... ? 一边听歌,一遍来看几个算法 一、数字摘要算法 数字摘要也称为消息摘要,它是一个唯一对应一个消息或文本的固定长度的值,它由一个...

2875
来自专栏阮一峰的网络日志

密码学笔记

1. 加密方法可以分为两大类。一类是单钥加密(private key cryptography),还有一类叫做双钥加密(public key cryptogra...

3374
来自专栏黑白安全

如何攻破加密算法

当应用加密算法时,有许多地方可能会出错。难点在于识别和分析程序员用来加密的方法,然后寻找其中的漏洞。漏洞的种类也很多,比如弱加密算法、弱密钥生成器、服务端漏洞和...

1782
来自专栏企鹅号快讯

黑客们都是如何给勒索软件加密的?

加密是计算机科学中历史最长久的一种计算了。早在二战时期,德国就制造了Enigma密码机,来传输机密信息。计算机科学的祖师爷之一图灵也参与了对Enigma密码的破...

2209
来自专栏安恒信息

NSA能破解大部分Tor加密密钥

全研究人员认为,Tor匿名网络使用的大部分密钥能被美国国家安全局(NSA)破解。 渗透测试公司Errata Security CEO Rob Graham设立了...

3043
来自专栏区块链

SSL证书的加密技术

根据密钥类型不同将现代密码技术分为两类:对称加密算法(秘密钥匙加密)和非对称加密算法(公开密钥加密)。对于对称性加密算法,信息接收双方都需事先知道密匙和加解密算...

2316
来自专栏GAIAWORLD

GaiaWorld:加密技术在区块链中的意义

加密技术作为区块链技术里极其重要、不可或缺的一部分,为区块链的匿名性、不可篡改和不可伪造等特点保驾护航。如果说共识机制是区分一个公链质量的核心和灵魂,那么加密算...

960
来自专栏Java技术栈

常用加密算法解析

今天介绍下工作当中常用的加密算法、分类、应用。 1、对称加密算法 所谓对称,就是采用这种加密方法的双方使用方式用同样的密钥进行加密和解密。密钥是控制加密及解密过...

6647

扫码关注云+社区

领取腾讯云代金券