旁路分析原理與方法 第一.二章

1、第一章緒論1密碼學(xué)基礎(chǔ)1.1通信環(huán)境下的密碼系統(tǒng)Alice)圖11理環(huán)境F的密碼系線模眾通過上圖可以清楚地了解通信環(huán)境下的密碼系統(tǒng)主要由明文、密文、密鑰（包括加密密鑰和解密密鑰）、加密算法、解密算法五部分構(gòu)成。發(fā)送者將明文、加密密鑰作為加密算法的輸入得到密文并發(fā)送給接收者，接收者解密密文后得到明文。密碼學(xué)發(fā)展歷程（1）科學(xué)密碼學(xué)的前夜發(fā)展時(shí)期：該時(shí)期的密碼技術(shù)還不是一種科學(xué)，密碼學(xué)專家常憑直覺和信念進(jìn)行密碼設(shè)計(jì)和分析，而不是推理和證明。（2）對稱密碼的早期發(fā)展時(shí)期：Shannon于1949年發(fā)表的保密系統(tǒng)的通信理論使密碼編碼至于堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)上，為對稱密碼學(xué)建立了理論基礎(chǔ)，標(biāo)志著密碼學(xué)學(xué)科的形

2、成。然而對稱密碼算法雙方必須約定使用相同密鑰，密鑰分配只能通過專用安全途徑，密鑰管理開銷很大，對稱密碼在密鑰分配上存在很大困難。（3）現(xiàn)代密碼學(xué)的發(fā)展時(shí)期：1976年Diffie和Hellman發(fā)表密碼編碼學(xué)新方向，提出公鑰密碼的概念。1977年美國制定了數(shù)據(jù)加密標(biāo)準(zhǔn)DES（對稱密碼算法）。（4）應(yīng)用密碼學(xué)的發(fā)展時(shí)期：美國AES征集計(jì)劃歐洲NESSIE征集計(jì)劃歐洲eSTREAM征集計(jì)劃美國SHA-3征集計(jì)劃傳統(tǒng)密碼分析（1）分析假設(shè)：密碼算法的安全性一般遵循Kirchhoffs準(zhǔn)則。根據(jù)Kirchhoffs假設(shè)，密碼系統(tǒng)的安全性應(yīng)依賴于密鑰的保密性，而不是密碼算法的保密性。（2）評估準(zhǔn)則：密碼

3、算法安全性分析評估一般需要從分析復(fù)雜度（數(shù)據(jù)復(fù)雜度、時(shí)間復(fù)雜度、空間復(fù)雜度）、分析結(jié)果來衡量。（3）分析方法：傳統(tǒng)密碼分析方法主要包括強(qiáng)力攻擊和數(shù)學(xué)分析兩種。其中強(qiáng)力攻擊包括密鑰窮舉攻擊、查表攻擊和時(shí)間-空間權(quán)衡攻擊。數(shù)學(xué)分析包括差分密碼分析、線性密碼分析、相關(guān)密碼分析和代數(shù)分析。密碼旁路分析概述攻心（E*）ffl1-2現(xiàn)實(shí)通佶環(huán)境卜的密碼系統(tǒng)模舉密碼算法設(shè)計(jì)的安全性并不等同于密碼芯片實(shí)現(xiàn)的安全性。密碼算法的實(shí)現(xiàn)總是需要依附一個(gè)物理設(shè)備平臺(tái)，即密碼芯片。由芯片的物理特性產(chǎn)生的額外信息泄露稱為旁路泄漏。這些泄露的信息同密碼中間運(yùn)算、中間狀態(tài)數(shù)據(jù)存在一定相關(guān)性，可為密碼分析提供更多信息，利用這些旁

4、路信息進(jìn)行密鑰分析稱為旁路分析。從圖1-2可看出，旁路分析中攻擊者除了可在公開信道上截獲信息，還可觀測加密端的旁路泄漏，然后結(jié)合密碼算法的設(shè)計(jì)細(xì)節(jié)進(jìn)行密鑰分析。發(fā)展歷程（1）萌芽期：瞬態(tài)電磁脈沖輻射大核監(jiān)測技術(shù)研究：貝爾電話公司工程師在進(jìn)行加密電傳終端貝爾電話131-B2調(diào)試時(shí)，發(fā)現(xiàn)電傳終端每加密一個(gè)字母，調(diào)試臺(tái)對面的示波器就會(huì)出現(xiàn)峰值波動(dòng)，利用該峰值泄漏可將加密電傳終端處理的信息轉(zhuǎn)換成明文。進(jìn)一步研究表明:在所有電子設(shè)備上進(jìn)行信息處理時(shí)，都會(huì)產(chǎn)生電磁輻射，并可用于信息的還原。聲音分析技術(shù)研究：1956年，英國情報(bào)部門利用聲音分析手段，執(zhí)行了代號為“咽吞”的計(jì)劃，通過監(jiān)聽手段來竊取密碼機(jī)情報(bào)。

5、（2）提出期：1996年，學(xué)術(shù)界陸續(xù)有研究人員發(fā)現(xiàn)密碼芯片存在旁路泄漏問題，并公開在會(huì)議和期刊上發(fā)表論文，不同類型的密碼旁路泄漏被陸續(xù)發(fā)現(xiàn)并用于密鑰分析。（3）發(fā)展期：衰1-1密碼旁路分析發(fā)展期主要進(jìn)展筆份分僑研克堆展2001分功耗分析方出2002Cache訪2003橫機(jī)分析方法1切、爹道舟爲(wèi)分析方*1撿舟踣分析力法1T*良出2004聲宵舟發(fā)星阿相關(guān)功耗分析力法|45,M*ih2005*機(jī)帳住分析方第域舟踣分析方法的訪対功Cbc計(jì)討分析力汕彼瘦出2006基于務(wù)踣的JavaK代円建自方法E出2007埶一拿功僥勞路分折書公開出版削、代（旁路分析法祓提出2008歐梢和H霰合川莎的労踣分折見WDPAC

6、ontest町心分析力乩（叭勞跆立方體分析力出2009旁路分析評估次釁出仗件木馬旁踣分析方a?M,.代分析方払【期代敬故分析法|阿鼻岀201014用的旁踣分析*聖和方注研究城為研丸熱點(diǎn).分析方怯労為水印方弦1.拽即硬敏廈分析方“Ji.分析方祛1戡楓出旁路分析技術(shù)飛速發(fā)展，各種方法蓬勃產(chǎn)生，旁路分析評估、防御和應(yīng)用得到重視。（4）鼎盛期：旁路信息釆集：類型更多、速度更快、精度更高旁路分析方法：效率提高，并與數(shù)學(xué)分析結(jié)合起來旁路分析防御：走向設(shè)計(jì)方式科學(xué)化、實(shí)現(xiàn)方法靈活化、部署應(yīng)用體系化旁路分析應(yīng)用：廣泛應(yīng)用到新的信息安全領(lǐng)域，分析技術(shù)走向通用化、廣泛化和交叉化基本原理分Alt攻&0WLR31-4

7、AES密碼呀賂分析甌即示倉*&CZJ匸|C5JCTDCKJ旁路泄漏同明文、密文和子密鑰塊具有相關(guān)性，攻擊者可利用一定的分析方法恢復(fù)出子密鑰塊值，最終達(dá)到恢復(fù)主密鑰值的目的。由圖1-4可看出密碼旁路分析可分為兩個(gè)階段：泄漏釆集階段：獲得實(shí)施密鑰分析所需的旁路泄漏泄漏分析階段：利用釆集的旁路泄漏，結(jié)合密碼算法的輸入、輸出和設(shè)計(jì)細(xì)節(jié)恢復(fù)部分密鑰片斷，然后結(jié)合密鑰擴(kuò)展算法設(shè)計(jì)恢復(fù)主密鑰。圖1-4右上部分是攻擊者通過示波器采集的AES執(zhí)行第一輪16次查找S盒操作的功耗曲線，可看出存在16個(gè)明顯的峰值，分別對應(yīng)每次查找S盒操作。發(fā)展動(dòng)因（1）分析對象存在固有脆弱性設(shè)計(jì)安全性不等于實(shí)現(xiàn)安全性密碼系統(tǒng)運(yùn)行會(huì)產(chǎn)

8、生旁路泄漏旁路泄漏同密碼運(yùn)算相關(guān)（2）攻擊者的能力超出預(yù)期（3）測試計(jì)量手段越來越先進(jìn)（4）密碼算法和芯片發(fā)展需要具備旁路分析能力方法分類（1）旁路泄漏采集模式：主動(dòng)分析：攻擊者使用專用設(shè)備主動(dòng)讀取密碼芯片運(yùn)行的中間狀態(tài)比特，并利用密碼芯片故障輸出進(jìn)行密鑰分析。被動(dòng)分析：攻擊者僅使用專用設(shè)備觀測密碼芯片運(yùn)行過程中的旁路泄漏進(jìn)行密鑰分析，并不對密碼芯片的運(yùn)行過程進(jìn)行主動(dòng)干擾。（2）旁路泄漏采集手段：非侵入式分析：攻擊者不需要對密碼芯片接口進(jìn)行破壞，只需要利用專用設(shè)備正常訪問密碼芯片接口，典型的方法包括:計(jì)時(shí)分析、功耗分析、電磁分析半侵入式分析：攻擊者需要使用化學(xué)腐蝕等手段破壞密碼芯片封裝，典型方

9、法包括：激光故障分析侵入式分析：攻擊者需要在半侵入式分析基礎(chǔ)上對密碼芯片進(jìn)行深一步的剖片，并使用探針讀取密碼設(shè)備運(yùn)行過程中的中間狀態(tài)比特，典型方法：探針分析。（3）旁路泄漏信息類型：計(jì)時(shí)分析、探針分析、故障分析、功耗分析、電磁分析、Cache分析，聲音分析（4）旁路泄漏分析方法：簡單旁路分析、差分旁路分析、相關(guān)旁路分析、模板旁路分析、隨機(jī)模型旁路分析、互信息旁路分析、Cache旁路分析、差分故障分析、旁路立方體分析、代數(shù)旁路分析第二章數(shù)學(xué)基礎(chǔ)代數(shù)學(xué)1.1數(shù)論基本概念：模運(yùn)算：用給定整數(shù)n除兩個(gè)整數(shù)a和b所得余數(shù)相同，則稱a,b關(guān)于n同余,記為a=b(modn)除數(shù)：和之前所學(xué)定義相同素?cái)?shù)：在非

10、負(fù)整數(shù)情況下，素?cái)?shù)指只能被1和它本身整除的數(shù)離散對數(shù)：令P=ax(modp),求X的問題稱為離散對數(shù)文題。最大公因子：當(dāng)兩個(gè)數(shù)除了1之外沒有公因子，則兩數(shù)互素。如果兩整數(shù)a和n最大公因子(GCD)等于1,則記為GCD(a,n)=l歐拉函數(shù)：歐拉函數(shù)屮(m)表示比m小且與m互素的正整數(shù)個(gè)數(shù)。其滿足兩個(gè)性質(zhì)：m是素?cái)?shù)時(shí)，屮(m)=m-l;m=pq,且p和q均為素?cái)?shù)時(shí)，有屮(m)=屮(p)Xip(q)=(p-l)(q-l)基本定理：費(fèi)馬定理：如果p是素?cái)?shù)且a是不能被p整除的正整數(shù)，則ap_1=l(modp)歐拉定理：對于任何互素的整數(shù)a和n,有卅(n)=l(modn)中國剩余定理：有時(shí)候在模運(yùn)算時(shí)大

11、數(shù)在運(yùn)算時(shí)比較復(fù)雜，于是可以將大數(shù)分解成小數(shù)的形式進(jìn)行運(yùn)算。1.2代數(shù)群、環(huán)、域的定義：三者從左至右存在包含的關(guān)系，定義條件越來越嚴(yán)苛。群包含一個(gè)集合G和一個(gè)定義在集合元素上的運(yùn)算，環(huán)包含一個(gè)集合和兩個(gè)定義在集合元素上的運(yùn)算，域則是在環(huán)的條件下加入新的條件。有限域和域上的多項(xiàng)式：具有有限個(gè)元素的域，元素的個(gè)數(shù)稱為域的階。域F上的多項(xiàng)式可表示為b(x)=bn_1%n-1+bn_2%n-2+b2%2+b1x+b0式中，x稱為多項(xiàng)式的變元；切WF是多項(xiàng)式的系數(shù)。漢明重量與漢明距離：漢明重量：x向量中非零分量的個(gè)數(shù)；漢明距離：x,y向量的差向量(異或)的漢明重量布爾向量與布爾函數(shù)：布爾向量：在有限域G

12、F中，只有0和1兩個(gè)元素，加法為模2下整數(shù)相加，乘法是模2下整數(shù)相乘，在GF(2)上取值的變量稱為布爾變量。布爾函數(shù)：如果函數(shù)b=0(a)將一個(gè)布爾向量映射為另外一個(gè)布爾向量,則稱為布爾函數(shù)。信息論2.1信息和爛密鑰信息的度量常用不確定性(爛)來進(jìn)行。對于密鑰來說，爛的大小同信息的不確定性成正比。信息的不確定性越大爛越大。自信息：離散隨機(jī)變量X有n個(gè)可能取值和已2,，n。則事件Xf的自信息定義為爛：離散隨機(jī)變量X有n個(gè)可能取值血，i,2,，n。則該隨機(jī)變量X的爛為所有取值的自信息乘以概率之和。聯(lián)合爛：對于兩個(gè)離散變量X和Y,X有n個(gè)可能取值”7,2,，n,Y有m個(gè)可能取值巧，冋2,m,則二者聯(lián)

13、合爛H(X,Y)=-SiS=iP(X=%py=乃)log(P(X=E，Y=乃)條件爛：對于兩個(gè)離散變量X和Y,其條件爛為H(x|y)=-SJtiS=iP(X=%i|Y=y,)log(P(X=%i|y=巧)2.2互信息：互信息：對于兩個(gè)隨機(jī)變量X和Y,互信息l(X;Y)的大小反映了變量X和Y的統(tǒng)計(jì)依存度。l(X;Y)越大，則X和Y之間的統(tǒng)計(jì)關(guān)聯(lián)性越強(qiáng)。l(X;Y)=l(Y;X)=H(X)+H(Y)-H(X/Y)計(jì)算復(fù)雜性算法的計(jì)算復(fù)雜度時(shí)間復(fù)雜度，空間復(fù)雜度問題復(fù)雜度按照求解問題所需的時(shí)間，計(jì)算復(fù)雜性理論可將各種問題分為多類P類問題：可以在多項(xiàng)式時(shí)間內(nèi)求解的問題NP類問題：可以在多項(xiàng)式時(shí)間內(nèi)利用

14、不確定性圖靈機(jī)求解的問題四：概率論1.事件與概率事件、樣本空間：事件是指實(shí)驗(yàn)或觀察的結(jié)果，簡單事件乂稱樣本點(diǎn)，樣本點(diǎn)的全體稱作樣本空間。概率與條件概率:對于一個(gè)事件X,其中的樣本點(diǎn)兀發(fā)生的概率，記為P(X=%J,且滿足n1=1此外，在事件為X的情況下，事件Y發(fā)生概率，即條件概率可記為P(Y|X)=需分布函數(shù)：X是一個(gè)隨機(jī)變量，則F(X)=PX%稱為X的分布函數(shù)。期望與方差期望：隨機(jī)變量X取值的均值E(X)方差：隨機(jī)變量X的取值偏離期望值E(X)的程度偏度：X統(tǒng)計(jì)分布的偏斜方向和程度峰度：衡量X統(tǒng)計(jì)分布的集中程度協(xié)方差：數(shù)學(xué)期望和方差反映隨機(jī)變量自身的分布特征，協(xié)方差表示隨機(jī)變量之間相互關(guān)系的數(shù)

15、值特征。相關(guān)性系數(shù)：用來度量兩個(gè)變量之間線性關(guān)系的方法概率分布正態(tài)分布：對于隨機(jī)變量，如果它的密度函數(shù)服從正態(tài)函數(shù)，則稱該變量服從正態(tài)分布二元正態(tài)分布：對于兩個(gè)變量，其密度函數(shù)服從正態(tài)函數(shù)，則兩個(gè)變量服從二元正態(tài)分布。中心極限定理：當(dāng)樣本數(shù)量足夠大時(shí)，隨機(jī)變量趨于正態(tài)分布五.數(shù)理統(tǒng)計(jì)參數(shù)估計(jì)極大似然估計(jì)：多元高斯分布是正態(tài)分布向更高維的擴(kuò)展，可以通過協(xié)方差矩陣和均值刻畫向量的發(fā)生概率。貝葉斯估計(jì)：在給定訓(xùn)練數(shù)據(jù)D時(shí)，確定假設(shè)空間的最佳假設(shè)。即對預(yù)先統(tǒng)計(jì)結(jié)果的利用。假設(shè)檢驗(yàn)t檢驗(yàn)：分析兩個(gè)不相關(guān)總體樣本的平均值F檢驗(yàn)：用于兩個(gè)和兩個(gè)以上樣本方差差別的顯著性檢驗(yàn)存在問題：對離散對數(shù)的深入理解？如果n滿足a=l(modp)的最小正整數(shù)，假設(shè)OWxvn,記x=La(3),并稱為與a相關(guān)的p的離散對數(shù)。擴(kuò)展：給定一個(gè)質(zhì)數(shù)p和有限域Zp上的一個(gè)本原元a,對Zp上整數(shù)b尋找唯一整數(shù)C,使得aC=b(modP)o如果仔細(xì)選擇p,則認(rèn)為該問題難解，且目前還沒有找到計(jì)算離散對數(shù)問題的多項(xiàng)式時(shí)間算法。歐拉定理證明？方法一：令乙