第2章密碼技術(shù)9.24

第2章密碼技術(shù)2.1密碼技術(shù)的基本概念2.2古典密碼體制2.3對稱密碼體系2.4公鑰（非對稱）密碼體制2.5橢圓曲線密碼體制學(xué)習(xí)目標知識點：密碼技術(shù)的基本概念，古典密碼體制如置換密碼、代換密碼，對稱密碼體制如流密碼、分組密碼、數(shù)據(jù)加密標準（DES）、高級加密標準（AES），公鑰密碼體制如公鑰密碼體制的基本原理、RSA算法、RSA算法與數(shù)字簽名、RSA算法與DES算法的特點等重點：古典密碼體制，數(shù)據(jù)加密標準（DES），高級加密標準（AES），公鑰加密體制的基本原理，RSA算法難點：AES算法、RSA算法2.1密碼技術(shù)的基本概念圖2.1傳統(tǒng)加密體制的基本過程加密過程：c=E（m，ke）解密過程：m=D（c，kd），所以有m=D（E（m，ke），kd）如果ke=kd，稱為單鑰或?qū)ΨQ密碼體制如果ke≠kd，稱為雙鑰或非對稱密碼體制于1976年由Diffie和Hellman等人所開創(chuàng)的新體制2.2古典加密技術(shù)2.2.1置換密碼置換密碼亦稱換位密碼。置換只是簡單的換位可用一個置換矩陣來Ek表示且都有一個與之對應(yīng)的逆置換Dk特點采用一個僅有發(fā)送方和接收方知道加密置換（用于加密）及對應(yīng)的逆置換（用于解密）只對明文中的字母位置進行重新排列，而每個字母本身并不改變令明文m=m0,m1,…,mL-1。令置換矩陣所決定的置換為π，則加密置換c=Ek(m)=(c0,c1,…,cL-1)=mπ(0),mπ(1),…,mπ(L-1)

解密置換舉例給定明文thesimplestpossibletranspositionciphers，將明文分為L=5的段，置換密碼如下舉例最后一段長不足5，加添一個字母x。將各段的字母序號按下述置換矩陣進行換位得到密文為:histepsemlpsstobteilapsrnsitoinpiocexshr利用下述置換矩陣：可將密文恢復(fù)為明文L=5時可能的置換矩陣總數(shù)為5！=120。一般為L!個。可以證明，在給定L下所有的置換矩陣構(gòu)成一個L!對稱群2.2.2代換密碼令Γ表示明文字母表，內(nèi)有q個“字母”或“字符”。設(shè)其順序號為：0,1,...,q-1，可以將Γ映射為一個整數(shù)集Zq={0,1,2,…,q-1}，在加密時常將明文信息劃分為長為L的信息單元，稱為明文組。以m表示，如m=(m0,m1,…,mL-1),mi∈Zq令?！浔硎久魑淖帜副恚瑑?nèi)有q′個“字母”或“字符”。設(shè)其順序號為：0,1,...,q′-1，可以將?！溆成錇橐粋€整數(shù)集Zq′={0,1,2,...,q′-1}，密文組為c=(c0,c1,…,cL′-1),ci∈Zq′，代換密碼的加密變換是由明文空間到密文空間的映射f:m→c,m∈Γ,c∈Γ′假定函數(shù)f是一對一的映射，那么，給定密文c，有且僅有一個對應(yīng)的明文組m，即對于f存在逆映射f-1，使f-1(c)=f-1f(m)=m加密變換通常是在密鑰控制下進行的，即c=f(m,k)=Ek(m)

1．單表代換密碼單表代換密碼是對明文的所有字母都用同一個固定的明文字母表到密文字母表的映射，即f:Zq→Zq'若明文為m=m0,m1,……,則相應(yīng)的密文為c=c0,c1,….=f(m0),f(m1),…1）位移代換密碼位移代換密碼是最簡單的一種代換密碼，其加密變換為Ek(i)=(i+k)≡jmodq0≤i,j<q,0≤k<q密鑰空間元素個數(shù)為q，其中有一恒等變換，k=0，解密變換為D(j)≡imodq舉例如凱撒密碼變換是對英文26個字母進行位移代換的密碼，即將每一字母向前推移k位。若q=26，如選擇密鑰k=5，則有下述變換:

明文：abcdefghijklmno

密文：fghIjklmnopqrst2）乘數(shù)密碼--也稱采樣密碼其加密變換為

:Ek(i)=i*k≡jmodq0≤j<q是將明文字母表按序號每隔k位取出一個字母排列而成密文特點:當(dāng)且僅當(dāng)(k,q)=1，加密交換才是一一對應(yīng)缺點:對于英文序列密文所對應(yīng)的密鑰非常有限，即q只能取:1357911151719212325舉例如英文字母表q=26，選k=9，則由明文密文字母對應(yīng)表明文:abcdefghijklmnopqrstuvwxyz密文:AJSBKTCLUDMVENWFOXGPYHQZIR對明文：Multiplicativercipher有密文：EYVPUFVUSAPUHKSUFLKX3）仿射密碼將移位密碼和乘數(shù)密碼進行組合即 Ek(i)=ik1+k0≡jmodqk1,k0∈Zq，其中，(k1,q)=1,以［k1,k0］表示密鑰。當(dāng)k0=0時就得到乘數(shù)密碼，當(dāng)k1=1時就得到位移密碼，q=26時可能的密鑰數(shù)為26×12-1=311個2．多表代換密碼多表代換密碼是一系列（兩個以上）代換表依次對明文信息的字母進行代換的加密方法維吉尼亞密碼加密算法是多表密碼的典型代表。方法如下：設(shè)密鑰k=k1,k2,…,kn，明文m=m1,m2,…,mn，加密變換為Ek(m)=c1,c2,…,cn

，其中ci≡（mi+ki）modqi=1,2,…,n舉例如，令q=26，明文m=polyalphabeticcipher，k=RADIO，即周期為5。首先將m分解成長為5的序列:

polyalphabeticcipher

每一段用密鑰k=RADIO加密得密文：

c=GOOGOCPKTPNTLKQZPKMF2.3對稱密碼體系2.3.1流密碼流密碼也稱為序列密碼，其原理是對輸入的明文串按比特進行連續(xù)變換，產(chǎn)生連續(xù)的密文輸出信道ciD(ki,ci)cimiE(ki,mi)mi

密鑰流生成器kiki

密鑰流生成器

k

k安全信道流密碼的基本思想密鑰:k，產(chǎn)生一個密鑰流為k=k1k2…ki…明文串:m=m1m2…mi…加密：密鑰流發(fā)生器f：ki=f(k,σi)σi是加密器中的記憶元件（存儲器）在時刻i的狀態(tài)，f是由密鑰k和σi產(chǎn)生的函數(shù)根據(jù)加密器中記憶元件的存儲狀態(tài)σi是否依賴于輸入的明文字符，流密碼可分為同步流密碼：σi獨立于明文字符自同步流密碼：σi不獨立于明文字符。由于自同步流密碼的密鑰流的產(chǎn)生與明文有關(guān)，因而較難從理論上進行分析。目前大多數(shù)研究成果都是關(guān)于同步流密碼的1.同步流密碼在同步流密碼中，由于ki=f(k,σi)與明文字符無關(guān)，因而此時密文字符ci=Eki(mi)也不依賴于此前的明文字符同步流密碼特點只要通信雙方的密鑰序列產(chǎn)生器具有相同的“種子序列”和相同的“初始狀態(tài)”,就能產(chǎn)生相同的密鑰序列通信雙方必須保持精確同步,才能正確解密容易檢測插入、刪除、重放等主動攻擊沒有差錯傳播2.自同步流密碼產(chǎn)生密鑰序列的算法與以前的密文有關(guān)自同步流密碼的特點密鑰流生成器是一種有記憶變換器密鑰流與明文符號有關(guān)：i時刻的密文不僅取決于i時刻的明文，而且與i時刻之前的l個明文符號有關(guān)具有自同步能力把明文每個字符擴散在密文多個字符中,強化了抗統(tǒng)計分析的能力3.密鑰流生成器流密碼的關(guān)鍵是密鑰生成器ki序列密碼系統(tǒng)中密鑰序列設(shè)計應(yīng)考慮如下因素：系統(tǒng)的安全保密性；密鑰易于分配、保管、更換；產(chǎn)生密鑰序列簡單、快速為達到安全保密性要求，序列密碼的密鑰序列應(yīng)滿足偽隨機準則：極大的周期良好的隨機統(tǒng)計特性，即序列中每位接近均勻分布序列線性不可預(yù)測性充分大(抗線性分析)抗統(tǒng)計分析4．線性反饋移位寄存器產(chǎn)生密鑰流序列的最重要部件是線性反饋移位寄存器LFSR（linearfeedbackshiftregister）,是因為:LFSR非常適合于硬件實現(xiàn)能產(chǎn)生大的周期序列能產(chǎn)生較好統(tǒng)計特性的序列其結(jié)構(gòu)能應(yīng)用代數(shù)方法進行很好的分析如果反饋函數(shù)f(a1,a2,…,an)是(a1,a2,…,an)的線性函數(shù)，則稱之為線性反饋移位寄存器，否則稱為非線性移位寄存器n級反饋移位寄存器2.3.2分組密碼也稱塊密碼分組密碼加密是在密鑰的控制之下，將定長的明文塊轉(zhuǎn)換成等長密文的技術(shù)。分組密碼使用同一密鑰通過逆向變換來實現(xiàn)解密加密算法解密算法明文m=(m0,m1,…,mn-1)

密文c=(c0,c1,…,cn-1)明文m=(m0,m1,…,mn-1)密鑰k=(k0,k1,…,kt-1)

密鑰k=(k0,k1,…,kt-1)2.3.2分組密碼在分組密碼中，必須處理一個問題——填充在分組加密中，要求填充是可逆的假定塊長度為8字節(jié)，要加密的明文數(shù)據(jù)長度為9字節(jié)。那么消息被切成兩個塊，第二塊只有1個字節(jié)，需要填充7個字節(jié)。如果把9字節(jié)的明文數(shù)據(jù)記為：F1F2F3F4F5F6F7F8F9Zeros填充算法：需要填充的7個字節(jié)全部填充為0，分組結(jié)果為：第一個消息分組：F1F2F3F4F5F6F7F8第二個消息分組：F900000000000000Zeros填充算法無法區(qū)分第二個消息分組中F9后的0序列是否是明文中的原始序列，因此該填充算法不可逆

X923填充算法：需要填充的7個字節(jié)中前6個字節(jié)填充0，最后一個字節(jié)記錄填充的總字節(jié)數(shù)，分組結(jié)果為：第一個消息分組：F1F2F3F4F5F6F7F8第二個消息分組：F900000000000007PKCS7填充算法：需要填充的7個字節(jié)中的每一個字節(jié)填充需要填充的總字節(jié)數(shù)，分組結(jié)果為：第一個消息分組：F1F2F3F4F5F6F7F8第二個消息分組：F907070707070707

ISO10126填充算法：需要填充的7個字節(jié)中前6個字節(jié)填充隨機字節(jié)序列，最后一個字節(jié)記錄填充的總字節(jié)數(shù)，分組結(jié)果為：第一個消息分組：F1F2F3F4F5F6F7F8第二個消息分組：F97D2A75EFF8EF07迭代的分組密碼是在加密過程有多次循環(huán)的密碼，因此提高了安全性。在每個循環(huán)中，可以通過使用特殊的函數(shù)從初始密鑰派生出的子密鑰來進行適當(dāng)?shù)淖儞Q分組密碼的主流算法包括：DES、AES、IDEA、SAFER、Blowfish和Skipjack迭代密碼明文：X=Y(0)密文：Y=Y(r)迭代函數(shù):F迭代次數(shù):r種子密鑰：k迭代的子密鑰：Z(i)Feistel密碼結(jié)構(gòu)是基于1949年Shannon提出的交替使用代換和置換方式構(gòu)造密碼體制的設(shè)想提出的Feistel密碼Feistel加密結(jié)構(gòu)子密鑰產(chǎn)生算法

KK1,K2,…,Kh明文:m=L0||R0第i輪迭代

Li=Ri-1

Ri=Li-1F(Ri-1,Ki)F:輪函數(shù)密文:c=Lh+1||Rh+1代換-置換網(wǎng)絡(luò)(substitution-permutationnetwork)FL1R1K1L0(w-bit)R0(w-bit)

明文:m(2w-bit)FLiRiKi….….….….FLhRhKhLh+1Rh+1

密文:c(2w-bit)Feistel分組密碼的一個加密階段示意圖其中S操作通過密鑰為每一個階段生成一個子密鑰，T為每一輪加密過程中的核心操作，要求為非線性運算，保證加密算法的安全性明文LRL’R’TS替換置換密鑰Feistel解密結(jié)構(gòu)與加密結(jié)構(gòu)相同子密鑰使用次序相反:

Kh,Kh-1,…,K2,K1輸入：密文c輸出：明文mFL1R1KhL0(w-bit)R0(w-bit)

密文:c(2w-bit)FLiRiKi….….….….FLhRhK1Lh+1Rh+1

明文:m(2w-bit)2.3.3數(shù)據(jù)加密標準（DES）數(shù)據(jù)加密標準（DataEncryptionStandard，DES）：DES算法使用了56位的密鑰以及附加的8位奇偶校驗位，形成的分組大小最大為64位DES算法采用一個迭代的分組密碼，實現(xiàn)中使用Feistel技術(shù)DES算法描述分組大小:2w=64密鑰大小:|K|=56

子密鑰:|Ki|=48輪數(shù):h=16對明文作置換IP后開始第1次迭代第16次迭代后，交換左、右32bit數(shù)據(jù)，再作逆置換IP-1，即得密文FL1R1K1….….….….FL16R16K16L0(32bit)R0(32bit)明文:m(64bit)

IP密文:c(64bit)

IP-1數(shù)據(jù)加密標準（DES）初始置換IP將64位明文打亂重新排列設(shè)m=m1m2…m64，則IP(m)=m58m50m42…m23m15m7IPIP15850423426181026052443628201246254463830221486456484032241665749413325179159514335271911361534537292113563554739312315740848165624643239747155523633138646145422623037545135321612936444135220602835343115119592734242105018582633141949175725輪函數(shù)F的設(shè)計輪函數(shù)F的結(jié)構(gòu)

F(Ri1,Ki):{0,1}32{0,1}48{0,1}32

F

Ki(48)….….LiRi….….Li-1Ri-1Ki(48)Ri-1(32)

E

F(Ri-1,Ki)置換P

S7

S6

S5

S4

S3

S2

S1

S8

擴展變換E擴展變換E:

將32位變?yōu)?8位，擴展了16位擴展變換E3212345456789891011121312131415161716171819202120212223242524252627282928293031321S-盒Sk:{0,1}6{0,1}4(k=1,2,…,8)輸入:b1b2b3b4b5b6,用10進制表示:(i)10=b1b6(0i3),(j)10=b2b3b4b5(0j15)輸出:Sk-盒的表中第i行j列位置元素(4位二進制)例:對于S1，輸入b=101011,有i=11=3--行,j=0101=5--列,

輸出:S1(b)=S1(3,5)=9=1001Sk0123456789101112131415

S1012314413121511831061259070157414213110612119538411481362111512973105015128249

17511314100613S－盒11441312151183106125907015741421311061211953841148136211151297310501512824917511314100613S—盒的輸出表示設(shè)對應(yīng)S－盒1的輸入序列為：行號：11即3列號：0111即70123

012345689101112131415結(jié)果為7即01117置換PP：整數(shù)1-32的置換置換P1672021291228171152326518311028241432273919133062211425總結(jié)：輪函數(shù)F(Ri-1,Ki)運算過程

Ri-1e=E(Ri-1)c=eKis=S(c)P(s)=F(Ri-1,Ki)=P(S(E(Ri-1)Ki))DES子密鑰生成算法

由64位密鑰K產(chǎn)生16個48位的子密鑰:

K1,K2,…,K16.DES子密鑰生成算法

LS1

LS1

C1

D1

K1

PC-2….….

LS2

LS2

C2

D2

K2

PC-2

LS16

LS16

C16

D16

K16

PC-2

密鑰:K(64bit)

PC-1

C0

D0

(48bit)(48bit)(48bit)(28bit)(28bit)置換選擇1:PC-1

64位密鑰K的第8,16,24,…,64位共8位是奇偶校驗位,其余56位作為密鑰用.選擇K的第57,49,…位共28位作為密鑰段C0;選擇K的第63,55,…位共28位作為密鑰段D0DES子密鑰生成算法PC-157494133251791585042342618102595143352719113605244366355473931231576254463830221466153453729211352820124DES子密鑰生成算法循環(huán)左移LSi

將28位的密鑰段作為Ci,Di循環(huán)左移1或2位,左移位數(shù)由下表確定.

i12345678910111213141516LSi1122222212222221置換選擇2:PC-2

從56位密鑰段Ci||Di中選擇48位作為子密鑰Ki.DES子密鑰生成算法PC-2

1417112415328156211023191242681672720132415231374755304051453348444939563453464250362932DES解密算法與DES加密結(jié)構(gòu)相同子密鑰使用次序相反:

K16

K15,…,K2,K1輸入：密文c輸出：明文mf1K0R1L=16K）bit密文（

64IP逆置換IP置換…明文（64bit）0R(32bit)0L1R?=),(0Rf1K15L16R?=),(15Rf16Kf…f

的擴展變換0R循環(huán)左移壓縮置換密鑰置換fS—盒1Kp—盒0L1R?=),(0Rf1K0L(32bit)15R16L=

(2)IDEA國際數(shù)據(jù)加密算法IDEA（InternationalDataEncryptionAlgorithm）:IDEA是作為迭代的分組密碼實現(xiàn)的，使用128位的密鑰和8個循環(huán)。這比DES提供了更多的安全性，但是在選擇用于IDEA的密鑰時，應(yīng)該排除那些稱為“弱密鑰”的密鑰。DES只有四個弱密鑰和12個次弱密鑰，而IDEA中的弱密鑰數(shù)相當(dāng)可觀，有251個。但是，如果密鑰的總數(shù)非常大，達到2128個，那么仍有277個密鑰可供選擇2.3.4高級加密標準(AES)

1.AES算法的概念

AES算法的輸入和輸出都是長度為128bit的序列串，序列中每個位的值為0或1。這些序列在算法中稱為數(shù)據(jù)分組(block)，序列包含的位(bit)數(shù)也稱為分組長度。AES算法使用128bit、192bit或256bit長度的密鑰。算法不支持其他的輸入、輸出長度和密鑰長度

1）字節(jié)(byte)

AES算法中的基本運算單位是字節(jié)(byte)，即作為一個整體的8bit二進制序列。算法的輸入數(shù)據(jù)、輸出數(shù)據(jù)和密鑰都以字節(jié)為單位，明文、密鑰和密文數(shù)據(jù)串被分割成一系列8個連續(xù)比特的分組，并形成字節(jié)數(shù)組。假設(shè)一個8字節(jié)的分組b是由字節(jié)序列{b7,b6,b5,b4,b3,b2,b1,b0}所組成的，則可將bi看做一個7次多項式b(x)的系數(shù)，即b(x)=b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x1+b0

式中，bi∈{0,1}。例如，{01010111}表示成多項式為x6+x4+x2+x+1也可以使用十六進制符號來表示字節(jié)值，將每4bit表示成一個符號便于記憶。例如，{01010111}={57}。

2）字節(jié)數(shù)組輸入序列按字節(jié)劃分，表示形式如下：

3）狀態(tài)（State）

AES算法的運算都是在一個二維字節(jié)數(shù)組上完成的，這個數(shù)組稱為狀態(tài)。當(dāng)輸入的明文序列轉(zhuǎn)換成字節(jié)數(shù)組后，進一步將一維的字節(jié)數(shù)組內(nèi)容轉(zhuǎn)換為二維排列，就形成了狀態(tài)矩陣。一個狀態(tài)矩陣由四行組成，每一行包括Nb個字節(jié)，Nb的值等于分組長度除以32。狀態(tài)矩陣用s表示，每一個字節(jié)的位置由行號r(范圍是0≤r<4)和列號c(范圍是0≤c＜Nb)惟一確定，記為sr,c或s［r,c］。在AES標準中狀態(tài)矩陣參數(shù)Nb=4，即0≤c＜4圖2.4

AES加解密狀態(tài)矩陣運算式中：0≤r＜4；0≤c＜Nb。在加密和解密的完成階段，狀態(tài)矩陣采用以下規(guī)則轉(zhuǎn)換，結(jié)果存儲在輸出數(shù)組out中：其中，0≤r＜4,0≤c＜Nb

4）狀態(tài)矩陣列數(shù)組狀態(tài)矩陣中每一列的4個字節(jié)是一個32位長的字，行號r是這個字中每個字節(jié)的索引，因此狀態(tài)矩陣可以看做32位字(列)長的一維數(shù)組，列號c是該數(shù)組的列索引。由此上例中的狀態(tài)可以看做4個字組成的數(shù)組，表示如下：

2.有限域基本數(shù)學(xué)運算

AES算法的基本思想是基于置換和代替變換的演算方法。其中，置換是對數(shù)據(jù)的重新排列，而代替則是用數(shù)據(jù)替換另一個。AES算法中的所有字節(jié)按照每4位表示成有限域GF（28）中的一個元素AES密碼中的運算是按字節(jié)（8位）或4字節(jié)的字（32位）定義的在AES密碼中，一個字節(jié)可看作有限域GF(28)中的一個元素，對應(yīng)于一個系數(shù)在GF(2)中的次數(shù)小于8的多項式--面向字節(jié)的運算GF(28)的元素8bit的字節(jié)=8維二元向量

b=b7b6b5b4b3b2b1b0=(b7,b6,b5,b4,b3,b2,b1,b0)次數(shù)不超過8的二元多項式

bb(x)=b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x1+b0.例:b=10011011=(1,0,0,1,1,0,1,1)b(x)=x7+x4+x3+x+1.GF(28)的加法:對應(yīng)位mod2相加例:a=01101111a(x)=x6+x5+x3+x2+x+1,ab=0110111110011011=11110100,

a(x)b(x)=x6+x5+x3++x2+x+1x7+x4+x3+x+1

=x7+

x6+x5+x4+x2.

GF(28)的乘法“”模多項式:m(x)=x8+x4+x3+x+1.兩個多項式相乘:將積按m(x)取模乘法逆元:如果a(x)與b(x)滿足:a(x)b(x)=1(modm(x))

則稱b(x)是a(x)的乘法逆元，記為b(x)=a(x)-1.例:設(shè)a(x)=x6+x4+x2+x+1,b(x)=x7+x+1,則

a(x)b(x)=(x6+x4+x2+x+1)(x7+x+1)=x13+x11+x9+x8+x6+x5+x4+x3+1=x7+x6+1(modm(x))又例:用16進制表示字節(jié)

(B2)(84)=(11000010)(10000100)

=(x7+x6+x)(x7+x2)=x14+x13+x9+x3=x7+x6+x5+x3+1

(modm(x))=11101001=(D9).（xtime()，乘x）將上面的結(jié)果模m(x)求余就得到xb(x)，顯然有：考察GF(28)上的多項式x乘以多項式b(x)

x

上述分析說明：xtime()可用字節(jié)內(nèi)左移一位和緊接著的一個與1b（十六進制）的條件比特異或來實現(xiàn)高次乘法可通過重復(fù)應(yīng)用xtime()來實現(xiàn)通過將中間結(jié)果相加，任意乘法都可以利用xtime()來實現(xiàn)倍乘函數(shù)(x乘)(02)b(x)=xb(x)=xtime(b),

(04)b(x)=x2b(x)=x(xb(x))=x(xtime(b))=xtime(xtime(b))，

(08)b(x)=x(x2b(x))=xtime(xtime(xtime(b))).例:計算571313=00010011=x4+x+1,x57=xtime(57)=AE,

x457=xtime(xtime(xtime(xtime(57))))=xtime(xtime(xtime(AE)))=xtime(xtime(47))=xtime(8E)=07.5713=57x57x457=57AE07=FE系數(shù)在GF(28)域的特殊多項式--面向4個字節(jié)的運算設(shè)變換多項式為：輸入多項式為：它們的乘積是次數(shù)不超過6的多項式

c(x)=c6x6+c5x5+c4x4+c3x3+c2x2+c1x+c0c0=a0

b0

c4=a3

b1

a2

b2

a1

b3

c1=a1

b0

a0

b1

c5=a3

b2

a2

b3

c2=a2

b0

a1

b1

a0

b2

c6=a3

b3c3=a3

b0

a2

b1

a1

b2

a0

b3取M(x)=x4

1令：兩個四字節(jié)字之間的乘法變換可表示為：d0=b0a0+b1a3+b2a2+b3a1d1=b0a1+b1a0+b2a3+b3a2d2=b0a2+b1a1+b2a0+b3a3d3=b0a3+b1a2+b2a1+b3a0關(guān)于乘法的實現(xiàn)（xtime()，x乘法）將上面的結(jié)果模M(x)求余就得到xb(x)，顯然有考察系數(shù)在GF(28)上的多項式x乘以多項式b(x)對于該變換，當(dāng)輸入為：(b3,b2,b1,b0)時輸出為：(b2,b1,b0,

b3)因此，用x或x的方冪乘GF(28)上的多項式等價于一個字中字節(jié)的左循環(huán)移位。注：x對應(yīng)一個4字節(jié)字，（00，00，01，00）AES加密算法AES加密算法結(jié)構(gòu)AES的流程圖加密算法結(jié)構(gòu)將待加密的明文分組以字節(jié)為單位填充狀態(tài)矩陣（4×Nb字節(jié)矩陣），做初始密鑰加變換進行Nr輪迭代，每輪包含四個變換：（1）字節(jié)代替變換；（2）行移位變換；（3）列混疊變換；（4）輪密鑰加變換（按位異或）注：最后一圈（第Nr圈）省略列混疊變換第Nr圈的輸出即為密文（輸出狀態(tài)）AES加密算法數(shù)據(jù)長度可變明文、密文分組長度:lm=128,192,256密鑰長度:

lk=128,192,256加密過程的中間結(jié)果稱為“狀態(tài)(state)”將每次變換的狀態(tài)以字節(jié)為單位表示成一個4行Nb列的矩陣.

Nb=lm/32=4,6,8.lm=192,Nb=6時的狀態(tài)表示s00s01s02s03s04s05s10s11s12s13s14s15s20s21s22s23s24s25s30s31s32s33s34s35密鑰k的表示將密鑰k以字節(jié)為單位表示成一個4行Nk列的矩陣.Nk=lk/32=4,6,8.lk=128,Nk=4時的密鑰表示k00k01k02k03k10k11k12k13k20k21k22k23k30k31k32k33迭代輪數(shù)NrNrNb=4Nb=6Nb=8Nk=4101214Nk=6121214Nk=8141414AES的輪函數(shù)字節(jié)代換:ByteSub對狀態(tài)的每個字節(jié)獨立進行代換，是字節(jié)的非線性變換，也稱為S盒變換。設(shè)

ByteSub(aij)=bija00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35b00b01b02b03b04b05b10b11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b35aijbijByteSubAES的輪函數(shù)字節(jié)代換：ByteSub(aij)=bij.第1步:求乘法逆元(GF(28)中的乘法)，‘00’的逆元為自己‘00’aijaij-1第2步:

對aij-1作仿射變換

字節(jié)代替變換實際上是一個8進8出的S盒。設(shè)xy(16進制表示)為狀態(tài)中的一個字節(jié)，則代替表(S盒)中第x行第y列的字節(jié)就是對應(yīng)的字節(jié)代替變換的結(jié)果AESS-盒算法設(shè)x=00001001轉(zhuǎn)換為16進制09行列查詢S盒AES算法的“S－盒”

16BB54B00F2D99416842E6BF0D89A18CFDF2855CEE9871E9B948ED9691198F8E1E9E1DC186B95735610EF6034866B53E70D8A8BBD481F74DDE8C6B4A61C2E2578BAC08AE7A65EAF4566CA94ED58D6D37C8E7B79E4959162ACD3C25C2406490A3A32E0ADB0B5EDE14B8EE4688902A22DC4F8160973195D643D7EA7C41744975FEC130CCD8D2F3FF1021DAB6BCF5389D928F40A3517A89F3C507F02F94585334D43FBAAEFD06CF584C4A39BECB6A5BB1FC20ED00D1535842FE329B3D63B52A05A6E1B1A2C8309475B227EBE28012079A059618C323C70431531D871F1E5A534CCF73F362693FDB72C072A49CAFA2D4ADF04759FA7DC982CA176ABD7FE2B670130C56F6BF27B777C630FEDCBA9876543210y返回AES的輪函數(shù)行移位:ShiftRow將狀態(tài)矩陣的每行進行循環(huán)左移:

第0行不移;第i行循環(huán)左移Ci

個字節(jié)(i=1,2,3)a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35Nb

C1C2C3412361238134a00a01a02a03a04a05a11a12a13a14a15a10a22a23a24a25a20a21a33a34a35a30a31a31AES的輪函數(shù)列混合:MixColumn將狀態(tài)矩陣每一列的4個字節(jié)表示成一個3次多項式，再與多項式c(x)相乘

c(x)=(03)x3+(01)x2+(01)x+(02)a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35例如:對于第2列,a(x)=a31x3+a21x2+a11x+a01,

則MixColumn(a(x))=a(x)c(x)(modM(x))=b31x3+b21x2+b11x+b01b00b01b02b03b04b05b10b11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b35依次按列進行處理，每列是一個四字節(jié)的字=AES的輪函數(shù)輪密鑰加:AddRoundKey(State,RoundKey)將狀態(tài)矩陣與子密鑰矩陣的對應(yīng)字節(jié)進行逐比特異或

AddRoundKey(aij,kij)=aij

kij例：a21

k21=b21a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31

a32a33a34a35b00b01b02b03b04b05b10b11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b35k00k01k02k03k04k05k10k11k12k13k14k15k20k21k22k23k24k25k30k31

k32k33k34k35AES的輪密鑰生成輪密鑰生成算法=密鑰擴展+輪密鑰選取密鑰擴展:將密鑰k擴展為擴展密鑰W[Nb(Nr+1)]W是以4個字節(jié)為元素的一維數(shù)組,共有Nb(Nr+1)個元素W的前Nk個元素正好是密鑰k,其他元素由擴展算法求出kW[1]W[Nk]W[Nk+1]W[Nb(Nr

+1)]

4.AES解密

AES的解密算法與加密算法不同，是加密過程的逆運算。解密算法中各個變換的操作順序與加密算法不同，但是加密和解密算法中的密鑰編排形式是一致的。解密算法中使用的變換依次為逆列混疊(InvMixColumns)變換、逆行位移變換(InvShiftRows)、逆字節(jié)替換變換(InvSubBytes)和輪密鑰加變換(AddRoundKey)，變換作用在密文序列對應(yīng)的狀態(tài)矩陣上AES解密過程2.4公鑰（非對稱）密碼體制2.4.1公鑰密碼體制的基本概念公鑰體制下，一個用戶可以將自己設(shè)計的加密公鑰和加密算法對外公布，而只保留解密用的私鑰。任何人都可以獲取這個用戶的加密公鑰和加密算法，并向該用戶發(fā)送加密過的信息，該用戶接收后可以使用私鑰還原消息。在這個公鑰加解密的過程中，會涉及到公私密鑰對、數(shù)字證書以及電子簽證機關(guān)等主要內(nèi)容

1.密鑰對在基于公鑰體系的安全加密系統(tǒng)中，密鑰生成過程每次都產(chǎn)生一個公鑰和一個私鑰，形成加密和解密的密鑰對。在實際應(yīng)用中，私鑰由用戶私人保存，而公鑰則通過某種手段對外公布。公鑰體系的基礎(chǔ)問題是公鑰的分發(fā)與管理，這是電子商務(wù)等業(yè)務(wù)系統(tǒng)能夠廣泛應(yīng)用的基礎(chǔ)

2.數(shù)字證書公開密鑰體系需要在開放環(huán)境下使用，公鑰加密體系采取將公鑰和公鑰的主人名字聯(lián)系在一起的方法，再請一個有信譽的公正權(quán)威機構(gòu)對每個公鑰和所有者身份進行確認，確認后的公鑰信息加上這個權(quán)威機構(gòu)的簽名，就形成了數(shù)字證書，也稱為證書。證書就是用戶在網(wǎng)上的電子個人身份證，在電子商務(wù)中的作用同日常生活中使用的個人身份證作用一樣

3.電子簽證機關(guān)電子簽證機關(guān)（即CA）是負責(zé)頒發(fā)數(shù)字證書的權(quán)威機構(gòu)。CA自身擁有密鑰對，可以使用私鑰完成對其他證書的數(shù)字簽名，同時也擁有一個對外開放的證書（內(nèi)含公鑰）。網(wǎng)上的公眾用戶通過驗證CA的數(shù)字簽名建立信任，任何人都可以得到CA的證書（含公鑰），用以驗證它所簽發(fā)的其他證書通常意義上的密碼學(xué)(Cryptography)技術(shù)主要用來保護信息傳遞的機密性。但是在電子交易環(huán)境下，對信息發(fā)送與接收人的真實身份的驗證、發(fā)送及接受信息的事后不可抵賴性以及保障數(shù)據(jù)的完整性，是另一個極為重要的問題公開密鑰密碼體制不僅可解決信息的保密性問題，還可以完成對信息傳遞雙方真實身份的驗證和數(shù)據(jù)完整性驗證RSA系統(tǒng)是公鑰密碼體系中應(yīng)用最為廣泛、影響力最大的一種公鑰加密體制具有以下優(yōu)點密鑰分配相對簡單，不需要復(fù)雜的流程密鑰的保存量少，且私鑰和公鑰分別存儲可以實現(xiàn)互不相識的人之間進行私人通信時的保密性要求可以完成通信雙方的數(shù)字簽名和數(shù)字身份鑒別2.4.2公鑰密碼體制的原理公鑰密碼體系中由于公鑰與私鑰之間存在依存關(guān)系，因此，信息使用公鑰加密后，只有私鑰擁有者本人才能解密該信息，任何未授權(quán)用戶甚至信息的發(fā)送者都無法將此信息解密。近代公鑰密碼系統(tǒng)的研究主要基于難解的可計算問題，該方法保證了整個體系和算法的安全性。常用的難解可計算問題包括：大數(shù)分解問題計算有限域的離散對數(shù)問題平方剩余問題橢圓曲線的對數(shù)問題等2.4.3RSA算法目前最流行的公開密鑰算法是1977年由RonaldL.Rivest、AdiShamir和LeonardM.Adleman共同提出的，算法名字的三個字母分別取三名數(shù)學(xué)家名字的首字母。RSA算法的理論基礎(chǔ)是數(shù)論中的歐拉定理，該算法的安全性完全依賴于大數(shù)因子分解的困難些歐拉定理歐拉定理若整數(shù)a和m互素，則式中，φ(m)為比m小，是與m互素的正整數(shù)個數(shù)求最大公因子Euclid算法是基于下面一個基本結(jié)論：對任意非負整數(shù)a和正整數(shù)b，有g(shù)cd(a,b)=gcd(b,amodb)如：gcd(55,22)=gcd(22,55mod22)=gcd(22,11)=gcd(11,0)=11在求兩個數(shù)的最大公因子時，可重復(fù)使用以上結(jié)論例如：gcd(18,12)=gcd(12,6)=gcd(6,0)=6， gcd(11,10)=gcd(10,1)=gcd(1,0)=1求gcd(1970,1066)。1970=1×1066+904, gcd(1066,904)1066=1×904+162, gcd(904,162)904=5×162+94, gcd(162,94)162=1×94+68, gcd(94,68)94=1×68+26, gcd(68,26)68=2×26+16, gcd(26,16)26=1×16+10, gcd(16,10)16=1×10+6, gcd(10,6)10=1×6+4, gcd(6,4)6=1×4+2, gcd(4,2)4=2×2+0, gcd(2,0)因此gcd(1970,1066)=2

大整數(shù)分解若已知兩個大素數(shù)p、q，求n=p×q僅需一次乘法，但已知n求p、q則是幾千年來數(shù)論專家的一道難題。已知的各種算法有：試除法、二次篩、數(shù)域篩、橢圓曲線。其中RSA問題是FAC問題的特例。n是兩個素數(shù)p、q之積，給定n以后求p、q的問題稱為RSA問題。求n=p×q分解問題有以下幾種形式：分解整數(shù)n為p、q；給定整數(shù)M、C，求d使得Cd≡Mmodn；給定整數(shù)k、C，求M使得Mk≡Cmodn；給定整數(shù)x、C，決定是否存在y使得x≡y2modn（二次剩余問題）則A收到密文c以后，用只有自己才知道的解密密鑰ka′對c進行解密得公鑰密碼體制的原理加解密模型認證模型對稱密鑰和公鑰密鑰

1.RSA密鑰的產(chǎn)生

RSA密鑰的產(chǎn)生過程如下：選擇兩個大素數(shù)p、q，選擇的素數(shù)要保密計算n=pq(p、q分別為兩個互異的大素數(shù)，n的長度大于512bit，這主要是因為RSA算法的安全性依賴于大數(shù)因子分解問題)。歐拉函數(shù)為φ(n)=(p-1)(q-1)隨機選擇加密密鑰e，要求e和φ(n)互質(zhì)利用Euclid算法計算解密密鑰d，應(yīng)滿足d×e≡1modφ(n)，其中n和d也要互素。數(shù)e和n是公鑰，d是私鑰。兩個素數(shù)p、q不再需要，應(yīng)該丟棄，不要讓任何人知道

2.RSA加密加密信息（二進制表示）時，首先把分成等長數(shù)據(jù)塊m1,m2,m3,...,mi,塊長s，其中2s≤n,s要盡可能的大對應(yīng)的密文是：3.RSA解密 對加密消息進行解密計算時，計算例：RSA加解密設(shè)p=11，q＝23，則n＝pq＝11×23＝253φ(n)＝(p－1)(q－1)＝10×22＝220

選取e＝3，顯然gcd(e,φ(n))＝gcd(3,220)＝1

計算d＝e-1modφ(n)–220＝22×5×11–φ(220)＝220×1/2×4/5×10/11＝80–d＝3-1mod220＝380-1mod220＝147

明文空間Zn

={0,1,2,…,251,252}

公鑰(3,253)，私鑰(147,253)

加密：對于明文m＝165，密文c＝1653mod253＝110

解密：對于密文c＝110，明文m＝110147mod