一种改进的CRT-RSA防御侧信道攻击算法

李子木

(海军驻北京地区通信军事代表室，北京 100039)

0 引言

侧信道攻击技术(Side Channel Attacks)是一种快速、低成本和可实施的密码攻击技术，可以有效获取密码芯片或设备中的关键数据或密钥，如简单功耗攻击(Simple Power Attack，SPA)、差分功耗攻击(Differential Power Analysis，DPA)和故障攻击(Fault Attacks，FA)等。文中主要研究了基于中国剩余定理(CRT)的RSA签名算法，称为CRT-RSA算法。由于CRT-RSA算法可以极大的提高RSA签名的运算速度而被广泛应用。然而，CRT-RSA算法却容易受到 SPA、DPA［1］和 FA［2］的攻击。

为了防御功耗攻击和故障攻击，许多安全防御算法被提出来［3－5］。然而，这些算法又逐渐被一些新的攻击技术或故障注入技术所攻破。最近，Ha等人提出了一种新的CRT-RSA算法可抵抗目前已知的所有攻击［7］，称之为 Ha算法。研究发现，Ha算法在使用中国剩余定理(CRT)过程中仍存在降低效率的模逆运算。基于明文掩盖方法，提出了一种改进的安全CRT-RSA防御算法，该算法可抵抗现有已知功耗攻击(SPA、DPA、RDA和(N－1)攻击)及故障攻击(FA)且不存在降低计算效率的模逆运算。

1 CRT-RSA算法

RSA是著名的公钥密码算法，它使用的模数N为2个大素数的乘积即N=p·q，指数e和d必须选定满足ed≡1mod(p－1)(q－1)条件，RSA密钥由公钥(N，e)和私钥d组成。对给定消息m进行签名，执行运算S≡mdmodN，其中S是对m的签名，验证签名只需执行运算Se≡mmodN。攻击者若想获取私钥d，则必须首先分解出大数N的素因子p和q，而进行大数分解是十分困难的。CRT-RSA算法中，首先计算Sp≡mdpmodp和Sq≡mdqmodq，其中dp≡dmod(p－1)和dq≡dmod(q－1)，签名S可通过Ganer算法计算得到:

式中，iq≡q－1modp应预先计算并存储以减少重复计算的代价。CRT-RSA算法的运算速率约是只单独使用RSA签名运算速率的1/4，这也正是其在有限系统资源环境(如智能卡芯片)中得到广泛应用的原因。

2 故障攻击

故障攻击指攻击者使用物理方法(如电磁辐射和激光注入等)干扰密码芯片的正常工作，使其在运算过程中得到错误的结果，并依据错误结果有效推算出密码系统的密钥信息。

通过下面公式可成功分解N。

Lenstra改进了上述攻击方法，指出如果已知明文m，攻击者只需一个与该明文相对应的错误签名结果就足够破解出密钥。设e是签名公钥，则有gcd((m－S－e)mod N，N)=q，因此成功分解模数N。同理，当Sp计算正确，Sq计算错误时，可得到素因子p。

3 现有防御措施

为防止故障攻击，国内外设计了很多防御算法，其中最著名的防御算法由Shamir设计，他通过使用随机素数 r计算 p'=p·r和 q'=q·r，Sp'≡mdpmodp'和Sq'≡mdqmodq'，其中dp'≡d mod(p－1)(r－1)和dq'≡d mod(q－1)(r－1)，在输出签名结果S前，检验Sp'≡Sq'mod r是否成立。但这种方法在iq出错时检测失败且所有基于Shamir思想的防御方法都被认为是不完善的［11］。

Yen等人提出了一种采用错误信息扩散的防御算法［12］，然而他们的方法被证明面对其他故障攻击时是不安全的［13］。2005年，Giraud提出了一种基于Montgomery Ladder的防御算法［14，15］，该方法可以抵抗SPA和FA，但不能抵抗SPA的另一变种RDA(Relative Doubling Attack)［16］。

2007年，Fumaroli和 Vigilant将 Giraud的算法改进提出了一种指数算法，可抵抗 SPA、DPA和FA［17］。Kim和Quisquater指出FV的方法不能检验随机数r发生在模平方运算过程中出现的错误［18］，另一方面，其算法使用随机数r掩盖消息m后进行指数运算，但这样的指数算法不能抵抗(N－1)攻击［19］或者 2－torsion攻击［20］。但 KQ 算法中需要计算r－1，这需要浪费更多的内存空间和时间。

4 改进的CRT-RSA算法

为解决第3节中的问题，基于明文掩盖方法，提出了一种改进的安全CRT-RSA防御算法。该算法与现有防御方案相比较，不仅可以抵抗现有各种攻击，而且在不增加额外寄存器数量情况下有效减少了运算时间。明文掩盖算法如下:

其中r为随机素数，假定m、r和N均为n bit长正整数，c为较小的随机数0＜c＜28。明文掩盖算法主要思想是通过计算 (mr)t·rs·(mr)2n－1代替直接计算md且不引入模逆运算。

下面，设计抵抗FA的安全CRT-RSA算法，计算dp=d mod(p－1)与dq=d mod(q－1)和ep=e mod(p－1)与eq=e mod(q－1)，预计算并存储ip=p－1modq和iq=q－1modp。安全CRT-RSA 算法如下:

如果在计算过程中无故障错误发生，则Sp=mdp· r－c和 Sq= mdq· r－c，因 此 在 步 骤 ④ 中mrc(φ(p)－ep)=S*epmodp 且 mrc(φ(q)－eq)=S*eqmodq ，所以c1=c2=1，最后输出签名 S=S*·rc=mdmodN。

5 安全性分析

5.1 抗功耗攻击

明文掩盖算法在循环运算时每做一步模平方运算就做一步模乘运算并且没有直接使用密钥d，因此它可以抵抗SPA。而对于DPA，算法过程中的中间数据始终被随机数r掩盖，攻击者不可能使用DPA对本算法进行攻击［20］。

攻击者可分别输入2个特定消息m和m2得到2条不同的功耗曲线，进而进行差分功耗分析，这种攻击方法叫做平方攻击(Doubling Analysis，DA)［21］。然而在运算过程中引入了随机数使得功耗曲线被随机化，所以DA并适用于该算法。即使攻击者使用选定的消息(N－1)代替消息m进行攻击(N－1)攻击，同样会因为引入了随机数r而失效。

5.2 故障攻击

设Sp或Sq其中之一发生了错误，则ci不再为1，攻击者得到错误签名·δ，其中δ为ZN中的随机数。则 (S －·δ)或 (·δ)e－ m)中不包含素因子 p或q，因此攻击者不能从gcd((S－S－·δ)modN，N)或 gcd(((·δ)e－ m)modN，N)中分解出 p或q。对于 p，q－1modp，d，dp之一发生错误的情况与上述类似。

5.3 效率分析

表1显示了本文设计的安全CRT-RSA算法与其他3个代表算法在安全性、寄存器数量和计算复杂度方面的对比情况。设h表示模数p或q的比特长度，b表示ti的比特长度。新的CRT-RSA算法需要调用2次明文掩盖算法，每次需要进行h次模乘和h次2个h bit数的模平方，因此总的计算复杂度为2·2h3。另外，该算法不需要增加额外的寄存器数量和不存在模逆运算。

表1 与其他算法对比结果

6 结束语

近年来，出现了很多针对CRT-RSA算法的功耗攻击和故障攻击技术，同时许多不同的防御方法也相继被提出，但这些防御方法要么不能抵抗某些改进的攻击技术，例如RDA和(N－1)攻击，要么具有很高的算法复杂度。基于明文掩盖方法，提出的安全CRT-RSA防御算法不但可以抵抗现有已知功耗攻击(SPA、DPA、RDA及(N－1)攻击)和故障攻击(FA)，而且不存在降低计算效率的模逆运算，从而更加高效与实用。

［1］KOCHER P，JAFFE J，JUN B.Differential power analysis［P］.USA:US 7599488 B2，1999.

［2］JOYE M，LENSTRA A， QUISQUATER J.Chinese remaindering based cryptosystems in the presence of faults Journal of Cryptology［J］.1999，12(4):241 －245.

［3］AUMULLER C，BIER P，FISCHER W，et al.Fault Attacks on RSA with CRT:Concreteresults and Practical Countermeasures［J］. Cryptographic Hardware and Embedded Systems-CHES 2002，2002，252:3260 －275.

［4］MAMIYA H，MIYAJIA，MORIMOTO H.Efficient Countermeasure Against RPA， DPA， and SPA，Cryptographic Hardware and Embedded Systems-CHES 2004:343－356.

［5］BLOMER J，OTTO M，SEIFERT J P.A New CRTRSA Algorithm Secure Against Bellcore Attacks［C］//10th ACM ConferenceonComputerandCommunications Security，2003:311 －320.

［6］KIM C，HA J，KIM S H，et al，A Secure and Practical CRT-Based RSA to Resist Side Channel Attacks［J］.ICCSA ’04，2004:150 －158.

［7］HA J，JUN C，PARK J，et al.A new CRT-RSA Scheme Resistant to Power Analysis and Fault Attacks［C］//Third 2008 International Conference on Convergence and Hyhid Information Technology，2008:351 －356.

［8］BONEH D，DEMILLO R A，LIPTION R J.One the Important of Checking Cryptographic Protocols for Faults［J］.Advances in Cryptology-Eurocrypt’97，1997:37 －51.

［9］LENSTRA AK.Memo on RSA Signature Generation in the Presence of Faults［R］，1996:515 －528.

［10］SHAMIR A.Improved Method and Apparatusfor Protecting Public Key Schemes from Timing and Fault Attacks［P］.US Patent: 7587044，1999.

［11］YEN S，MOON S，ANDHA J.Permanent Fault Attack on the Parameters of RSA with CRT［J］.ACISP ’03，2003:285－296.

［12］YEN S，KIM S，LIM S，et al.RSA Speedup with Residue Number System Immune Against Hardware Fault Cryptanalysis［J］.ICISC ’01，2001:397-413.

［13］YEN S，KIM D，ANDMOON S.Cryptanalysis of Two Protocols for RSA with CRT based on Fault Infection［J］.FDTC ’06，2006:53 －61.

［14］GIRAUD C.Fault Resistant RSA Implementation［J］.FDTC ’05，2005:142 －151.

［15］JOYE M，YEN S.The Montgomery powering ladder［J］.International Association for Cryptologic Research 2002:291－302.

［16］YEN S，KO L，MOON S，et al.Relative Doubling Attack Against Montgomery Ladder［J］.ICISC’05，2005:117 －128.

［17］FUMAROLI F，VIGILANT D.Blinded fault resistant exponentiation［C］//FDTC ’06，2006:62 －70.

［18］KIM C，QUISQUATER J.How Can We Overcome both Side Channel Analysis and Fault Attacks on RSA－CRT［C］//FDTC ’07，2007:21 －29.

［19］YEN S，LIEN W，MOON S，et al.Power Analysis by Exploiting Chosen Message and InternalCollisions-Vulnerability of Checking Mechanism for RSA Decryption［C］//Mycrypt’05，2005:183 －195.

［20］HA J，PARK J，MOON S，etal.ProvablySecure Countermeasure Resistant to Several Types of Power Attack for ECC［J］.WISA ’07，2007:333 －344.

［21］FOUQUE P，VALETTE F.The Doubling Attack-Why Upwards is Better than Downwards［J］.CHES’03，2001:269－280.