基于并行滑动窗口算法的RSA计时攻击防御的研究
[摘要]模幂运算是RSA公钥密码算法中最基本也是最耗时的运算。为了防御计时攻击,一般采用以“绑定法”为代表,影响运算性能的模幂算法。本文指出并行滑动窗口算法在不牺牲性能的条件下,对于RSA计时攻击有内在的免疫能力,并在特定条件下可以有效提高RSA密码算法的运算速度,具有推广的价值。
对于RSA公钥密码体制的攻击方法可分为暴力攻击和非暴力攻击。其中非暴力攻击方法大致分为4类:第一类是对于明显的误用RSA加密系统的基本攻击;第二类是小私钥指数攻击;第三类是小公钥指数攻击;第四类是对于加密过程的攻击。计时攻击是一种对于加密过程的攻击,RSA计时攻击的实行基于RSA算法的模幂运算。对于大多数的包括RSA在内的公钥密码体制来说,模幂运算是其中最基本也是最耗时的运算,因此对于模幂运算本身的研究是很有研究价值的。本文就模幂运算中的并行窗口算法展开论述,得出该算法对于RSA计时攻击有内在的免疫能力,并能有效提高其运算速度的结论。
1.RSA加密算法
分两个步骤简要介绍RSA加密算法:
2.窗口算法
模幂运算的主要算法有加法链算法及其改进算法;基于预计算技术的BGMW算法及其改进算法;基于预计算技术的双基计数系统(DBNS,double-based number system);还有模重复平方法、因子方法等。在各类的模幂运算算法中,窗口算法是最常用的基本算法。
2.1.滑动窗口算法
滑动窗口算法是一种快速计算模幂乘运算的算法,用一个固定大小为k的窗口,在二进制模幂乘指数d上从右到左滑动。滑动过程直到窗口最右边第一次碰到“1”结束,然后再创建一个窗口从上次结束的地方开始
3.2.2使用并行滑动窗口算法
从并行滑动窗口算法的实现方式出发,我们分两种情况分析:第一种是使用x个处理机的情况;第二种是使用单个处理器x个进程的情况。
在第一种情况下,每次模幂运算可由4个计算时间段组成:数据分布时间、预计算时间、计算时间和数据收集时间。在给定C、d的情况下每次模幂运算中数据分布、预计算还有数据收集时间是固定的。由于各个Pi的运算是并行进行的,故此时计算时间是不固定的,它取决于第二步中花费时间最长的Pi的计算时间。根据David Brumley和Dan Boneh的计时攻击原理,当C的取值为指数倍数时计算时间会出现峰值。那么第二步中这x个并行进行的滑动窗口算法在C的取值遍历一个数值区间时会产生多个不相干的峰值。由于无法确定一个峰值产生时哪个Pi的计算时间最长,我们无法针对某一个Pi的指数进行计时攻击。因此,并行滑动窗口算法对David Brumley和Dan Boneh的计时攻击具有内在的免疫能力。
在第二种情况下,由于操作系统对于进程的管理加入了很多不确定的因素。每次模幂运算的耗时由数据分布时间、预计算时间、计算时间、数据收集时间和进程调度耗时组成。由于进程调度耗时具有随机性,我们无法确定每次模幂运算的进程调度耗时,故此时,并行滑动窗口算法同样对David Brumley和Dan Boneh的计时攻击具有内在的免疫能力。
因此,我们得出这样的结论:使用并行滑动窗口算法在不增加无谓的时间消耗的情况下,可有效地防御RSA计时攻击。
4.结束语
RSA计时攻击是针对RSA密码体制中的模幂运算出现的。David Brumley和Dan Boneh的计时攻击在Kocher计时攻击的基础上有了长足的发展,对于现有采用RSA公钥密码算法的密码软件产生了直接的威胁。对于以RSA为代表的公钥密码体制来说,模幂运算是最基本的运算。它的运算时间直接影响了密码体制实现的有效性。基于现有的RSA计时攻击的防御方案需要付出一定的性能代价情况的考虑,本文给出了一个防御方案。该方案对于RSA计时攻击具有内在的免疫能力,在采用多处理机的情况下极大地提高了模幂运算的速度;在采用单处理器多进程的情况下没有无谓的时耗。该算法简单易行,具有很大的可行性。
|
