一種改進的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.