《密碼學(xué)基礎(chǔ)》全套教學(xué)課件

——密碼的歷史及古典密碼傳統(tǒng)加密技術(shù)4學(xué)時(shí)第1章

古典密碼第2章分組密碼與DES第3章AES第4章

序列密碼第5章公鑰密碼與RSA第6章

數(shù)字簽名第7章消息認(rèn)證與Hash函數(shù)全套可編輯PPT課件密碼的起源和發(fā)展密碼學(xué)的基本概念古典密碼初等密碼分析主要內(nèi)容全套可編輯PPT課件了解密碼的產(chǎn)生和發(fā)展歷史掌握密碼學(xué)的基本概念理解古典密碼的加密思想，掌握基本的加密方法：置換和代替掌握密碼體制的分類方法理解初等密碼分析的思想教學(xué)目的全套可編輯PPT課件古代——近代——現(xiàn)代

一、密碼的起源和發(fā)展19491976全套可編輯PPT課件隱寫術(shù)Staganography

由希臘詞Steganos（覆蓋）和Graphein（寫）派生而來。密碼術(shù)Cryptography

由希臘詞Kryptos（隱藏）派生而來。密碼的起源希波戰(zhàn)爭(zhēng)，漏格板希斯塔亞烏斯，在奴隸頭皮上寫字中國(guó)古代，蠟封小球公元一世紀(jì)，普林尼，隱形墨水一、密碼的起源和發(fā)展密碼技術(shù)的發(fā)展15世紀(jì)，意大利建筑師利昂．阿爾伯提設(shè)計(jì)的密碼盤密碼技術(shù)的發(fā)展?jié)摲嚓P(guān)影視作品例：

愷撒《高盧記》——將羅馬字母用希臘字母替換蘇托尼厄斯《愷撒傳》——愷撒密碼一、密碼的起源和發(fā)展兩種基本加密方法代替——對(duì)標(biāo)準(zhǔn)書寫符號(hào)的修改Substitution機(jī)械密碼大行其道Enigma，Hagelin密碼機(jī)密碼破譯成果輝煌紫密，圖靈炸彈，中途島新技術(shù)的大量使用微粒照片，圖靈機(jī)一、密碼的起源和發(fā)展二戰(zhàn)中的密碼特點(diǎn)機(jī)械密碼：用機(jī)器實(shí)現(xiàn)代替與置換三種有代表性的密碼機(jī)：

Enigma（德、意、日軍方）

Lorenz（德國(guó)高層）Hagelin（盟國(guó)：美、英、法等）

二戰(zhàn)中的密碼一、密碼的起源和發(fā)展三、古典密碼（Classical

Ciphers）Enigma三、古典密碼（Classical

Ciphers）Hagelin1912年，美國(guó)人愛德華.休.赫本(EdwardHughHebern)發(fā)明了可以通過”移動(dòng)字母板”加密的打字機(jī)，并申請(qǐng)專利。1918年，德國(guó)人阿瑟．謝爾比斯為Enigma申請(qǐng)專利。瑞典人鮑里斯.愷撒.威廉.哈格林（BorisCaesarWilhelmHagelin），靠密碼機(jī)發(fā)財(cái)?shù)谝蝗?/p>

三、古典密碼（Classical

Ciphers）機(jī)械密碼轉(zhuǎn)輪機(jī)(RotorMachine)

大量裝備、參加實(shí)戰(zhàn)、遭到破譯、徹底曝光

1918年，德國(guó)發(fā)明家阿瑟．謝爾比斯為Enigma申請(qǐng)專利，并與理查德．里特建立了謝爾比斯＆里特公司，出售Enigma，售價(jià)為今天的3萬$/臺(tái)困境：賣不出去采取措施：拼命改進(jìn)轉(zhuǎn)機(jī)：1922年，丘吉爾出版《第一次世界大戰(zhàn)回憶錄》

Enigma納粹德國(guó)的四大軍事象征

普魯士之鷹鐵十字EnigmaEnigma英國(guó)組織破譯（布萊切利莊園）圖靈發(fā)明BombeEnigma破譯Enigma的意義：波蘭人，Bomba，機(jī)械化密碼分析時(shí)代的到來英國(guó)Bombe，證明了機(jī)械化密碼分析手段在破解機(jī)械化密碼時(shí)的極端必要性波蘭和英國(guó)專家能手工破譯，說明了密碼破譯歸根結(jié)底是人類智慧的勝利。Enigma密碼學(xué)(Cryptology):

研究信息系統(tǒng)安全保密的科學(xué)，包括密碼編碼學(xué)和密碼分析學(xué)。密碼編碼學(xué)(Cryptography):

主要研究對(duì)信息進(jìn)行編碼,實(shí)現(xiàn)對(duì)信息的隱蔽.密碼分析學(xué)(Cryptanalytics):主要研究加密消息的破譯或消息的偽造.二、密碼學(xué)的基本概念密碼體制：是一個(gè)五元組（P,C,K,E,D)，滿足條件：（1）P是可能明文的有限集（明文空間）（2）C是可能密文的有限集（密文空間）（3）K是一切可能密鑰構(gòu)成的有限集（密鑰空間）（4）任意k∈K,有一個(gè)加密算法ek∈E和相應(yīng)的解密算法dk∈D，使得ek:P→C和dk:C→P分別為加密解密函數(shù)，滿足dk(ek(x))=x,這里x∈P。二、密碼學(xué)的基本概念密碼體制Example明文：Allofgaulisdividedintothreeparts.密文：DOORIJEXOLVGLYLGHGLQWRWKUHHSDUWV代替密碼2.單表代替（MonoalphabeticSubstitution）所有的消息用同一個(gè)代替表加密，相同的明文替換為相同的密文。例：

乘法密碼 仿射密碼，多項(xiàng)式代替密碼 密鑰短語(yǔ)密碼（將口令字中的字符無重復(fù)地寫下，再將余下的字符按順序?qū)懞茫⑺鼈兒兔魑淖帜附⒁灰粚?duì)應(yīng)的關(guān)系。）三、古典密碼（Classical

Ciphers）代替密碼多表代替：1412年，埃及數(shù)學(xué)家艾哈邁德.卡勒卡尚迪(Ahmadal-Qalqashandi)在百科全書中第一次提出。1508年，德國(guó)修道院院長(zhǎng)約翰內(nèi)斯.特米特里烏斯(HohannesTrithemius)首先構(gòu)造出方表（tableau）——多個(gè)代替表1553年，意大利學(xué)者吉奧萬.巴蒂斯塔.貝拉索（GiovanBattistaBellaso）設(shè)計(jì)出了密鑰。貝拉索密碼，使用時(shí)間較長(zhǎng)，美國(guó)內(nèi)戰(zhàn)時(shí)北軍使用。多表代替1586年，法國(guó)外交官布萊斯.德.維吉尼亞（BlaiseDeVigenere）對(duì)貝拉索密碼進(jìn)行改良。Vigenère密碼：1854年，被英國(guó)人查理斯.巴貝奇（CharlesBabbage）所破譯查理斯.巴貝奇（1792-1871）：設(shè)計(jì)了差分機(jī)（differenceengine）和分析機(jī)（analyticalengine），是現(xiàn)代計(jì)算機(jī)的雛形。多表代替二、置換技術(shù)（Permutation）1.柵欄技術(shù)——按列寫入，按行讀出。例：用深度為2的柵欄技術(shù)加密明文“meetmeaftertheparty”

可寫為按行讀出密文為“mematrhtgpryetefeteoaat”2.矩陣密碼——把消息按行寫入，再按列讀出。mematrhtgpryetefeteoaat三、古典密碼（Classical

Ciphers）置換密碼加密部分可分為：多表代替模塊：轉(zhuǎn)輪組單表代替模塊：連接板附加模塊：反射板Enigma破譯或攻擊（Break/Attack）密碼的方法包括窮舉破譯法（ExhaustiveAttack）和分析法兩類。窮舉法，又稱為強(qiáng)力攻擊（Brute-forceMethod），指對(duì)截收的密文依次用各種可能的密鑰試譯，直到得到有意義的明文；或者在不變密鑰下，對(duì)所有可能的明文加密直到得到與截獲密文一致，這又稱為完全試湊法（CompleteTrial-and-errorMethod）四、初等密碼分析唯密文攻擊（CiphertectOnlyAttak）分析者從僅知道的密文進(jìn)行分析，試圖得出明文或密鑰。已知明文攻擊（KnowPlaintextAttak）分析者除了有截獲密文外，還有一些已知的明文－密文對(duì)。選擇明文攻擊（ChosenPlaintextAttack）分析者可以選定任何明文－密文對(duì)進(jìn)行攻擊，以確定未知密鑰。選擇密文攻擊（ChosenCiphertextAttack）分析者可以利用解密機(jī)由他所選的密文解密出相應(yīng)明文，以確定未知密鑰。四、初等密碼分析密碼分析分類分組密碼與數(shù)據(jù)加密標(biāo)準(zhǔn)4學(xué)時(shí)分組密碼的基本概念數(shù)據(jù)加密標(biāo)準(zhǔn)DESDES的產(chǎn)生及使用DES算法細(xì)節(jié)DES的安全性分析DES在設(shè)計(jì)上的優(yōu)點(diǎn)分組密碼的設(shè)計(jì)原理分組密碼的工作方式主要內(nèi)容現(xiàn)代密碼對(duì)稱密碼非對(duì)稱密碼序列密碼分組密碼對(duì)稱密碼非對(duì)稱密碼現(xiàn)代密碼的分類加密方式序列密碼（Streamcipher）：也叫流密碼，用隨機(jī)的密鑰序列依次對(duì)明文字符加密，一次加密一個(gè)字符。分組密碼（Blockcipher）：將明文劃分為長(zhǎng)度固定的組，逐組進(jìn)行加密，得到長(zhǎng)度固定的一組密文。密文分組中的每一個(gè)字符與明文分組的每一個(gè)字符都有關(guān)。第一節(jié)分組密碼的基本概念加密算法解密算法明文密鑰密鑰x=(x1,…,xm

)y=(y1,…,yn

)密文第一節(jié)分組密碼的基本概念分組密碼加密框圖分組長(zhǎng)度：64bit有效密鑰長(zhǎng)度：56bit密鑰生成算法：產(chǎn)生16個(gè)48bit的子密鑰解密過程與加密過程相同，所使用的密鑰也相同，但各個(gè)子密鑰的使用順序不同。算法的全部的細(xì)節(jié)公開，安全性完全依賴于密鑰。第二節(jié)數(shù)據(jù)加密標(biāo)準(zhǔn)DESDES基本特征初始置換IP16輪迭代逆初始置換IP-1子密鑰產(chǎn)生算法。

第二節(jié)數(shù)據(jù)加密標(biāo)準(zhǔn)DESDES算法細(xì)節(jié)算法構(gòu)成對(duì)64bit的明文重新排列，而后分成左右兩段，每段32bit，以L0和R0表示。IP中各列元素位置號(hào)數(shù)相差為8，相當(dāng)于將原明文各字節(jié)按列寫出，各列比特經(jīng)過偶采樣和奇采樣置換后，再對(duì)各行進(jìn)行逆序排列，將陣中元素按行讀出，構(gòu)成置換的輸出。第二節(jié)數(shù)據(jù)加密標(biāo)準(zhǔn)DES初始置換IP在16圈迭代之后，將左右兩段合并為64bit，進(jìn)行置換IP-1，得到輸出的64bit密文。第二節(jié)數(shù)據(jù)加密標(biāo)準(zhǔn)DES逆初始置換IP和IP-1的輸入與輸出是已知的一一對(duì)應(yīng)關(guān)系作用：打亂原來輸入的ASCII碼字劃分，并將原來明文的校驗(yàn)位（如果有的話）變?yōu)镮P輸出的一個(gè)字節(jié)。第二節(jié)數(shù)據(jù)加密標(biāo)準(zhǔn)DES逆初始置換將經(jīng)過IP置換后的數(shù)據(jù)分成32bit的左右兩段，進(jìn)行16圈迭代每次迭代只對(duì)右邊的32bit進(jìn)行一系列的加密變換一輪迭代即將結(jié)束時(shí)，將左邊的32bit與右邊進(jìn)行變換后得到的32bit按位模2加，作為下一輪迭代時(shí)右邊的段，并將原來右邊未經(jīng)變換的段直接作為下一輪迭代時(shí)左邊的段。

第二節(jié)數(shù)據(jù)加密標(biāo)準(zhǔn)DES乘積變換——DES算法的核心64比特初始密鑰經(jīng)過置換選擇PC-1循環(huán)移位置換選擇PC-2產(chǎn)生16次迭代所用的子密鑰ki

初始密鑰的第8、16、24、32、40、48、56、64位為奇偶校驗(yàn)位，其余56位為有效位，PC-1的目的是從64位中選出56位有效位。第二節(jié)數(shù)據(jù)加密標(biāo)準(zhǔn)DES子密鑰生成算法每次移位后，將C和D中的原存數(shù)送給置換選擇PC-2，PC-2將C中第9、18、22、25位和D中第7、9、15、26位刪去，將其余數(shù)字置換位置，輸出48比特，作為子密鑰。第二節(jié)數(shù)據(jù)加密標(biāo)準(zhǔn)DES子密鑰生成IP：初始置換ki

：第i次迭代所用的子密鑰Li、Ri：第i次迭代時(shí)左邊和右邊的32比特f：每次迭代時(shí)對(duì)右邊所作的變換：逐位模2加。

第二節(jié)數(shù)據(jù)加密標(biāo)準(zhǔn)DESDES算法的數(shù)學(xué)表示符號(hào)說明加密過程：64Bit明文64Bit密文（1）（2）第二節(jié)數(shù)據(jù)加密標(biāo)準(zhǔn)DESDES算法的數(shù)學(xué)表示解密過程：（64比特明文）（64比特密文）第二節(jié)數(shù)據(jù)加密標(biāo)準(zhǔn)DESDES算法的數(shù)學(xué)表示互補(bǔ)對(duì)稱性弱密鑰和半弱密鑰對(duì)DES的強(qiáng)力攻擊差分分析和線性分析第二節(jié)數(shù)據(jù)加密標(biāo)準(zhǔn)DESDES的安全性DES設(shè)計(jì)上的優(yōu)點(diǎn)主要體現(xiàn)在以下幾個(gè)方面循環(huán)次數(shù)雪崩準(zhǔn)則精巧的S盒和P盒第二節(jié)數(shù)據(jù)加密標(biāo)準(zhǔn)DESDES在設(shè)計(jì)上的優(yōu)點(diǎn)電子密碼本ECB(electroniccodebookmode)密碼分組鏈接CBC(cipherblockchaining)密碼反饋CFB(cipherfeedback)輸出反饋OFB(outputfeedback)第四節(jié)分組密碼的工作方式第四節(jié)分組密碼的工作方式分組密碼的加密方式和設(shè)計(jì)準(zhǔn)則DES算法的基本結(jié)構(gòu)，非線性運(yùn)算DES的安全性及設(shè)計(jì)上的優(yōu)點(diǎn)分組密碼的設(shè)計(jì)原理及Feistel模型分組密碼的四種工作方式第二節(jié)數(shù)據(jù)加密標(biāo)準(zhǔn)DES小結(jié)高級(jí)加密標(biāo)準(zhǔn)4學(xué)時(shí)AES概述Rijndael加密算法主要內(nèi)容了解高級(jí)加密標(biāo)準(zhǔn)的設(shè)計(jì)思想掌握AES算法的運(yùn)算過程教學(xué)目的1997年4月15日，（美國(guó)）國(guó)家標(biāo)準(zhǔn)技術(shù)研究所（NIST）發(fā)起征集高級(jí)加密標(biāo)準(zhǔn)AES的活動(dòng)，目的是確定一個(gè)非保密的、可以公開技術(shù)細(xì)節(jié)的、全球免費(fèi)使用的分組密碼算法，作為新的數(shù)據(jù)加密標(biāo)準(zhǔn)。1997年9月12日，美國(guó)聯(lián)邦登記處公布了正式征集AES候選算法的通告。第一節(jié)AES

概述第一節(jié)AES概述對(duì)AES的基本要求：比三重DES快至少與三重DES一樣安全數(shù)據(jù)分組長(zhǎng)度為128比特密鑰長(zhǎng)度為128/192/256比特。AESBackground第一節(jié)AES

概述1998年8月，首屆AES會(huì)議，指定15個(gè)候選算法。1999年3月22日，第二次AES會(huì)議，候選名單減少為5個(gè)：RC6，Rijndael，SERPENT，Twofish和MARS。2000年4月13日，第三次AES會(huì)議，對(duì)這5個(gè)候選算法的各種分析結(jié)果進(jìn)行了討論。2000年10月2日，NIST宣布了獲勝者—Rijndael算法，2001年11月出版了最終標(biāo)準(zhǔn)FIPSPUB197。AESBackground第一節(jié)AES

概述Rijndael加解密過程第六節(jié)高級(jí)加密標(biāo)準(zhǔn)AES唯一的非線性運(yùn)算，代替表（S盒）可逆，由兩個(gè)變換構(gòu)成：首先在GF(28)中模m(x)取乘法逆，m(x)=x8+x4+x3+x+1，0映射到自身；然后經(jīng)過一個(gè)仿射變換字節(jié)代替（Bytesub）第二節(jié)Rijndael加密算法逆運(yùn)算（InvByteSub）先經(jīng)過仿射變換的逆變換作用之后，再在GF(28)中模m(x)取乘法逆。字節(jié)代替（Bytesub）第二節(jié)Rijndael加密算法行移位（ShiftRow）第二節(jié)Rijndael加密算法狀態(tài)行移位不同的位移量第0行不移動(dòng)第1行循環(huán)左移C1字節(jié)第2行循環(huán)左移C2字節(jié)第3行循環(huán)左移C3字節(jié)，逆運(yùn)算（InvShiftRow）

后面3行分別循環(huán)左移：

Nb-C1字節(jié)

Nb-C2字節(jié)

Nb-C3字節(jié)行移位（ShiftRow）第二節(jié)Rijndael加密算法Rijndael加密程序S=B⊕K0；Fori=1toNr-1 S=ByteSub(S)；

S=ShiftRow(S)；

S=MixColumn(S)；

S=Ki⊕S；S=ByteSub(S)；S=ShiftRow(S)；S=KNrS；Rijndael算法第二節(jié)Rijndael加密算法注：最后一圈無列混合Rijndael解密程序S=KNr⊕C；S=InvShiftRow(S)；S=InvByteSub(S)；S=KNr⊕

S；Fori=Nr-1to1 S=KiS；

S=InvMixColumn(S)；

S=InvShiftRow(S)；

S=ByteSub(S)；

S=K0⊕S；Rijndael算法第二節(jié)Rijndael加密算法將16字節(jié)初始密鑰擴(kuò)展為156字節(jié)（44字）的擴(kuò)展密鑰；擴(kuò)展密鑰的前四個(gè)字直接由輸入密鑰中復(fù)制，即w[0]~w[3]；w[i]的值依賴于w[i-1]和w[i-4]密鑰擴(kuò)展算法第二節(jié)Rijndael加密算法（迭代圈數(shù)為10時(shí)）對(duì)于下標(biāo)為4的倍數(shù)的密鑰字，其產(chǎn)生方法更為復(fù)雜，表示為函數(shù)g包括的運(yùn)算步驟有：字循環(huán)（RotWord）：使一個(gè)字中的4個(gè)字節(jié)循環(huán)左移一個(gè)字節(jié)字節(jié)代換（SubWord）：利用S盒對(duì)輸入字中的每個(gè)字節(jié)進(jìn)行代替字循環(huán)與字節(jié)代換的結(jié)果再與輪常量Rcon[j]相異或密鑰擴(kuò)展算法第二節(jié)Rijndael加密算法無弱密鑰或補(bǔ)密鑰能有效抵抗差分分析和線性分析迭代圈數(shù)大于6時(shí)可抗截?cái)嗖罘址治鋈?shù)大于7時(shí)可抗Square攻擊密鑰量大，窮舉攻擊較困難Rijndael的安全性第二節(jié)Rijndael加密算法第一節(jié)序列的隨機(jī)性２學(xué)時(shí)第四章序列的隨機(jī)性隨機(jī)性的概念及參數(shù)隨機(jī)性假設(shè)偽隨機(jī)數(shù)發(fā)生器線性同余發(fā)生器用密碼編碼產(chǎn)生隨機(jī)數(shù)BBS發(fā)生器主要內(nèi)容掌握隨機(jī)性的含義及衡量方法理解隨機(jī)性假設(shè)的含義掌握線性同余發(fā)生器的原理及參數(shù)選擇理解如何用密碼產(chǎn)生隨機(jī)數(shù)理解BBS發(fā)生器的原理教學(xué)目的隨機(jī)序列：不能重復(fù)產(chǎn)生的序列幾個(gè)相關(guān)概念真隨機(jī)——不能重復(fù)產(chǎn)生密碼學(xué)意義上的隨機(jī)——不能預(yù)測(cè)偽隨機(jī)——看起來是隨機(jī)的，并能通過許多隨機(jī)性測(cè)試第一節(jié)序列的隨機(jī)性真隨機(jī)數(shù)發(fā)生器（TRNG）：利用物理方法實(shí)現(xiàn)的隨機(jī)數(shù)發(fā)生器，它是自然界隨機(jī)的物理過程（所產(chǎn)生物理現(xiàn)象的不確定性）的反映，即使算法等重要信息被暴露，都無法猜測(cè)其結(jié)果如何產(chǎn)生真隨機(jī)數(shù)1．若序列的周期為偶數(shù)，則在一個(gè)周期內(nèi)，0、1的個(gè)數(shù)相等；若周期為奇數(shù)，則在一個(gè)周期內(nèi)，0、1的個(gè)數(shù)相差1。2．在一個(gè)周期內(nèi)，長(zhǎng)度為l的游程數(shù)占游程總數(shù)的1/2l，且對(duì)于任意長(zhǎng)度，0游程與1游程個(gè)數(shù)相等。3．所有異相自相關(guān)函數(shù)值相等。Golomb隨機(jī)性假設(shè)第一節(jié)序列的隨機(jī)性偽隨機(jī)數(shù)發(fā)生器——將一個(gè)短的隨機(jī)數(shù)“種子”擴(kuò)展為較長(zhǎng)的偽隨機(jī)序列的確定算法。線性同余發(fā)生器（Linearcongruentialgenerator）用加密方式產(chǎn)生隨機(jī)數(shù)BBS發(fā)生器偽隨機(jī)數(shù)發(fā)生器第一節(jié)序列的隨機(jī)性評(píng)價(jià)線性同余發(fā)生器有以下準(zhǔn)則：（1）完整周期：即在一個(gè)周期中，０至m-1之間的數(shù)都出現(xiàn)。（2）滿足隨機(jī)性測(cè)試。（3）可以高效地實(shí)現(xiàn)。線性同余法的優(yōu)點(diǎn)：方便，快速；缺點(diǎn)：除初值外，其它數(shù)字都用確定算法產(chǎn)生。第一節(jié)序列的隨機(jī)性線性同余發(fā)生器線性同余發(fā)生器先后被JimReeds和JoanBoyar破譯后者還破譯了二次同余發(fā)生器Xn=(ax2n-1+bxn+c)modm和三次同余發(fā)生器Xn=ax3n-1+bx2n-1+cxn-1+d線性同余發(fā)生器NIST為銀行電子支付系統(tǒng)建議的標(biāo)準(zhǔn)算法，被PGP采納，在Internet中使用。方法：用三重DES的EDE模式產(chǎn)生，使用兩個(gè)密鑰K1，K2兩個(gè)驅(qū)動(dòng)隨機(jī)數(shù)：初始化時(shí)，設(shè)DT0為初始時(shí)刻的日期和時(shí)間(64bit)，V0為種子密鑰(64bit)輸出：64bit的隨機(jī)數(shù)Ri和更新后的Vi+1偽隨機(jī)數(shù)發(fā)生器第一節(jié)序列的隨機(jī)性（3）ANSIX9.17偽隨機(jī)數(shù)產(chǎn)生器

每一時(shí)刻要進(jìn)行三次加密，相當(dāng)于9次DES加密，由兩個(gè)偽隨機(jī)數(shù)驅(qū)動(dòng)。偽隨機(jī)數(shù)發(fā)生器第一節(jié)序列的隨機(jī)性用K1，K2對(duì)DT0加密，結(jié)果與V0相加，再對(duì)其加密，得到R0BlumBlumShub產(chǎn)生器（BBS發(fā)生器）:

利用數(shù)論方法產(chǎn)生偽隨機(jī)數(shù)選擇兩個(gè)大素?cái)?shù)p，q，滿足p≡q≡3mod4；計(jì)算其乘積n=pq；選擇隨機(jī)數(shù)s，(s,n)=1；通過以下公式迭代計(jì)算序列{Bi}偽隨機(jī)數(shù)發(fā)生器第一節(jié)序列的隨機(jī)性BBS發(fā)生器在密碼學(xué)意義上是相對(duì)安全的，但計(jì)算量比較大。偽隨機(jī)數(shù)發(fā)生器第一節(jié)序列的隨機(jī)性第二節(jié)序列密碼的原理2學(xué)時(shí)序列密碼的基本概念加密方式密鑰序列生成器線性反饋移位寄存器與m序列線性反饋移位寄存器移位寄存器的周期及m序列序列的線性復(fù)雜度與B-M算法主要內(nèi)容明文符號(hào)序列與密鑰符號(hào)序列逐個(gè)加密密鑰序列z=z1z2…的第i個(gè)符號(hào)加密明文序列m=m1m2…的第i個(gè)符號(hào)，即若密鑰序列重復(fù)使用，則稱為周期序列密碼，否則，就是一次一密密碼。序列密碼的加密方式第二節(jié)序列密碼的基本概念由密鑰流生成器生成第i個(gè)密鑰取決于第i時(shí)刻密鑰生成器的內(nèi)部狀態(tài)和初始密鑰。對(duì)序列密碼的安全性有兩個(gè)基本要求：根據(jù)密鑰序列以前的狀態(tài)，不能很容易地推導(dǎo)出后續(xù)狀態(tài)，即密鑰序列要有足夠高的隨機(jī)性；傳輸密鑰的秘密信道必須足夠安全。序列密碼中的密鑰密碼的安全性主要取決于所用密鑰的隨機(jī)性，所以設(shè)計(jì)序列密碼的核心問題是設(shè)計(jì)隨機(jī)性較好的密鑰流生成器設(shè)計(jì)密鑰流生成器的關(guān)鍵：尋找狀態(tài)轉(zhuǎn)移函數(shù)和輸出函數(shù)，使輸出的密鑰序列有良好的偽隨機(jī)性。密鑰流生成器第二節(jié)序列密碼的基本概念Rueppel將密鑰流生成器分為兩部分：驅(qū)動(dòng)部分和非線性組合部分。驅(qū)動(dòng)部分控制生成器的狀態(tài)，并為非線性組合部分提供周期長(zhǎng)、統(tǒng)計(jì)性能良好的序列；非線性組合部分利用這些序列組合出滿足要求的密鑰序列。密鑰流生成器第二節(jié)序列密碼的基本概念根據(jù)密鑰序列的產(chǎn)生方法，可將序列密碼可分為兩類：同步序列密碼（SynchronousStreamCipher）：狀態(tài)轉(zhuǎn)移函數(shù)與明文字符無關(guān)自同步序列密碼（Self-SynchronousStreamCipher）：狀態(tài)轉(zhuǎn)移函數(shù)與明文字符相關(guān)。在同步流密碼中，只要發(fā)送端和接收端有相同的種子或?qū)嶋H密鑰和內(nèi)部狀態(tài)，就能產(chǎn)生出相同的密鑰流，此時(shí)，認(rèn)為發(fā)送端和接收端的密鑰生成器是同步的。序列密碼的分類第二節(jié)序列密碼的基本概念衡量密碼體制安全性的方法計(jì)算安全性（computationalsecurity），又稱實(shí)際安全性（practicalsecrecy）：利用已有的最好的方法破譯該系統(tǒng)所需要的努力超過了敵手的破譯能力?？勺C明安全性（provablesecurity）：能用嚴(yán)格的數(shù)學(xué)方法證明破譯該體制等價(jià)于某個(gè)困難問題。無條件安全性（unconditionalsecurity）或完善保密性（perfectsecrecy）：在信息論意義上是安全的。理論保密的密碼體制定理若某一密碼系統(tǒng)的明文數(shù)、密文數(shù)和密鑰數(shù)都相等，則該密碼體制完全保密的充要條件是：將某一明文加密成某一密文的密鑰只能有一個(gè)；所有密鑰都是等概率的。理論保密的密碼體制組成：一系列存儲(chǔ)單元、若干個(gè)乘法器和加法器通過電路連接而成。假設(shè)共有n個(gè)存儲(chǔ)單元（此時(shí)稱該移位寄存器為n級(jí)），每個(gè)存儲(chǔ)單元可存儲(chǔ)一比特信息，在第i時(shí)刻各個(gè)存儲(chǔ)單元中的比特序列(aiai+1…ai+n-1)稱為移位寄存器的狀態(tài)，為初始狀態(tài)。線性反饋移位寄存器第三節(jié)線性反饋移位寄存器與m序列給定初態(tài)（101），按照反饋函數(shù)可求出各個(gè)時(shí)刻的狀態(tài)及輸出.狀態(tài)在第5時(shí)刻開始重復(fù)，因此輸出序列的周期是4，輸出序列為1011101110111011……線性反饋移位寄存器（LFSR）第三節(jié)線性反饋移位寄存器與m序列定理5-1

n級(jí)LFSR的周期≤2n-1證明：n級(jí)LFSR最多有2n種不同狀態(tài)，若初態(tài)為全零，則其后續(xù)狀態(tài)恒為零，構(gòu)成一個(gè)平凡序列，若初態(tài)不為零，則一個(gè)周期中最多出現(xiàn)2n-1種非零狀態(tài)，故狀態(tài)周期小于等于2n-1，同樣，輸出序列的周期也小于等于2n-1。定義5-1周期為2n-1的n級(jí)LFSR的輸出序列稱為m序列。移位寄存器的周期及m序列第三節(jié)線性反饋移位寄存器與m序列序列的隨機(jī)性隨機(jī)性的含義偽隨機(jī)數(shù)發(fā)生器序列密碼的基本概念LFSR及m序列小結(jié)公鑰密碼學(xué)與RSA6學(xué)時(shí)第五章對(duì)稱密碼的弱點(diǎn)及公鑰密碼的原理MH背包公鑰密碼Diffie-Hellman密鑰交換RSA密碼主要內(nèi)容密鑰量大密鑰管理困難：傳遞、換發(fā)、保存無法實(shí)現(xiàn)網(wǎng)絡(luò)中的簽名、認(rèn)證等應(yīng)用對(duì)稱密碼的弱點(diǎn)第一節(jié)公鑰密碼的原理密鑰量大對(duì)稱密碼的弱點(diǎn)設(shè)系統(tǒng)中共有n個(gè)用戶，兩兩進(jìn)行保密通信，總共需要多少個(gè)密鑰？當(dāng)n=5時(shí)，C（5，2）=10當(dāng)n=1000時(shí)，C（1000，2）=499500密鑰量大對(duì)稱密碼的弱點(diǎn)設(shè)系統(tǒng)中共有n個(gè)用戶，兩兩進(jìn)行保密通信，每個(gè)用戶有多少個(gè)密鑰？n-1個(gè)密鑰管理困難對(duì)稱密碼的弱點(diǎn)對(duì)稱密碼的弱點(diǎn)無法適應(yīng)網(wǎng)絡(luò)應(yīng)用數(shù)字簽名身份認(rèn)證消息認(rèn)證公鑰密碼的原理基本原理使用兩個(gè)不同的密鑰，一個(gè)用于加密，一個(gè)用于解密用于加密的密鑰Ek可以公開，用于解密的密鑰Dk保密Ek與Dk之間有聯(lián)系，但不能由Ek很容易地算出Dk公鑰密碼的原理加密與解密公鑰密碼的原理c=Ek(m)m=Dk(c)公鑰密碼的優(yōu)點(diǎn)密鑰數(shù)量大大減少密鑰管理方便公鑰密碼的原理公鑰密碼的安全性公鑰密碼的原理計(jì)算復(fù)雜性理論公鑰密碼的原理如何構(gòu)造陷門單向函數(shù)：利用困難問題背包問題離散對(duì)數(shù)問題整數(shù)分解問題橢圓曲線離散對(duì)數(shù)問題公鑰密碼的原理典型公鑰密碼背包密碼RSA密碼Rabin密碼ElGamal密碼橢圓曲線密碼背包密碼1978年，Merkle和Hellman提出了基于背包問題的公鑰密碼體制。如何解決背包問題：窮舉法背包問題當(dāng)物品個(gè)數(shù)為100時(shí)，有2100≈1.27×1030種可能性。把全世界所有的5億臺(tái)計(jì)算機(jī)全部聯(lián)網(wǎng)來求解這個(gè)問題，需要1000萬年！

背包密碼的安全性破譯方法： Shamir方法 L3格基歸約方法：由AKLenstra,HWLenstra&LLovasz提出

Lagarias-Odlyzko-Brickell的方法Diffie-Hellman密鑰交換功能：在沒有秘密信道的情況下，讓兩個(gè)用戶共享一個(gè)秘密密鑰理論基礎(chǔ)：離散對(duì)數(shù)問題方法：利用用戶的公鑰和私鑰Diffie-Hellman密鑰交換計(jì)算Diffie-Hellman問題（CDH問題）：已知ga和gb，計(jì)算gab如果CDH問題是容易的，則gab可以由p,g,ga,gb計(jì)算得到。背景數(shù)學(xué)基礎(chǔ)加密解密過程安全性及應(yīng)用第二節(jié)RSA密碼復(fù)習(xí)：歐拉定理

如果a,n互素，則有a

Ф(n)≡1modn設(shè)n=pq,p,q均為素?cái)?shù)，且a,n互素，則Ф(n)=(p-1)(q-1)aФ(n)=a

(p-1)(q-1)≡1modn

第二節(jié)RSA密碼

選擇p,qp,q均為素?cái)?shù)且p≠q

計(jì)算n=pq

計(jì)算Ф(n)=(p-1)(q-1)

選擇e1<e<Ф(n)且gcd(e,Ф(n))=1

計(jì)算dd≡e-1modФ(n)

公開n,e

保密d系統(tǒng)構(gòu)造對(duì)明文m=374加密計(jì)算c≡memodn≡37431mod2173=446解密：計(jì)算cd≡446671mod2173=374RSA：Example選擇p=53,q=41,n=pq=2173,Ф(n)=2080選擇e=31,計(jì)算出d=671將n,e公開，d保密加密：模冪運(yùn)算解密：模冪運(yùn)算正確性：歐拉定理安全性：分解大整數(shù)參數(shù)選擇RSA小結(jié)數(shù)字簽名4學(xué)時(shí)第六章

數(shù)字簽名的概念數(shù)字簽名與手寫簽名的區(qū)別數(shù)字簽名的特征

數(shù)字簽名的原理數(shù)字簽名分類

直接數(shù)字簽名仲裁數(shù)字簽名主要內(nèi)容數(shù)字簽名(DigitalSignature)：以電子化形式，使用密碼方法，在數(shù)字消息中嵌入一個(gè)秘密信息，以驗(yàn)證這個(gè)秘密信息是否正確來達(dá)到識(shí)別的目的，其實(shí)質(zhì)是一種密碼變換。第一節(jié)數(shù)字簽名概述手寫簽名的特點(diǎn)：

(1)簽名不可偽造。簽名中包含了簽名者個(gè)人所特有的一些信息，如寫字習(xí)慣、運(yùn)筆方法等，是別人很難仿造的。

(2)簽名不可重用。一個(gè)簽名只能對(duì)一份文件起作用，不可能移到別的不同的文件上。第一節(jié)數(shù)字簽名概述手寫簽名

(3)文件內(nèi)容不可改變。在文件簽名后，文件的內(nèi)容就不能再變。

(4)簽名不可抵賴。簽名和文件都是物理的實(shí)體，簽名者不能在簽名后還聲稱他沒簽過名。手寫簽名應(yīng)用：網(wǎng)絡(luò)中的身份認(rèn)證和消息認(rèn)證。特征：

(1)不可否認(rèn)性：簽名者事后不能否認(rèn)。

(2)可驗(yàn)證性：接收者能驗(yàn)證簽名，而任何其他人都不能偽造簽名。

(3)可仲裁性：當(dāng)雙方發(fā)生爭(zhēng)執(zhí)時(shí)，可以由一個(gè)公正的第三方出面解決爭(zhēng)端。第一節(jié)數(shù)字簽名概述數(shù)字簽名的特征構(gòu)成：簽名者、驗(yàn)證者、密鑰、算法、待簽名消息簽名系統(tǒng)的參數(shù)包括：

——消息空間M，所有可能的消息的集合

——簽名空間S，所有可能的簽名的集合

——密鑰空間K，所有可能的密鑰的集合

——簽名者的密鑰，包括公鑰pK和私鑰sK兩部分

——算法：保密的簽名算法S(.)和公開的驗(yàn)證算法V(..)第一節(jié)數(shù)字簽名概述數(shù)字簽名的原理(1)A→B：EKRa(M)提供鑒別與簽名只有A具有KRa傳輸中沒有被篡改任何第三方可以用KUa驗(yàn)證簽名(1’)A→B：EKUb[EKRa(M)]

提供保密、鑒別與簽名第一節(jié)數(shù)字簽名概述直接數(shù)字簽名（DSS）(2)A→B：M||EKRa[H(M)]

提供鑒別及數(shù)字簽名H(M)受到密碼算法的保護(hù)只有A能夠生成EKRa[H(M)](2’)A→B：EKUb[M||EKRa(H(M))]

提供保密性、鑒別和簽名第一節(jié)數(shù)字簽名概述直接數(shù)字簽名（DSS）驗(yàn)證模式依賴于發(fā)送方的保密密鑰發(fā)送方要抵賴發(fā)送某一消息時(shí)，可能會(huì)聲稱其私有密鑰丟失或被竊，從而他人偽造了他的簽名對(duì)策：要求被簽名的信息包含一個(gè)時(shí)間戳（日期與時(shí)間），并要求將已暴露的密鑰報(bào)告給一個(gè)授權(quán)中心X的某些私有密鑰確實(shí)在時(shí)間T被竊取，敵方可以偽造X的簽名及早于或等于時(shí)間T的時(shí)間戳第一節(jié)數(shù)字簽名概述直接數(shù)字簽名的缺點(diǎn)引入仲裁者所有從發(fā)送方X到接收方Y(jié)的簽名消息首先送到仲裁者A，A將消息及其簽名進(jìn)行一系列測(cè)試，以檢查其來源和內(nèi)容，然后將消息加上日期并與已被仲裁者驗(yàn)證通過的指示一起發(fā)給Y。第一節(jié)數(shù)字簽名概述仲裁數(shù)字簽名（ADS）當(dāng)X否認(rèn)時(shí)，通過以下方法解決糾紛：

Y：向A發(fā)送EKay[IDx||M||EKax[IDx||H(M)]]

A：用Kay恢復(fù)IDx，M，和簽名（EKax[IDx||H(M)]），然后用Kax解密簽名并驗(yàn)證散列碼第一節(jié)數(shù)字簽名概述仲裁數(shù)字簽名（ADS）Y不能直接驗(yàn)證X的簽名，Y認(rèn)為消息正確，只因?yàn)樗鼇碜訟。因此，雙方都需要高度相信A:X必須信任A沒有暴露Kax，并且沒有生成錯(cuò)誤的簽名

Y必須信任A僅當(dāng)散列值正確并且簽名確實(shí)是X產(chǎn)生的情況下才發(fā)送消息（2）雙方都必須信任A能公正地處理爭(zhēng)議第一節(jié)數(shù)字簽名概述仲裁數(shù)字簽名（ADS）(b)單密鑰加密方式，消息對(duì)仲裁者不可見

(1)XA：IDx||EKxy[M]||EKax[IDx||H(EKxy[M])] (2)AY：EKay[IDx||EKxy[M]||EKax[IDx||H(EKxy[M])]||T]X與Y之間共享密鑰Kxy

第一節(jié)數(shù)字簽名概述仲裁數(shù)字簽名（ADS）(c)公鑰加密方式，消息對(duì)仲裁者不可見

(1)XA：IDx||EKRx[IDx||EKUy(EKRx[M])] (2)AY：EKRa[IDx||EKUy[EKRx[M]]||T]X：對(duì)消息M雙重加密：首先用X的私有密鑰KRx，然后用Y的公開密鑰KUy。雙重加密的消息對(duì)A以及對(duì)除Y以外的其它人都是保密的。A：檢查X的公開/私有密鑰對(duì)是否仍然有效，是則確認(rèn)消息。第一節(jié)數(shù)字簽名概述仲裁數(shù)字簽名（ADS）(c)與(a)(b)相比具有以下好處：

1、在通信之前各方之間無須共享任何信息，從而避免了聯(lián)手作弊；

2、即使KRx暴露，只要KRa未暴露，就不會(huì)有時(shí)間戳不正確的消息被發(fā)送；

3、從X發(fā)送給Y的消息的內(nèi)容對(duì)A和任何其他人是保密的。第一節(jié)數(shù)字簽名概述仲裁數(shù)字簽名（ADS）掌握數(shù)字簽名的基本概念理解數(shù)字簽名的特征理解數(shù)字簽名的原理及分類方法小結(jié)數(shù)字簽名算法第二節(jié)RSA簽名算法ElGamal簽名算法DSA概述DSA簽名過程主要內(nèi)容Alice的公開密鑰：nA,eA；秘密密鑰：dA；消息m簽名算法：驗(yàn)證算法：Alice要對(duì)秘密信息簽名時(shí)，先用私鑰計(jì)算簽名，再用公鑰加密。第二節(jié)常見簽名算法RSA簽名簽名：對(duì)信息m簽名時(shí)，首先選取隨機(jī)數(shù)k(1≤k≤p-2)，k與p-1互素，計(jì)算

r=gk

modps=k-1(m-xr)modp-1或m=xr+ksmodp-1驗(yàn)證：驗(yàn)證者A驗(yàn)證等式是否成立：gm=yrrs

modp

若正確，則(r，s)為m的合法簽名，否則為非法簽名。第二節(jié)常見簽名算法ElGamal簽名1991年美國(guó)國(guó)家標(biāo)準(zhǔn)局NIST將數(shù)字簽名算法DSA作為其數(shù)字簽名標(biāo)準(zhǔn)(DigitalSignatureStandard，DSS)，DSA是ElGamal數(shù)字簽名算法的變形。使用了安全散列函數(shù)SHA-1，以長(zhǎng)度小于264bits的明文作為輸入，產(chǎn)生160bit的消息摘要作為DSA的輸入。驗(yàn)證簽名時(shí)必須使用相同的散列函數(shù)。數(shù)字簽名算法DSA簽名：對(duì)明文m

(1,q)，簽名者選取隨機(jī)整數(shù)k，1≤k≤p-2且k與p-1互素，計(jì)算r=(gk

modp)modqs=k-1(H(m)+xr)modq其中kk-1modq≡1(r，s)即為消息m的數(shù)字簽名。數(shù)字簽名算法DSA驗(yàn)證：計(jì)算w=s-1modq

u1=H(m)wmodqu2=rwmodqv=[(gu1yu2)modp]modq檢驗(yàn)v=r是否成立。數(shù)字簽名算法DSA簽名者對(duì)消息m=1234簽名：選擇隨機(jī)數(shù)k=50，得k-1(mod101)=99計(jì)算簽名：r=(17050(mod7879)(mod101)=2518(mod101)=94s=(1234+75*94)99(mod101)=97簽名為(1234,94,97)Example數(shù)字簽名算法DSA掌握RSA簽名算法掌握ElGamal簽名算法理解隨機(jī)數(shù)在簽名中的作用理解DSA簽名過程小結(jié)橢圓曲線簽名第三節(jié)ECDSA算法ECDSA中的閾下信道ECDSA算法的變形主要內(nèi)容ECDSA(EllipticCurveDigitalSignatureAlgorithm)——DSA算法在橢圓曲線上的模擬。1992年，作為NIST所征集的DSS候選算法之一，ScottVanstone提出了ECDSA算法。后來被各標(biāo)準(zhǔn)化組織廣泛接受，1998年被ISO作為ISO14888-3標(biāo)準(zhǔn)，1999年被ANSI作為ANSIX9.62標(biāo)準(zhǔn)，2000年被IEEE作為IEEE1363-2000標(biāo)準(zhǔn)，同年被FIPS作為FIPS186-2標(biāo)準(zhǔn)。ECDSA簡(jiǎn)介1.方案建立設(shè)U為簽名方，V為驗(yàn)證方：(1）U建立橢圓曲線域參數(shù)T=(p，a，b，G，n，h)；(2）U建立自己的密鑰對(duì)（dU,QU），QU

=dUG；(3）U選擇一個(gè)Hash函數(shù)；(4）U

通過可靠的方式將所選擇的Hash函數(shù)和建立的橢圓曲線域參數(shù)T傳遞給V。算法描述2.簽名算法(1）選擇臨時(shí)密鑰對(duì)(k，R)，其中R=kG=(xR，yR)與域參數(shù)T相關(guān)(2）令r=xR

(modn)，如果r=0,返回1(3）計(jì)算待簽消息的hash值H=Hash(M)，將H轉(zhuǎn)換成整數(shù)e(4）計(jì)算s

k-1(e+rdU)(modn)，如果s=0,返回1(5）輸出S=(r，s)為數(shù)字簽名算法描述3.驗(yàn)證算法(1）如果r,s

[1,n-1],驗(yàn)證失敗(2）計(jì)算待簽消息的hash值H=Hash(M)，將H轉(zhuǎn)換成整數(shù)e(3）計(jì)算u1

es-1(modn)，u2

rs-1(modn)(4）計(jì)算R=(xR，yR)=u1G+u2QU，如果R=O,驗(yàn)證失敗(5）令v=

xR

(modn)，如果v=r，驗(yàn)證成功，否則驗(yàn)證失敗算法描述對(duì)ECDLP的攻擊ECDSA算法的安全性基于ECDLP問題的困難性。如果一種攻擊能夠從簽名者U的公鑰恢復(fù)出私鑰，攻擊者就可以偽造出U對(duì)任何消息的數(shù)字簽名。目前，當(dāng)基點(diǎn)的階為大素?cái)?shù)時(shí)，素?cái)?shù)域上的ECDLP是不可解的。對(duì)密鑰生成的攻擊在密鑰生成過程中用到了秘密隨機(jī)或偽隨機(jī)數(shù)，不安全的隨機(jī)或偽隨機(jī)數(shù)生成器將直接導(dǎo)致密碼被攻破。攻擊思路對(duì)哈希函數(shù)的攻擊簽名和驗(yàn)證階段使用的哈希函數(shù)必須具備單向和抗沖突的特性。如果哈希函數(shù)不能抵抗沖突，攻擊者可能會(huì)發(fā)現(xiàn)消息(M1;M2)的碰撞，在U對(duì)消息M1簽名后可以偽造出對(duì)消息M2的簽名?；跓o效域參數(shù)和無效公鑰的攻擊ECDSA的安全性依賴于U使用的有效域參數(shù)，無效的域參數(shù)對(duì)Pohlig-Hellman攻擊不免疫。U應(yīng)該確保所采用的域參數(shù)是有效的。V在驗(yàn)證之前也應(yīng)該檢驗(yàn)這些參數(shù)的有效性。攻擊思路閾下信道——在密碼協(xié)議中，存在一些特殊的編碼方法或數(shù)學(xué)結(jié)構(gòu)，可以用于傳輸秘密消息。閾下信道主要存在于數(shù)字簽名和認(rèn)證協(xié)議中。簽名者（發(fā)送方）可以將秘密信息隱藏在數(shù)字簽名之中，驗(yàn)證者（接收方）通過事先約定的某種協(xié)議或參數(shù)恢復(fù)出閾下信息，這種秘密通信方式很難被第三方檢測(cè)到。與一般的加密傳輸相比，閾下信道具有更高的安全性。ECDSA中的閾下信道如果簽名中的附加數(shù)據(jù)量為αbit，其中βbit用來保證簽名的安全性，則理論上最大可以傳遞α-β

bit的閾下信息。利用了全部或幾乎全部α-βbit的附加數(shù)據(jù)的閾下信道為寬帶閾下信道，只利用了一小部分的為窄帶閾下信道?；謴?fù)閾下信息時(shí)需要簽名者密鑰的方式定義為方式I，不需要的定義為方式Ⅱ。在方式I中，簽名者的密鑰同時(shí)也是該閾下信道的恢復(fù)密鑰。ECDSA中的閾下信道在ECDSA中，由于s

k-1

(e+rdU)(modn)，可得k

s-1

(e+rdU)(modn)，（r,s）和e為簽名對(duì)于驗(yàn)證者V來說，只要事先知道簽名者U的私鑰dU就可以恢復(fù)出k來。于是以k作為閾下信息，可以實(shí)現(xiàn)方式I的閾下信道。ECDSA中的閾下信道在數(shù)字簽名協(xié)議中補(bǔ)充以下步驟，就能設(shè)計(jì)出閾下通信協(xié)議：信道建立U為發(fā)送方，V為接收方:(1）U執(zhí)行方案建立協(xié)議。建立參數(shù)T,(dU,QU),Hash。(2）U將私鑰dU,秘密傳輸給V。ECDSA中的閾下信道閾下信息隱藏(1）U對(duì)秘密消息編碼，得到一整數(shù)k。(2）U建立臨時(shí)密鑰對(duì)(k，R)，其中R=kG=(xR，yR)和域參數(shù)T相關(guān)。(3）U執(zhí)行以上簽名算法。ECDSA中的閾下信道閾下信息恢復(fù)(1）V執(zhí)行驗(yàn)證協(xié)議。(2）V計(jì)算

k

s-1(e+rdU)(modn)，恢復(fù)閾下信息。(3)V對(duì)k解碼恢復(fù)原始的秘密信息。ECDSA中的閾下信道ECDSA算法中的簽名附加數(shù)據(jù)量為（logn+logp）bit，而閾下信息k為lognbit，該信道是一種寬帶信道。按照目前對(duì)橢圓曲線參數(shù)的安全要求，通過這個(gè)信道可傳輸192bit以上的閾下信息。ECDSA中的閾下信道簽名算法(1）選擇臨時(shí)密鑰對(duì)(k，R)，其中R=kG=(xR，yR)和域參數(shù)T相關(guān)。(2）令r=xR(modn)，如果r=0,返回1。 (3）計(jì)算待簽名消息的hash值H=Hash(M)，將H轉(zhuǎn)換成整數(shù)e。(4）計(jì)算s

dU-1(rk-e)(modn)，如果s=0,返回1。(5）輸出S=(r，s)為數(shù)字簽名。ECDSA算法的變形一驗(yàn)證算法(1）如果r,s

[1,n-1],驗(yàn)證失敗。(2）計(jì)算待簽消息的hash值H=Hash(M)，將H轉(zhuǎn)換成整數(shù)e(3）計(jì)算u1

er-1(modn),u2

sr-1(modn)(4）計(jì)算R=(xR，yR)=u1G+u2QU，如果R=O,驗(yàn)證失敗。(5）令v=

xR(modn)，如果v=r,驗(yàn)證成功，否則驗(yàn)證失敗。這個(gè)改進(jìn)方案中，可以預(yù)計(jì)算dU-1，將計(jì)算結(jié)果存儲(chǔ)下來作為簽名參數(shù)，在每次簽名時(shí)模乘dU-1即可，于是模逆轉(zhuǎn)化為模乘，運(yùn)算量將減小。ECDSA算法的變形一簽名算法(1）選擇臨時(shí)密鑰對(duì)(k，R)，其中R=kG=(xR，yR)和域參數(shù)T相關(guān)；(2）令r=xR(modn)，如果r=0,返回1；(3）計(jì)算待簽名消息的hash值H=Hash(M)，將H轉(zhuǎn)換成整數(shù)e；(4）計(jì)算s

k(e+rdU)-1(modn)，如果s=0,返回1；(5）S=(r，s)作為數(shù)字簽名。ECDSA算法的變形二驗(yàn)證算法(1)如果r,s

[1,n-1],驗(yàn)證失敗；(2)計(jì)算待簽名消息的hash值H=Hash(M)，將H轉(zhuǎn)換成整數(shù)e；(3)計(jì)算u1

es(modn),u2

rs(modn)；(4)計(jì)算R=(xR，yR)=u1G+u2QU，如果R=O,驗(yàn)證失敗。(5)令v=

xR(modn)，如果v=r,驗(yàn)證成功，否則驗(yàn)證失敗。ECDSA算法的變形二掌握ECDSA簽名過程理解閾下信道的含義理解如何在ECDSA中利用閾下信道進(jìn)行信息隱藏了解ECDSA的兩種變形小結(jié)第四節(jié)盲簽名三、盲簽名的原理及典型算法(重點(diǎn))二、盲簽名的產(chǎn)生背景----電子投票主要內(nèi)容：一、盲簽名的基本概念盲簽名

盲簽名:是一類特殊的數(shù)字簽名,消息持有者希望簽名者對(duì)他的消息作數(shù)字簽名，但又不想讓簽名看到消息的真實(shí)內(nèi)容。一、盲簽名的基本概念1、遠(yuǎn)程匿名投票20世紀(jì)80年代，密碼學(xué)家DavidChaum就建立過一個(gè)遠(yuǎn)程匿名投票模型設(shè)立一個(gè)選舉委員會(huì)，其職責(zé)為：

規(guī)定選票格式。

確認(rèn)選民身份。

統(tǒng)計(jì)選票。二、電子投票問題（盲簽名產(chǎn)生的背景）條件：所有投票人散居各城市，無法集中，利用普通郵政系統(tǒng)投票。選民選委會(huì)資格審查票數(shù)統(tǒng)計(jì)

①②⑤③④

1、遠(yuǎn)程匿名投票

二、電子投票問題（盲簽名產(chǎn)生的背景）用電子手段解決以下三個(gè)關(guān)鍵問題：（1）如何使選委會(huì)看不到選票內(nèi)容？（2）選舉委員會(huì)如何蓋章？（3）選民如何確認(rèn)收回的選票沒有被做上記號(hào)？2、電子投票二、電子投票問題（盲簽名產(chǎn)生的背景）1、盲簽名的特性（1）簽名人看不到所簽的“文件內(nèi)容”。（2）簽名人無法建立文件與他的簽名之間的聯(lián)系。三、盲簽名的原理及算法消息持有者簽名者M(jìn)S=S(M)M=B(M)S=B-1(S

)

2、盲簽名的原理盲化盲簽名解盲

消息持有者希望簽名者對(duì)他的消息作數(shù)字簽名，但又不想讓簽名者看到消息的真實(shí)內(nèi)容。三、盲簽名的原理及算法1.不可偽造性除了簽名者本人外，任何人都不能以他的名義生成有效的盲簽名。2.不可抵賴性簽名者簽署了某個(gè)消息后將無法否認(rèn)自己對(duì)消息的簽名。3.盲性簽名者不可能得到消息的具體內(nèi)容。4.不可跟蹤性一旦消息的簽名公開后，簽名者不能確定自己何時(shí)簽署的這條消息。一個(gè)好的盲簽名算法應(yīng)該具有以下的性質(zhì)：

三、盲簽名的原理及算法3、基于RSA密碼的盲簽名算法（1）參數(shù)選取（同RSA公鑰密碼）：選定p,q為大素?cái)?shù)，計(jì)算n=pq。選取秘密密鑰d，要求gcd(d,φ(n))=1。計(jì)算e,滿足de=1modφ(n)。

e,n

公開，其它參數(shù)均保密。三、盲簽名的原理及算法RSA數(shù)字簽名過程AliceBobn,epublicdprivates≡md

modngcd(m,n)=1m≡se

modnsSetp1:選定M，隨機(jī)數(shù)R。計(jì)算M

=ReM

modn簽名者消息持有者Setp2:計(jì)算S

=M

d

modnStep3:S=R-1S

modn

=M

dmodnStep4:驗(yàn)證

Semodn？=M（2）簽名算法三、盲簽名的原理及算法（3）分析MM

(M,S)(M

，S

)

簽名人對(duì)簽的“文件內(nèi)容”是看不見的。即使公布文件內(nèi)容，簽名人也不能把文件與他所作的簽名聯(lián)系起來。

三、盲簽名的原理及算法（4）與普通RSA簽名比較MS=M

dmodnRSA簽名RSA盲簽名M?=S

emodnS

=M

dmodnM?=S

emodnMM

S=R-1S

modn三、盲簽名的原理及算法1.密鑰的長(zhǎng)度；2.盲簽名的長(zhǎng)度；3.盲簽名的算法和驗(yàn)證算法。盲簽名的可操作性和實(shí)現(xiàn)速度取決于：三、盲簽名的原理及算法4、盲簽名技術(shù)的應(yīng)用現(xiàn)狀（1）匿名電子投票系統(tǒng)（2）電子商務(wù)系統(tǒng)中的匿名支付

Microsoft公司的eWallet系統(tǒng)。三、盲簽名的原理及算法主要內(nèi)容：（1）盲簽名的基本概念（2）盲簽名的產(chǎn)生背景。（3）基于RSA密碼的盲簽名算法。

四、小結(jié)及相關(guān)問題第五節(jié)代理簽名代理簽名的含義及特點(diǎn)代理簽名的分類M-U-O代理簽名方案主要內(nèi)容代理簽名：簽名者可以授權(quán)他人代理自己，由被指定的代理簽名者代表原始簽名者生成有效的簽名。1996年，Mambo、Usuda和Okamoto首先提出了代理簽名的概念。代理簽名系統(tǒng)中的參與者：原始簽名者獲得授權(quán)執(zhí)行簽名的一個(gè)或多個(gè)代理簽名者驗(yàn)證者第五節(jié)代理簽名代理簽名應(yīng)滿足三個(gè)基本條件驗(yàn)證者能夠像驗(yàn)證原始簽名者的簽名那樣來驗(yàn)證代理簽名；能夠容易區(qū)分代理簽名和原始簽名；原始簽名者對(duì)代理簽名者所作的代理簽名不可否認(rèn)。代理簽名的特點(diǎn)第五節(jié)代理簽名Mambo、Usuda和Okamoto把代理簽名分為三類：完全代理簽名、部分代理簽名和具有證書的代理簽名。完全代理簽名(fulldelegation)：原始簽名者通過可靠途徑直接把自己的簽名密鑰分發(fā)給代理簽名者，代理簽名者產(chǎn)生的簽名與原始簽名者所產(chǎn)生的簽名完全相同。代理簽名的分類第五節(jié)代理簽名部分代理簽名(partialdelegation)，原始簽名者用自己的簽名密鑰生成代理簽名密鑰s，然后將代理簽名密鑰通過可靠途徑分發(fā)給代理簽名者。要求：代理簽名者不能由自己所獲得的代理簽名密鑰推算出原始簽名者的簽名密鑰。又可分為兩種：代理非保護(hù)代理簽名和代理保護(hù)代理簽名。代理簽名的分類第五節(jié)代理簽名具有證書的代理簽名(delegationbywarrant)，分兩種類型：授權(quán)代理簽名和持票代理簽名。授權(quán)代理簽名(delegateproxy)：原始簽名者用他的簽名密鑰使用普通的簽名方案簽一個(gè)文件（證書），然后把產(chǎn)生的證書發(fā)給代理簽名者。持票代理簽名(bearerproxy)：證書由消息部分和原始簽名者對(duì)新產(chǎn)生的公鑰的簽名組成。原始簽名者把新產(chǎn)生的公鑰所對(duì)應(yīng)的私鑰以安全的方式發(fā)給代理簽名者。代理簽名的分類第五節(jié)代理簽名代理簽名又可分為強(qiáng)代理簽名和弱代理簽名。強(qiáng)代理簽名——代理簽名不僅能夠代表原始簽名者的簽名，也能代表代理簽名者的簽名；弱代理簽名——代理簽名只代表原始簽名者的簽名。代理簽名的分類第五節(jié)代理簽名2學(xué)時(shí)消息認(rèn)證與Hash函數(shù)——公鑰密碼的應(yīng)用第七章消息認(rèn)證概述認(rèn)證函數(shù)消息認(rèn)證碼Hash函數(shù)和MAC的安全性Hash算法主要內(nèi)容機(jī)密性（Confidentiality）：確保信息不暴露給未經(jīng)授權(quán)的人或應(yīng)用進(jìn)程。完整性（Integrity）：只有得到允許的人或應(yīng)用進(jìn)程才能修改數(shù)據(jù)，并且能夠判別出數(shù)據(jù)是否已被更改?？捎眯裕ˋvailability）：只有得到授權(quán)的用戶在需要時(shí)才可以訪問數(shù)據(jù)，即使在網(wǎng)絡(luò)被攻擊時(shí)也不能阻礙授權(quán)用戶對(duì)網(wǎng)絡(luò)的使用。三種基本安全需求認(rèn)證系統(tǒng)由認(rèn)證編碼器和認(rèn)證譯碼器組成條件：指定的接收者能檢驗(yàn)和證實(shí)消息的合法性、真實(shí)性和完整性發(fā)送者和接收者不能抵賴除了合法的發(fā)送者，其它人不能偽造消息認(rèn)證系統(tǒng)第一節(jié)消息認(rèn)證認(rèn)證函數(shù)的特點(diǎn)：必須是單向函數(shù)對(duì)于一個(gè)特定消息，很難找到另外一個(gè)消息與其具有相同的認(rèn)證碼很難找到一對(duì)具有相同認(rèn)證碼的消息認(rèn)證函數(shù)第一節(jié)消息認(rèn)證認(rèn)證函數(shù)可分為三類：消息加密：將整個(gè)消息的密文作為認(rèn)證符；消息認(rèn)證碼（MAC）：是消息和密鑰的公開函數(shù)，產(chǎn)生定長(zhǎng)的認(rèn)證符；Hash函數(shù)：將任意長(zhǎng)的消息映射為定長(zhǎng)的hash值的公開函數(shù)，該hash值則作為認(rèn)證符。認(rèn)證函數(shù)第一節(jié)消息認(rèn)證消息認(rèn)證碼（MessageAuthenticationCode）：利用密鑰生成固定長(zhǎng)度的短數(shù)據(jù)塊（MAC），將其附加在消息之后，也稱為密碼校驗(yàn)和（cryptographicchecksum）。MAC函數(shù)與加密的區(qū)別：不要求可逆性多對(duì)一不能用于數(shù)字簽名第一節(jié)消息認(rèn)證用消息認(rèn)證碼實(shí)現(xiàn)認(rèn)證通過MAC，可以認(rèn)證以下內(nèi)容：

a.接收者可以確信所收到的消息M未被篡改；

b.接收者可以確信消息來自真實(shí)的發(fā)送者；

c.如果消息中包含順序碼(如X.25,TCP)，接收者可以確認(rèn)消息的正常順序。消息認(rèn)證碼第一節(jié)消息認(rèn)證已知M和Ck(M)時(shí)，構(gòu)造滿足Ck(M’)=Ck(M)的消息M’在計(jì)算上不可行；Ck(M)應(yīng)是均勻分布的，即對(duì)任何隨機(jī)選擇的消息M和M’，Ck(M’)=Ck(M)的概率是2-n，其中n是MAC的位數(shù)；設(shè)M’是M的某個(gè)已知的變換，即M’=f(M)，例如可令f

表示對(duì)M的一位或多位取反，那么

Pr[Ck(M’)=Ck(M)]=2-n

對(duì)MAC的要求第一節(jié)消息認(rèn)證十進(jìn)制移位加MAC算法

1980年，Sievi提出，稱為十進(jìn)制移位加算法(DecimalShiftandAddAlgorithm)簡(jiǎn)記為DSA，適用于金融支付中的數(shù)值消息交換業(yè)務(wù)，消息按十位十進(jìn)制數(shù)字分段處理，不足十位時(shí)在右邊以0補(bǔ)齊基于DES的MAC算法

兩種：CBC模式和CFB模式。CBC模式是使用最廣泛的一種，被美國(guó)作為數(shù)據(jù)認(rèn)證算法(DataAuthenticationAlgorithm)，已被FIPS(FIPSPUB113)和ANSI(X9.17)作為標(biāo)準(zhǔn)。MAC算法第一節(jié)消息認(rèn)證消息按64bit分組M1,M2,…,MN，不足時(shí)以0補(bǔ)齊，DES加密，設(shè)密鑰為K，初始向量為0，計(jì)算如下：

O1=EK(M1)

O2=EK(M2XORO1)

O3=EK(M3XORO2) …

ON=EK(MNXORON-1)取加密結(jié)果最左邊的r位作為認(rèn)證碼。r的大小由通信雙方約定。第二節(jié)消息認(rèn)證碼MAC算法——CBC模式散列函數(shù)（HashFunction）：也稱哈希函數(shù)，對(duì)任意長(zhǎng)度的明文進(jìn)行變換，得到相對(duì)應(yīng)的函數(shù)值，稱為散列值，或稱散列值、消息摘要（MessageDigest）、指紋（Fingerprint），變換的過程稱為散列變換。散列值的長(zhǎng)度一般是固定的。用途：（1）消息鑒別碼；（2）數(shù)字簽名之前的預(yù)處理第二節(jié)散列函數(shù)第二節(jié)散列函數(shù)要求：對(duì)任意長(zhǎng)度輸入進(jìn)行變換，得到固定長(zhǎng)度輸出求逆不可行對(duì)給定x，很難找到x’≠x，使得h(x’)=h(x)很難找到一對(duì)不同的x,x’，使得h(x’)=h(x)第二節(jié)散列函數(shù)對(duì)hash函數(shù)的要求滿足條件（1）（2）的稱之為單向散列函數(shù)(One-WayHashFunction)滿足條件（1）~（3）的稱之為弱散列函數(shù)（WeakHashFunction）或弱無碰撞的散列函數(shù)滿足條件（1）~（4）的稱之為強(qiáng)散列函數(shù)（StrongHashFunction）或強(qiáng)無碰撞的散列函數(shù)。對(duì)hash函數(shù)的要求第二節(jié)散列函數(shù)1978年，Rabin的方法利用DES的密碼分組鏈接模式設(shè)計(jì)將明文M按M=m1m2…mn進(jìn)行分組，mi為64bit，按DES的CBC模式依次對(duì)每個(gè)分組進(jìn)行加密，令h0=初始向量，hi=Emi[hi-1]，加密過程不使用任何密鑰，G=hn為最終得到的散列值。第二節(jié)Hash函數(shù)Hash函數(shù)舉例散列函數(shù)用于簽名時(shí)，假設(shè)簽名消息為(x,y)，y=sigk(h(x))，則攻擊者可用如下方式偽造攻擊者計(jì)算Z=h(x)，找到x’≠x，但h(x’)=h(x)，則（x’,y）構(gòu)成有效的簽名；攻擊者找到任意兩個(gè)不同消息x’，x，滿足h(x’)=h(x)，令簽名者對(duì)h(x)簽名，則（x’,h(x)）也是有效簽名；攻擊者偽造一個(gè)簽名Z，若能計(jì)算h-1(Z)=x，則(x,h(x))為有效簽名。對(duì)Hash函數(shù)的攻擊第二節(jié)散列函數(shù)對(duì)hash函數(shù)的攻擊可以看作是尋找碰撞的過程，攻擊者的主要目標(biāo)不是恢復(fù)原始的明文，而是用非法消息替代合法消息進(jìn)行偽造和欺騙，。攻擊方法：生日攻擊、中間相遇攻擊、窮舉攻擊第二節(jié)Hash函數(shù)對(duì)Hash函數(shù)的攻擊攻擊者通過一對(duì)已知的明文和散列值，就可以任意偽造其它明文的散列值，步驟如下：第一步，對(duì)已知明文M產(chǎn)生散列值G；第二步，將非法明文Q按Q=Q1Q2…Qn-2進(jìn)行分組，每個(gè)分組長(zhǎng)度為64bit；第三步，計(jì)算hi=EQi[hi-1]，1≤i≤n-2；第二節(jié)Hash函數(shù)中間相遇攻擊第四步，產(chǎn)生232個(gè)不同的x，對(duì)每個(gè)x計(jì)算Ex[hn-2]，再任意產(chǎn)生232個(gè)不同的y，對(duì)每個(gè)y計(jì)算Dy[G]，D是對(duì)應(yīng)于E的解密函數(shù)；第五步，找到一對(duì)對(duì)應(yīng)的x和y，使得Ex[hn-2]=Dy[G]；第六步，生成新的明文Q′=Q1Q2…Qn-2xy。第二節(jié)Hash函數(shù)中間相遇攻擊Merkle在1989年提出了散列函數(shù)的通用結(jié)構(gòu)：

a.將原始消息M分成固定長(zhǎng)度的分組(Block)Mi；

b.對(duì)最后一個(gè)分組MN填充，并附上原始消息M的長(zhǎng)度，

使其長(zhǎng)度等于固定長(zhǎng)度；

c.設(shè)定鏈接變量(chainingvalue)的初始值CV0；

d.定義壓縮函數(shù)f，CVi=f(CVi-1,Mi-1)；

e.循環(huán)操作N次，最后一個(gè)CVN為散列值。第二節(jié)Hash函數(shù)Hash函數(shù)的通用結(jié)構(gòu)對(duì)hash函數(shù)的密碼分析主要集中在f的內(nèi)部結(jié)構(gòu)進(jìn)行分析，并試圖找到能與f的執(zhí)行產(chǎn)生碰撞的有效方法。第二節(jié)Hash函數(shù)密碼分析2004年8月17日，美國(guó)加州圣巴巴拉，Crypto’2004。來自山東大學(xué)的王小云教授做了破譯MD5、HAVAL-128、MD4和RIPEMD算法的報(bào)告。第二節(jié)Hash函數(shù)密碼分析CollisionsforHashFunctionsMD4,MD5,HAVAL-128andRIPEMDMD5SHA-1RIPEMD-160HMAC第三節(jié)Hash算法Merkle于1989年提出hashfunction模型RonRivest于1990年提出MD41992年,RonRivest完成MD5(RFC1321)現(xiàn)行美國(guó)標(biāo)準(zhǔn)SHA-1以MD5的前身MD4為基礎(chǔ)第三節(jié)Hash算法MD5輸出：128bit分組長(zhǎng)度：512bit算法細(xì)節(jié)：填充→輪函數(shù)MD5總體特征第三節(jié)Hash算法Step1:Padding，

M→M’ |M’|448mod512 |M’|>|M|→

如果|M|448mod512,則|M’