一種對(duì)RSA-CRT的錯(cuò)誤模攻擊.pdf

1、RSA算法于1977年由Ron Rivest，Adi Shamir和Len Adleman提出，并被廣泛應(yīng)用于加密和數(shù)字簽名等公鑰密碼算法中。RSA的安全性依賴于大數(shù)的因子分解，分解N是最直接的攻擊方法。為了改善RSA的解密速度，一般采用RSA算法的變形RSA-CRT，其解密速度是經(jīng)典RSA的4倍。
　　 1997年，Boneeh，Demillo和Lipton指出RSA-CRT容易受到錯(cuò)誤攻擊的威脅，即假設(shè)攻擊者通過(guò)植入錯(cuò)誤簽名

2、，可以利用錯(cuò)誤簽名和正確簽名的關(guān)系將N進(jìn)行分解。這種攻擊適用于將消息m經(jīng)過(guò)編碼處理的RSA加密算法，比如RSA PKCS＃1 v1.5或者Full-Domain Hash。Seifert于2005年利用RSA公開(kāi)的模N對(duì)RSA進(jìn)行錯(cuò)誤攻擊。此攻擊適用于RSA的數(shù)字簽名，隨后Brier et al提出了密鑰恢復(fù)攻擊，并在文獻(xiàn)[6，7，8，9]中做出改進(jìn)。但后來(lái)改進(jìn)的密鑰恢復(fù)攻擊僅適用于不含CRT的RSA加密算法，而且比Brier etal

3、攻擊需要更多的錯(cuò)誤簽名。
　　 2012年(E)ric Brier,David Naccache,Phong Q.Nguyen和Mehdi Tibouchi[10]利用正交格原理提出了一種新的RSA錯(cuò)誤模攻擊。他們利用恢復(fù)密鑰的方法來(lái)對(duì)RSA-CRT簽名進(jìn)行攻擊，其中攻擊是需要注入的激光技術(shù)來(lái)實(shí)現(xiàn)錯(cuò)誤模的生成。這種攻擊靈活使用了RSA-CRT簽名中的各項(xiàng)參數(shù)，即:σp=μ(m)d mod p,σq=μ(m)d mod q,然后生

4、成RSA-CRT簽名:σ=σp·α+σq·β mod N.利用錯(cuò)誤模注入技術(shù)得到錯(cuò)誤簽名σ'，即:σ'=σp·α+σq·βmod N'.對(duì)生成的兩種簽名σ和σ'使用中國(guó)剩余定理可計(jì)算出:v=σp·α+σq·β mod N· N',通過(guò)簽名對(duì)(σ，σ'）可以構(gòu)造出帶有未知整參數(shù)α，β的多組線性組合。最后利用格的約化算法來(lái)恢復(fù)參數(shù)σp和σq，最終達(dá)到分解N的目的。實(shí)踐證明他們的方法是高效的，假設(shè)敵手能夠獲得5對(duì)正確的簽名與錯(cuò)誤的簽名，利用一

5、臺(tái)標(biāo)準(zhǔn)的計(jì)算機(jī)就可以在幾秒鐘內(nèi)將N進(jìn)行分解。
　　 本文根據(jù)上述的錯(cuò)誤模攻擊提出了新的攻擊RSA-CRT的方法，計(jì)算效率更高，通過(guò)轉(zhuǎn)換上述攻擊中生成的v=σp·α+σq·β∈Z，將v進(jìn)一步變形: v=（σmod p）·α+（σmod q）·β=（σ-p「σ/p」）·α+（σ-q「σ/q」）·β，觀察可知α+β=N+1，因此可得:v=σ·(N+1)-pα「σ/p」-qβ「σ/q」，并引入?yún)?shù)ω=(σ·(N+1)-v）/N，通過(guò)變形

6、可以得到:ω=σ·(N+1)-v/N=pα「σ/p」+qβ「σ/q」.
　　 通過(guò)證明可以得出ω是一個(gè)整數(shù)。最后通過(guò)敵手的假設(shè)對(duì)ω進(jìn)行討論和精確求解，利用二分法求解N的最小素因子min(p，q)，實(shí)現(xiàn)對(duì)大整數(shù)N的分解，最終達(dá)到攻擊RSA-CRT的目的。
　　 本文的攻擊需要對(duì)ω進(jìn)行討論，根據(jù)ω所定義的形式可以獲知，如果σ＜ min(p，q)，那么ω=0;如果σ＞min(p，q)，那么ω＞0。文章針對(duì)ω這一特性可以確定最小

7、素因子的上下限，最多經(jīng)過(guò)log N次嘗試后可以確定出最小素因子。
　　 錯(cuò)誤模N'的有兩種不同的情況，不同的錯(cuò)誤模N'所需要的錯(cuò)誤實(shí)例也是不同的，即一種是錯(cuò)誤N'與初始的N相差一個(gè)未知比特;另一種是錯(cuò)誤N'與初始N的不同要少于最低有效位比特的一半:最低有效位比特的錯(cuò)誤數(shù)量最多不能超過(guò)N長(zhǎng)度的一半。此外，我們假設(shè)攻擊者可以根據(jù)自己的需要向模擬器請(qǐng)求簽名，模擬器亦必須無(wú)條件的回復(fù)攻擊者的簽名請(qǐng)求，這樣，攻擊者可以從回復(fù)的簽名中尋找適