現(xiàn)代密碼學(xué)基礎(chǔ)

現(xiàn)代密碼學(xué)基礎(chǔ)徐江峰鄭州大學(xué)信息工程學(xué)院E-mail:jfxu@2008年5月緒論古典密碼學(xué)密碼學(xué)信息論基礎(chǔ)對(duì)稱(chēng)加密技術(shù)非對(duì)稱(chēng)加密技術(shù)數(shù)字簽名Hash函數(shù)身份認(rèn)證密鑰管理課程內(nèi)容參考文獻(xiàn)應(yīng)用密碼學(xué)－－協(xié)議、算法與C源程序

(美)BruceSchneier

著，吳世忠、祝世雄、張文政譯密碼編碼和密碼分析－－原理與方法

(德)F.L.Bauer著，吳世忠、宋曉龍、李守鵬譯密碼編碼學(xué)與網(wǎng)絡(luò)安全－－原理與實(shí)踐

(美)WilliamStallings著劉玉珍、王麗娜、傅建明譯計(jì)算機(jī)密碼學(xué)盧開(kāi)澄編著現(xiàn)代密碼學(xué)基礎(chǔ)章照止主編

緒論古典密碼學(xué)密碼學(xué)信息論基礎(chǔ)對(duì)稱(chēng)加密技術(shù)非對(duì)稱(chēng)加密技術(shù)數(shù)字簽名Hash函數(shù)身份認(rèn)證密鑰管理課程內(nèi)容密碼學(xué)發(fā)展歷史密碼學(xué)中的術(shù)語(yǔ)緒論密碼學(xué)發(fā)展歷史1949年之前密碼學(xué)是一門(mén)藝術(shù)1949～1975年密碼學(xué)成為科學(xué)1976年以后密碼學(xué)的新方向——公鑰密碼學(xué)第1階段－古典密碼密碼學(xué)還不是科學(xué),而是藝術(shù)出現(xiàn)一些密碼算法和加密設(shè)備密碼算法的基本手段出現(xiàn)，針對(duì)的是字符簡(jiǎn)單的密碼分析手段出現(xiàn)主要特點(diǎn)：數(shù)據(jù)的安全基于算法的保密Phaistos圓盤(pán)，一種直徑約為160mm的Cretan-Mnoan粘土圓盤(pán)，始于公元前17世紀(jì)。表面有明顯字間空格的字母，至今還沒(méi)有破解。第1階段—古典密碼20世紀(jì)早期密碼機(jī)Kerckhoff加密原則

1883年Kerckhoff第一次明確提出了編碼的原則,該原則已得到普遍承認(rèn)，成為傳統(tǒng)密碼和現(xiàn)代密碼的分界線。計(jì)算機(jī)使得基于復(fù)雜計(jì)算的密碼成為可能相關(guān)技術(shù)的發(fā)展1949年Shannon的“TheCommunicationTheoryofSecretSystems”1967年DavidKahn的《TheCodebreakers》1971-73年IBMWatson實(shí)驗(yàn)室的HorstFeistel等幾篇技術(shù)報(bào)告主要特點(diǎn)：數(shù)據(jù)的安全基于密鑰而不是算法的保密

第2階段1949~19751976年：Diffie&Hellman

的

“NewDirectionsinCryptography”提出了不對(duì)稱(chēng)密鑰密1977年Rivest,Shamir&Adleman提出了RSA公鑰算法90年代逐步出現(xiàn)橢圓曲線等其他公鑰算法主要特點(diǎn)：公鑰密碼使得發(fā)送端和接收端無(wú)密鑰傳輸?shù)谋Ｃ芡ㄐ懦蔀榭赡艿?階段1976~密碼學(xué)發(fā)展歷史密碼學(xué)中的術(shù)語(yǔ)緒論信息傳遞的一般問(wèn)題信源、信道、信宿攻擊的種類(lèi)：中斷（Interruption)（干擾）截?。↖nterception)(偵聽(tīng)）修改（Modification）偽造（Fabrication)角色：通信雙方、可信第三方、不可信第三方介質(zhì)：軟件、硬件、數(shù)據(jù)數(shù)據(jù)的性質(zhì)可用性(Availability)：保證信息和信息系統(tǒng)確實(shí)為授權(quán)者所用，防止由于計(jì)算機(jī)病毒或其它人為因素造成系統(tǒng)的拒絕服務(wù)，或者為非法者所用。保密性(Confidentiality)：保證信息不泄漏給未經(jīng)授權(quán)的人。完整性(Integrity)：防止信息被未經(jīng)授權(quán)的篡改。真實(shí)性(Authenticity)：保證信息不是偽造的。不可否認(rèn)性:保證信息行為人不能過(guò)后否認(rèn)自己的行動(dòng)。被動(dòng)攻擊截取獲取消息內(nèi)容流量分析主動(dòng)攻擊中斷修改偽造破壞可用性破壞完整性破壞真實(shí)性攻擊分類(lèi)破壞機(jī)密性安全性攻擊舉例獲取對(duì)信息的非授權(quán)訪問(wèn)；冒充別的用戶以推卸責(zé)任或使用他人的許可證，以達(dá)到以下目的：制造欺詐信息篡改合法信息使用欺詐性的身份來(lái)獲得非授權(quán)訪問(wèn)欺詐性地對(duì)交易進(jìn)行認(rèn)證或簽注抵賴欺詐引起的責(zé)任；安全性攻擊舉例（續(xù)）聲稱(chēng)收到了別的用戶的信息，其實(shí)這是自己偽造的；聲稱(chēng)已經(jīng)將消息發(fā)送給接收方，而當(dāng)時(shí)根本沒(méi)有發(fā)送；否認(rèn)收到的信息或接收信息的時(shí)間；擴(kuò)大他的合法權(quán)限；未經(jīng)授權(quán)修改他人的權(quán)限；將自身作為中繼插入到其他用戶的通信線路中；阻止其他用戶間的通信，特別是通過(guò)秘密介入，使合法通信被拒絕．密碼學(xué)(Cryptology):是研究信息系統(tǒng)安全保密的科學(xué)。密碼編碼學(xué)(Cryptography):主要研究對(duì)信息進(jìn)行編碼，實(shí)現(xiàn)對(duì)信息的隱蔽。密碼分析學(xué)(Cryptanalysis):主要研究加密消息的破譯或消息的偽造。密碼學(xué)概念EncryptDecryptPlaintextCiphertextPlaintextAliceBobEveInsecureChannelC=E(P)P=D(C)Emustbeinvertible加密通信過(guò)程明文(Plaintext)

：發(fā)送者要傳遞給接收者的源信息，消息的初始形式。密文(Cyphertext)

：明文加密后的表現(xiàn)形式，是發(fā)送者在信道上傳遞給接收者的信息。密鑰(Key)：是加密和解密時(shí)用到的數(shù)據(jù)，只有加密者和解密者知道。加密(Encrypt)：把明文轉(zhuǎn)換成密文的過(guò)程，C=E(P)。解密(Decrypt)：把密文轉(zhuǎn)換成明文的過(guò)程，P=D(C)。破譯：攻擊者利用各種手段，對(duì)加密密鑰或算法進(jìn)行破解。密碼學(xué)術(shù)語(yǔ)密碼體系是一個(gè)五元組（P,C,K,E,D)滿足條件：（1）P是可能明文的有限集；（明文空間）（2）C是可能密文的有限集；（密文空間）（3）K是一切可能密鑰構(gòu)成的有限集；（密鑰空間）（4）任意k∈K，有一個(gè)加密算法和相應(yīng)的解密算法，使得和分別為加密解密函數(shù)，滿足dk(ek(x))=x

，這里x∈P。密碼體系形式化描述

Kerckhoff加密原則SecurityshoulddependonlyonthekeyDon’tassumeenemywon’tknowalgorithmSecuritythroughobscurityisn’tLookathistoryofexamplesBettertohavescrutinybyopenexperts“Theenemyknowsthesystembeingused.”ClaudeShannon密碼分析試圖破譯單條消息試圖識(shí)別加密的消息格式，以便借助直接的解密算法破譯后續(xù)的消息試圖找到加密算法中的普遍缺陷（無(wú)須截取任何消息）密碼分析的條件與工具已知加密算法截取到明文、密文中已知或推測(cè)的數(shù)據(jù)項(xiàng)數(shù)學(xué)或統(tǒng)計(jì)工具和技術(shù)語(yǔ)言特性計(jì)算機(jī)技巧與運(yùn)氣密碼分析類(lèi)型加密方案的安全性無(wú)條件安全(unconditionallysecure)：無(wú)論提供的密文有多少，如果由一個(gè)加密方案產(chǎn)生的密文中包含的信息不足以唯一地決定對(duì)應(yīng)的明文除了一次一密(one-time-pad)的方案外，沒(méi)有無(wú)條件安全的算法計(jì)算上安全(computationallysecure):破譯的成本超過(guò)加密信息的價(jià)值破譯的時(shí)間超過(guò)密文信息有效生命周期攻擊的復(fù)雜性分析數(shù)據(jù)復(fù)雜性（datacomplexity）用作攻擊輸入所需要的數(shù)據(jù)處理復(fù)雜性（processingcomplexity）完成攻擊所需要的時(shí)間存儲(chǔ)需求（storagerequirement）進(jìn)行攻擊所需要的數(shù)據(jù)量窮盡攻擊窮盡攻擊(exhaustivekeysearch)：也稱(chēng)為窮舉攻擊或蠻力攻擊(bruteforceattack)．攻擊者對(duì)一條密文嘗試所有可能的密鑰，直到把它轉(zhuǎn)化為可讀的有意義的明文．平均而言，獲得成功至少要常使所有可能密鑰的一半．差分分析（differentialcryptanalysis）是一種較新的攻擊方法。密鑰搜索所需平均時(shí)間1995年硬件窮舉攻擊的平均時(shí)間和金錢(qián)估計(jì)花費(fèi)的金錢(qián)（美元）密鑰長(zhǎng)度（位）4056648011212810萬(wàn)2秒35小時(shí)1年70000年年年100萬(wàn)0.2秒3.5小時(shí)37天7000年年年1000萬(wàn)0.02秒21分鐘4天700年年年1億2毫秒2分鐘9小時(shí)70年年年10億0.2毫秒13秒1小時(shí)7年年年緒論古典密碼學(xué)密碼學(xué)信息論基礎(chǔ)對(duì)稱(chēng)加密技術(shù)非對(duì)稱(chēng)加密技術(shù)數(shù)字簽名Hash函數(shù)身份認(rèn)證密鑰管理課程內(nèi)容替代(SubstitutionCipher)

置換(PermutationCipher)古典密碼學(xué)也稱(chēng)為代換，就是將明文字符用其它字母、數(shù)字或符號(hào)代替．它又分為單字母代換(MonogramSubstitution)和多字母代換(PolygramSubstitution)．單字母代換又分為單表代換(MonoalphabeticSubstitution)和多表代換(Polyalphabetic).替代對(duì)明文的所有字母都用一個(gè)固定的明文字母表到密文字母表的映射設(shè)則其中是一個(gè)字母表映射:

a

J,b

L,...單表代換密碼愷撒密碼（Caesar）破譯以下密文：wuhdwb

lpsrvvleohTREATYIMPOSSIBLE加密算法：字母表：(密碼本）

ABCDEFGHIJKLMNOPQRSTUVWXYZ

defghijklmnopqrstuvwxyzabc愷撒密碼的特點(diǎn)單字母密碼（簡(jiǎn)單替換技術(shù)）簡(jiǎn)單，便于記憶缺點(diǎn):(1)結(jié)構(gòu)過(guò)于簡(jiǎn)單，密碼分析員只使用很少的信息就可預(yù)言加密的整個(gè)結(jié)構(gòu)；(2)密鑰空間大小只有26，而需要測(cè)試的密鑰只有２５個(gè)；(3)明文所用語(yǔ)言已知，且其意義易于識(shí)別．單字母替換－－使用密鑰使用密鑰keyABCDEFGHIJKLMNOPQRSTUVWXYZkeyabcdfghijlmnopqrstuvwxzspectacularABCDEFGHIJKLMNOPQRSTUVWXYZspectaulrbdfghijkmnoqvwxyz泄露給破譯者的信息更少使用置換：密鑰空間大?。?，大于56位DES的密鑰空間，窮舉攻擊很困難，但基于語(yǔ)言統(tǒng)計(jì)規(guī)律仍可破譯．

單字母替換－－使用置換單字母變換－－使用句子作密鑰任意置換較難記憶，有時(shí)使用密鑰句子：

themessagewastransmittedanhourago源字母表：abcdefghijklmnopqrstuvwxyz代換字母表：HEMESAGWRNIDOUBCFJKLPQVXYZ明文：pleaseconfirmreceipt密文：CDSTKSEBUARJOJSESRCL英文字母相對(duì)使用頻率例：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ多字母替換密碼--平穩(wěn)分布單字母替換E1和E2，分別用于明文信息中奇數(shù)和偶數(shù)位置的字符，從而打亂密文中的字母分布頻率特性（通常E2應(yīng)為的E1補(bǔ)充）例1：E1(T)=a,E2(T)=bE1(X)=b,E2(X)=a E1(a)=(3*a)mod26E2(a)=(5*a+13)mod26

TREATYIMPOSSIBL

E

fumnf

dyvtf

czysh

h多字母替換密碼--平穩(wěn)分布例2：E1(a)=a E2(a)=25-aABCDEFGHIJKLMNOPQRSTUVWXYZzyxwvutsrqponmlkjihgfedcbaItwasthebestoftimes,itwastheworstoftimes…Ig

wzs

ghv

bvsg

ou

trmvs

rt

dah

tse

doisg

ou

trmvsPlayfair密碼把明文中的雙字母音節(jié)作為一個(gè)單元并將其轉(zhuǎn)換成密文的“雙字母音節(jié)”．加密算法基于一個(gè)由密鑰詞構(gòu)成的字母矩陣．例：MONARCHYBDEFGI/JKLPQSTUVWXZ密鑰詞：monarchyPlayfair密碼（續(xù)）如果該字母對(duì)兩個(gè)字母相同，那么在它們之間加一個(gè)填充字母，比如x。如：balloon先把它變成balxloon四個(gè)字母對(duì)。落在矩陣同一行的明文字母對(duì)中的字母由其右邊字母代換，最右邊的用最左邊的代換。如ar變成RM.落在矩陣同一列的明文字母對(duì)中的字母由其下邊字母代換，最下邊的用最上邊的代換。如mu變成CM.其他的每組明文字母對(duì)中的字母按照如下方式代換：它所在的行是該字母的所在行，列是另一字母所在列。如hs變成BP,ea變成IM(或JM).Playfair密碼分析字母對(duì)26*26=676個(gè)；單個(gè)字母在使用頻率的統(tǒng)計(jì)規(guī)律上比字母對(duì)要強(qiáng)得多；密文仍然完整的保留了明文語(yǔ)言結(jié)構(gòu)，容易攻破。一次一密(one-timepad)亂碼本它是一個(gè)大的不重復(fù)的真隨機(jī)字母集，寫(xiě)在幾張紙上，粘成一個(gè)亂碼本；每個(gè)密鑰僅對(duì)一個(gè)消息使用一次，使用過(guò)銷(xiāo)毀；接收者有一個(gè)同樣的亂碼本；密鑰序列的長(zhǎng)度等于消息的長(zhǎng)度。產(chǎn)生、分配、保存與使用存在一定問(wèn)題與難度。PolyalphabeticSubstitutionCipher-ExampleBreaktheplaintextinto3-characterdiagramsSubstitutethediagramasfollows:1stletterisreplacedwiththeletter3positionstoitsright2nd：7positionstoitsright3rd：10positionstoitsrightPlaintext:THISCIPHERISCERTAINLYNOTSECURE

THISCIPHERISCERTAINLYNOTSECURECipher

WOSVJSSOOUPCFLBWHSQSIQVDVLMXYO替代(SubstitutionCipher)

置換(PermutationCipher)古典密碼學(xué)

置換的基本思想是保持明文字符不變，通過(guò)重排而改變它們的位置，也稱(chēng)為換位加密（TranspositionCipher)。置換

設(shè)m為固定的正整數(shù)，P=C=(Z/(26))m,K是由{1,2,..,m}的所有置換構(gòu)成，對(duì)一個(gè)密鑰π∈K，定義

eπ(x1,x2,..,xm)=(xπ(1),,..,xπ(m))和

dπ(y1,y2,..,ym)=(yπ(1),,..,yπ(m))

這里π－1為π的逆置換注：這里的加密與解密僅僅用了置換，無(wú)代數(shù)運(yùn)算例子：設(shè)m=6，取密鑰

而若給定的明文是：cryptography首先找分成6個(gè)字母長(zhǎng)的明文組：crypto|graphy

求得的密文是：YTCOPRAHGYPR置換例子置換矩陣把明文按照列（行）順序?qū)懭刖仃?，按照行（列）讀出；讀出的順序就是密鑰；緒論古典密碼學(xué)密碼學(xué)信息論基礎(chǔ)對(duì)稱(chēng)加密技術(shù)非對(duì)稱(chēng)加密技術(shù)數(shù)字簽名Hash函數(shù)身份認(rèn)證密鑰管理課程內(nèi)容保密系統(tǒng)的數(shù)學(xué)模型Shannon保密系統(tǒng)模型信息量和熵定義1：設(shè)隨機(jī)變量,則X的不確定性或熵定義為聯(lián)合熵和條件熵

條件熵H(X|Y)理解為觀察到Y(jié)后X還保留的不確定性，通常將其成為含糊度，而將H(Y|X)稱(chēng)為散布度，I(X,Y)=H(X)-H(X|Y)表示X上減少量。聯(lián)合熵和條件熵（續(xù)）定理1，當(dāng)且僅當(dāng)X和Y獨(dú)立是等號(hào)成立。定理2定理3，當(dāng)且僅當(dāng)X和Y獨(dú)立是等號(hào)成立。聯(lián)合熵和條件熵（續(xù)）定理4設(shè)(P,C,K,e,d)是一個(gè)密碼系統(tǒng)，則H(K|C)=H(K)+H(P)-H(C)證明：由于

H(K,P,C)=H(C|K,P)+H(K,P)=H(P|K,C)+H(K,C)而H(C|K,P)=H(P|K,C)=0,H(K,P)=H(K)+H(P),H(K,C)=H(C)+H(K|C)故結(jié)論成立完善保密性定義2一個(gè)完善保密系統(tǒng)(P,C,K,e,d)稱(chēng)為是完善的或無(wú)條件的保密系統(tǒng)，如果H(P|C)=H(P)或I(P,C)=0.

Shnnon證明，僅當(dāng)可能的密鑰數(shù)目至少與可能的消息數(shù)目一樣多時(shí)，完全保密才是可能的。即密鑰必須至少與消息本身一樣長(zhǎng)，并且不重復(fù)使用。一次一密的加密Shannon在1949給出了完全安全（無(wú)條件安全）的加密系統(tǒng)的充要條件： 對(duì)所有的明文M和秘文E成立，即與M無(wú)關(guān)。其中，是當(dāng)明文為M時(shí)，密文為E的條件概率；是在所有情況下秘文為E的概率。一次一密加密是完全安全的，也是唯一完全安全的加密體制?；靵y與擴(kuò)散

混亂(Confusion)與擴(kuò)散(Diffusion)是Shannon提出的隱蔽明文消息中冗余度的基本技術(shù)?；靵y用于掩蓋明文和密文之間的關(guān)系。實(shí)現(xiàn)的簡(jiǎn)單方法是通過(guò)替代。擴(kuò)散通過(guò)將明文冗余度分散到密文中使之分散開(kāi)來(lái)。實(shí)現(xiàn)的簡(jiǎn)單方法是通過(guò)簡(jiǎn)單換位。單向函數(shù)單向函數(shù)是現(xiàn)代密碼學(xué)的一個(gè)基本工具，它可以用來(lái)構(gòu)造偽隨機(jī)序列生成器（密鑰流生成器），單向陷門(mén)函數(shù)可用來(lái)構(gòu)造公鑰密碼體制，單向雜湊（Hash）函數(shù)可以用于數(shù)字簽名和消息完整性檢測(cè)等。定義：函數(shù)稱(chēng)為強(qiáng)單向函數(shù)，若滿足：（1）計(jì)算f(x)使容易的；（2）計(jì)算f(x)的逆是困難的。單向函數(shù)（續(xù)）單向函數(shù)計(jì)算容易值得是f(x)在多項(xiàng)式時(shí)間內(nèi)可計(jì)算，其逆計(jì)算是困難的指的是用任一個(gè)多項(xiàng)式時(shí)間算法來(lái)計(jì)算f(x)的逆，若算法的輸入y=f(x)由中隨機(jī)抽取，計(jì)算出結(jié)果為x的概率是可以忽略的。候選單向函數(shù)例1整數(shù)因子分解n=pq例2背包問(wèn)題有一個(gè)背包，其容積為s，有n種東西體積分別為，要從中挑選出若干件把其裝滿。即求，使得。緒論古典密碼學(xué)密碼學(xué)信息論基礎(chǔ)對(duì)稱(chēng)加密技術(shù)非對(duì)稱(chēng)加密技術(shù)數(shù)字簽名Hash函數(shù)身份認(rèn)證密鑰管理課程內(nèi)容對(duì)稱(chēng)加密結(jié)構(gòu)對(duì)稱(chēng)加密流加密(StreamCipher)

流密碼又稱(chēng)為序列密碼，一直是作為軍事和外交場(chǎng)合使用的主要密碼技術(shù)之一，它的主要加密方法是使用優(yōu)良的偽隨機(jī)序列作為密鑰，對(duì)信息流進(jìn)行逐比特加密，得到密文序列。所以，序列密碼算法的安全強(qiáng)度完全決定于它所產(chǎn)生的偽隨機(jī)序列的好壞。

塊加密(BlockCipher)塊密碼也稱(chēng)為分組密碼，其工作方式是將明文分成固定長(zhǎng)度的組（塊），用同一密鑰和算法對(duì)每一塊加密，輸出也是固定長(zhǎng)度的密文。

流加密結(jié)構(gòu)圖明文密鑰流密文流加密密鑰流的周期性密鑰流生成器DES數(shù)據(jù)加密標(biāo)準(zhǔn)DES（DataEncryptionStandard）是美國(guó)國(guó)家標(biāo)準(zhǔn)局開(kāi)始研究除國(guó)防部以外的其他部門(mén)的計(jì)算機(jī)系統(tǒng)的數(shù)據(jù)加密標(biāo)準(zhǔn)。1977年1月，美國(guó)政府采納1BM公司設(shè)計(jì)的方案作為非機(jī)密數(shù)據(jù)的正式數(shù)據(jù)加密標(biāo)準(zhǔn)（DES）。DES被授權(quán)用于所有公開(kāi)的和私人的非保密通信場(chǎng)合，后來(lái)它又曾被國(guó)際標(biāo)準(zhǔn)組織采納為國(guó)際標(biāo)準(zhǔn)。在1973年，NBS發(fā)布了公開(kāi)征集標(biāo)準(zhǔn)密碼算法的請(qǐng)求，他們確定的設(shè)計(jì)準(zhǔn)則為：（1）必須提供高度的安全性；（2）具有相當(dāng)高的復(fù)雜性，使得破譯的開(kāi)銷(xiāo)超過(guò)可能獲得的利益，同時(shí)又便于理解和掌握；（3）安全性應(yīng)不依賴于算法的保密，其加密的安全性僅以加密密鑰的保密為基礎(chǔ)；（4）必須適用于不同的用戶和不同的場(chǎng)合；（5）實(shí)現(xiàn)經(jīng)濟(jì)、運(yùn)行有效；（6）必須能夠驗(yàn)證，允許出口。數(shù)據(jù)加密算法設(shè)計(jì)標(biāo)準(zhǔn)DES算法描述初始置換與逆置換LiandRiare32-bitlong算法每一輪迭代的結(jié)構(gòu)密鑰置換密鑰的64位中產(chǎn)生出56位56位密鑰分成兩部分,每部分28位,然后根據(jù)輪數(shù),這兩部分分別循環(huán)左移1位或2位.57106314492556415947613351395325433145173523379271529119721581162135035454260462834523820264430121836224輪位112132425262728291102112122132142152161密鑰置換(續(xù))從56位中選出48位1423414417195249111231392443756126473458555331630462874042152751506204536211333291024832詳細(xì)結(jié)構(gòu)函數(shù)F(R,K)擴(kuò)展置換32位擴(kuò)展成48位,其中16位重復(fù)S盒S盒的輸入是6位,輸出是4位數(shù)據(jù)產(chǎn)生方法:

設(shè)S盒的6位輸入為b1,b2,b3,b4,b5,b6,則b1和b6組合成的2位數(shù)對(duì)應(yīng)行號(hào);b2b3b4b5組合成一個(gè)4位數(shù)對(duì)應(yīng)表中的列.查找S盒種對(duì)應(yīng)位置的元素,得到一個(gè)4位數(shù).S盒(1-4)S盒(5-8)S盒的輸入S盒的輸出P盒置換S盒代替運(yùn)算后的32位輸出依照P盒進(jìn)行置換.DES解密解密與加密算法相同,不同之處是密鑰的次序相反.加密時(shí)為K1,k2,……,K16,解密時(shí)為k16,k15,……,k1.產(chǎn)生密鑰的算法也是循環(huán)的,密鑰向右移動(dòng).雪崩效應(yīng)(TheAvalancheEffect)DES的安全性弱密鑰:算法的任一周期的密鑰都相同;半弱密鑰:一些密鑰對(duì)把明文加密成相同的密文;迭代的次數(shù)密鑰長(zhǎng)度S盒的安全性差分攻擊線性分析DES加密與解密例子已知明文m=computer,密鑰k=program密文:0101100010101000010000011011100001101001111111101010111000110011高級(jí)加密標(biāo)準(zhǔn)(AES)AES的起源AES的設(shè)計(jì)原則AES算法描述1.AES的起源1997年9月，NIST征集AES方案，以替代DES。1999年8月，以下5個(gè)方案成為最終候選方案：MARS,RC6,Rijndael,Serpent,Twofish。2000年10月，由比利時(shí)的JoanDaemen和VincentRijmen提出的算法最終勝出。（Rijndael

讀成RainDoll。）http://www.esat.kuleuven.ac.be/~rijmen/rijndael/2.AES的設(shè)計(jì)原則能抵抗所有已知的攻擊；在各種平臺(tái)上易于實(shí)現(xiàn)，速度快；設(shè)計(jì)簡(jiǎn)單。

Rijndael是一個(gè)分組密碼算法，其分組長(zhǎng)度和密鑰長(zhǎng)度相互獨(dú)立，都可以改變。分組長(zhǎng)度（bit）128192256密鑰長(zhǎng)度（bit）128192256表1.分組長(zhǎng)度和密鑰長(zhǎng)度的不同取值3.

AES

算法的一般描述RijndaelRound的構(gòu)成ByteSubstitutionByteRotationMixColumn+RoundKey一般的輪變換ByteSubstitutionByteRotation+RoundKey最后一輪的輪變換3.

AES

算法加密部分的實(shí)現(xiàn)01234567891011121314150481215913261014371115Fig1.以明文分組為128bits為例組成的陣列048121591326101437111504812162015913172126101418223711151923048121620242815913172125292610141822263037111519232731Fig2.以明文分組（或密鑰）為128bits、192bits、256bits為例組成的陣列

一些相關(guān)的的術(shù)語(yǔ)定義和表示狀態(tài)（State）：密碼運(yùn)算的中間結(jié)果稱(chēng)為狀態(tài)。State的表示：狀態(tài)用以字節(jié)為基本構(gòu)成元素的矩陣陣列來(lái)表示，該陣列有4行，列數(shù)記為Nb。Nb=分組長(zhǎng)度（bits）÷32

Nb可以取的值為4，6，8，對(duì)應(yīng)的分組長(zhǎng)度為128，192，256bits。密碼密鑰（CipherKey）的表示：CipherKey類(lèi)似地用一個(gè)4行的矩陣陣列來(lái)表示，列數(shù)記為Nk。Nk=密鑰長(zhǎng)度（bits）÷32

Nk可以取的值為4，6，8，對(duì)應(yīng)的密鑰長(zhǎng)度為128，192，256bits。Fig3.當(dāng)Nb=6時(shí)的狀態(tài)和Nk=4時(shí)的密鑰布局a0,0a0,1a0,2a0,3a0,4a0,5a1,0a1,1a1,2a1,3a1,4a1,5a2,0a2,1a2,2a2,3a2,4a2,5a3,0a3,1a3,2a3,3a3,4a3,5Nb=6BlockLength=192bitsK0,0K0,1K0,2K0,3K1,0K1,1K1,2K1,3K2,0K2,1K2,2K2,3K3,0K3,1K3,2K3,3Nk=4KeyLength=128bitsFig4.分組長(zhǎng)度和密鑰長(zhǎng)度均為128bits時(shí)的Rijndael加密算法框圖Data/KeyAdditionRnd0Rnd1Rnd8FinalRndKeyScheduleCipherTextKeyPlainText表2.輪數(shù)（Round）的不同取值輪數(shù)（Round）BlockLength=128BlockLength=192BlockLength=256KeyLength=128101214KeyLength=192121214KeyLength=256141414用偽代碼表示的Rijndael輪變換一般的輪變換Round(State,RoundKey){ByteSubstitution;

ByteRotation;

MixColumn;

AddRounKey;}結(jié)尾輪變換FinalRound(State,RoundKey){ByteSubstituion;

ByteRotation;

AddRoundKey;}ByteSubstitution(字節(jié)替代)

ByteSubstitution是一個(gè)非線性的字節(jié)替代，獨(dú)立地在每個(gè)狀態(tài)字節(jié)上進(jìn)行運(yùn)算。它包括兩個(gè)變換。

1.在有限域GF()上求乘法逆，‘00’映射到它自身。

2.在GF(2)上進(jìn)行下面的仿射變換：

y01

11

1

1

000x00y10

11

1

1

100x11y2001

1

1

110x21y3000

1

1

111x30y4＝

1

00

0

1

111x4＋

0y51

10

0

0

111x50y61

11

0

0

011x61y71

11

1

0

001x71Fig6.ByteSubstitution

該變換可以用一個(gè)256字節(jié)的表來(lái)實(shí)現(xiàn)B0,0B0,1B0,2B0,3B1,0B1,1B1,2B1,3B2,0B2,1B2,2B2,3B3,0B3,1B3,2B3,3A0,0A0,1A0,2A0,3A1,0A1,1A1,2A1,3A2,0A2,1A2,2A2,3A3,0A3,1A3,2A3,3取逆仿射變換ByteRotation(字節(jié)移位)在ByteRotation變換中，狀態(tài)陣列的后3行循環(huán)移位不同的偏移量。第1行循環(huán)移位C1字節(jié)，第2行循環(huán)移位C2字節(jié)，第3行循環(huán)移位C3字節(jié)。偏移量C1、C2、C3與分組長(zhǎng)度Nb有關(guān)，如下表所示：NbC1C2C3412361238134Fig7.ByteRotation04812159132610143711150481259131101426153711循環(huán)左移1字節(jié)循環(huán)左移2字節(jié)循環(huán)左移3字節(jié)MixColumn(列混合)將狀態(tài)的列看作是有限域GF(28)上的多項(xiàng)式a(x)，與多項(xiàng)式c(x)=03x3+01x2+01x+02相乘(模x4＋1)。令b(x)=c(x)×a(x)，寫(xiě)成矩陣形式為：

b002030101a0

b1=01

020301a1

b20101

0203a2

b303010102a3Fig8.MixColumn

這一運(yùn)算作用在每一列上A0,0A0,1A0,2A0,3A1,0A1,1A1,2A1,3A2,0A2,1A2,2A2,3A3,0A3,1A3,2A3,3B0,0B0,1B0,2B0,3B1,0B1,1B1,2B1,3B2,0B2,1B2,2B2,3B3,0B3,1B3,2B3,3×C(X)2.4AddRoundKey(輪密鑰加)將輪密鑰與狀態(tài)按比特異或。輪密鑰是通過(guò)KeySchedule過(guò)程從密碼密鑰中得到的，輪密鑰長(zhǎng)度等于分組長(zhǎng)度。A0,0A0,1A0,2A0,3A1,0A1,1A1,2A1,3A2,0A2,1A2,2A2,3A3,0A3,1A3,2A3,3K0,0K0,1K0,2K0,3K1,0K1,1K1,2K1,3K2,0K2,1K2,2K2,3K3,0K3,1K3,2K3,3＋B0,0B0,1B0,2B0,3B1,0B1,1B1,2B1,3B2,0B2,1B2,2B2,3B3,0B3,1B3,2B3,3A3,3＋K3,3＝B3,3(mod2)Fig7.Rijndael加密及解密的標(biāo)準(zhǔn)結(jié)構(gòu)Block,KeyLength=128bitsPlaintext(128bits)ByteSubstitutionMixColumn＋Ciphertext(128bits)

K0Kii=10ByteRotationfori=1to10Ciphertext(128bits)

K10InvMixCoumnInvByteRotationInvByteSubstitution＋＋

Ki＋Plaintext(128bits)i=9fori=9to0加密解密用偽代碼表示的Rijndael加密算法Rijndael(State,CipherKey){

KeyExpansion(CipherKey,ExpandedKey);

AddRoundKey(State,ExpandedKey);For(i=1;i<Rnd;i++)Round(State,ExpandedKey+Nb*i);

FinalRound(State,ExpandedKey+Nb*Rnd);}提前進(jìn)行密鑰擴(kuò)展后的Rijndael加密算法描述Rijndael(State,ExpandedKey){

AddRoundKey(State,ExpandedKey);For(i=1;i<Rnd;i++)Round(State,ExpandedKey+Nb*i);

FinalRound(State,ExpandedKey+Nb*Rnd);}AES

的密鑰調(diào)度

密鑰調(diào)度包括兩個(gè)部分：密鑰擴(kuò)展和輪密鑰選取。密鑰bit的總數(shù)＝分組長(zhǎng)度×（輪數(shù)Round＋1）例如當(dāng)分組長(zhǎng)度為128bits和輪數(shù)Round為10時(shí)，輪密鑰長(zhǎng)度為128×(10＋1)＝1408bits。將密碼密鑰擴(kuò)展成一個(gè)擴(kuò)展密鑰。從擴(kuò)展密鑰中取出輪密鑰：第一個(gè)輪密鑰由擴(kuò)展密鑰的第一個(gè)Nb個(gè)4字節(jié)字，第二個(gè)圈密鑰由接下來(lái)的Nb個(gè)4字節(jié)字組成，以此類(lèi)推。密鑰擴(kuò)展K0,0K0,1K0,2K0,3K1,0K1,1K1,2K1,3K2,0K2,1K2,2K2,3K3,0K3,1K3,2K3,3K0K1K2K3K0K1K2K3K4K5K6K7+++K0K1K2K3K4K5K6K7ByteSubstitutionByteRotate+RconWi-4Wi-3Wi-2Wi-1WiByteSubstituionByteRotate+Rcons+Keyexpansion4=<i<4(Rnd+1)imod4=0imod4!=0

輪密鑰選取K0K1K2K3K4K5K6K7K8K9K10K11K12輪密鑰0輪密鑰1輪密鑰2AES的解密算法解密算法與加密算法不同每個(gè)階段均可逆，因此易證解密函授的確可以恢復(fù)明文AES

算法的設(shè)計(jì)原理

GF(28)中乘法使用的多項(xiàng)式是8次不可約多項(xiàng)式列表中的第一個(gè)多項(xiàng)式。ByteSubstitution（稱(chēng)為S盒）在設(shè)計(jì)時(shí)考慮到抵抗差分密碼分析、線性密碼分析的要求，應(yīng)滿足以下條件：1.可逆性；2.輸入比特的線性組合與輸出比特的組合之間的最大非平凡相關(guān)性的極小化；3.異或差分表中最大非平凡值的極小化；4.GF(28)中代數(shù)表示的復(fù)雜性；5.描述的簡(jiǎn)單性。滿足前3條準(zhǔn)則的S盒的構(gòu)造方法已被給出，AES的作者從眾多候選構(gòu)造中選擇將x映射到它的逆的S盒。該映射過(guò)于簡(jiǎn)單，為了抵抗插入攻擊，加入仿射變換：b(x)=(x7

+x6

+x2

+x)+a(x)(x7

+x6

+x5

+x4

+1)modx8

+1模數(shù)多項(xiàng)式x8+1選擇為可能是最簡(jiǎn)單的模數(shù)多項(xiàng)式?？梢哉业狡渌腟盒滿足以上準(zhǔn)則。MixColumn變換符合以下準(zhǔn)則：1.可逆性；2.GF(2)中的線性性；3.適當(dāng)?shù)臄U(kuò)散性能；4.8位處理器上實(shí)現(xiàn)速度快；5.對(duì)稱(chēng)性；6.描述的簡(jiǎn)單性。選擇模數(shù)多項(xiàng)式x4＋1可滿足準(zhǔn)則2、5、6。準(zhǔn)則1、3、4要求系數(shù)的值要小，故選00、01、02、03。ByteRotation符合以下準(zhǔn)則：1.4個(gè)位移量互不相同且C0＝0；2.能抵抗差分截?cái)喙簦?.能抗Square攻擊；4.簡(jiǎn)單。從滿足準(zhǔn)則2和準(zhǔn)則3出發(fā)，AES的作者選取了最簡(jiǎn)單的組合。與一些其它算法的比較：與DES相比：1.無(wú)DES中的弱密鑰和半弱密鑰；2.緊湊的設(shè)計(jì)使得沒(méi)有足夠的空間來(lái)隱藏陷門(mén)。與IDEA相比：無(wú)IDEA中的弱密鑰。具有擴(kuò)展性：密鑰長(zhǎng)度可以擴(kuò)展到為32bits倍數(shù)的任意密鑰長(zhǎng)度，分組長(zhǎng)度可以擴(kuò)展到為64bits倍數(shù)的任意分組長(zhǎng)度。圈數(shù)和循環(huán)移位偏移量作為參數(shù)，要重新定義。關(guān)于有限域G(28)的一些解釋G(28)可看為8位二進(jìn)制比特串的集合直觀上有限域的運(yùn)算可為密碼算法的實(shí)現(xiàn)帶來(lái)方便只有滿足一些規(guī)則后，G(28)才是有限域G(28)上的運(yùn)算加法按位異或乘法可通過(guò)對(duì)多個(gè)中間結(jié)果的移位運(yùn)算和異或一個(gè)特定的比特串（比如00011011）實(shí)現(xiàn)。緒論古典密碼學(xué)密碼學(xué)信息論基礎(chǔ)對(duì)稱(chēng)加密技術(shù)非對(duì)稱(chēng)加密技術(shù)數(shù)字簽名Hash函數(shù)身份認(rèn)證密鑰管理課程內(nèi)容數(shù)學(xué)基礎(chǔ)素?cái)?shù)Fermat定理和Euler定理素性測(cè)試中國(guó)剩余定理離散對(duì)數(shù)素?cái)?shù)235711131719232931374143535961717379838997101103107109113127131139149151163167173179181191193197199211223227229233241251257263269271277281283293307311313317331337347349353359367373379383389397401409419421431433439443449457461463467479487491499素?cái)?shù)Fermat

定理Euler定理nnn111110211221124221032131223224214624854158252062168261276171627188418628129619182928104208308Miller和Rabin提出的算法：考察奇數(shù)n，設(shè)n-1=2kq選擇整數(shù)1<a<n-1計(jì)算若n為素?cái)?shù)，要么序列的第一個(gè)元素為1，要么該序列中存在元素n-1.素?cái)?shù)測(cè)試Miller和Rabin提出的算法：考察奇數(shù)n，設(shè)n-1=2kq選擇整數(shù)1<a<n-1計(jì)算若n為素?cái)?shù)，要么序列的第一個(gè)元素為1，要么該序列中存在元素n-1.素?cái)?shù)測(cè)試中國(guó)剩余定理RSA的基本原理

RSA體制是根據(jù)尋求兩個(gè)大素?cái)?shù)容易，而將他們的乘積分解開(kāi)則極其困難這一原理來(lái)設(shè)計(jì)的。RSA中的密鑰RSA中的加密與解密RSA中密鑰中參數(shù)的選擇RSA中密鑰中參數(shù)的選擇（示例一）RSA中密鑰中參數(shù)的選擇（示例二）RSA算法的安全性RSA安全性取決于對(duì)模n因數(shù)分解的困難性。1999年8月，荷蘭國(guó)家數(shù)學(xué)與計(jì)算機(jī)科學(xué)研究所家們的一組科學(xué)家成功分解了512bit的整數(shù)，大約300臺(tái)高速工作站與PC機(jī)并行運(yùn)行，整個(gè)工作花了7個(gè)月。1999年9月，以色列密碼學(xué)家Adi

Shamir設(shè)計(jì)了一種名叫“TWINKLE”的因數(shù)分解設(shè)備，可以在幾天內(nèi)攻破512bit的RSA密鑰。（但要做到這一點(diǎn)，需要300-400臺(tái)設(shè)備，每臺(tái)設(shè)備價(jià)值5000美圓）。橢圓曲線加密（EllipticCurveCryptography）橢圓曲線密碼介紹橢圓曲線理論是代數(shù)、幾何、數(shù)論等多個(gè)數(shù)學(xué)分支的交叉點(diǎn)，近年來(lái)被廣泛應(yīng)用于公鑰密碼學(xué)研究中。橢圓曲線的一般方程 y2+axy+by=x3+cx2+dx+e

其中a,b,c,d,e屬于集合F,F可以是有理數(shù)域，也可以是復(fù)數(shù)域。一般采用如下方程：橢圓曲線密碼示意圖橢圓曲線上的加法:P+Q=R橢圓曲線上一點(diǎn)的2倍:P+P=R.有限域上橢圓曲線Ep(a,b)加法公式:P+O=P如果P=(x,y)，則P+(x,-y)=O，(x,-y)點(diǎn)是P的負(fù)點(diǎn)，記為-P。而且(x,-y)也在Ep(a,b)中如果P=(x1,y1)，Q=(x2,y2)，則P+Q=(x3,y3)為

x3=

2-x1-x2(modp)

y3=

(x1-x3)-y1(modp)

其中，如果PQ，則=(y2-y1)/(x2-x1)

如果P=Q，則=(3x12+a)/(2y1)橢圓曲線用于加密找到一個(gè)難題：考慮等式Q=kP，其中Q、P屬于Ep(a,b)，k<p已知k和P，計(jì)算Q，是容易的已知Q和P，計(jì)算k，是困難的選擇Ep(a,b)的元素G,使得G的階n是一個(gè)大素?cái)?shù)G的階是指滿足nG=O的最小n值秘密選擇整數(shù)r，計(jì)算P=rG，然后公開(kāi)(p,a,b,G,P)，P為公鑰保密r加密M：先把消息M變換成為Ep(a,b)中一個(gè)點(diǎn)Pm然后，選擇隨機(jī)數(shù)k，計(jì)算密文Cm=(kG,Pm+kP)如果k使得kG或者kP為O，則要重新選擇k.解密Cm:(Pm+kP)-r(kG)=Pm+krG-rkG=Pm加密信息有擴(kuò)張橢圓曲線密碼的安全性

難點(diǎn):從P和kP獲得k對(duì)橢圓曲線研究的時(shí)間短橢圓曲線要求密鑰長(zhǎng)度短,速度快對(duì)比:ECCRSAKeysizeMIPS-Yrs1503.8

10102057.1

10182341.6

10285123

1047682

10810243

101112801

101415363

101620483

1020信息認(rèn)證和散列函數(shù)

（MessageAuthenticationandHashFunctions)1信息認(rèn)證網(wǎng)絡(luò)系統(tǒng)安全要考慮兩個(gè)方面。一方面，用密碼保護(hù)傳送的信息使其不被破譯；另一方面，就是防止對(duì)手對(duì)系統(tǒng)進(jìn)行主動(dòng)攻擊，如偽造，篡改信息等。認(rèn)證（authentication）則是防止主動(dòng)攻擊的重要技術(shù)，它對(duì)于開(kāi)放的網(wǎng)絡(luò)中的各種信息系統(tǒng)的安全性有重要作用。認(rèn)證的主要目的有二：第一，驗(yàn)證信息的發(fā)送者是真正的，而不是冒充的，此為信源識(shí)別；第二，驗(yàn)證信息的完整性，在傳送或存儲(chǔ)過(guò)程中未被篡改，重放或延遲等。保密和認(rèn)證同時(shí)是信息系統(tǒng)安全的兩個(gè)方面，但它們是兩個(gè)不同屬性的問(wèn)題，認(rèn)證不能自動(dòng)提供保密性，而保密性也不能自然提供認(rèn)證功能。一個(gè)純認(rèn)證系統(tǒng)的模型如下圖所示：竄擾者信宿信源認(rèn)證編碼器認(rèn)證譯碼器信道安全信道密鑰源在這個(gè)系統(tǒng)中的發(fā)送者通過(guò)一個(gè)公開(kāi)的無(wú)擾信道將消息送給接收者，接收者不僅想收到消息本身，而且還要驗(yàn)證消息是否來(lái)自合法的發(fā)送者及消息是否經(jīng)過(guò)篡改。系統(tǒng)中的密碼分析者不僅要截收和破譯信道中傳送的密報(bào)，而且可偽造密文送給接收者進(jìn)行欺詐，將其稱(chēng)為系統(tǒng)的竄擾者(tamper)更加合適。實(shí)際認(rèn)證系統(tǒng)可能還要防止收方、發(fā)方之間的相互欺詐。上述標(biāo)出的認(rèn)證編碼器和認(rèn)證譯碼器可抽象為認(rèn)證函數(shù)。一個(gè)安全的認(rèn)證系統(tǒng)，首先要選好恰當(dāng)?shù)恼J(rèn)證函數(shù)，然后在此基礎(chǔ)上，給出合理的認(rèn)證協(xié)議(AuthenticationProtocol)。2認(rèn)證函數(shù)

（AuthenticationFunctions)可用來(lái)做認(rèn)證的函數(shù)分為三類(lèi)：(1)信息加密函數(shù)(Messageencryption)

用完整信息的密文作為對(duì)信息的認(rèn)證。(2)信息認(rèn)證碼MAC(MessageAuthenticationCode)

是對(duì)信源消息的一個(gè)編碼函數(shù)。(3)散列函數(shù)(HashFunction)

是一個(gè)公開(kāi)的函數(shù)，它將任意長(zhǎng)的信息映射成一個(gè)固定長(zhǎng)度的信息。

對(duì)于（1），用信息加密函數(shù)作認(rèn)證的方式，信息加密函數(shù)分二種，一種是常規(guī)的對(duì)稱(chēng)密鑰加密函數(shù)，另一種是公開(kāi)密鑰的雙密鑰加密函數(shù)。下圖的通信雙方是，用戶A為發(fā)信方，用戶B為接收方。用戶B接收到信息后，通過(guò)解密來(lái)判決信息是否來(lái)自A，信息是否是完整的，有無(wú)竄擾。信源信宿MEEk(M)DMA方B方kkDk(Ek(M))(a)常規(guī)加密：具有機(jī)密性，可認(rèn)證KUb(B方的公鑰)MEEKUb(M)DMA方B方DkRb(b)公鑰加密：具有機(jī)密性MEEkRa(M)DMA方B方KRaKUa(c)公鑰加密：認(rèn)證和簽名MEEkRa(M)EEKUb(EkRa(M))A方KRaKUbDEkRa(M)DMB方KRbKUa(d)公鑰加密：機(jī)密性，可認(rèn)證和簽名對(duì)于（2），信息認(rèn)證碼(MAC)

設(shè)S為通信中的發(fā)方A發(fā)送的所有可能的信源集合。為了達(dá)到防竄擾的目的，發(fā)方A和收方B設(shè)計(jì)一個(gè)編碼法則。發(fā)方A根據(jù)這個(gè)法則對(duì)信源S進(jìn)行編碼，信源經(jīng)編碼后成為消息，M表示所有可能的消息集合。發(fā)方A通信時(shí)，發(fā)送的是消息。用簡(jiǎn)單的例子說(shuō)明：設(shè)S={0,1},M={00,01,10,11},定義四個(gè)不同的編碼法則e0,e1,e2,e3:00011011e001e101e201e301這樣就構(gòu)成一個(gè)認(rèn)證碼MAC。發(fā)方A和收方B在通信前先秘密約定使用的編碼法則。例如，若決定采用e0，則以發(fā)送消息00代表信源0；發(fā)送消息10代表信源1，我們稱(chēng)消息00和10在e0之下是合法的。而消息01和11在e0之下不合法，收方將拒收這二個(gè)消息。信息的認(rèn)證和保密是不同的兩個(gè)方面，一個(gè)認(rèn)證碼可具有保密功能，也可沒(méi)有保密功能。認(rèn)證編碼的基本方法是要在發(fā)送的消息中引入多余度，使通過(guò)信道傳送的可能序列集Y大于消息集X。對(duì)于任何選定的編碼規(guī)則(相應(yīng)于某一特定密鑰):發(fā)方從Y中選出用來(lái)代表消息的許用序列，即碼字；收方根據(jù)編碼規(guī)則唯一地確定出發(fā)方按此規(guī)則向他傳來(lái)的消息。竄擾者由于不知道密鑰，因而所偽造的假碼字多是Y中的禁用序列，收方將以很高的概率將其檢測(cè)出來(lái)而被拒絕。認(rèn)證系統(tǒng)設(shè)計(jì)者的任務(wù)是構(gòu)造好的認(rèn)證碼(AuthenticationCode),使接收者受騙概率極小化。令x∈X為要發(fā)送的消息，k∈K為發(fā)方選定的密鑰，y=A(x,k)∈Y是表示消息X的認(rèn)證碼字，Ak={y=A(x,k)|x∈X}為認(rèn)證碼。Ak是Y中的許用(合法)序列集，易見(jiàn)Y=Ak∪Ak。接收者知道認(rèn)證編碼A(.,.)和密鑰k,故從收到的y,唯一確定出消息x。竄擾者雖然知道X,Y,y,A(.,.),但不知具體密碼k,他的目的是想偽造出一個(gè)假碼字y*，使y*∈Ak,以使接收者收到y(tǒng)*后可用密鑰k解密，得到一個(gè)合法的消息x*。這樣，竄擾者欺詐成功。消息認(rèn)證消息認(rèn)證是使意定的消息接收者能夠檢驗(yàn)收到的消息是否真實(shí)的方法。檢驗(yàn)內(nèi)容應(yīng)包括：(1)證實(shí)報(bào)文的源和宿；(2)報(bào)文內(nèi)容是否曾受到偶然的或有意的篡改；(3)報(bào)文的序號(hào)和時(shí)間欄?？傊⒄J(rèn)證使接收者能識(shí)別：消息的源，內(nèi)容的真?zhèn)?，時(shí)間性和意定的信宿。這種認(rèn)證只在相應(yīng)通信的雙方之間進(jìn)行，而不允許第三者進(jìn)行上述認(rèn)證。認(rèn)證不一定是實(shí)時(shí)的。可用消息認(rèn)證碼MAC對(duì)消息做認(rèn)證。.利用函數(shù)f和密鑰k，對(duì)要發(fā)送的明文x或密文y變換成rbit的消息認(rèn)證碼f(k,x)(或f(k,y))，將其稱(chēng)為認(rèn)證符附加在x(或y)之后發(fā)出，以x//As(或y//As)表示，其中“//”符號(hào)表示數(shù)字的鏈接。接收者收到發(fā)送的消息序列后，按發(fā)方同樣的方法對(duì)接收的數(shù)據(jù)(或解密后)進(jìn)行計(jì)算，應(yīng)得到相應(yīng)的rbit數(shù)據(jù)。

兩種實(shí)用的MAC算法

(一)十進(jìn)制移位加MAC算法

Sievi于1980年向ISO提出一項(xiàng)消息認(rèn)證法的建議[Davies等1984]，這種認(rèn)證法稱(chēng)為十進(jìn)制移位加算法(DecimalShiftandAddAlgorithm)，簡(jiǎn)記為DSA。它特別適用于金融支付中的數(shù)值消息交換業(yè)務(wù)。消息按十位十進(jìn)制數(shù)字分段處理，不足十位時(shí)在右邊以0補(bǔ)齊，下面舉例說(shuō)明。令x1=1583492637是要認(rèn)證的第一組消息，令b1=5236179902和b2=4893524771為認(rèn)證用的密鑰。DSA算法是以b1和b2并行對(duì)x1進(jìn)行運(yùn)算。先算x1+b1,x1+b2(mod1010),而后根據(jù)b2的第一位數(shù)值4對(duì)x1+b2循環(huán)左移4位，記作R(4)(x1+b1)再與(x1+b1)相加得

R(4)(x1+b1)+(x1+b1)

P1(mod1010)類(lèi)似地，右路在b1的第一位數(shù)值5控制下運(yùn)算結(jié)果為

R(5)(x1+b2)+(x1+b2)=Q1(mod1010)表：左路 右路第b1=5236179902 b2=4893224771一+x1=1583492637 +x1=1583492637輪b1+x1=6819672539b2+x1=6477017408+R(4)(b1+x1)=2539681976+R(5)(b2+x1)=1740864770P1=9359354506Q1=8217882178第+x2=5283586900+x2=5283586900二P1+x2=4642941406Q1+x2=3501469078輪+R(8)(P1+x2)=4294140646+R(9)(Q1+x2)=7835014690P2=8937082052Q2=1336483768

….

….第P10=7869031447Q10=3408472104十P10+Q10=1277403551(mod1010)輪403551+1277

認(rèn)證符404828(mod1010)將第二組消息x2=528358586900分別與P1和Q1相加，其結(jié)果又分別以P1和Q1的第一位控制循環(huán)移位后進(jìn)行相加得到P2和Q2，依此類(lèi)推。直至進(jìn)行十輪后得P10和Q10。計(jì)算P10+Q10(mod1010),并將結(jié)果的后6位數(shù)與前4位數(shù)在(mod1010)下相加，得6位認(rèn)證符！(二)采用DES的認(rèn)證算法：有二種基于DES的認(rèn)證算法，一種按CFB模式，一種按CBC模式運(yùn)行。在CBC模式下，消息按64bit分組，不足時(shí)以0補(bǔ)齊，送入DES系統(tǒng)加密，但不輸出密文，只取加密結(jié)果最左邊的r位作為認(rèn)證符。(64bit)x1,..xnAs(24bitor32bit)64比特寄存器DES選左r位+y1,y2,…,yn(64bit數(shù)組)yn利用CBC模式下DES的認(rèn)證法

r取大小可由通信雙方約定。美國(guó)聯(lián)邦電信建議采用24bit[見(jiàn)FTSC-1026],而美國(guó)金融系統(tǒng)采用32bit[ABA,1986]64bit寄存器DES選左邊k位選左邊r位As+yixi利用工作于CFB模式下DESk對(duì)于（3），散列函數(shù)(HashFunction)

若對(duì)相當(dāng)長(zhǎng)的文件通過(guò)簽名認(rèn)證怎么辦？如一個(gè)合法文件有數(shù)兆字節(jié)長(zhǎng)。自然按160比特分劃成一塊一塊，用相同的密鑰獨(dú)立地簽每一個(gè)塊。然而，這樣太慢。

解決的辦法：引入可公開(kāi)的密碼散列函數(shù)(Hashfunction)。它將取任意長(zhǎng)度的消息做自變量，結(jié)果產(chǎn)生規(guī)定長(zhǎng)度的消息摘要。[如，使用數(shù)字簽名標(biāo)準(zhǔn)DSS，消息摘要為160比特]，然后簽名消息摘要。對(duì)數(shù)字簽名來(lái)說(shuō)，散列函數(shù)h是這樣使用的：消息：x任意長(zhǎng)消息摘要：Z=h(x)160bits

簽名：y=sigk(Z)320bits(簽名一個(gè)消息摘要)驗(yàn)證簽名:(x,y),其中y=sigk(h(x))，使用公開(kāi)的散列函數(shù)h，重構(gòu)作Z'=h(x)。然后檢驗(yàn)Verk(Z,y),來(lái)看Z

=Z'。

(一)無(wú)碰撞的散列函數(shù)用以認(rèn)證的散列函數(shù)，能否減弱認(rèn)證方案的安全性？這個(gè)問(wèn)題是要分析的。簽名的對(duì)象由完整消息變成消息摘要，這就有可能出現(xiàn)偽造。

(a)偽造方式一：Oscar以一個(gè)有效簽名(x,y)開(kāi)始，此處y=sigk(h(x))。首先他計(jì)算Z=h(x)，并企圖找到一個(gè)x'=x滿足h(x')=h(x)。若他做到這一點(diǎn)，則(x',y)也將為有效簽名。為防止這一點(diǎn)，要求函數(shù)h具有無(wú)碰撞特性。

定義1(弱無(wú)碰撞)，散列函數(shù)h稱(chēng)為是弱無(wú)碰撞的，是指對(duì)給定消息x∈X，在計(jì)算上幾乎找不到異與x的x'∈X使h(x)=h(x')。