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

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

(美)BruceSchneier

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

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

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

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

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

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

的

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

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

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

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

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

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

a

J,b

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

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

ABCDEFGHIJKLMNOPQRSTUVWXYZ

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

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

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

THISCIPHERISCERTAINLYNOTSECURECipher

WOSVJSSOOUPCFLBWHSQSIQVDVLMXYO替代(SubstitutionCipher)

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

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

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

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

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

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

而若給定的明文是：cryptography首先找分成6個字母長的明文組：crypto|graphy

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

條件熵H(X|Y)理解為觀察到Y(jié)后X還保留的不確定性，通常將其成為含糊度，而將H(Y|X)稱為散布度，I(X,Y)=H(X)-H(X|Y)表示X上減少量。聯(lián)合熵和條件熵（續(xù)）定理1，當(dāng)且僅當(dāng)X和Y獨立是等號成立。定理2定理3，當(dāng)且僅當(dāng)X和Y獨立是等號成立。聯(lián)合熵和條件熵（續(xù)）定理4設(shè)(P,C,K,e,d)是一個密碼系統(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一個完善保密系統(tǒng)(P,C,K,e,d)稱為是完善的或無條件的保密系統(tǒng)，如果H(P|C)=H(P)或I(P,C)=0.

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

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

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

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

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

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

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

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

AES

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

AES

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

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

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

Nk可以取的值為4，6，8，對應(yīng)的密鑰長度為128，192，256bits。Fig3.當(dāng)Nb=6時的狀態(tài)和Nk=4時的密鑰布局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.分組長度和密鑰長度均為128bits時的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是一個非線性的字節(jié)替代，獨立地在每個狀態(tài)字節(jié)上進行運算。它包括兩個變換。

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

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

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

該變換可以用一個256字節(jié)的表來實現(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與分組長度Nb有關(guān)，如下表所示：NbC1C2C3412361238134Fig7.ByteRotation04812159132610143711150481259131101426153711循環(huán)左移1字節(jié)循環(huán)左移2字節(jié)循環(huán)左移3字節(jié)MixColumn(列混合)將狀態(tài)的列看作是有限域GF(28)上的多項式a(x)，與多項式c(x)=03x3+01x2+01x+02相乘(模x4＋1)。令b(x)=c(x)×a(x)，寫成矩陣形式為：

b002030101a0

b1=01

020301a1

b20101

0203a2

b303010102a3Fig8.MixColumn

這一運算作用在每一列上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)按比特異或。輪密鑰是通過KeySchedule過程從密碼密鑰中得到的，輪密鑰長度等于分組長度。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);}提前進行密鑰擴展后的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)度包括兩個部分：密鑰擴展和輪密鑰選取。密鑰bit的總數(shù)＝分組長度×（輪數(shù)Round＋1）例如當(dāng)分組長度為128bits和輪數(shù)Round為10時，輪密鑰長度為128×(10＋1)＝1408bits。將密碼密鑰擴展成一個擴展密鑰。從擴展密鑰中取出輪密鑰：第一個輪密鑰由擴展密鑰的第一個Nb個4字節(jié)字，第二個圈密鑰由接下來的Nb個4字節(jié)字組成，以此類推。密鑰擴展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的解密算法解密算法與加密算法不同每個階段均可逆，因此易證解密函授的確可以恢復(fù)明文AES

算法的設(shè)計原理

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

+x6

+x2

+x)+a(x)(x7

+x6

+x5

+x4

+1)modx8

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

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

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

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

其中a,b,c,d,e屬于集合F,F可以是有理數(shù)域，也可以是復(fù)數(shù)域。一般采用如下方程：橢圓曲線密碼示意圖橢圓曲線上的加法:P+Q=R橢圓曲線上一點的2倍:P+P=R.有限域上橢圓曲線Ep(a,b)加法公式:P+O=P如果P=(x,y)，則P+(x,-y)=O，(x,-y)點是P的負點，記為-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)橢圓曲線用于加密找到一個難題：考慮等式Q=kP，其中Q、P屬于Ep(a,b)，k<p已知k和P，計算Q，是容易的已知Q和P，計算k，是困難的選擇Ep(a,b)的元素G,使得G的階n是一個大素數(shù)G的階是指滿足nG=O的最小n值秘密選擇整數(shù)r，計算P=rG，然后公開(p,a,b,G,P)，P為公鑰保密r加密M：先把消息M變換成為Ep(a,b)中一個點Pm然后，選擇隨機數(shù)k，計算密文Cm=(kG,Pm+kP)如果k使得kG或者kP為O，則要重新選擇k.解密Cm:(Pm+kP)-r(kG)=Pm+krG-rkG=Pm加密信息有擴張橢圓曲線密碼的安全性

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

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

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

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

是一個公開的函數(shù)，它將任意長的信息映射成一個固定長度的信息。

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

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

兩種實用的MAC算法

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

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

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

P1(mod1010)類似地，右路在b1的第一位數(shù)值5控制下運算結(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)移位后進行相加得到P2和Q2，依此類推。直至進行十輪后得P10和Q10。計算P10+Q10(mod1010),并將結(jié)果的后6位數(shù)與前4位數(shù)在(mod1010)下相加，得6位認(rèn)證符！(二)采用DES的認(rèn)證算法：有二種基于DES的認(rèn)證算法，一種按CFB模式，一種按CBC模式運行。在CBC模式下，消息按64bit分組，不足時以0補齊，送入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取大小可由通信雙方約定。美國聯(lián)邦電信建議采用24bit[見FTSC-1026],而美國金融系統(tǒng)采用32bit[ABA,1986]64bit寄存器DES選左邊k位選左邊r位As+yixi利用工作于CFB模式下DESk對于（3），散列函數(shù)(HashFunction)

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

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

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

=Z'。

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

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

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