Solobear 述而不作

公钥密码学中的RSA算法分析

2018-03-18

公钥密码学应用场景

公钥密码体系又称为非对称密码,即加密和解密算法使用不同的密钥:一个是公钥Pu、一个是私钥Pr。公钥密码学的应用场景有:

  • 加密和解密 发送方使用接收方的公钥加密,接收方使用对应的私钥解密。这样只有私钥的拥有者能解密,这样就保证了消息的私密性
  • 数字签名 发送方使用私钥做签名。消息接收者根据对应的公钥进行签名验证。由于只有消息发送方拥有私钥、生成签名,因此签名验证成功后表明此消息确实由发送方发送过(注意,是发送过,而非消息来源是发送方)。数字签名解决了发送方否认问题
  • 密钥协商 双方能够安全地交换彼此共享的秘密信息,作为后续对称加密所使用的密钥。常用的有基于离散对数的Diffie-Hellman交换和基于椭圆曲线算法的ECDH算法,这里暂时不涉及。

RSA中的数论知识

RSA依赖数论中的一些知识:

  • 乘法逆元 对于互素的两个正整数a, n,根据扩展欧几里得算法,总存在正整数b,使得 \(a*b=1(mod n)\)
  • 欧拉定理 对于正整数a, n,phi(n)为n的欧拉函数(小于n且与之互素的所有正整数的个数),则有: a^{phi(n)+1}=a(mod n)
  • 离散对数难题: 对于正整数a, n, x, y,已知a, n, x,正向求幂y=a^x(mod n)是容易的,反之,求指数x在计算上是困难的;这个性质在RSA签名中得到应用。
  • 大素数分解难题,已知两个大素数p,q,求其乘积n=p*q是容易的,而已知n,求其素因子p,q是困难的。

其中计算乘法逆元时的欧几里得算法在计算上是容易的,通常将a对n取模的逆元写成b=a^(-1)(mod n).

此外,根据欧拉定理,还可进一步得到推论:对于正整数a, n, k,phi(n)为n的欧拉函数,有:a^(k*phi(n)+1)=a(mod n),这一推论可用于RSA加密和解密过程。

RSA密钥生成

RSA算法是基于大素数分解难题,即已知两个大素数p,q,求其乘积n=p*q是容易的,而已知n求其素因子p,q是困难的。基于此,RSA算法按如下过程生成私钥和公钥:

  • 选定两个大素数p,q,这两个素数是私密的;
  • n = p*q,这个乘积n可以公开;
  • 随机选定e满足gcd(phi(n), e) = 1 ,其中phi(n)=(p-1)*(q-1), 为n的欧拉函数。e的选取是公开的;
  • 根据欧几里得算法求d = e^(-1) (mod phi(n)),d私密
  • 最后一步,销毁大素数p,q

最终生成公钥Pu={e, n},私钥Pr={d, n}。

RSA加密过程

加密和解密的场景为:对于明文M,Bob使用Alice的公钥加密消息发往Alice;Alice根据自己的私钥解密消息,得到明文。RSA中的过程如下:

  • 对于明文M,Bob根据Alice的公钥Pu={e, n}进行加密运算,得到密文C=M^d(\bmod n)
  • Alice收到密文后,根据自己的私钥Pr={d, n}进行解密运算,C’=C^d=M^{d*e}(\bmod n)

由于d = e^(-1) (mod phi(n)),则必有de=kphi(n)+1,k为正整数。则根据之前的推论,有: C’=M^(de)(mod n)=M^(k*phi(n)+1)=M(mod n)

至此密文被解密为原来的明文M。值得一提的是,实际中的明文通常为字符串,在应用RSA算法时,需要将字符串映射为整数。

攻击者想得到明文,则必须得到私钥d,这等价于求得phi(n),无异于想分解n为两个大素数这一大素数分解难题。

RSA签名过程

签名的场景为发送方Alice使用私钥做签名,附带着消息原文M发送。所有的接收者都可以使用Alice公开的公钥对签名进行验证。

Alice生成签名的过程如下:

  • Alice对消息原文M进行Hash运算,得到消息的摘要H=Hash(M)
  • Alice根据自己的私钥d对消息摘要进行签名S=H^d(mod n)
  • Alice将签名附在消息原文后,一起发送出去,消息为(M   S)

接受者Bob收到消息后的签名验证过程如下:

  • Bob收到消息后根据Alice的公钥e对签名S进行验证,验证结果为H’=S^e(mod n)
  • Bob对接收的消息原文M进行Hash计算,得到消息的摘要H=Hash(M)
  • 根据欧拉定理的推论,自然有H’=H,此时可以认定签名来自Alice,且消息M未经篡改

上面的签名过程,事实上解决了发送方否认问题消息完整性两个问题:

  • 消息接受方Bob用Alice分发的公钥确实能够解开签名,Alice无法否认这条消息,这就保证了消息中所声称的身份(Alice)是真实可靠的。
  • Hash函数的引入,可以保证消息完整、不被篡改,通常使用HMAC——基于MAC消息验证码的Hash函数

签名发送过程中S=H^d(mod n)和H是公开的,攻击者如果想获取私钥d,则必须解开离散对数难题,这在数学上是困难的。

RSA签名仍然不能解决发送方身份可信问题,因为公钥的来源是没有保障的,这就需要引入CA证书机制。因为和RSA算法本身无关,这里就不再赘述。


Similar Posts

Comments