計算機網(wǎng)絡(luò)安全與管理：第四講

網(wǎng)絡(luò)安全與管理

第四講本講內(nèi)容塊加密模式補充數(shù)論基礎(chǔ)公鑰密碼學(xué)應(yīng)用方式對于塊定長，密鑰長度定長的快加密算法實際應(yīng)用當(dāng)中常常需要加密任意長的數(shù)據(jù)ANSIX3.106-1983中定義了四種應(yīng)用方式后來發(fā)展為5類應(yīng)用于像AES&DES的算法具有塊模式與流模式電子密碼本

ElectronicCodebookBook(ECB)明文被分塊獨立加密，明文塊與密文塊具有一一對應(yīng)的關(guān)系。就像密碼本（記得上節(jié)課提到的特大字符的概念嗎）Ci=DESK1(Pi)用于單一值的安全傳輸ECB的優(yōu)缺點明文塊的重復(fù)會體現(xiàn)在密文當(dāng)中，當(dāng)報文量很小時沒什么，但當(dāng)報文量大的時候，特別是報文具備結(jié)構(gòu)性特征：比如總是以某些事先規(guī)定好的域開始。那么分析者有可能獲得很多可供分析的明文-密文對。結(jié)合64bit的劃分，給篡改，重排帶來隱患應(yīng)用范圍：小規(guī)模數(shù)據(jù)傳輸（幾塊）密碼分組鏈接方式

CipherBlockChaining(CBC)消息經(jīng)過分塊通過加密操作將分塊鏈接起來通過將前一個密文塊與當(dāng)前明文塊連接（異或）因而得名步驟開始時利用一個初始值Ci=DESK1(PiXORCi-1)C-1=IV

用于：大量數(shù)據(jù)的加密，鑒別（http，email,ftp)CipherBlockChaining(CBC)消息填充

MessagePadding消息最后可能需要處理一個小分組，這是需要進行消息填充填充方法可以是填入空值，也可以是填入填充值。Eg：[b1b2b300005]就是說8個字節(jié)前面三個是消息，后面五個是填充這樣的填充有可能需要一個完整的塊某些更加深奧的方法可能避免該塊CBC的優(yōu)缺點每一塊都依賴于其前面所有的塊對一塊的改變可影響其后所有初始向量IV需要雙方知道若明文傳輸，攻擊者有可能篡改用固定文字（EFTPOS）先用ECB加密傳。密碼反饋模式

CipherFeedBack(CFB)消息被作為一個數(shù)據(jù)流對待添加到加密器的后端結(jié)果被反饋在后面的過程中（由此得名）標(biāo)準允許任意長度的比特數(shù)。CFB-1,CFB-8,CFB-64,CFB-128etcCi=PiXORDESK1(Ci-1)C-1=IV

用于：流數(shù)據(jù)加密，鑒別CFBCFB優(yōu)缺點適應(yīng)于數(shù)據(jù)一比特或字節(jié)到達最常見的流模式每過n比特需要等待塊加密加密過程應(yīng)用于兩端錯誤影響其后多個塊輸出反饋模式

OutputFeedBack(OFB)消息被作為數(shù)據(jù)流對待加密結(jié)果被加到消息上輸出的是接下來的反饋反饋獨立于消息Ci=PiXOROi

Oi=DESK1(Oi-1)O-1=IV用于噪聲信道優(yōu)缺點比特錯誤不會傳播易受報文篡改攻擊雙方應(yīng)保持同步目前用的就是64bit與128bit的Counter(CTR)一個新的方式與OFT相似但是加密的是對應(yīng)值（countervalue）而不是反饋值每個明文塊都要有不同的密鑰與對應(yīng)值Ci=PiXOROi

Oi=DESK1(i)用于高速網(wǎng)絡(luò)加密傳播優(yōu)缺點高效可并行可預(yù)處理爆發(fā)性高速連接隨機存取加密塊可證安全需保證密鑰與對應(yīng)值不復(fù)用流加密將報文作為數(shù)據(jù)流處理有一個偽隨機密鑰流通過XOR操作與原文按位復(fù)合隨機的密鑰流完全破壞了報文的統(tǒng)計特性：Ci=MiXORStreamKeyi

不可重用StreamCipherStructure特點設(shè)計準則應(yīng)該滿足：長時期的不重復(fù)較強的統(tǒng)計隨機性依賴于足夠大的密鑰較大的線性復(fù)雜度設(shè)計恰當(dāng)?shù)脑捘苓_到不亞于塊加密的效果簡便高速RC4RonRivest設(shè)計，簡單高效可變密鑰長度，面向字節(jié)的廣泛應(yīng)用（ssl，wep）密鑰構(gòu)成對8比特數(shù)據(jù)的置換每次一個字節(jié)將報文進行置換亂排方案

開始由一個數(shù)組S：0，。。。，255利用密鑰進行混洗S構(gòu)成了初始狀態(tài)fori=0to255doS[i]=iT[i]=K[imodkeylen])j=0fori=0to255doj=(j+S[i]+T[i])(mod256)swap(S[i],S[j])RC4加密加密過程繼續(xù)混洗數(shù)組通過混洗，置換等操作取出子密鑰按字節(jié)加密i=j=0foreachmessagebyteMii=(i+1)(mod256)j=(j+S[i])(mod256)swap(S[i],S[j])t=(S[i]+S[j])(mod256)Ci=MiXORS[t]安全性對已知攻擊方式抵御較好很好的非線性不可重用密鑰WEP的應(yīng)用問題群一個元素的集合對于定義的運算封閉遵從結(jié)合律：(a.b).c=a.(b.c)

由單位元e：e.a=a.e=a

有逆元：a-1: a.a-1=e如果還遵從交換律：a.b=b.a

則我們稱該群為阿貝爾群（交換群）abeliangroup循環(huán)群定義冪運算為群上運算的重復(fù)疊加例：a3=a.a.a且有單位元e=a0我們說一個群是循環(huán)的就是指對該群中的任意元素均可表示為某一固定元素的冪ieb=

ak

對某個a

與與任意一個b在群中。其中a稱為該群的生成元環(huán)集合上定義了兩種操作（乘和加）對于加法運算是一個阿貝爾群對于乘法運算有是封閉的滿足結(jié)合律具有對加運算符合分配率：a(b+c)=ab+ac若對乘法具有可交換性則稱為交換環(huán)若對乘法運算有單位元但無零因子，則稱為整環(huán)域域作為定義了兩中運算的集合具有對于加法是阿貝爾群對于乘法是阿貝爾群（忽略0）是一個環(huán)模運算定義“amodn”表示用n去除a得到的余數(shù)用“a=bmodn”表示a與b模n具有相同的余數(shù)對于一個數(shù)a通?？梢员硎緸閍=qn+r稱r為余數(shù)（余數(shù)通常取最小的正數(shù)）模運算的性質(zhì)模運算我們在整數(shù)群上定義模運算

Zn={0,1,…,n-1}構(gòu)成了一個加法交換群具有乘法單位元具有下面的性質(zhì)：if(a+b)=(a+c)modn thenb=cmodnbutif(a.b)=(a.c)modn thenb=cmodn當(dāng)且僅當(dāng)a與n互質(zhì)例如：出現(xiàn)這種情況的原因是當(dāng)有公因數(shù)時不會產(chǎn)生完整的余數(shù)集合最大公約數(shù)gcd該問題是數(shù)論中的一個普便問題GCD(a,b)表示能同時整除a與b的數(shù)中最大的一個當(dāng)除1外不存在其它公因式時稱作互質(zhì)EuclideanAlgorithm該算法是一個很有效的計算最大公約數(shù)的算法利用到了GCD(a,b)=GCD(b,amodb)

EUCLID(a,b)1.A=a;B=b2.ifB=0returnA=gcd(a,b)3.R=AmodB4.A=B5.B=R6.goto2

例1970=1x1066+904 gcd(1066,904)1066=1x904+162 gcd(904,162)904=5x162+94 gcd(162,94)162=1x94+68 gcd(94,68)94=1x68+26 gcd(68,26)68=2x26+16 gcd(26,16)26=1x16+10 gcd(16,10)16=1x10+6 gcd(10,6)10=1x6+4 gcd(6,4)6=1x4+2 gcd(4,2)4=2x2+0 gcd(2,0)練習(xí)：gcd（2152，764）迦羅華域（有限域）

GaloisFields有限域理論在密碼學(xué)中具有重要作用元素數(shù)為某一個素數(shù)的n次方這樣的域被稱為有限域（迦羅華域）記為GF(pn)經(jīng)常用到的有：GF(p)GF(2n)GaloisFieldsGF(p)GF(p)是{0,1,…,p-1}的集合，其上定義了模p的算術(shù)運算構(gòu)成了一個有限域因為乘法運算有逆元其上可以進行加減乘除運算GF(7)Example012345600000000101234562024613530362514404152635053164260654321FindingInversesEXTENDEDEUCLID(m,b)1. (A1,A2,A3)=(1,0,m); (B1,B2,B3)=(0,1,b)2.ifB3=0 returnA3=gcd(m,b);noinverse3.ifB3=1 returnB3=gcd(m,b);B2=b–1modm4.Q=A3divB35.(T1,T2,T3)=(A1–QB1,A2–QB2,A3–QB3)6.(A1,A2,A3)=(B1,B2,B3)7.(B1,B2,B3)=(T1,T2,T3)8.goto2練習(xí)：550在1769上的逆Inverseof550inGF(1759)QA1A2A3B1B2B3—101759015503015501–310951–3109–516521–5165106–33941106–3394–1113551多項式算數(shù)可以使用多項式運算

f(x)=anxn+an-1xn-1+…+a1x+a0=∑aixinb.并不關(guān)心x的值x作為不確定的值可以有若干可變的選擇原始多項式運算modp多項式運算modp與modm(x)多項式運算原始多項式算數(shù)可以有加，減，乘eg取f(x)=x3+x2+2g(x)=x2–x+1f(x)+g(x)=x3+2x2–x+3f(x)–g(x)=x3+x+1f(x)xg(x)=x5+3x2–2x+2模系數(shù)的多項式運算在計算系數(shù)的時候模某個值構(gòu)成一個多項式環(huán)可以模任意的素數(shù)更為關(guān)心的是mod2的運算ie所有的系數(shù)為0或1eg.letf(x)=x3+x2andg(x)=x2+x+1 f(x)+g(x)=x3+x+1 f(x)xg(x)=x5+x2多項式除法可以把任意多項式寫成如下形式:f(x)=q(x)g(x)+r(x)可以把r(x)作為一個余項r(x)=f(x)modg(x)如果沒有余項說g(x)整除f(x)如果g(x)沒有除了1和它自身以外的因子則稱其為不可歸約多項式或（素）多項式算數(shù)模和不可約多項式構(gòu)成了一個域多項式最大公約數(shù)可以找到多項式的最大公約數(shù)c(x)=GCD(a(x),b(x))如果c(x)isthepolyofgreatestdegreewhichdividesbotha(x),b(x)可以通過歐幾里得算法求出: EUCLID[a(x),b(x)]

1.A(x)=a(x);B(x)=b(x) 2.ifB(x)=0returnA(x)=gcd[a(x),b(x)] 3.R(x)=A(x)modB(x) 4.A(x)¨B(x) 5.B(x)¨R(x) 6.goto2模多項式算數(shù)可以在域GF(2n)中運算多項式系數(shù)都模2次數(shù)小于n因此需要利用一個次數(shù)為n的不可歸約多項式為模進行簡化(僅對乘運算)構(gòu)成一個有限域總能找到相應(yīng)的逆元可以利用擴展的歐幾里得求逆算法尋找ExampleGF(23)計算的考量因為系數(shù)是0或者1,可以把任意的比特串轉(zhuǎn)化為多項式形式加法成為這樣比特串的XOR運算乘法是shift&XOR模運算通過將最高次冪替換為不可歸約多項式的余項獲得(alsoshift&XOR)ComputationalExampleinGF(23)have(x2+1)is1012&(x2+x+1)is1112soadditionis(x2+1)+(x2+x+1)=x101XOR111=0102andmultiplicationis(x+1).(x2+1)=x.(x2+1)+1.(x2+1) =x3+x+x2+1=x3+x2+x+1011.101=(101)<<1XOR(101)<<0= 1010XOR101=11112

polynomialmoduloreduction(getq(x)&r(x))is(x3+x2+x+1)mod(x3+x+1)=1.(x3+x+1)+(x2)=x21111mod1011=1111XOR1011=01002UsingaGeneratorequivalentdefinitionofafinitefieldageneratorgisanelementwhosepowersgenerateallnon-zeroelementsinFhave0,g0,g1,…,gq-2cancreategeneratorfromrootoftheirreduciblepolynomialthenimplementmultiplicationbyaddingexponentsofgeneratorAES起源很明顯DES需要被改進具有理論的攻擊方式加以破解窮舉密鑰搜索攻擊示范可以使用Triple-DES–但是速度較慢而且分塊較小USNIST1997提出了對加密器的征求98年六月挑選了15個算法99年8月進入最后候選2000年10月Rijndael獲選為AES200110月發(fā)布為FIPS（theFederalInformationProcessingStandards,(美國)聯(lián)邦信息處理標(biāo)準）PUB197AES需求對稱塊加密128-bit數(shù)據(jù),128/192/256-bit密鑰相比于Triple-DES更加快速與安全實際應(yīng)用20-30年(+實際應(yīng)用)提供了完整的規(guī)范與設(shè)計細節(jié)

同時具有C&Java實現(xiàn)NIST已經(jīng)解密了所有提交的和非機密的分析AES評估標(biāo)準初始標(biāo)準:安全性

–實際密碼分析的的效果成本

–依據(jù)計算效率算法與實現(xiàn)的性能最終標(biāo)準一般安全性軟硬件實現(xiàn)對于實施的攻擊靈活性

(inen/decrypt,keying,otherfactors)AESShortlist經(jīng)過測試與評估,99年8月提出的shortlist:MARS(IBM)-complex,fast,highsecuritymarginRC6(USA)-v.simple,v.fast,lowsecuritymarginRijndael(Belgium)-clean,fast,goodsecuritymarginSerpent(Euro)-slow,clean,v.highsecuritymarginTwofish(USA)-complex,v.fast,highsecuritymargin然后對其進行更進一步的analysis&comment在算法中進行對比復(fù)雜論變換與簡單變換現(xiàn)有加密器與新標(biāo)準TheAES加密器-Rijndael由比利時Rijmen-Daemen設(shè)計有128/192/256bit密鑰,128bit數(shù)據(jù)一個勝于feistel加密器的迭代把數(shù)據(jù)作為4字節(jié)4列的塊進行處理在每一輪對整個數(shù)據(jù)塊進行操作設(shè)計以達到:抵抗已知攻擊在許多CPUs上的速度與代碼的緊致設(shè)計的簡明Rijndael4列4個字節(jié)的數(shù)據(jù)塊作為statekey被擴展為字符數(shù)組在9/11/13輪中state做下面變化:逐字節(jié)替代(1S-box用在每一個字節(jié))行移位(permutebytesbetweengroups/columns)列混淆(subsusingmatrixmultipyofgroups)加輪密鑰(將輪密鑰與stateXOR)可以看做交替的使用輪密鑰XOR與對數(shù)據(jù)字節(jié)進行擾亂的操作XORkey需要初始化操作&最后一輪只有三步變化可以采用高速的查表操作實現(xiàn)RijndaelByteSubstitution對每個字節(jié)進行簡單的替代操作使用一個16x16字節(jié)的表，其中包含了256個8bit值的置換每個state的字節(jié)通過查表左4bits的行號與右4bit的列號替代eg.byte{95}被第

9行第

5列的{2A}替代S-box的構(gòu)造利用了

GF(28)上值的變換被設(shè)計來抵抗已知的攻擊ByteSubstitution行移位

對行進行循環(huán)移位操作1strow不變2ndrow左移一個字節(jié)3rdrow左移兩個字節(jié)4throw左移三個字節(jié)解密逆操作使用右移相應(yīng)字節(jié)的方式實現(xiàn)由于

state是按照列進行操作的,這一步在列之間進行了字節(jié)置換操作ShiftRows列混洗每一列均單獨處理each每個字節(jié)均由一個與其同列的4個字節(jié)相關(guān)值替代使用GF(28)上的矩陣乘運算使用的“素”多項式m(x)=x8+x4+x3+x+1MixColumnsMixColumns可以把每一列表示為4個等式以獲得每一列的新的字節(jié)解密需要使用逆矩陣使用了大系數(shù),所以有一點難有另一種描述方式

每一列是一個4次多項式使用GF(28)上的系數(shù)多項式乘的模為(x4+1)加輪密鑰XORstate使用

128-bits的輪密鑰再一次以列為單位操作(通過一系列以字節(jié)