RSA加密

  1. 云栖社区>
  2. 博客>
  3. 正文

RSA加密

科技探索者 2017-11-15 19:37:00 浏览648
展开阅读全文

RSA背景

在1976年以前,传统的加解密过程是:

1、A采用某种手段对数据进行加密。

2、数据传输到B的手中。

3、B逆向的实施A加密采用的步骤。

4、数据被还原。

这就是所谓的对称加密。

解密和加密的互为彼此的逆过程。加密的人必定知道解密的手段。解密的人也必定知道加密的手段。

这种加解密手段的最大特点就是对称(易于操作),但这也正是它的最大缺点。因为加密方,必须将加密规则告知解密方。

这就造成两个问题:

1、加解密规则定期就要更新,如何将加解密规则顺利的告诉对方。

2、如何安全的保存加解密规则。因为只要有一方将加解密规则泄露。那么这种加密手段就可以说被破解了。

基于此,在1976年由两位美国计算机科学家提出了一种全新的思路("Diffie-Hellman密钥交换算法"),即采用公钥-私钥对的形式进行加解密。

1、解密方生成一对密钥:公钥-私钥对。两者不存在互相推导出彼此的可能。

2、公钥随普通网络到达加密方,私钥则始终保留在解密者手中。

3、加密方使用公钥将文件转为密文

4、将密文传输给解密方。

5、解密方使用私钥将密文转为明文,完成解密。

由于公钥和私钥在逻辑上无法互相推算出彼此。这样只要私钥不被泄露,那么密文就不会解密。基于此对称加密的第一个问题的风险被解决,第二个问题的风险被缩小了一半。

受这种思路的启发,在次年,也就是1977年,由三位数学家(Rivest、Shamir 和 Adleman )联合发表了RSA算法,算法名称的来源是三位科学家的首字母的和。在随后的几十年,RSA加密算法,在密码领域中大放异彩,成为非对称加密的代表加密算法。并且随着密钥长度的不断增加,以当下的计算机运算水平,是不可能在有限的时间下,暴力破解出密钥,而攻破该算法的。

RSA加密算法的实现逻辑

在RSA算法中,需要存在五个重要的数字元素:

  p、q:这是随机选取的两个不相等质数

  n:n=p*q,也就是p和q的乘积

  φ(n):φ(n) = (p-1)(q-1) ,也就是p-1和q-1的乘积

  e:随机选取一个和φ(n)互质的正整数。并且保证 e < φ(n)

d:根据ed ≡ 1 (mod φ(n)),计算出对于φ(n)的模反元素d

ed ≡ 1 (mod φ(n)) 的含义是,ed整除φ(n)之后,余数为1。

也就是ed=k*φ(n)+1

可以看作

ed=φ(n)x+1最终利用辗转相除法(看了一下网上的推导逻辑,觉得纯数学领域了,纯记住意义不大),可以计算出一组满足的解(d,x)。

这样(n,e)是公钥,(n,d)是私钥。

由于e,d的推导是依赖的φ(n)的,而φ(n)的值来自于p、q。p、q尽管是随机取得的,但是可以由n因式分解而成。因此n的因式分解速度就成为整个解密的瓶颈。n的因式分解换言之,类似于判断n是否是质数,目前除去不断的暴力尝试,并没有好的办法。目前已知的最大分解数目的量级是10^232,占768bit位,所以一旦n突破了768位,就可以说很难破解了。(但是据说量子计算机非常适合于计算因式分解,可惜现在还是雏形)

知道了,公钥和私钥的生成后。来看下公钥私钥是如何使用的:

1、将原始信息转化为数字:无论是ascii码值,还是Unicode码,或者是其他base64转码等等,生成数字序列之后。依次循环按照下文进行加密:

公钥(n,e)、原文m

m^e ≡ c (mod n)

换言之c等于m^e除以n的余数

也就是计算出密文c

2、将密文发送给解密者,解密者依次按照下文进行还原

c^d ≡ m (mod n)公式

换言之m等于c^d除以n的余数

反向求出m即为明文

证明过程这里就忽略了,有兴趣的可以看下阮一峰写的RSA加密博客。里边的算式推理比较严谨。

此外有一点需要说明的是,在公钥加密的过程中,需要m小于n,如果在加密的过程中,发现有元素比公钥的n还要大,则需要将原文进行切割成更小的元素,然后再进行加密。

其它

另外最近流行面非常广的病毒“永恒之蓝”,始于欧洲,通过网络传播了半个世界的勒索病毒,其核心的思路就是将RSA公钥传播到本机,接着用RSA公钥加密本地文件。使本地文件不可被正常使用,进而勒索机主。待勒索成功后,只要将私钥文件再发送到本机对文件进行解密即可。思路简单,但是非常有效,难以破解,每台机器的私钥文件也几乎不会相同。

本文转自帅气的头头博客51CTO博客,原文链接http://blog.51cto.com/12902932/1926487如需转载请自行联系原作者

sshpp

网友评论

登录后评论
0/500
评论
科技探索者
+ 关注