ch-1-數(shù)論基礎及對稱加密算法

1、,1,數(shù)論基礎及對稱加密算法,,,2,提綱,數(shù)論基礎加密系統(tǒng)中常用的數(shù)論知識復雜性理論簡介對稱加密算法對稱密碼體制模型流密碼分組密碼DESRijndael密碼體制（AES加密算法）KASUMI分組密碼,,3,數(shù)論基礎,,,4,加密系統(tǒng)中常用數(shù)論知識,模q運算定義：給定任一正整數(shù)q和任一整數(shù)a，如果用q除a，得到商s和余數(shù)r，則有a=sq+r，記r≡a mod q;運算操作：加法：[(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ù)論知識,模q運算運算性質：Zn定義為集合{0,1,……,q-1}，也稱為模q的剩余類集合，以下為Zn上的模運算的性質；交換律：(a+b) mod q=(b+a) mod q (a×b) mod q=(b×a) mod q結合律

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ù)論知識,模q運算求模逆運算: (輾轉相除法)定理：設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，以上操作必終止于有限步，不妨設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ù)論知識,環(huán)群是一種代數(shù)結構，由一個集合以及一個二元運算所組成。 群是一個集合 G，連同一個運算 "·"，它結合了任何兩個元素 a 和 b 而形成另一個

6、元素指示，記為 a · b。符號 "·" 是對具體給出的運算，比如上面加法的一般的占位符。要具備成為群的資格，這個集合和運算 (G, ·) 必須滿足叫做群公理的四個要求:1.閉合。對于所有 G 中 a, b，運算 a · b 的結果也在 G 中。2.結合律。對于所有 G 中的 a, b 和 c，等式 (a · b) · c = a · (b &

7、#183; c) 成立。3.單位元。存在 G 中的一個元素 e，使得對于所有 G 中的元素 a，等式 e · a = a · e = a 成立。4.逆元。對于每個 G 中的 a，存在 G 中的一個元素 b 使得 a · b = b · a = e，這里的 e 是單位元。使等式 a · b = b · a 總是成立的群叫做阿貝爾群（以尼爾斯·阿貝爾命名）。 例子

8、：整數(shù)配備上加法運算就形成一個群。,,8,加密系統(tǒng)中常用數(shù)論知識,環(huán)集合R和定義于其上的二元運算 + 和·，(R, +, ·)構成一個環(huán)，若它們滿足：(R, +)形成一個交換群，其幺元稱為零元素，記作‘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、, ·)形成一個半群，即： (a·b)·c = a·(b·c) 乘法關于加法滿足分配律： a·(b + c) = (a·b) + (a·c) (a + b)·c = (a·c) + (b·c) 其中，乘法運算符·常被省略，所以 a·b 可簡寫為 ab。 此外，乘法是比加法優(yōu)先的運算，所以 a + b

10、c 其實是 a + (b·c)。交換環(huán) ：若環(huán)R中，(R, ·)還滿足交換律，從而構成交換半群，即：?a，b∈R，有ab=ba，則R稱為交換環(huán)。,,9,加密系統(tǒng)中常用數(shù)論知識,域集合R和定義于其上的二元運算 + 和·，(R, +, ·)構成一個環(huán)，若它們滿足：(R, +)形成一個交換群，其幺元稱為零元素，記作‘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, ·)形成一個半群，即： (a·b)·c = a·(b·c) 乘法關于加法滿足分配律： a·(b + c) = (a·b) + (a·c) (a + b)·c = (a·c) + (b·c

12、) 其中，乘法運算符·常被省略，所以 a·b 可簡寫為 ab。 此外，乘法是比加法優(yōu)先的運算，所以 a + bc 其實是 a + (b·c)。交換環(huán) ：若環(huán)R中，(R, ·)還滿足交換律，從而構成交換半群，即：?a，b∈R，有ab=ba，則R稱為交換環(huán)。,,10,加密系統(tǒng)中常用數(shù)論知識,域：是一種可進行加、減、乘和除（除了除以零之外）運算的代數(shù)結構，是數(shù)域以及四則運算的推廣；域分為兩種：無

13、限域，元素個數(shù)無限，特征為0；有限域，元素個數(shù)有限，特征為p；特征：假設p是最小的正整數(shù)， 使得p個1相加等于0， 那么p就稱為域的特征；有限域元素個數(shù)為q=pn；有限域GF(q)同構于GF(p)[x]/f(x)，其中f(x)為GF(p)上的不可約多項式；多項式在GF(p)上不可約：有限域GF(p)的任一元素都不是多項式方程的解。,域,,,無限域,有限域,,,特征0,特征p,含有q = pn個元素,,GF(q)同構于GF(p

14、)[x]/f(x)其中f(x)為GF(p)上不可約多項式,,11,加密系統(tǒng)中常用數(shù)論知識,歐拉定理若m,a為正整數(shù)，且m,a互素，(gcd(a,m) = 1)，則aφ(m)≡1 mod m，其中φ(m)為歐拉函數(shù)，mod m為同余關系。 在數(shù)論中，對正整數(shù)n，歐拉函數(shù)φ(n)是小于或等于n的正整數(shù)中與n互質的數(shù)的數(shù)目。此函數(shù)以其首名研究者歐拉命名，它又稱為φ函數(shù)、歐拉商數(shù)等。例如φ(8)=4，因為1,3,5,7均和8互質。這個定

15、理可以用來簡化冪的模運算。比如計算7222的個位數(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ù)論中的一個定理：假如a是一個整數(shù)，p是一個素數(shù)，那么： ap≡a (mod p)如果a不是

16、p的倍數(shù)，這個定理也可以寫成： ap-1≡1 (mod p)費馬定理是歐拉定理的一種特殊情況。,,13,復雜性理論簡介,算法復雜性時間復雜性T(n)：以某特定的基本步驟為單元，完成計算過程所需的總單元數(shù)稱為算法的時間復雜性，或時間復雜度，n是輸入的規(guī)模和尺寸；時間復雜度：多項式時間復雜度和指數(shù)時間復雜度；空間復雜性S(n)：以某特定的基本存儲空間為單元，完成計算過程所用的存儲單元數(shù)，稱為算法的空間復雜性或空間復雜度，n是輸

17、入的規(guī)模和尺寸。,,14,復雜性理論簡介,問題復雜性圖靈機：一種具有無限讀寫能力的有限狀態(tài)機，是一種具有無限讀寫能力的有限狀態(tài)機，有確定型和非確定型的兩種。P類：確定性多項式時間可解類。在確定型圖靈機上多項式時間可解的問題，為P問題，也就是易處理問題。NP類：不確定性多項式可解類，在非確定型圖靈機上多項式時間可解的問題，為NP問題，難解問題。NPC類：不確定性多項式時間可解完全類。NPC問題，又稱NP完全問題或NP完備問題，是N

18、P（非決定性多項式時間）中最難的決定性問題。因此NP完備問題應該是最不可能被化簡為P（多項式時間可決定）的決定性問題的集合。,,15,對稱密碼體制,,,16,對稱密碼算法,如果一個系統(tǒng)加密密鑰和解密密鑰相同，或存在簡單的可推導關系，那么就稱為對稱密碼體制；對稱密碼體制有很高保密程度，運算速度很快，處理效率很高；對稱密碼體制安全使用的關鍵在于：加密算法本身必須是足夠強的，至少在攻擊者獲得一個或者多個密文是無法破譯；發(fā)送者和接收者必

19、須在某種安全的條件下獲得密鑰，并保證密鑰的安全。核心問題在于密鑰的管理；機制本身決定了不能處理不可抵賴問題；典型算法：DES算法；分為：序列密碼和分組密碼兩類。,,17,流密碼（序列密碼）,軍事和外交場合常用；安全強度取決于產生的偽隨機序列；速度快，安全程度高；分為：同步流密碼和自同步流密碼。,產生偽隨機序列,,使用該序列加密信息流(逐比特),,,明文,密文,,18,同步流密碼,利用滾動密鑰ki對輸入的明文符號xi進行加

20、密的，加密器可分為密鑰流生成器和加密變化器兩部分。在傳輸過程中出現(xiàn)一個錯誤只影響一個字符，不會影響后繼字符。對敵方的惡意篡改沒有任何檢測能力。,初始密鑰,,19,自同步流加密算法,其加密器也可劃分為密鑰流生成器和加密變換器兩部分，但是密鑰流的生成與明文有關，因此密文不但與當前時刻明文有關，還與之前時刻明文有關將明文每個字符都擴散在密文的多個字符中，具有較強的抗統(tǒng)計分析能力。,,20,分組密碼,將明文按照固定長度進行分 組，加密

21、以分組為單位進行；速度快，易于標準化，便于 軟硬件實現(xiàn)；與流密碼相比，加密器中沒 有有記憶功能的元件。其核心是相信復雜函數(shù)可以 由簡單函數(shù)迭代得到；根據(jù)明文組和密文組的長度，可分為有數(shù)據(jù)擴展、有數(shù)據(jù)壓縮和通常的分組加密算法主要算法包括：DES,3-DES,IDEA,Skipjack,Safer-64, LOK189,Shark等,,21,DES算法,密匙長度是56位（因為每個第8 位都用作奇偶校驗），密匙可以是

22、任意的數(shù)；DES對64(bit)位的明文進行一個初始置換IP置換并分成左半部分和右半部分(L0,R0)，各32位長。在每一輪中:密匙位移位，然后再從密匙的56位中選出48位。通過一個擴展置換將數(shù)據(jù)的右半部分擴展成48位，并通過一個異或操作替代成新的32位數(shù)據(jù)，在將其置換換一次。這四步運算構成了函數(shù)f。通過另一個異或運算，函數(shù)f的輸出與左半部分結合，其結果成為新的右半部分，原來的右半部分成為新的左半部分。算法保密性依賴于密鑰

23、，密鑰分為弱密鑰，半弱密鑰和互補密鑰；,,22,對稱加密算法發(fā)展,DES算法變形，得到3-DES,獨立子密鑰方法，GDES等；差分攻擊法可攻擊DES算法；AES算法：信息塊長度和密鑰長度都可變；寬軌跡設計策略；每層由線性混合層、非線性層和密鑰加層組成；,,23,有限域計算在AES中應用,有限域GF(28)由不可約多項式定義m(x)=x8+x4+x3+x+1,,,1 1 B,x6+x4+x2+x+157,x7+x+183

24、,,,+,x7+x6+x4+x2D4,二進制位異或,,,x7+x6+1C1,×,a(x)×b(x) mod m(x),,,,,這里選的M(x)所有次數(shù)為8的不可約多項式列表中的第一個,,如果a(x)×b(x) mod m(x) =1那么稱b(x)為a(x)的逆元,,24,有限環(huán)運算,環(huán)和域的區(qū)別在于，域可以進行除法運算而環(huán)不可以；加法定義為簡單的比特位異或；,兩個系數(shù)為G

25、F(28)上的多項式,,,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ù)每一輪迭代的結

27、構都一樣，由下述4個不同的變換構成，只是最后一輪省略了列混合變換。 字節(jié)替換（ByteSub）：對數(shù)據(jù)的每一字節(jié)應用一個非線性變換。 行移位(ShiftRow)：對每一行的字節(jié)循環(huán)重新排序。 列混合（MixColumn）：對矩陣的列應用一個線性變換。輪密鑰加(AddRoundKey)：把輪密鑰混合到中間數(shù)據(jù)。,,28,,S-BOX替換盒,把數(shù)據(jù)塊分成字的形式，每個 字包含4個字節(jié)，每個字節(jié)8bit；字節(jié)變換ByteSub是

28、一種非線性 字節(jié)變換，定義入右圖所示，其 中ai,j代表了一個字節(jié)，而ai,j-1 則是ai,j在GF(28)中的乘法逆； 在具體實現(xiàn)中，S-BOX使用查表法實現(xiàn)來提供效率；替代表是一個16×16的矩陣。表中縱向的x取自狀態(tài)矩陣中的高4比特，橫向的y取自低取自狀態(tài)矩陣中的4比特。替代的過程如下表，x行和y列的數(shù)據(jù)就用來替代的數(shù)據(jù),=,+,,29,AES字節(jié)變換替換表,,30,AES行位移變換,行移位運算（Shi

29、ftRow）：這是狀態(tài)中字節(jié)的循環(huán)移位運算。這個運算可以表示成為Bi,j = Ai,(i+j) mod 4,,31,AES列混合變換,列混合變換：將狀態(tài)每一列都視為環(huán)GF(28)上多項式s(x)，然后乘以固定多項式a(x)，并模除x4+1其中a(x)={03}x3+{01}x2+{01}x+{02}，定義變換公式 根據(jù)環(huán)GF(28)的相關理論有：,,32,AES輪密鑰加密過程,對狀態(tài)和每輪的子密鑰進行簡單的異或操作。每

30、輪子密鑰是通過密鑰調度算法從主密鑰中產生， 子密鑰長度等于分組長度。輪密鑰加運算需要用到4個導出的32比特子密鑰。,,33,AES子密鑰的生成,第i-1輪的16個字節(jié)的子密鑰被分成4組來處理，每組4個字節(jié)。先執(zhí)行一個字節(jié)的循環(huán)左移，由S盒（這個S盒與字節(jié)替代時的S盒是一樣的）來進行替代處理，然后這4個字節(jié)結果中的第一個字節(jié)和預先定義的輪常數(shù)ai相異或。最后把上面得到的結果和輪密鑰的前4個字節(jié)按位相異或，得到i輪密鑰的前4個字節(jié)

31、，然后又和密鑰的下面4個字節(jié)按位相異或，得到i輪密鑰的下面4個字節(jié)，以此類推。,,34,AES算法解密過程,因為AES算法每步計算都是可逆的，所以AES解密算法結構和加密算法相同，只是對其中的操作做逆；過程：先進行仿射的逆變換；把字節(jié)的值用的乘法逆來代替；列混合變換的逆類似于列混合變換，將狀態(tài)的每一列都乘以多項式d(x)=‘0B’x3+‘0D’x2+‘09’x+‘0E’,,35,下次課提要,KUSAMI算法非對稱機密體制RS