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

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

數(shù)論基礎第3頁，共31頁，2023年，2月20日，星期五4加密系統(tǒng)中常用數(shù)論知識模q運算定義：給定任一正整數(shù)q和任一整數(shù)a，如果用a除以q，得到商s和余數(shù)r，則有a=sq+r，記r≡amodq;運算操作：加法：[(amodq)+(bmodq)]=(a+b)modq乘法：[(amodq)×(bmodq)]=(a×b)modq第4頁，共31頁，2023年，2月20日，星期五5加密系統(tǒng)中常用數(shù)論知識模q運算運算性質：Zn定義為集合{0,1,……,q-1}，也稱為模q的剩余類集合，以下為Zn上的模運算的性質；交換律：(a+b)modq=(b+a)modq(a×b)modq=(b×a)modq結合律：[(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運算求模逆運算:(輾轉相除法)定理：設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，以上操作必終止于有限步，不妨設rk+1=0，那么必有1=rk=(rk,rk-1)=……=(r3,r2)=(r2,r1)=(u,q)利用性質：若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ù)結構，由一個集合以及一個二元運算所組成。群是一個集合G，連同一個運算"·"，它結合了任何兩個元素a

和b

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

中a,b，運算a·b

的結果也在G

中。2.結合律。對于所有G

中的a,b

和c，等式(a·b)·c=a·(b·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

總是成立的群叫做阿貝爾群（以尼爾斯·阿貝爾命名）。例子：整數(shù)配備上加法運算就形成一個群。第7頁，共31頁，2023年，2月20日，星期五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,·)形成一個半群，即：(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+bc其實是a+(b·c)。交換環(huán)：若環(huán)R中，(R,·)還滿足交換律，從而構成交換半群，即：?a，b∈R，有ab=ba，則R稱為交換環(huán)。第8頁，共31頁，2023年，2月20日，星期五9加密系統(tǒng)中常用數(shù)論知識域：是一種可進行加、減、乘和除（除了除以零之外）運算的代數(shù)結構，是數(shù)域以及四則運算的推廣；域分為兩種：無限域，元素個數(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)[x]/f(x)其中f(x)為GF(p)上不可約多項式第9頁，共31頁，2023年，2月20日，星期五10加密系統(tǒng)中常用數(shù)論知識歐拉定理若m,a為正整數(shù)，且m,a互素，(gcd(a,m)=1)，則aφ(m)≡1modm，其中φ(m)為歐拉函數(shù)，modm為同余關系。在數(shù)論中，對正整數(shù)n，歐拉函數(shù)φ(n)是小于或等于n的正整數(shù)中與n互質的數(shù)的數(shù)目。此函數(shù)以其首名研究者歐拉命名，它又稱為φ函數(shù)、歐拉商數(shù)等。例如φ(8)=4，因為1,3,5,7均和8互質。這個定理可以用來簡化冪的模運算。比如計算7222的個位數(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ù)論知識費馬定理費馬小定理是數(shù)論中的一個定理：假如a是一個整數(shù)，p是一個素數(shù)，那么：

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

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

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

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

1

Bx6+x4+x2+x+157x7+x+183+x7+x6+x4+x2D4二進制位異或x7+x6+1C1×a(x)×b(x)modm(x)這里選的M(x)所有次數(shù)為8的不可約多項式列表中的第一個如果a(x)×b(x)modm(x)=1那么稱b(x)為a(x)的逆元第22頁，共31頁，2023年，2月20日，星期五23有限環(huán)運算環(huán)和域的區(qū)別在于，域可以進行除法運算而環(huán)不可以；加法定義為簡單的比特位異或；兩個系數(shù)為GF(28)上的多項式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ù)每一輪迭代的結構都一樣，由下述4個不同的變換構成，只是最后一輪省略了列混合變換。

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