计国民

（滁州职业技术学院，安徽 滁州 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，利用此原理就可以得到整个指数。……