RSA算法

密码学学习笔记

 Liu Ke     2018-06-05   1375 words    & views

Contents

  1. 简介
  2. 加密
  3. 解密
  4. 密钥对生成过程
    1. 求N
    2. 求L
    3. 求E
    4. 求D
  5. 对RSA的攻击

简介

公钥密码,也就是非对称加密,用公钥加密,用私钥解密。公钥一般是公开的,私钥仅供自己使用。公钥和私钥是一一对应的,被称为密钥对。

RSA就是一种公钥密码算法。同样,它的名字也是由三个人名组成的,他们是Ron Rivest、Adi Shamir和Leonard Adleman,即Rivest-Shamir-Adleman。

RSA的明文、密文和密钥的都是数字

加密

RSA的加密和解密过程非常简洁。

RSA加密如下所示,求E次方的modN,E代表Encryption加密,N代表Number:

RSA的密文是代表明文的数字的E次方求modN的结果。即先对明文做E次方运算,然后除以N,所得的余数,就是密文。公钥为数E和N的组合(E,N)

解密

RSA解密如下所示,求D次方的modN,D代表Decryption解密,N代表Number:

RSA的明文是代表密文的数字的D次方求modN的结果。即先对密文做D次方运算,然后除以N,所得的余数,就是密文。私钥为数D和N的组合(D,N),这里的N和加密所用的N为同一个数字。

密钥对生成过程

求N

用伪随机数生成器生成两个非常大的质数p和q,将p和q相乘即为N

求L

L是仅在密钥对生成过程中使用到的数。

L是p-1和q-1的最小公倍数

求E

E是满足以下两个条件的数:

  • 1<E<L
  • E和L互质,即E和L的最大公约数为1。

E和L互质能保证“一定存在解密时的数D”。

到这一步,就已经生成了数E和N,也就是密钥对中的公钥。

求D

数D是由数E计算得到,满足以下条件:

  • 1<D<L
  • E×DmodL=1

对于式E×DmodL=1,只有保证E和L的最大公约数为1,才存在D。

这样,就生成了数D和N,也就是密钥对中的私钥。

对RSA的攻击

“求D”与“对N进行质因数分解”在2014年被Alexander May证明在确定多项式时间内是等价的。只要对N进行质因数分解并求出p和q,就能求出D。

大质数p和q必须保密。通过N无法求出p和q,因为只能对N进行分解质因数来完成,但是对大整数进行质因数分解目前是非常困难的。所以发现大整数质因数分解的高效算法就代表着RSA可被破译

中间人攻击:对发送者伪装成接收者,对接收者伪装成发送者,获取密钥。

选择密文攻击:攻击者向服务器反复发送自己生成的伪造密文,并通过分析服务器返回的错误消息和响应时间获得提示。

选择密文攻击

解密提示:发送任意数据,服务器都会将其当做密文来解密并返回解密的结果。

抵御选择密文攻击:解密时判断“密文是否由知道明文的人通过合法的方式产生”,即认证

RSA-OAEP(Optimal Asymmetric Encryption Padding,最优非对称加密填充):在加密时在明文前面填充一些认证信息,包括明文的散列值和一定数量的0,然后再对填充后的明文用RSA进行加密。解密时,如果判断“密文不是由知道明文的人产生的”,就返回一条固定的错误消息“decryption error”(不能将具体的错误内容告知发送者)。实际运用时,还会通过随机数生成器使得每次产生的密文呈现不同的排列方式,进一步提高安全性。