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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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