李子臣　孙亚飞　杨亚涛　梁　斓　汤永利

1(西安电子科技大学通信工程学院　陕西 西安 710071) 2(北京印刷学院　北京 102600) 3(北京电子科技学院　北京 100070) 4(河南理工大学计算机科学与技术学院　河南 焦作 454000)

0　引　言

RSA密码算法是由Ron Rivest、Adi Shamir和Leonard Adleman[1]于1978年提出的著名公钥密码体制。目前关于RSA密码算法的研究已经相当成熟，且广泛应用在多个行业内。同时，也正是由于其应用的广泛性，有大量的研究人员对其算法进行漏洞分析。传统的数学分析方法包括：RSA小指数攻击[2]、非共模攻击及共模攻击[3]、循环攻击[4]等。有别于传统攻击方法的是文献[5]提出的计时攻击，也从此开辟了关于RSA的侧信道攻击。

近年来，国内外针对RSA密码算法的侧信道攻击与防御研究主要有：文献[6]针对部分密钥泄露，给出攻击方法，并提出相应的防御策略。文献[7]指出常规的模幂运算并不能达到其声称的抵抗计时攻击效果。文献[8]针对采用盲化策略的RSA密码算法进行能量攻击，通过采用多条能量迹成功对RSA实现攻击。

本文通过分析基于大整数分解困难问题及基于椭圆曲线离散对数问题的核心运算，详细介绍侧信道攻击中的计时攻击与能量攻击技术，结合运算本身的性质及侧信道攻击的关键点，提出一种随机功耗的思想来提高密码算法的安全性及效率。

与RSA类似的椭圆曲线公钥密码体制[9]，其核心运算均为如下：y=mxmodn。为便于计算，针对此幂指数运算，我们一般采用从左向右、从右向左及随机指数三种方法进行运算。考虑到运算效率，我们采用蒙哥马利模乘器来加速其运算。下面叙述从左向右、从右向左算法及随机算法的蒙哥马利实现算法。首先，计算x=ak(modn)，将k表示成二进制形式k=(1kt-1…k1k0)2。

算法1从左向右算法

ak=(…((a2·akt-1)2·akt-2)2·…·ak1)2·ak0。

Input:t,k0,k1,…,kt-1,a,n

Setx=a

Fori=t-1,t-2,…,1,0repeat

Setx=x2(modn)

Ifki=1thensetx=xa(modn)

Output:x

算法2从右向左。

ak=a2t·((a2t-1)kt-1·…·((a22)k2·((a2)k1·(ak0·1)))…)。

Input:t,k0,k1,…,kt-1,a,n

Setx=1,y=a

Fori=0,1,…,t-1repeat

Ifki=1thensetx=xy(modn)

Sety=y2(modn)

Setx=xy(modn)

Output:x

算法3随机指数。

Input:t,k0,k1,…,kt-1,a,n

Setx=1,y=a,z=random(1,n-2)

Fori=z,…,n-2repeat

Ifki=1thensetx=xy(modn)

Sety=y2(modn)

Setx=xy(modn)

Fori=z-1,…,0repeat

x=x2modn

Ifki=1thensetx=xy(modn)

Output:x

1　侧信道攻击及防御技术

通过上述模幂运算，可知，当对应bit位为1的时候，与bit位为0相比较，多了一个乘法同余运算。因此，其运算时间和能量消耗明显增多，利用此信息，能够方便、快速、有效地实施计时攻击及能量攻击。

1.1　计时攻击

计时攻击[5]通过获得一系列经密码芯片处理后的信息及处理时间，根据应答时序差来进行密钥的推断。计时攻击模型如图1所示。

图1　计时攻击模型

其中，m：消息，k：密钥，S：输出，A：算法。A(m,k)=m*k,*指算法，T：算法计算需要的时间，T(m,k)=t[A(m,k)]。

假定计算中密钥恒定，且监听者已经破解一组消息及计算时间T，现为了攻击密钥的第i个比特ki，当监听者捕获时间T(m,ki)，则可建立函数判断比特位的值。

假定随机变量v0,v1的分布是不同的，通过观察实际的T(m,0)与T(m,1)的分布，则有可能推测出ki，进而推测出完整的密钥值。

1.2　能量攻击

能量攻击[10]主要有：简单能量攻击SPA(Simple Power Analysis)和差分能量攻击DPA(Differential Power Analysis)。

简单能量攻击：通过分析硬件电路加密时释放出的能量特征获取与密钥相关的信息，根据能量曲线的特征及分析者的经验就可直观分析出指令执行的顺序。程序运行时，能量曲线有明显的不同，通常情况下轨迹较宽且能量消耗较多对应密钥位“1”，否则，对应密钥位“0”。逐位逐比特对密钥位进行猜测，即可完成对算法的破译。

差分能量攻击：根据能量曲线的差分信号分析出所需的关键信息，并采集多组能量曲线及每条曲线对应的明密文，需要大量的信息及一定的SPA分析经验和长时间分析运算。DPA需要采集多组能量曲线，将其作为先验函数，而将猜测的密钥组根据一定规则进行分类作为后验函数，通过找出两组函数所具有信息量的相关性，若相关性强，则密钥猜测正确，反之，重新采集数据并作比对。

1.3　防御措施

针对侧信道攻击技术的特点，主要是防御思想是通过增加冗余信息、延长算法执行时间、加入固定(随机)噪声及扰乱能量曲线等。常用的侧信道攻击防御措施主要有：掩码技术[11]、功耗平衡技术[12]及功耗扰乱技术。其中掩码技术分为布尔掩码、多项式掩码及内积掩码，都是通过变换掩盖明文信息或中间结果，即使破译成功，得到的也不是原始明文信息。功耗技术主要是通过增加时间或者能量的消耗，加大噪声功率，减少信噪比，提高信息提取难度，从而达到防御目的。

2　随机功耗算法实现

信息的泄露主要是由于时序差及能量的消耗所引起，理论上讲，设计一种算法，增加执行代码，使得对于“0”和“1”执行相同的动作，这样就能使得每一次计算消耗的能量就无法区分，且计算过程的时间相同。因此，通过此方法能很好地防御SPA和DPA。

根据上述基本思想，本文提出随机功耗算法，并给出编码实现如下,以从左向右算法为例：

对于计算x=ak(modn)，将k表示成二进制形式k=(1kt-1…k1k0)2。

算法4从左向右随机功耗算法

ak=(…((a2·akt-1)2·akt-2)2·…·ak1)2·ak0。

Input:t,k0,k1,…,kt-1,a,n

Setx=a

Fori=t-1,t-2,…,1,0repeat

Setx=x2(modn)

Ifki=1thensetx=xa(modn)

Ifr=random(0,1)=1thensetx=rx(modn)

Output:x

其中r=random(0,1)表示r为随机从{0,1}中选取。对于从右向左及随机算法，有类似的改进。

3　方案分析

3.1　抗计时攻击

在每轮的迭代运算中，当比特位不为1而随机数r为1的时候，算法包含伪操作，耗时增加。由于随机数的存在，造成时序差的混乱，即对于比特位为0的运算，耗时是不固定的，同时也混淆了0和1的时间消耗，这样攻击者就无法通过对比迭代运算的时序差获取相应的密钥信息。

假设密钥比特位出现“0”和“1”的概率是完全随机的，对于全“0”字段，其对应的操作是重复进行的，由于随机数的参与，或造成其消耗的时间类似于有比特位为1的运算参与。攻击者无法通过计时获取密钥的具体内容。

综合以上分析，本文提出的随机功耗算法能够有效地达到抗计时攻击的目的。

3.2　抗能量攻击

对于抗简单能量攻击：在随机功耗算法中，当满足随机数为1时，存在伪操作运算。伪操作运算在多精度算法相同的情况下，消耗的平均能量是相同，由于随机数的存在，攻击者无法根据全“0”时的曲线有效分析出原比特值。

虽说伪操作运算在一定程度上会存在泄露信息的风险，但可以使用简单的时序控制屏蔽信息泄露，加之随机数的混淆作用，可以有效地防御SPA攻击。

对于抗差分能量攻击：差分能量攻击能够通过差分计算将噪声和伪操作剔除，然后通过简单能力分析即可破译密码。

随机功耗算法则不同，由于当伪随机操作被过滤之后，攻击者可以区分全“1”字段，然而这样的字段概率是很小的。通过模幂运算的操作步骤可知，密钥比特位猜测的关键是本轮迭代中是否有乘同余操作，若有，则对应指数为“1”，否则为“0”。平方剩余的计算则与指数位取值无关。

对于n比特长的密钥，若要成功破译密码算法，则其关键是确定非全“0”指数段的取值。而这样的情况有2n-1种，而对于比特位为“1”的字节，其每次计算消耗的能量也是随机的，因此无法有效地区分取值。若要从相同的操作中分析出对应比特位的具体值，则攻击者需要采用高阶攻击的方法。导致所需采集和处理的数据呈指数增长，而根据文献[13]的结果，三阶以上的DPA实施起来都是相当困难。

综上所述，该随机功耗算法能够有效地混淆能量曲线，加大分析破译难度。从而达到防御侧信道攻击的效果。

4　效率分析

本节从算法消耗的时间及运行过程消耗的能量进行分析。算法设计本身就是采用运算效率较高的蒙哥马利形式的算法，因此，运算效率相比较传统的算法[14]，有明显的提高。

在运行效率上，假设密钥长度为n比特长，其中0、1各占50%，执行一次模平方操作消耗的时间为T，一次模乘操作消耗时间为T。对于未加保护的原始方案，当比特位为1时，需要执行模平方与模乘计算，需要的执行时间为n/2×(T+T)=nT；当比特位为0时，仅有一次模乘运算，需要的执行时间为nT/2，共计需要执行的时间为3nT/2。对于等功耗编码的实现方式，当比特位为1时，每次均需要执行一次模平方计算和模乘计算，则需要执行的时间为：n/2×(T+T)=nT；对于比特位为0时，每次计算时同样需要执行一次模平方计算和模乘计算，则需要执行的时间为：n/2×(T+T)=nT，共计需要执行的时间为2nT。针对本文提出的方法，当比特位为1时，计算时间为n/2×(T+T)=nT，当比特位为0时，有一半的需要执行模平方操作，需要执行时间为nT/2，另一半需要的时间为nT/4，因此，需要的总运算时间为：nT+nT/2+nT/4=7nT/4。

在能量消耗方面，假设执行一次模平方操作消耗能量为P/2，一次模乘操作消耗能量为P/2。对于未加保护的原始方案，当比特位为1时，需要消耗的能量为nP，当比特位为0时，均需要进行模乘操作，需消耗能量为nP/2，共需消耗能量为3nP/2。等功耗编码方式，对于所有的0比特位时，均执行模平方操作，使得0比特位与1比特位消耗的能量相同，共需消耗能量为2nP，提高了方案的安全性，但是增大了能量的消耗。本文所提出的方案对比特位为0时进行处理，当比特位为0时，以一定的概率进行模平方操作，假设n长比特中0、1各占50%，比特位为0的字节中，有50%的做模平方操作。当比特位为0时，均需要进行模乘操作，需消耗能量为nP/2，存在一半的比特位执行模平方操作，即能量消耗为1/2×nP/2=nP/4，则共需消耗的能量为7nP/4。

通过分析比较，本文提出的方案，比原始方案增加了15%左右的时间和能耗开销，但是提高了方案的安全性；对比等功耗编码实现方式节省了15%左右的时间和能耗开销，但同样的能保证方案的安全性。针对目前RSA密码算法的安全密钥长度至少为2 048比特，文献[12]中的算法至少增加1 000次模乘，而本文所设计的算法，与文献[12]相比较节约了至少500次模乘，在效率上有大幅度的提高。

由此可以看出，改进后的随机功耗算法能够有效地节省运算时间，提高执行效率。同时，也正是由于随机数的引入，对能量的消耗起到一个很好的混淆效果，使得能量攻击难度加大。表1给出本文算法与蒙哥马利算法及静态掩盖法的效率对比。

表1　算法效率对比分析

其中，P为消耗的单位能量。

5　结　语

本文通过设计一种随机功耗算法，既能提高模幂运算的安全性，同时还能保证其效率相对较高。该算法能够有效地抵抗计时攻击及能量攻击，在运行效率上，能够提高15%左右；在功耗上能够节省15%左右。该方法便于应用在椭圆曲线公钥密码体制，对所有涉及模幂运算的算法都有一定的借鉴意义。

[1] Rivest R L, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the Acm, 1978, 26(2):96-99.

[2] 韩立东,王小云,许光午. RSA密码系统小CRT解密指数的攻击分析[J]. 中国科学:信息科学,2011,41(2):173-180.

[3] Zou H. An Prime Generating Scheme to Avoid Effectively Common Modulus Attack on RSA[J]. Computer Engineering & Applications, 2004, 40(27):88-91.

[4] 姜正涛,怀进鹏,王育民. RSA推广循环攻击实效性与弱模问题的研究与分析[J]. 通信学报,2009,30(6):70-74.

[5] Kocher P C. Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems[C]//International Cryptology Conference on Advances in Cryptology. Springer-Verlag, 1996:104-113.

[6] Cimato S, Mella S, Susella R. Partial Key Exposure Attacks on RSA with Exponent Blinding[C]//International Conference on E-Business and Telecommunications. Springer International Publishing, 2015:364-385.

[7] Schindler W. Exclusive Exponent Blinding May Not Suffice to Prevent Timing Attacks on RSA[M]//Cryptographic Hardware and Embedded Systems-CHES 2015. Springer Berlin Heidelberg, 2015: 229-247.

[8] Schindler W, Wiemers A. Power attacks in the presence of exponent blinding[J]. Journal of Cryptographic Engineering, 2014, 4(4):213-236.

[9] Menezes A J. Elliptic Curve Public Key Cryptography[J]. International Course on the State of the Art & Evolution of Computer Security & Industrial Cryptography Location Leuven Be Date, 1993(3):76-79.

[10] Kocher P, Jaffe J, Jun B. Differential Power Analysis[C]//International Cryptology Conference on Advances in Cryptology. Springer-Verlag, 1999:388-397.

[11] 任燕婷,乌力吉,李翔宇,等. 抗攻击低功耗RSA处理器设计与实现[J]. 清华大学学报(自然科学版),2016,56(1):1-6.

[12] 陈运,吴震,陈俊,等. 防范边信道攻击的等功耗编码实现算法[J]. 电子科技大学学报,2008,37(2):168-171.

[13] Gebotys C H. A table masking countermeasure for low-energy secure embedded systems[J]. IEEE Transactions on Very Large Scale Integration Systems, 2006, 14(7):740-753.

[14] 陈运,龚耀寰. 大数幂剩余的二进制冗余数Montgomery算法[J]. 电子科技大学学报,2000,29(6):587-590.