一種改進的CRT-RSA防御側(cè)信道攻擊算法

李子木

(海軍駐北京地區(qū)通信軍事代表室，北京 100039)

0 引言

側(cè)信道攻擊技術(shù)(Side Channel Attacks)是一種快速、低成本和可實施的密碼攻擊技術(shù)，可以有效獲取密碼芯片或設(shè)備中的關(guān)鍵數(shù)據(jù)或密鑰，如簡單功耗攻擊(Simple Power Attack，SPA)、差分功耗攻擊(Differential Power Analysis，DPA)和故障攻擊(Fault Attacks，F(xiàn)A)等。文中主要研究了基于中國剩余定理(CRT)的RSA簽名算法，稱為CRT-RSA算法。由于CRT-RSA算法可以極大的提高RSA簽名的運算速度而被廣泛應(yīng)用。然而，CRT-RSA算法卻容易受到 SPA、DPA［1］和 FA［2］的攻擊。

為了防御功耗攻擊和故障攻擊，許多安全防御算法被提出來［3－5］。然而，這些算法又逐漸被一些新的攻擊技術(shù)或故障注入技術(shù)所攻破。最近，Ha等人提出了一種新的CRT-RSA算法可抵抗目前已知的所有攻擊［7］，稱之為 Ha算法。研究發(fā)現(xiàn)，Ha算法在使用中國剩余定理(CRT)過程中仍存在降低效率的模逆運算?；诿魑难谏w方法，提出了一種改進的安全CRT-RSA防御算法，該算法可抵抗現(xiàn)有已知功耗攻擊(SPA、DPA、RDA和(N－1)攻擊)及故障攻擊(FA)且不存在降低計算效率的模逆運算。

1 CRT-RSA算法

RSA是著名的公鑰密碼算法，它使用的模數(shù)N為2個大素數(shù)的乘積即N=p·q，指數(shù)e和d必須選定滿足ed≡1mod(p－1)(q－1)條件，RSA密鑰由公鑰(N，e)和私鑰d組成。對給定消息m進行簽名，執(zhí)行運算S≡mdmodN，其中S是對m的簽名，驗證簽名只需執(zhí)行運算Se≡mmodN。攻擊者若想獲取私鑰d，則必須首先分解出大數(shù)N的素因子p和q，而進行大數(shù)分解是十分困難的。CRT-RSA算法中，首先計算Sp≡mdpmodp和Sq≡mdqmodq，其中dp≡dmod(p－1)和dq≡dmod(q－1)，簽名S可通過Ganer算法計算得到:

式中，iq≡q－1modp應(yīng)預(yù)先計算并存儲以減少重復(fù)計算的代價。CRT-RSA算法的運算速率約是只單獨使用RSA簽名運算速率的1/4，這也正是其在有限系統(tǒng)資源環(huán)境(如智能卡芯片)中得到廣泛應(yīng)用的原因。

2 故障攻擊

故障攻擊指攻擊者使用物理方法(如電磁輻射和激光注入等)干擾密碼芯片的正常工作，使其在運算過程中得到錯誤的結(jié)果，并依據(jù)錯誤結(jié)果有效推算出密碼系統(tǒng)的密鑰信息。

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

Lenstra改進了上述攻擊方法，指出如果已知明文m，攻擊者只需一個與該明文相對應(yīng)的錯誤簽名結(jié)果就足夠破解出密鑰。設(shè)e是簽名公鑰，則有g(shù)cd((m－S－e)mod N，N)=q，因此成功分解模數(shù)N。同理，當Sp計算正確，Sq計算錯誤時，可得到素因子p。

3 現(xiàn)有防御措施

為防止故障攻擊，國內(nèi)外設(shè)計了很多防御算法，其中最著名的防御算法由Shamir設(shè)計，他通過使用隨機素數(shù) 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)，在輸出簽名結(jié)果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年，F(xiàn)umaroli和 Vigilant將 Giraud的算法改進提出了一種指數(shù)算法，可抵抗 SPA、DPA和FA［17］。Kim和Quisquater指出FV的方法不能檢驗隨機數(shù)r發(fā)生在模平方運算過程中出現(xiàn)的錯誤［18］，另一方面，其算法使用隨機數(shù)r掩蓋消息m后進行指數(shù)運算，但這樣的指數(shù)算法不能抵抗(N－1)攻擊［19］或者 2－torsion攻擊［20］。但 KQ 算法中需要計算r－1，這需要浪費更多的內(nèi)存空間和時間。

4 改進的CRT-RSA算法

為解決第3節(jié)中的問題，基于明文掩蓋方法，提出了一種改進的安全CRT-RSA防御算法。該算法與現(xiàn)有防御方案相比較，不僅可以抵抗現(xiàn)有各種攻擊，而且在不增加額外寄存器數(shù)量情況下有效減少了運算時間。明文掩蓋算法如下:

其中r為隨機素數(shù)，假定m、r和N均為n bit長正整數(shù)，c為較小的隨機數(shù)0＜c＜28。明文掩蓋算法主要思想是通過計算 (mr)t·rs·(mr)2n－1代替直接計算md且不引入模逆運算。

下面，設(shè)計抵抗FA的安全CRT-RSA算法，計算dp=d mod(p－1)與dq=d mod(q－1)和ep=e mod(p－1)與eq=e mod(q－1)，預(yù)計算并存儲ip=p－1modq和iq=q－1modp。安全CRT-RSA 算法如下:

如果在計算過程中無故障錯誤發(fā)生，則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 抗功耗攻擊

明文掩蓋算法在循環(huán)運算時每做一步模平方運算就做一步模乘運算并且沒有直接使用密鑰d，因此它可以抵抗SPA。而對于DPA，算法過程中的中間數(shù)據(jù)始終被隨機數(shù)r掩蓋，攻擊者不可能使用DPA對本算法進行攻擊［20］。

攻擊者可分別輸入2個特定消息m和m2得到2條不同的功耗曲線，進而進行差分功耗分析，這種攻擊方法叫做平方攻擊(Doubling Analysis，DA)［21］。然而在運算過程中引入了隨機數(shù)使得功耗曲線被隨機化，所以DA并適用于該算法。即使攻擊者使用選定的消息(N－1)代替消息m進行攻擊(N－1)攻擊，同樣會因為引入了隨機數(shù)r而失效。

5.2 故障攻擊

設(shè)Sp或Sq其中之一發(fā)生了錯誤，則ci不再為1，攻擊者得到錯誤簽名·δ，其中δ為ZN中的隨機數(shù)。則 (S －·δ)或 (·δ)e－ m)中不包含素因子 p或q，因此攻擊者不能從gcd((S－S－·δ)modN，N)或 gcd(((·δ)e－ m)modN，N)中分解出 p或q。對于 p，q－1modp，d，dp之一發(fā)生錯誤的情況與上述類似。

5.3 效率分析

表1顯示了本文設(shè)計的安全CRT-RSA算法與其他3個代表算法在安全性、寄存器數(shù)量和計算復(fù)雜度方面的對比情況。設(shè)h表示模數(shù)p或q的比特長度，b表示ti的比特長度。新的CRT-RSA算法需要調(diào)用2次明文掩蓋算法，每次需要進行h次模乘和h次2個h bit數(shù)的模平方，因此總的計算復(fù)雜度為2·2h3。另外，該算法不需要增加額外的寄存器數(shù)量和不存在模逆運算。

表1 與其他算法對比結(jié)果

6 結(jié)束語

近年來，出現(xiàn)了很多針對CRT-RSA算法的功耗攻擊和故障攻擊技術(shù)，同時許多不同的防御方法也相繼被提出，但這些防御方法要么不能抵抗某些改進的攻擊技術(shù)，例如RDA和(N－1)攻擊，要么具有很高的算法復(fù)雜度?；诿魑难谏w方法，提出的安全CRT-RSA防御算法不但可以抵抗現(xiàn)有已知功耗攻擊(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，F(xiàn)ISCHER 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.