版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、,1,數(shù)論基礎(chǔ)及對(duì)稱加密算法,,,2,提綱,數(shù)論基礎(chǔ)加密系統(tǒng)中常用的數(shù)論知識(shí)復(fù)雜性理論簡(jiǎn)介對(duì)稱加密算法對(duì)稱密碼體制模型流密碼分組密碼DESRijndael密碼體制(AES加密算法)KASUMI分組密碼,,3,數(shù)論基礎(chǔ),,,4,加密系統(tǒng)中常用數(shù)論知識(shí),模q運(yùn)算定義:給定任一正整數(shù)q和任一整數(shù)a,如果用q除a,得到商s和余數(shù)r,則有a=sq+r,記r≡a mod q;運(yùn)算操作:加法:[(a mod q)+(b mod
2、 q)]=(a+b) mod q乘法: [(a mod q)×(b mod q)]=(a×b) mod q,,5,加密系統(tǒng)中常用數(shù)論知識(shí),模q運(yùn)算運(yùn)算性質(zhì):Zn定義為集合{0,1,……,q-1},也稱為模q的剩余類集合,以下為Zn上的模運(yùn)算的性質(zhì);交換律:(a+b) mod q=(b+a) mod q (a×b) mod q=(b×a) mod q結(jié)合律
3、:[(a+b)+c] mod q= [a+(b+c)] mod q [(a×b)×c] mod q= [a×(b×c)] mod q分配律: [a×(b+c)] mod q=[a×b+a×c] mod q恒等律:(0+a) mod q=a mod q (1×a) mod q=a mo
4、d q加法逆元:若存在a,b∈ Zn,使得(a+b) mod q=0,則b是a模q的加法逆元。乘法逆元:若存在a,b∈ Zn,使得ab=1 mod q,則b是a模q的乘法逆元。,,6,加密系統(tǒng)中常用數(shù)論知識(shí),模q運(yùn)算求模逆運(yùn)算: (輾轉(zhuǎn)相除法)定理:設(shè)r1=b1u mod q,r2=b2u mod q,r1=mr2+r3,則r3=(b1-mb2)u mod q。求逆元:u,q已知,求x,(0r3>……>rk>
5、rk+1≥0,以上操作必終止于有限步,不妨設(shè)rk+1=0,那么必有1=rk=(rk,rk-1)=……=(r3,r2)=(r2,r1)=(u,q)所以rk=bku mod q,得bku≡1 mod q,于是u-1≡bk mod q,,7,加密系統(tǒng)中常用數(shù)論知識(shí),環(huán)群是一種代數(shù)結(jié)構(gòu),由一個(gè)集合以及一個(gè)二元運(yùn)算所組成。 群是一個(gè)集合 G,連同一個(gè)運(yùn)算 "·",它結(jié)合了任何兩個(gè)元素 a 和 b 而形成另一個(gè)
6、元素指示,記為 a · b。符號(hào) "·" 是對(duì)具體給出的運(yùn)算,比如上面加法的一般的占位符。要具備成為群的資格,這個(gè)集合和運(yùn)算 (G, ·) 必須滿足叫做群公理的四個(gè)要求:1.閉合。對(duì)于所有 G 中 a, b,運(yùn)算 a · b 的結(jié)果也在 G 中。2.結(jié)合律。對(duì)于所有 G 中的 a, b 和 c,等式 (a · b) · c = a · (b &
7、#183; c) 成立。3.單位元。存在 G 中的一個(gè)元素 e,使得對(duì)于所有 G 中的元素 a,等式 e · a = a · e = a 成立。4.逆元。對(duì)于每個(gè) G 中的 a,存在 G 中的一個(gè)元素 b 使得 a · b = b · a = e,這里的 e 是單位元。使等式 a · b = b · a 總是成立的群叫做阿貝爾群(以尼爾斯·阿貝爾命名)。 例子
8、:整數(shù)配備上加法運(yùn)算就形成一個(gè)群。,,8,加密系統(tǒng)中常用數(shù)論知識(shí),環(huán)集合R和定義于其上的二元運(yùn)算 + 和·,(R, +, ·)構(gòu)成一個(gè)環(huán),若它們滿足:(R, +)形成一個(gè)交換群,其幺元稱為零元素,記作‘0’。即: (a + b) = (b + a) (a + b) + c = a + (b + c) 0 + a = a + 0 = a ?a ?(?a) 滿足 a + ?a = ?a + a = 0 (R
9、, ·)形成一個(gè)半群,即: (a·b)·c = a·(b·c) 乘法關(guān)于加法滿足分配律: a·(b + c) = (a·b) + (a·c) (a + b)·c = (a·c) + (b·c) 其中,乘法運(yùn)算符·常被省略,所以 a·b 可簡(jiǎn)寫為 ab。 此外,乘法是比加法優(yōu)先的運(yùn)算,所以 a + b
10、c 其實(shí)是 a + (b·c)。交換環(huán) :若環(huán)R中,(R, ·)還滿足交換律,從而構(gòu)成交換半群,即:?a,b∈R,有ab=ba,則R稱為交換環(huán)。,,9,加密系統(tǒng)中常用數(shù)論知識(shí),域集合R和定義于其上的二元運(yùn)算 + 和·,(R, +, ·)構(gòu)成一個(gè)環(huán),若它們滿足:(R, +)形成一個(gè)交換群,其幺元稱為零元素,記作‘0’。即: (a + b) = (b + a) (a + b) + c = a
11、 + (b + c) 0 + a = a + 0 = a ?a ?(?a) 滿足 a + ?a = ?a + a = 0 (R, ·)形成一個(gè)半群,即: (a·b)·c = a·(b·c) 乘法關(guān)于加法滿足分配律: a·(b + c) = (a·b) + (a·c) (a + b)·c = (a·c) + (b·c
12、) 其中,乘法運(yùn)算符·常被省略,所以 a·b 可簡(jiǎn)寫為 ab。 此外,乘法是比加法優(yōu)先的運(yùn)算,所以 a + bc 其實(shí)是 a + (b·c)。交換環(huán) :若環(huán)R中,(R, ·)還滿足交換律,從而構(gòu)成交換半群,即:?a,b∈R,有ab=ba,則R稱為交換環(huán)。,,10,加密系統(tǒng)中常用數(shù)論知識(shí),域:是一種可進(jìn)行加、減、乘和除(除了除以零之外)運(yùn)算的代數(shù)結(jié)構(gòu),是數(shù)域以及四則運(yùn)算的推廣;域分為兩種:無(wú)
13、限域,元素個(gè)數(shù)無(wú)限,特征為0;有限域,元素個(gè)數(shù)有限,特征為p;特征:假設(shè)p是最小的正整數(shù), 使得p個(gè)1相加等于0, 那么p就稱為域的特征;有限域元素個(gè)數(shù)為q=pn;有限域GF(q)同構(gòu)于GF(p)[x]/f(x),其中f(x)為GF(p)上的不可約多項(xiàng)式;多項(xiàng)式在GF(p)上不可約:有限域GF(p)的任一元素都不是多項(xiàng)式方程的解。,域,,,無(wú)限域,有限域,,,特征0,特征p,含有q = pn個(gè)元素,,GF(q)同構(gòu)于GF(p
14、)[x]/f(x)其中f(x)為GF(p)上不可約多項(xiàng)式,,11,加密系統(tǒng)中常用數(shù)論知識(shí),歐拉定理若m,a為正整數(shù),且m,a互素,(gcd(a,m) = 1),則aφ(m)≡1 mod m,其中φ(m)為歐拉函數(shù),mod m為同余關(guān)系。 在數(shù)論中,對(duì)正整數(shù)n,歐拉函數(shù)φ(n)是小于或等于n的正整數(shù)中與n互質(zhì)的數(shù)的數(shù)目。此函數(shù)以其首名研究者歐拉命名,它又稱為φ函數(shù)、歐拉商數(shù)等。例如φ(8)=4,因?yàn)?,3,5,7均和8互質(zhì)。這個(gè)定
15、理可以用來(lái)簡(jiǎn)化冪的模運(yùn)算。比如計(jì)算7222的個(gè)位數(shù),實(shí)際是求7222被10除的余數(shù)。7和10互素,且φ(10)=4,由歐拉定理知74 ≡1 (mod 10),所以:7222=74×55+2=(74)55×72≡155×72≡49≡9 (mod 10),,12,加密系統(tǒng)中常用數(shù)論知識(shí),費(fèi)馬定理費(fèi)馬小定理是數(shù)論中的一個(gè)定理:假如a是一個(gè)整數(shù),p是一個(gè)素?cái)?shù),那么: ap≡a (mod p)如果a不是
16、p的倍數(shù),這個(gè)定理也可以寫成: ap-1≡1 (mod p)費(fèi)馬定理是歐拉定理的一種特殊情況。,,13,復(fù)雜性理論簡(jiǎn)介,算法復(fù)雜性時(shí)間復(fù)雜性T(n):以某特定的基本步驟為單元,完成計(jì)算過(guò)程所需的總單元數(shù)稱為算法的時(shí)間復(fù)雜性,或時(shí)間復(fù)雜度,n是輸入的規(guī)模和尺寸;時(shí)間復(fù)雜度:多項(xiàng)式時(shí)間復(fù)雜度和指數(shù)時(shí)間復(fù)雜度;空間復(fù)雜性S(n):以某特定的基本存儲(chǔ)空間為單元,完成計(jì)算過(guò)程所用的存儲(chǔ)單元數(shù),稱為算法的空間復(fù)雜性或空間復(fù)雜度,n是輸
17、入的規(guī)模和尺寸。,,14,復(fù)雜性理論簡(jiǎn)介,問(wèn)題復(fù)雜性圖靈機(jī):一種具有無(wú)限讀寫能力的有限狀態(tài)機(jī),是一種具有無(wú)限讀寫能力的有限狀態(tài)機(jī),有確定型和非確定型的兩種。P類:確定性多項(xiàng)式時(shí)間可解類。在確定型圖靈機(jī)上多項(xiàng)式時(shí)間可解的問(wèn)題,為P問(wèn)題,也就是易處理問(wèn)題。NP類:不確定性多項(xiàng)式可解類,在非確定型圖靈機(jī)上多項(xiàng)式時(shí)間可解的問(wèn)題,為NP問(wèn)題,難解問(wèn)題。NPC類:不確定性多項(xiàng)式時(shí)間可解完全類。NPC問(wèn)題,又稱NP完全問(wèn)題或NP完備問(wèn)題,是N
18、P(非決定性多項(xiàng)式時(shí)間)中最難的決定性問(wèn)題。因此NP完備問(wèn)題應(yīng)該是最不可能被化簡(jiǎn)為P(多項(xiàng)式時(shí)間可決定)的決定性問(wèn)題的集合。,,15,對(duì)稱密碼體制,,,16,對(duì)稱密碼算法,如果一個(gè)系統(tǒng)加密密鑰和解密密鑰相同,或存在簡(jiǎn)單的可推導(dǎo)關(guān)系,那么就稱為對(duì)稱密碼體制;對(duì)稱密碼體制有很高保密程度,運(yùn)算速度很快,處理效率很高;對(duì)稱密碼體制安全使用的關(guān)鍵在于:加密算法本身必須是足夠強(qiáng)的,至少在攻擊者獲得一個(gè)或者多個(gè)密文是無(wú)法破譯;發(fā)送者和接收者必
19、須在某種安全的條件下獲得密鑰,并保證密鑰的安全。核心問(wèn)題在于密鑰的管理;機(jī)制本身決定了不能處理不可抵賴問(wèn)題;典型算法:DES算法;分為:序列密碼和分組密碼兩類。,,17,流密碼(序列密碼),軍事和外交場(chǎng)合常用;安全強(qiáng)度取決于產(chǎn)生的偽隨機(jī)序列;速度快,安全程度高;分為:同步流密碼和自同步流密碼。,產(chǎn)生偽隨機(jī)序列,,使用該序列加密信息流(逐比特),,,明文,密文,,18,同步流密碼,利用滾動(dòng)密鑰ki對(duì)輸入的明文符號(hào)xi進(jìn)行加
20、密的,加密器可分為密鑰流生成器和加密變化器兩部分。在傳輸過(guò)程中出現(xiàn)一個(gè)錯(cuò)誤只影響一個(gè)字符,不會(huì)影響后繼字符。對(duì)敵方的惡意篡改沒(méi)有任何檢測(cè)能力。,初始密鑰,,19,自同步流加密算法,其加密器也可劃分為密鑰流生成器和加密變換器兩部分,但是密鑰流的生成與明文有關(guān),因此密文不但與當(dāng)前時(shí)刻明文有關(guān),還與之前時(shí)刻明文有關(guān)將明文每個(gè)字符都擴(kuò)散在密文的多個(gè)字符中,具有較強(qiáng)的抗統(tǒng)計(jì)分析能力。,,20,分組密碼,將明文按照固定長(zhǎng)度進(jìn)行分 組,加密
21、以分組為單位進(jìn)行;速度快,易于標(biāo)準(zhǔn)化,便于 軟硬件實(shí)現(xiàn);與流密碼相比,加密器中沒(méi) 有有記憶功能的元件。其核心是相信復(fù)雜函數(shù)可以 由簡(jiǎn)單函數(shù)迭代得到;根據(jù)明文組和密文組的長(zhǎng)度,可分為有數(shù)據(jù)擴(kuò)展、有數(shù)據(jù)壓縮和通常的分組加密算法主要算法包括:DES,3-DES,IDEA,Skipjack,Safer-64, LOK189,Shark等,,21,DES算法,密匙長(zhǎng)度是56位(因?yàn)槊總€(gè)第8 位都用作奇偶校驗(yàn)),密匙可以是
22、任意的數(shù);DES對(duì)64(bit)位的明文進(jìn)行一個(gè)初始置換IP置換并分成左半部分和右半部分(L0,R0),各32位長(zhǎng)。在每一輪中:密匙位移位,然后再?gòu)拿艹椎?6位中選出48位。通過(guò)一個(gè)擴(kuò)展置換將數(shù)據(jù)的右半部分?jǐn)U展成48位,并通過(guò)一個(gè)異或操作替代成新的32位數(shù)據(jù),在將其置換換一次。這四步運(yùn)算構(gòu)成了函數(shù)f。通過(guò)另一個(gè)異或運(yùn)算,函數(shù)f的輸出與左半部分結(jié)合,其結(jié)果成為新的右半部分,原來(lái)的右半部分成為新的左半部分。算法保密性依賴于密鑰
23、,密鑰分為弱密鑰,半弱密鑰和互補(bǔ)密鑰;,,22,對(duì)稱加密算法發(fā)展,DES算法變形,得到3-DES,獨(dú)立子密鑰方法,GDES等;差分攻擊法可攻擊DES算法;AES算法:信息塊長(zhǎng)度和密鑰長(zhǎng)度都可變;寬軌跡設(shè)計(jì)策略;每層由線性混合層、非線性層和密鑰加層組成;,,23,有限域計(jì)算在AES中應(yīng)用,有限域GF(28)由不可約多項(xiàng)式定義m(x)=x8+x4+x3+x+1,,,1 1 B,x6+x4+x2+x+157,x7+x+183
24、,,,+,x7+x6+x4+x2D4,二進(jìn)制位異或,,,x7+x6+1C1,×,a(x)×b(x) mod m(x),,,,,這里選的M(x)所有次數(shù)為8的不可約多項(xiàng)式列表中的第一個(gè),,如果a(x)×b(x) mod m(x) =1那么稱b(x)為a(x)的逆元,,24,有限環(huán)運(yùn)算,環(huán)和域的區(qū)別在于,域可以進(jìn)行除法運(yùn)算而環(huán)不可以;加法定義為簡(jiǎn)單的比特位異或;,兩個(gè)系數(shù)為G
25、F(28)上的多項(xiàng)式,,,a(x)=a3x3+a2x2+a1x1+a0,b(x)=b3x3+b2x2+b1x1+b0,,,×,c(x)=c6x6+c5x5+c4x4+c3x3+c2x2+c1x1+c0,,c6=a3*b3,c5=a3*b2⊕a2b3,c4=a3*b1⊕a2b2⊕a1b3,c3=a3*b0⊕a2b1⊕a1b2⊕a0b3,c2=a2*b0⊕a1b1⊕a0b2,c1=a1*b0⊕a0b1,c0=a0*b0,,d3
26、=a3*b0⊕a2b1⊕a1b2⊕a0b3,d2=a2*b0⊕a1b1⊕a0b2⊕a3b3,d1=a1*b0⊕a0b1⊕a3b2⊕a2b3,d0=a0*b0⊕a3b1⊕a2b2⊕a1b3,因xq mod x4+1=xq mod 4因此a(x) ×b(x)=d(x)其中d(x)=d3x3+d2x2+d1x1+d0,,,25,AES算法框架流程,,26,128位AES算法流程,,27,AES輪函數(shù),AES的輪函數(shù)每一輪迭代的結(jié)
27、構(gòu)都一樣,由下述4個(gè)不同的變換構(gòu)成,只是最后一輪省略了列混合變換。 字節(jié)替換(ByteSub):對(duì)數(shù)據(jù)的每一字節(jié)應(yīng)用一個(gè)非線性變換。 行移位(ShiftRow):對(duì)每一行的字節(jié)循環(huán)重新排序。 列混合(MixColumn):對(duì)矩陣的列應(yīng)用一個(gè)線性變換。輪密鑰加(AddRoundKey):把輪密鑰混合到中間數(shù)據(jù)。,,28,,S-BOX替換盒,把數(shù)據(jù)塊分成字的形式,每個(gè) 字包含4個(gè)字節(jié),每個(gè)字節(jié)8bit;字節(jié)變換ByteSub是
28、一種非線性 字節(jié)變換,定義入右圖所示,其 中ai,j代表了一個(gè)字節(jié),而ai,j-1 則是ai,j在GF(28)中的乘法逆; 在具體實(shí)現(xiàn)中,S-BOX使用查表法實(shí)現(xiàn)來(lái)提供效率;替代表是一個(gè)16×16的矩陣。表中縱向的x取自狀態(tài)矩陣中的高4比特,橫向的y取自低取自狀態(tài)矩陣中的4比特。替代的過(guò)程如下表,x行和y列的數(shù)據(jù)就用來(lái)替代的數(shù)據(jù),=,+,,29,AES字節(jié)變換替換表,,30,AES行位移變換,行移位運(yùn)算(Shi
29、ftRow):這是狀態(tài)中字節(jié)的循環(huán)移位運(yùn)算。這個(gè)運(yùn)算可以表示成為Bi,j = Ai,(i+j) mod 4,,31,AES列混合變換,列混合變換:將狀態(tài)每一列都視為環(huán)GF(28)上多項(xiàng)式s(x),然后乘以固定多項(xiàng)式a(x),并模除x4+1其中a(x)={03}x3+{01}x2+{01}x+{02},定義變換公式 根據(jù)環(huán)GF(28)的相關(guān)理論有:,,32,AES輪密鑰加密過(guò)程,對(duì)狀態(tài)和每輪的子密鑰進(jìn)行簡(jiǎn)單的異或操作。每
30、輪子密鑰是通過(guò)密鑰調(diào)度算法從主密鑰中產(chǎn)生, 子密鑰長(zhǎng)度等于分組長(zhǎng)度。輪密鑰加運(yùn)算需要用到4個(gè)導(dǎo)出的32比特子密鑰。,,33,AES子密鑰的生成,第i-1輪的16個(gè)字節(jié)的子密鑰被分成4組來(lái)處理,每組4個(gè)字節(jié)。先執(zhí)行一個(gè)字節(jié)的循環(huán)左移,由S盒(這個(gè)S盒與字節(jié)替代時(shí)的S盒是一樣的)來(lái)進(jìn)行替代處理,然后這4個(gè)字節(jié)結(jié)果中的第一個(gè)字節(jié)和預(yù)先定義的輪常數(shù)ai相異或。最后把上面得到的結(jié)果和輪密鑰的前4個(gè)字節(jié)按位相異或,得到i輪密鑰的前4個(gè)字節(jié)
31、,然后又和密鑰的下面4個(gè)字節(jié)按位相異或,得到i輪密鑰的下面4個(gè)字節(jié),以此類推。,,34,AES算法解密過(guò)程,因?yàn)锳ES算法每步計(jì)算都是可逆的,所以AES解密算法結(jié)構(gòu)和加密算法相同,只是對(duì)其中的操作做逆;過(guò)程:先進(jìn)行仿射的逆變換;把字節(jié)的值用的乘法逆來(lái)代替;列混合變換的逆類似于列混合變換,將狀態(tài)的每一列都乘以多項(xiàng)式d(x)=‘0B’x3+‘0D’x2+‘09’x+‘0E’,,35,下次課提要,KUSAMI算法非對(duì)稱機(jī)密體制RS
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 加密算法
- 光學(xué)非對(duì)稱圖像加密算法研究.pdf
- 基于混沌理論的非對(duì)稱加密算法研究.pdf
- sea加密算法
- 數(shù)據(jù)加密算法
- rsa算法公鑰加密算法
- 基于非對(duì)稱加密算法的qr二維碼
- 用于文檔加密算法研究
- RFID安全協(xié)議及加密算法研究.pdf
- 3個(gè)著名加密算法
- Arnold加密算法改進(jìn).pdf
- 基于加密算法的gps航跡加密設(shè)計(jì)
- 混沌圖像加密算法研究.pdf
- 屬性基加密算法研究.pdf
- 基于屬性的加密算法.pdf
- 基于混沌的圖像加密算法及應(yīng)用.pdf
- 高級(jí)加密算法的研究.pdf
- WSN的加密算法研究.pdf
- 基于混沌加密算法的視頻加密系統(tǒng).pdf
- 跳頻加密算法研究及芯片實(shí)現(xiàn).pdf
評(píng)論
0/150
提交評(píng)論