RSA算法的定时攻击及其防范措施

计国民

（滁州职业技术学院，安徽 滁州 239000）

一、引言

RSA算法是以其发明人MIT的Ronald.L.Rivest，A－di.Shamir和Leonard.M.Adleman三人名字的首字母来命名的，是公钥密码体制中使用最广泛的一种安全密码体制算法。其安全性是基于整数的因子分解困难性的。RSA算法的私钥(d,n)，公钥(e,n)，要求满足条件ed=1mod φ(n)，其中n为两个大素数p和q的积，即n=p*q。

假设明文和密文分组分别用M、C来表示，RSA算法加密和解密过程为：

（1）加密：C=Memod n

（2）解密：M=Cdmod n

RSA算法的数字签名过程：

（1）签名过程：计算消息M的散列值H(M)，用签名者的私钥(d,n)计算签名s=(H(M))dmodn，发送消息和签名(M,s)。

（2）验证过程：利用签名者的公钥(e,n)计算

h=semod n,利用M计算其散列值H(M)，比较h=H(M),如果成立，表示签名有效。否则，该签名无效。

二、基本思想

根据RSA算法的描述，在对消息进行处理时，都要用到幂运算，即F=abmod n，这就给定时攻击留下了一个机会。所谓的定时攻击是由密码分析家P.C.Kocher于1996年提出，该攻击与常规攻击方式完全不同，其仅仅使用密文进行攻击，所以通常被安全专家称之为“有创意的攻击”。定时攻击的基本思想为：要计算F=abmod n,其中b用二进制表示为b=(bk…b1bo)2，即为k比特长度。那么程序可以用如下伪代码实现（其中m为临时变量）：

从上面的算法可以看出，如果指数的当前比特为1时（即b1=1），就要运算额外的模运算(d×a)mod n，这必将花费一定的计算时间，从而导致运算速度减慢。对于一些a和d来说，该模运算是相当的慢，攻击者很容易就能掌握这些值。由此，攻击者可以通过观察系统处理上述函数所花费的时间来判断，当很慢时指数比特很可能就是1，否则就是0，利用此原理就可以得到整个指数。也就是说可以得出其私钥和相应的公钥，从而会导致该算法的不安全。

三、防范措施

要克服RSA算法中的定时攻击，可以采取以下三种方法：

（一）对密文进行盲化处理

所谓的盲化处理，就是为了避免逐位运算，在其取幂运算之前，先产生一个随机数 t，要求0＜t≤(n-1)，然后对密文进行盲化， 分别计算C＇=c(te)mod n，M＇=(C＇)dmod n，M=(M＇t-1)mod n。 这样，就可以防止攻击者了解计算机中所处理的数据，从而防止了定时攻击的逐位分析。

（二）随机延长幂运算时间

由于定时攻击主要是根据逐位运算时间的长短来得到该位的值是0还是1，因此，在取幂运算时可以增加一个随机延时来调整其运算时间，从而迷惑攻击者判断真正的运算时间。

（三）固定取幂运算时间

除了随机延长幂运算时间外，也可以采用固定幂运算时间，也就是说保证所有取幂运算操作在返回结果之前都花费同样多的时间，这样攻击者就无法得到哪一位运算时间需要的时间是长还是短，从而无法判断是0还是1。

四、建议

RSA算法的安全性不仅是要对其安全攻击进行防范，而且还要对各种不安全的因素进行防范，这些因素包括以下几个方面：

（一）参数的选择要合理

RSA算法中所涉及到的主要参数包括 p、q、e和d四个。对于p和q来说，要求为强素数并且足够大，p与q之间的差值要大，(p-1)与(q-1)的最大公因子要小。参数e的值不可太小，选择的e在mod φ(n)中的阶数i要求达到(p-1)(q-1)/2，即满足 ei=1 mod φ(n)。 选择参数d时，应使d>n1/4。

（二）在RSA数字签名算法中，要使用散列函数

在RSA数字签名中，使用散列函数可以使数据的完整性得到保护，在对签名进行验证时，其验证h=H(M)，如果消息M在传输过程中被篡改或发生其他变化，其散列值H(M)也会发生变化。如果不使用散列函数，那么在签名验证时，仅验证h=M，其完整性无法得到保证。

（三）明文的熵要尽可能的大

明文的熵越大，就会使得在已知密文的情况下，要猜测明文就越接近于完全随机等概情况。如果明文的熵值比较低，可以在明文分组中加入一个随机数t来处理。

（四）不要使用公共模

使用公共模可以使得密钥管理简单，其存储空间相应减小，重新分配密钥问题也变得比较简单，但其安全性也相应地变得脆弱，建议不要使用公共模。

[1]赖溪松，韩亮，张真诚．计算机密码学及其应用[M]．北京：国防工业出版社，2001：84-105.

[2]吕述望，范修斌，张如文．密码学函数迭代原理信息论分析[J]．电子学报，2002，(2)：1511-1513.