[摘要]模幂运算是RSA公钥密码算法中最基本也是最耗时的运算。为了防御计时攻击,一般采用“以绑定法”为代表,影响运算性能的模幂算法。
本文指出并行滑动窗口算法在不牺牲性能的条件下,对于RSA计时攻击有内在的免疫能力,并在特定条件下可以有效提高RSA密码算法的运算速度,
具有推广的价值。
[关键词]RSA;计时攻击;模幂运算;滑动窗口算法;并行
对于RSA公钥密码体制的攻击方法可分为暴力攻击和非暴力攻击。其中非暴力攻击方法大致分为4类:第一类是对于明显的误用RSA加密系统的基
本攻击;第二类是小私钥指数攻击;第三类是小公钥指数攻击;第四类是对于加密过程的攻击。计时攻击是一种对于加密过程的攻击,RSA计时攻击
的实行基于RSA算法的模幂运算。对于大多数的包括RSA在内的公钥密码体制来说,模幂运算是其中最基本也是最耗时的运算,因此对于模幂运算
本身的研究是很有研究价值的。本文就模幂运算中的并行窗口算法展开论述,得出该算法对于RSA计时攻击有内在的免疫能力,并能有效提高其运
算速度的结论。
1.RSA加密算法
分两个步骤简要介绍RSA加密算法:
(1)产生密钥对
首先找到两个大素数p,q(每个n/2位),N=pq称为RSA模数(RSA modulus)。设e(gcd(N,e)=1)和d是两个整数,满足ed=1modφ(N),其中φ(N)=(p-1)
(q-1)是乘法群Z*N的指数。e称为公钥指数(encryption exponent),d称为私钥指数(decryption exponent),而(N,e)则为公钥,(N,d)为私钥。
(2)加解密的过程
消息M是一个整数,M∈=Z*N
加密过程:C=Memod N
解密过程:M=Cdmod N
2.窗口算法
模幂运算的主要算法有加法链算法及其改进算法;基于预计算技术的BGMW算法及其改进算法;基于预计算技术的双基计数系统(DBNS,double-
based number system);还有模重复平方法、因子方法等。在各类的模幂运算算法中,窗口算法是最常用的基本算法。
2.1.滑动窗口算法
滑动窗口算法是一种快速计算模幂乘运算的算法,用一个固定大小为k的窗口,在二进制模幂乘指数d上从右到左滑动。滑动过程直到窗口最右边
第一次碰“到1”结束,然后再创建一个窗口从上次结束的地方开始另一次滑动,这样的过程一直持续到d的二进制表达中没“有1”为止。(从左
到右的滑动方法与此类似,不再赘述)于是,在窗口中二进制数所代表的值便构成了集合Sk={1,3,5,…,2k-1}。
设k=3,对于d=10101100001101使用滑动窗口算法。重新编码以后的结果如下:
1 0 1 0 1 1 0 0 0 0 1 1 0 1
5 0 0 3 0 0 0 0 1 0 0 5
其中d=di2i,di∈{0}∪Sk下面提供了一种从右到左的滑动窗口算法的实现:
首先,计算C的指数从1到-1的值,并将它们存储下来:
G1←C
M←CC mod N
for i=3 to 2k-1 step 2 do
Gi←Ci-2M mod N
然后,使用上面的计算结果计算Cd:
M←Gdn-k
for i=n-k-1 down to 0 do
M←M2 mod N
if di≠0 then
M←MGdimod N
return M
当窗口大小k=1时,滑动窗口算法就是模重复平方法。因此,滑动窗口算法可看成是模重复平方法的一种改进,其思想是通过预计算来提高运算速
度。算法在预计算阶段,为了计算M=Cd mod N,d要遍历1,3,5,…2k-1,。如果采用从左到右的滑动窗口算法,则
需要增加一倍的预计算工作量。
对于w个非零窗口,预计算时需要进行1次平方运算,2k-1-1次乘法运算,计算时需要进行n-k次平方运算和w次乘法运算。对于每一个确定位数的d
来说都存在着一个最佳的窗口宽度k,使得滑动窗口算法的平均运算时间最少。在表1中我们可看到滑动窗口算法中d的长度n、最佳窗口大小k以
及平均运算次数的对应关系。
表1 k和平均运算次数关系表[6]
d的长度n(位) 最佳窗口大小k 平均运算次数
128 4 156
256 5 308
512 5 607
1024 6 1195
2048 7 2360
2.2.并行滑动窗口算法
设有x个处理单元,每个处理单元可根据实际情况由一个处理机或进程Pi来具体实现,指数d采用dn-1dn-2…d0的二进制形式,首先将d从最低位起
分为x份Mx-1Mx-2,…,M0。如图1所示,其中每份Mi(0≤i≤x-1)的长度为「l=n/x」位,|Mx-1|≤l,则d可重新表示为:
n-1
i=0∑
记Ti=cMimod N,则可将Cd mod N运算划分成x个子任务,每个子任务为计算Ti,分配给Pi去完成。对每个Pi而言(0≤i≤x-1),可用滑动窗口算法求
出结果Ti。并行算法如下:
(1)将C,N,Mi,l分配给每个计算实体Pi(0≤i≤x-1)
(2)for i=0 up to x-1 do{
Pi计算底数c
2il
mod N
使用滑动窗口算法计算Ti=cMimod N}
(3)(情况1:使用x个处理机并行计算)
for j=1 up to log2x do(分别交给P1…Plog2x进行计算)
for i=0 up to x-1 step 2j do
Ti=TiTi+2j-1 mod N
return T0
(情况2:使用单处理机x个进程串行计算)
for i=x-1down to 1 do
Ti-1=Ti-1Ti
return T0
算法中的计算工作量可分为两种情况分析:一种使用x个处理机并行计算;另一种则是使用单处理机x个进程串行计算的情况。
第一种情况的计算工作量可分析如下:第二步中,x个处理单元同时计算各自的底数,Px-1花费的时间最长,需要进行(x-1)l-1次平方运算和1次乘
法运算;x个处理单元各自利用滑动窗口算法计算Ti时,设各自分成个窗口,每个窗口宽度为k′(k′的选择可参照表1的数据),则共需要进行l-k′
+1次平方运算和2k′-1-1+w′次乘法运算。这样在第二步中Pi以共需要进行il-k′次平方运算和2k′-1-1+w′次乘法运算。第三步中,Pi需要进
行x/2i步乘法运算得到最后结果。假设有t个指定长度的指数d需要计算Cd mod N,则所要进行的运算次数可根据表1得到。经过分析我们可看到
当t较大时,可取得显著的加速比。随着窗口宽度的增大,单个处理单元的计算时间减少,但是考虑处理机之间的数据传输的时间消耗,总时间呈减
—加趋势。随着指数d位数的增加,计算时间也在增加,但是时间的增加比指数d位数的增加要慢得多。因此,第一种的并行滑动窗口算法更适合于
指数d位数比较大的情况。
由于第二种情况和滑动窗口算法的计算时间没有明显的差别,在这里就不展开叙述了。它共需要x(x-1)l/2-xk′次平方运算2k′-1x+w′i次乘法
运算。
3.计时攻击
x-1
i=0∑
3.1计时攻击的原理
Kocher针对RSA加密算法中的模幂运算提出了一套称“为RSA计时攻击”(RSA Timing Attack)的攻击方法。这种攻击方法在RSA解密或是签名时
可通过统计的方法获得解密指数d,这种方法通常用于有较弱计算能力的设备,例如智能卡。
为了使得攻击得以实行,攻击者首先请求智能卡对一系列很大的随机消息签名,并测量相应的耗时Ti。从最低有效位开始,一次攻击可得到d的一
些比特位。因为d0=1,所以从第二轮开始,根据模重复平方计算法c2=c21 mod N并m0=C。如果d1=1,智能卡计算m0c2CC2 mod N。否则不计算。设
ti是智能卡计算mi-1cdii mod N花费的时间。每个不同的ti都是不同的。攻击者在取得智能卡技术说明之后,可在脱机的状态下测量ti的值。
当di=1时,{ti}和{Ti}是相互联系的(Ti是智能卡计算一次签名使用的时间)。比如说,如果对于某些i,ti比预期的要大很多,且Ti也比预期的要。
另一方面,如果di=0则ti和Ti表现得如同两个相互独立的变量。通过测量其相关性,攻击者可判断di为0或1。
值得提出:我们设<N,d>是RSA私钥,N有n位长。则一旦得到d的「n/4」位最低有效位,攻击者可在kelog2e的时间内恢复出d。如此对于Kocher计时
攻击得到d的1/4位即可。不久以前,RSA计时攻击仅仅是理论上的讨论,并没有多少实际的威胁,直至2003年David Brumley和DanBoneh在校园网的
环境下完成了对目前普遍使用的OpenSSL攻击。他们使用了大约一百万个请求,耗时时左右的时间从OpenSSL0.9.7服务器获得一个1024位的RSA私
钥。此计时攻击和Kocher计时攻击有所不同。这种攻击方法的实现关键是基于以下的事实:进行RSA解密操作时,C遍取一个范围中的数值,每个不
同的C其计算时间是不一样,若C为p或q的倍数,其运算时间将会出现峰值。因此可通过不断使用不同的密文C得到q的信息。一旦得到了一半的q的
最高位,我们可使用Coppersmith算法得到q的其他比特位。于是,我们分解了N。
分解N=pq和得到d是等价的。于是,对OpenSSL的计时攻击得到了RSA私钥。下面证明这个结论:设(N,e)是一个RSA公钥。
证明:给定d,计算k=de-1。从d和e的定义我们知道k是φ(N)整数倍。φ(N)是偶数,所以k可写成k=2tr,r是奇数、t≥1。对于任何有g∈Z*N=1,因
此,gk/2是以N为模的1的一个平方根。以N为模的1有四个平方根。其中两个是±1,另外两个是±x,x满足x=1mod p且x=-1mod q。使用±x中的任
何一个我们可通过计算gcd(x-1,N)来分解N。进一步指出,如果g∈Z*N是随机选择的,则有至少1/2的可能性在序列gk/2,gk/4,…,gk/2tmod N中有
一个以N为模的1的平方根。通过它可分解模数N。上述序列中的数可在O(n3)的时间内被计算出来,其中n=log2N。
3.2如何防范计时攻击
3.2.1有性能损耗的防范方法
从滑动窗口算法容易看出当窗口大小k>1时,对采用这种模幂算法的RSA系统,Kocher计时攻击是无效的。这是因为Kocher计时攻击是通过判断d的
某位是否非零来得到d的位信息的。由于k>1,所以只判断d的某位是否非零已经无法满足恢复d的要求。另外,这种模幂乘法对于防范其他类似攻
击如:能量攻击是十分有效的。
然而,2003年David Brumley和Dan Boneh另辟蹊径,通过分析一次签名的耗时与待签名的数值以及q的关系来分解N=pq。对于这种计时攻击“,绑
定法”可有效防御。其实施过程是这样的:在解密C之前,产生一个随机的数字r∈Z*N并计算C′=Cre mod N。在计算得到M′=(C′)d mod N后,可
通过M=M′/r mod/N得到M。由于r是随机的,所以每次计算的输入值和C并不相关。因此,其攻击方法是无效的。根据[8],采“用绑定法”会带来
2%到10%的性能损失。此方法同样适用于所有现有的计时攻击。
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计时攻击具有内在的免疫能力,在采用多处理机的情况下极大地提高了模幂运算的速度;在采用单处理器多进程的情况下没有无谓的时耗。
该算法简单易行,具有很大的可行性。
|
