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

數(shù)論基礎(chǔ)及對稱加密算法1第1頁，共31頁，2023年，2月20日，星期五2提綱數(shù)論基礎(chǔ)加密系統(tǒng)中常用的數(shù)論知識復(fù)雜性理論簡介對稱加密算法對稱密碼體制模型流密碼分組密碼DESRijndael密碼體制（AES加密算法）KASUMI分組密碼第2頁，共31頁，2023年，2月20日，星期五3

數(shù)論基礎(chǔ)第3頁，共31頁，2023年，2月20日，星期五4加密系統(tǒng)中常用數(shù)論知識模q運(yùn)算定義：給定任一正整數(shù)q和任一整數(shù)a，如果用a除以q，得到商s和余數(shù)r，則有a=sq+r，記r≡amodq;運(yùn)算操作：加法：[(amodq)+(bmodq)]=(a+b)modq乘法：[(amodq)×(bmodq)]=(a×b)modq第4頁，共31頁，2023年，2月20日，星期五5加密系統(tǒng)中常用數(shù)論知識模q運(yùn)算運(yùn)算性質(zhì)：Zn定義為集合{0,1,……,q-1}，也稱為模q的剩余類集合，以下為Zn上的模運(yùn)算的性質(zhì)；交換律：(a+b)modq=(b+a)modq(a×b)modq=(b×a)modq結(jié)合律：[(a+b)+c]modq=[a+(b+c)]modq[(a×b)×c]modq=[a×(b×c)]modq分配律：[a×(b+c)]modq=[a×b+a×c]modq恒等律：(0+a)modq=amodq(1×a)modq=amodq加法逆元：若存在a,b∈Zn，使得(a＋b)modq=0，則b是a模q的加法逆元。乘法逆元：若存在a,b∈Zn，使得ab=1modq，則b是a模q的乘法逆元。第5頁，共31頁，2023年，2月20日，星期五6加密系統(tǒng)中常用數(shù)論知識模q運(yùn)算求模逆運(yùn)算:(輾轉(zhuǎn)相除法)定理：設(shè)r1=b1umodq，r2=b2umodq，r1=mr2+r3，則r3=(b1-mb2)umodq。求逆元：u,q已知，求x，(0<x<q)，使得ux=1modq解：令r1=q，r2=u，則r1=q≡0×umodq，r2=u≡1×umodq

即有:b1=0，b2=1

令r1=m1r2+r3，0≤r3<r2，得到r3≡(b1-m1b2)umodq，記b3=b1-mb2，則有r2≡b2umodq，r3≡b3umodq。令r2=m2r3+r4，0≤r4<r3，得到r4≡(b2-m2b3)umodq，記b4=b2-mb3，則有r4≡b4umodq。繼續(xù)下去，總之有：

r1≡b1umodq，r2≡b2umodq，r1=m1r2+r3，0≤r3<r2r2≡b2umodq，r3≡b3umodq，r2=m2r3+r4，0≤r4<r3……rk-1≡bk-1umodq，rk≡bkumodq，rk-1=mk-1rk+rk+1，0≤rk+1<rk……由于r2>r3>……>rk>rk+1≥0，以上操作必終止于有限步，不妨設(shè)rk+1=0，那么必有1=rk=(rk,rk-1)=……=(r3,r2)=(r2,r1)=(u,q)利用性質(zhì)：若r是a÷b的余數(shù),則gcd(a,b)=gcd(b,r)所以rk=bkumodq，得bku≡1modq，于是u-1≡bkmodq第6頁，共31頁，2023年，2月20日，星期五7加密系統(tǒng)中常用數(shù)論知識群群是一種代數(shù)結(jié)構(gòu)，由一個(gè)集合以及一個(gè)二元運(yùn)算所組成。群是一個(gè)集合G，連同一個(gè)運(yùn)算"·"，它結(jié)合了任何兩個(gè)元素a

和b

而形成另一個(gè)元素指示，記為a·b。符號"·"是對具體給出的運(yùn)算，比如上面加法的一般的占位符。要具備成為群的資格，這個(gè)集合和運(yùn)算(G,·)必須滿足叫做群公理的四個(gè)要求:1.閉合。對于所有G

中a,b，運(yùn)算a·b

的結(jié)果也在G

中。2.結(jié)合律。對于所有G

中的a,b

和c，等式(a·b)·c=a·(b·c)成立。3.單位元。存在G

中的一個(gè)元素e，使得對于所有G

中的元素a，等式e·a=a·e=a

成立。4.逆元。對于每個(gè)G

中的a，存在G

中的一個(gè)元素b

使得a·b=b·a=e，這里的e

是單位元。使等式a·b=b·a

總是成立的群叫做阿貝爾群（以尼爾斯·阿貝爾命名）。例子：整數(shù)配備上加法運(yùn)算就形成一個(gè)群。第7頁，共31頁，2023年，2月20日，星期五8加密系統(tǒng)中常用數(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,·)形成一個(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可簡寫為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)。第8頁，共31頁，2023年，2月20日，星期五9加密系統(tǒng)中常用數(shù)論知識域：是一種可進(jìn)行加、減、乘和除（除了除以零之外）運(yùn)算的代數(shù)結(jié)構(gòu)，是數(shù)域以及四則運(yùn)算的推廣；域分為兩種：無限域，元素個(gè)數(shù)無限，特征為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)式方程的解。域無限域有限域特征0特征p,含有q=pn個(gè)元素GF(q)同構(gòu)于GF(p)[x]/f(x)其中f(x)為GF(p)上不可約多項(xiàng)式第9頁，共31頁，2023年，2月20日，星期五10加密系統(tǒng)中常用數(shù)論知識歐拉定理若m,a為正整數(shù)，且m,a互素，(gcd(a,m)=1)，則aφ(m)≡1modm，其中φ(m)為歐拉函數(shù)，modm為同余關(guān)系。在數(shù)論中，對正整數(shù)n，歐拉函數(shù)φ(n)是小于或等于n的正整數(shù)中與n互質(zhì)的數(shù)的數(shù)目。此函數(shù)以其首名研究者歐拉命名，它又稱為φ函數(shù)、歐拉商數(shù)等。例如φ(8)=4，因?yàn)?,3,5,7均和8互質(zhì)。這個(gè)定理可以用來簡化冪的模運(yùn)算。比如計(jì)算7222的個(gè)位數(shù)，實(shí)際是求7222被10除的余數(shù)。7和10互素，且φ(10)=4，由歐拉定理知74≡1(mod10)，所以：7222=74×55+2=(74)55×72≡155×72≡49≡9(mod10)第10頁，共31頁，2023年，2月20日，星期五11加密系統(tǒng)中常用數(shù)論知識費(fèi)馬定理費(fèi)馬小定理是數(shù)論中的一個(gè)定理：假如a是一個(gè)整數(shù)，p是一個(gè)素?cái)?shù)，那么：

ap≡a(modp)如果a不是p的倍數(shù)，這個(gè)定理也可以寫成：

ap-1≡1(modp)費(fèi)馬定理是歐拉定理的一種特殊情況。第11頁，共31頁，2023年，2月20日，星期五12復(fù)雜性理論簡介算法復(fù)雜性時(shí)間復(fù)雜性T(n)：以某特定的基本步驟為單元，完成計(jì)算過程所需的總單元數(shù)稱為算法的時(shí)間復(fù)雜性，或時(shí)間復(fù)雜度，n是輸入的規(guī)模和尺寸；時(shí)間復(fù)雜度：多項(xiàng)式時(shí)間復(fù)雜度和指數(shù)時(shí)間復(fù)雜度；空間復(fù)雜性S(n)：以某特定的基本存儲空間為單元，完成計(jì)算過程所用的存儲單元數(shù)，稱為算法的空間復(fù)雜性或空間復(fù)雜度，n是輸入的規(guī)模和尺寸。第12頁，共31頁，2023年，2月20日，星期五13復(fù)雜性理論簡介問題復(fù)雜性圖靈機(jī)：一種具有無限讀寫能力的有限狀態(tài)機(jī)，是一種具有無限讀寫能力的有限狀態(tài)機(jī)，有確定型和非確定型的兩種。P類：確定性多項(xiàng)式時(shí)間可解類。在確定型圖靈機(jī)上多項(xiàng)式時(shí)間可解的問題，為P問題，也就是易處理問題。NP類：不確定性多項(xiàng)式可解類，在非確定型圖靈機(jī)上多項(xiàng)式時(shí)間可解的問題，為NP問題，難解問題。NPC類：不確定性多項(xiàng)式時(shí)間可解完全類。NPC問題，又稱NP完全問題或NP完備問題，是NP（非決定性多項(xiàng)式時(shí)間）中最難的決定性問題。因此NP完備問題應(yīng)該是最不可能被化簡為P（多項(xiàng)式時(shí)間可決定）的決定性問題的集合。第13頁，共31頁，2023年，2月20日，星期五14

對稱密碼體制第14頁，共31頁，2023年，2月20日，星期五15對稱密碼算法如果一個(gè)系統(tǒng)加密密鑰和解密密鑰相同，或存在簡單的可推導(dǎo)關(guān)系，那么就稱為對稱密碼體制；對稱密碼體制有很高保密程度，運(yùn)算速度很快，處理效率很高；對稱密碼體制安全使用的關(guān)鍵在于：加密算法本身必須是足夠強(qiáng)的，至少在攻擊者獲得一個(gè)或者多個(gè)密文是無法破譯；發(fā)送者和接收者必須在某種安全的條件下獲得密鑰，并保證密鑰的安全。核心問題在于密鑰的管理；機(jī)制本身決定了不能處理不可抵賴問題；典型算法：DES算法；分為：序列密碼和分組密碼兩類。第15頁，共31頁，2023年，2月20日，星期五16流密碼（序列密碼）軍事和外交場合常用；安全強(qiáng)度取決于產(chǎn)生的偽隨機(jī)序列；速度快，安全程度高；分為：同步流密碼和自同步流密碼。產(chǎn)生偽隨機(jī)序列使用該序列加密信息流(逐比特)明文密文第16頁，共31頁，2023年，2月20日，星期五17同步流密碼利用滾動密鑰ki對輸入的明文符號xi進(jìn)行加密的，加密器可分為密鑰流生成器和加密變化器兩部分。在傳輸過程中出現(xiàn)一個(gè)錯誤只影響一個(gè)字符，不會影響后繼字符。對敵方的惡意篡改沒有任何檢測能力。初始密鑰有記憶元件的密鑰流生成器加密器當(dāng)前時(shí)刻加密密鑰當(dāng)前時(shí)刻明文當(dāng)前時(shí)刻密文第17頁，共31頁，2023年，2月20日，星期五18自同步流加密算法其加密器也可劃分為密鑰流生成器和加密變換器兩部分，但是密鑰流的生成與明文有關(guān)，因此密文不但與當(dāng)前時(shí)刻明文有關(guān)，還與之前時(shí)刻明文有關(guān)將明文每個(gè)字符都擴(kuò)散在密文的多個(gè)字符中，具有較強(qiáng)的抗統(tǒng)計(jì)分析能力。有記憶元件的密鑰流生成器加密器當(dāng)前時(shí)刻加密密鑰當(dāng)前時(shí)刻明文當(dāng)前時(shí)刻密文第18頁，共31頁，2023年，2月20日，星期五19分組密碼將明文按照固定長度進(jìn)行分組，加密以分組為單位進(jìn)行；速度快，易于標(biāo)準(zhǔn)化，便于軟硬件實(shí)現(xiàn)；與流密碼相比，加密器中沒有有記憶功能的元件。其核心是相信復(fù)雜函數(shù)可以由簡單函數(shù)迭代得到；根據(jù)明文組和密文組的長度，可分為有數(shù)據(jù)擴(kuò)展、有數(shù)據(jù)壓縮和通常的分組加密算法主要算法包括：DES,3-DES,IDEA,Skipjack,Safer-64,LOK189,Shark等第19頁，共31頁，2023年，2月20日，星期五20DES算法密匙長度是56位（因?yàn)槊總€(gè)第8位都用作奇偶校驗(yàn)），密匙可以是任意的數(shù)；DES對64(bit)位的明文進(jìn)行一個(gè)初始置換IP置換并分成左半部分和右半部分(L0,R0)，各32位長。在每一輪中:密匙位移位，然后再從密匙的56位中選出48位。通過一個(gè)擴(kuò)展置換將數(shù)據(jù)的右半部分?jǐn)U展成48位，并通過一個(gè)異或操作替代成新的32位數(shù)據(jù)，在將其置換換一次。這四步運(yùn)算構(gòu)成了函數(shù)f。通過另一個(gè)異或運(yùn)算，函數(shù)f的輸出與左半部分結(jié)合，其結(jié)果成為新的右半部分，原來的右半部分成為新的左半部分。算法保密性依賴于密鑰，密鑰分為弱密鑰，半弱密鑰和互補(bǔ)密鑰；

第20頁，共31頁，2023年，2月20日，星期五21對稱加密算法發(fā)展DES算法變形，得到3-DES,獨(dú)立子密鑰方法，GDES等；差分攻擊法可攻擊DES算法；AES算法：信息塊長度和密鑰長度都可變；寬軌跡設(shè)計(jì)策略；每層由線性混合層、非線性層和密鑰加層組成；第21頁，共31頁，2023年，2月20日，星期五22有限域計(jì)算在AES中應(yīng)用有限域GF(28)由不可約多項(xiàng)式定義m(x)=x8+x4+x3+x+18765432101000110111

1

Bx6+x4+x2+x+157x7+x+183+x7+x6+x4+x2D4二進(jìn)制位異或x7+x6+1C1×a(x)×b(x)modm(x)這里選的M(x)所有次數(shù)為8的不可約多項(xiàng)式列表中的第一個(gè)如果a(x)×b(x)modm(x)=1那么稱b(x)為a(x)的逆元第22頁，共31頁，2023年，2月20日，星期五23有限環(huán)運(yùn)算環(huán)和域的區(qū)別在于，域可以進(jìn)行除法運(yùn)算而環(huán)不可以；加法定義為簡單的比特位異或；兩個(gè)系數(shù)為GF(28)上的多項(xiàng)式a(x)=a3x3+a2x2+a1x1+a0b(x)=b3x3+b2x2+b1x1+b0×c(x)=c6x6+c5x5+c4x4+c3x3+c2x2+c1x1+c0c6=a3*b3c5=a3*b2⊕a2b3c4=a3*b1⊕a2b2⊕a1b3c3=a3*b0⊕a2b1⊕a1b2⊕a0b3c2=a2*b0⊕a1b1⊕a0b2c1=a1*b0⊕a0b1c0=a0*b0d3=a3*b0⊕a2b1⊕a1b2⊕a0b3d2=a2*b0⊕a1b1⊕a0b2⊕a3b3d1=a1*b0⊕a0b1⊕a3b2⊕a2b3d0=a0*b0⊕a3b1⊕a2b2⊕a1b3因xqmodx4+1=xqmod4因此a(x)×b(x)=d(x)其中d(x)=d3x3+d2x2+d1x1+d0第23頁，共31頁，2023年，2月20日，星期五24AES算法框架流程PlainTextInitialRoundAddRoundKeyStandardRoundByteSubShiftRowMixColumnAddRoundKeyFinalRoundByteSub

ShiftRowAddRoundKeyCipherTextNr-1RoundsCipherKeyExpansionExpandedKeySelectionRoundKey1RoundKey2…RoundKeyNr-1RoundKeyNr第24頁，共31頁，2023年，2月20日，星期五25128位AES算法流程第25頁，共31頁，2023年，2月20日，星期五26AES輪函數(shù)AES的輪函數(shù)每一輪迭代的結(jié)構(gòu)都一樣，由下述4個(gè)不同的變換構(gòu)成，只是最后一輪省略了列混合變換。

字節(jié)替換（ByteSub）：對數(shù)據(jù)的每一字節(jié)應(yīng)用一個(gè)非線性變換。行移位(ShiftRow)：對每一行的字節(jié)循環(huán)重新排序。列混合（MixColumn）