現(xiàn)代密碼學(xué)-2016-3講述

現(xiàn)代密碼學(xué)

ModernCryptography

密碼小故事---跳舞的小人原理:自然語言的字母出現(xiàn)頻率有規(guī)律：

e:11.67t:9.53o:7.81a:7.73…

the:4.65to:3.02of:2.61and:1.85…e:11.67t:9.53….the:4.65…444455555

donttellherthesecrettttteeeeehhrrlldonsc課程信息

教學(xué)目的與要求:密碼學(xué)是信息安全的核心技術(shù),了解常用的密碼算法,經(jīng)典的密碼協(xié)議及其在當(dāng)前網(wǎng)絡(luò)熱點(diǎn)研究中的應(yīng)用,掌握解決計(jì)算機(jī)網(wǎng)絡(luò)安全問題的基本方法和策略.

教輔材料：

--楊波.現(xiàn)代密碼學(xué).清華大學(xué)出版社

--BruceSchneier著,吳世忠等譯.應(yīng)用密碼學(xué)—協(xié)議、算法與C源程序.機(jī)械工業(yè)出版社教師信息段桂華

計(jì)算機(jī)樓413

duangh@主要內(nèi)容1引言2現(xiàn)代密碼算法

2.1密碼機(jī)制分類2.2對(duì)稱密碼算法

2.3序列密碼算法2.4數(shù)字摘要算法

2.5公鑰密碼算法2.6數(shù)字簽名算法3經(jīng)典的密碼協(xié)議

3.1基本的密碼協(xié)議3.2中級(jí)協(xié)議

3.3高級(jí)協(xié)議4加密模式

4.1概述4.2ECB模式

4.3CBC模式4.4CFB模式

4.5OFB模式5密碼管理

5.1密鑰管理概述5.2對(duì)稱密鑰的管理

5.3公鑰的密鑰管理1引言網(wǎng)絡(luò)通信的困境與安全威脅網(wǎng)上黑客無孔不入個(gè)人隱私泄露國(guó)家信息安全網(wǎng)上犯罪形勢(shì)不容樂觀有害信息污染嚴(yán)重網(wǎng)絡(luò)病毒的蔓延和破壞PC機(jī)用戶虛假兼職44.1%退款欺詐13.4%網(wǎng)游交易12.4%手機(jī)用戶詐騙短信53.8%釣魚網(wǎng)站32.3%詐騙電話12.7%木馬病毒1.2%虛假購物55.5%虛假中獎(jiǎng)19.4%金融理財(cái)6.5%冒充熟人28.5%虛假中獎(jiǎng)25.6%冒充銀行19.9%保證信息安全要做什么呢認(rèn)證:消息來源確認(rèn),身份的驗(yàn)證.你是誰?我怎么相信你就是你?

授權(quán):根據(jù)實(shí)體身份決定其訪問權(quán)限.我能干什么?

你能干這個(gè),不能干那個(gè).保密:非授權(quán)人無法識(shí)別信息.我與你說話時(shí),別人能不能偷聽?

完整性:防止消息被篡改.傳送過程過程中別人篡改過沒有?

不可否認(rèn):不能對(duì)所作所為進(jìn)行抵賴.我收到貨后,不想付款,想抵賴,怎么樣?我將錢寄給你后,你不給發(fā)貨,想抵賴,如何?

2現(xiàn)代密碼算法2.1密碼機(jī)制分類2.2對(duì)稱密碼算法2.3序列密碼算法2.4數(shù)字摘要算法2.5公鑰密碼算法2.6數(shù)字簽名算法2.1密碼機(jī)制分類密碼機(jī)制分類按照保密的內(nèi)容分類古典密碼:保密算法和密鑰現(xiàn)代密碼:保密密鑰

按照密鑰的特點(diǎn)分類對(duì)稱密碼機(jī)制,加密密鑰和解密密鑰相同,或可以容易地從一個(gè)推出另一個(gè);特點(diǎn):加密速度快,密鑰管理復(fù)雜,主要用于加密信息.非對(duì)稱密碼機(jī)制,加密密鑰和解密密鑰不同,且很難從一個(gè)推出另一個(gè);特點(diǎn):密鑰管理簡(jiǎn)單,加密速度慢,用于加密會(huì)話密鑰和用于數(shù)字簽名.Kerchoffs原則對(duì)稱密碼類似保險(xiǎn)柜:密鑰為保險(xiǎn)柜密碼加密文件---將文件放入保險(xiǎn)柜,設(shè)置密碼鎖上解密文件---用密碼打開保險(xiǎn)柜,取出文件解密密鑰加密密鑰公鑰密碼類似郵箱:加密文件---將文件發(fā)到郵箱duangh@解密文件---用郵箱密碼打開郵箱,取出文件加密密鑰,公開解密密鑰,保密文件簽名---收到郵箱duangh@發(fā)來的文件經(jīng)典的密碼算法經(jīng)典的古典密碼算法主要有:代替密碼換位密碼古典密碼多字母代替單字母代替單表代替密碼多表代替密碼（流密碼）（分組密碼）代替密碼:將明文字符用另外的字符代替換位密碼:明文的字母保持不變,但順序打亂

經(jīng)典的現(xiàn)代密碼算法主要有很多,常用的有:DES,數(shù)據(jù)加密標(biāo)準(zhǔn),對(duì)稱密碼,用于加密IDEA,國(guó)際數(shù)據(jù)加密標(biāo)準(zhǔn),對(duì)稱密碼AES,高級(jí)加密標(biāo)準(zhǔn),對(duì)稱密碼,用于加密RC4,序列密碼,面向字節(jié)流RSA,最流行的公鑰密碼,用于加密和數(shù)字簽名ECC,公鑰密碼,安全性高,密鑰量小,靈活性好DSA,數(shù)字簽名算法,用于數(shù)字簽名SHA(MD5),散列算法,用于簽名和認(rèn)證2.2對(duì)稱密碼算法2.2.1DES算法2.2.2IDEA算法2.2.3AES算法1973年5月15日NBS開始公開征集標(biāo)準(zhǔn)加密算法DES(DataEncryptionStandard),并公布了它的設(shè)計(jì)要求:算法必須提供高度的安全性算法必須有詳細(xì)的說明,并易于理解算法的安全性取決于密鑰,不依賴于算法算法適用于所有用戶算法適用于不同應(yīng)用場(chǎng)合算法必須高效,經(jīng)濟(jì)算法必須能被證實(shí)有效算法必須是可出口的1.對(duì)稱密碼算法--DES1974年8月27日,NBS開始第二次征集,IBM提交了算法LUCIFER.1975年3月公開發(fā)表,1977年1月由美國(guó)國(guó)家標(biāo)準(zhǔn)局NBS頒布為數(shù)據(jù)加密標(biāo)準(zhǔn)DES，同年7月成為美國(guó)聯(lián)邦信息處理標(biāo)準(zhǔn)FIPS-46.1980年,美國(guó)國(guó)家標(biāo)準(zhǔn)協(xié)會(huì)(ANSI)正式采納DES作為美國(guó)商用加密算法DEA.1983年,國(guó)際化標(biāo)準(zhǔn)組織(ISO)同意將DES作為國(guó)際標(biāo)準(zhǔn),稱之為DEA-1.1998年,美國(guó)政府不再將DES作為聯(lián)邦加密標(biāo)準(zhǔn).但其結(jié)構(gòu)和部件一直作為分組密碼設(shè)計(jì)的標(biāo)準(zhǔn)參照物.后更名為NISTDES是一個(gè)分組加密算法,對(duì)稱密碼,64位分組,密鑰長(zhǎng)度為64位(實(shí)際長(zhǎng)度為56位).DES的整個(gè)算法是公開的,系統(tǒng)的安全性靠密鑰保證.算法包括三個(gè)步驟:初始置換IP,16輪迭代的乘積變換,逆初始變換IP-1.基本思想:混淆與擴(kuò)散IP和IP-1的作用主要是打亂輸入的ASCII碼字劃分關(guān)系,并將明文校驗(yàn)碼變成IP輸出的一個(gè)字節(jié).初始置換IP和逆初始置換IP-1混淆:復(fù)雜化密文與明文,密鑰之間的統(tǒng)計(jì)特性.擴(kuò)散:將每一位明文的影響盡可能多地分散到多個(gè)輸出密文中,以更隱秘明文的統(tǒng)計(jì)特性.f=1234…63644084816…5719f-1=1234…636458504234…157IP置換IP-1置換乘積變換是DES算法的核心部分.將經(jīng)過IP置換后的數(shù)據(jù)分成32位的左右兩組,在迭代過程中彼此左右交換位置.每次迭代時(shí)只對(duì)右邊的32位進(jìn)行一系列的加密變換,然后把左邊的32位與右邊得到的32位逐位進(jìn)行異或操作,作為下一輪迭代時(shí)左邊的段.乘積變換迭代公式為:Li=Ri-1，Ri=Li-1

f(Ri-1,ki)

:按位異或操作運(yùn)算符,即按位作模2相加運(yùn)算.運(yùn)算規(guī)則為:1

0=1,0

1=1,0

0=0,1

1=0f的功能是將32比特的數(shù)據(jù)經(jīng)過選擇擴(kuò)展運(yùn)算E,密鑰加密運(yùn)算,選擇壓縮運(yùn)算S和置換運(yùn)算P轉(zhuǎn)換為32比特的輸出.位擴(kuò)展位置換子密鑰生成64比特初始密鑰k經(jīng)過換位函數(shù)PC-1將位置號(hào)為8,16,24,32,40,48,56和64的8位奇偶位去掉并換位;換位后的數(shù)據(jù)分為2組,經(jīng)過循環(huán)左移位LSi和換位函數(shù)PC-2變換后得到每次迭代加密用的子密鑰ki選擇壓縮運(yùn)算

將密鑰加密運(yùn)算后的48比特?cái)?shù)據(jù)從左至右分成8組,每組為6比特,并行送入8個(gè)S盒后壓縮成32比特輸出.每個(gè)S盒的輸入為6比特,輸出為4比特.安全性分析:窮舉攻擊:在得到明密文對(duì)的情況下,進(jìn)行256≈1017次窮舉.MitsuruMatsui提出的線性密碼分析,采用近似值來逼近分組密碼的操作,約243次.Biham和Shamir提出的差分密碼分析,通過分析特定明文差分對(duì)密文差分影響來獲得可能密鑰,約247次.DES的出現(xiàn)在密碼史上是個(gè)創(chuàng)舉,自公布以來,它一直活躍在國(guó)際保密通信的舞臺(tái)上,成為商用保密通信和計(jì)算機(jī)通信的最常用的加密算法.DES的安全性完全依賴于密鑰,而其56bit的密鑰太短,因而出現(xiàn)了許多DES的改進(jìn)算法,如三重DES,分組反饋連接式DES以及密碼反饋模式DES等.

來學(xué)嘉和JamesMassey1990年公布,1992年更名為IDEA(國(guó)際數(shù)據(jù)加密算法).分組長(zhǎng)度為64位,分4子組進(jìn)行操作,密鑰長(zhǎng)度為128位,使用異或,模216加,模216+1乘三個(gè)混合運(yùn)算,在16位子分組上進(jìn)行.強(qiáng)化了抗差分分析的能力,應(yīng)用于PGP中.軟件實(shí)現(xiàn)IDEA比DES快兩倍.乘加結(jié)構(gòu)(MA)保證了擴(kuò)散的特點(diǎn).特點(diǎn):2.對(duì)稱密碼算法--IDEA模乘異或模加(1)64位數(shù)據(jù)分成4個(gè)16位子分組X1,X2,X3,X4;(2)共進(jìn)行8輪操作,每輪與6個(gè)16位子密鑰異或,相加,相乘;(3)在每輪之間,第2個(gè)和第3個(gè)子分組交換;(4)最終由一個(gè)輸出變換,如下圖所示:原理:128位的k分組:k1,k2,k3,k4,k5,k6,k7,k8;然后進(jìn)行左環(huán)移(25位).子密鑰產(chǎn)生:1k1k2k3k4k5k6k7k8128位的k分組左環(huán)移25位125k9k10k11k12k13k14k15k16該算法克服了DES算法的弱點(diǎn),保留了多輪的合理模式,2002年成為現(xiàn)代加密標(biāo)準(zhǔn)AES.分組,密鑰長(zhǎng)度和輪數(shù)可變.支持長(zhǎng)度為128位,192和256位的分組和密鑰.

比利時(shí)密碼學(xué)家JoanDaemen和VincentRijmen提出的密碼算法方案,稱之為Rijndael算法.特點(diǎn):密鑰長(zhǎng)度4/16/1286/24/1928/32/256分組長(zhǎng)度Nb4/16/1284/16/1284/16/128輪數(shù)Nr101214輪密鑰長(zhǎng)4/16/1284/16/1284/16/128擴(kuò)展密鑰總長(zhǎng)44/17652/208

60/2403.對(duì)稱密碼算法--AES高級(jí)加密標(biāo)準(zhǔn)AES的誕生1997年,美國(guó)國(guó)家標(biāo)準(zhǔn)和技術(shù)研究所NIST向密碼學(xué)界征尋用于新的高級(jí)加密標(biāo)準(zhǔn)AES候選算法,規(guī)定:密碼系統(tǒng)是沒有密級(jí)的;算法的全部描述必須公開;可在世界范圍內(nèi)免費(fèi)使用;支持至少128位的分組;支持的密鑰長(zhǎng)度至少為128,192和256位.1998年8月提交了15個(gè)候選算法,NIST于1999年9月宣布5個(gè)候選算法進(jìn)入第二輪;2000年10月選擇Rijdeal作為AES,其特點(diǎn)為:安全,易實(shí)現(xiàn),算法靈活與簡(jiǎn)便.2001年11月NIST將AES定為聯(lián)邦信息處理標(biāo)準(zhǔn)FIPSPUB197,2002年5月正式生效.(1)從加解密時(shí)間上來看:MARS,RC6,Serpert:相同,與密鑰長(zhǎng)度無關(guān);Rijndael:密鑰為192比特的比128的慢20%,

密鑰為256比特的比128的慢40%;Twofish:需要更多的時(shí)間來設(shè)置更長(zhǎng)的密鑰.(2)軟件性能(PII,匯編,C實(shí)現(xiàn),時(shí)鐘周期)密碼128比特密鑰192比特密鑰256比特密鑰內(nèi)存字節(jié)數(shù)MARS300380300380300380100RC6225240225240225240210Rijndael23040027552033060052Serpent75075075075075075050Twofish25038025038025038060AES最終候選算法性能比較算法分析:

128比特的明文分組被分成4×4的字節(jié)矩陣.字節(jié)替換SubBytes.非線性置換,獨(dú)立作用于狀態(tài)中的每一個(gè)字節(jié).移位行運(yùn)算ShiftRows.字節(jié)的循環(huán)移位運(yùn)算,第1行~第4行字節(jié)分別向左移動(dòng)0~3列.混合列運(yùn)算MixColumns.由一個(gè)線性變換對(duì)狀態(tài)的每一列進(jìn)行變換.02030101010203010101020303010102輪密鑰加密AddRoundKey.與相應(yīng)的密鑰進(jìn)行異或.線性變換AES加密算法:

Rijndael(State,CipherKey){KeyExpansion(CipherKey,W[1,…,Nb*(Nr+1)]);

AddRoundKey(State,W[0,…,Nb-1]);for(i=1;i<Nr;i++){SubBytes(State);

ShiftRows(State);

MixColumns(State);

AddRoundKey(State,W[i*Nb,…,(i+1)*Nb-1]);}//中間Nr-1輪

SubBytes(State);ShiftRows(State);//末輪

AddRoundKey(State,W[Nr*Nb,…,(Nr+1)*Nb-1)];}12810非線性置換S盒SubBytes:19d49輪的操作過程如下:(Nb=128,Nr=10)

02×d4+03×bf+01×5d+01×3004密鑰編排KeyExpansion

所需密鑰比特總數(shù)等于Nb(Nr+1),如分組長(zhǎng)度Nb為128比特,輪數(shù)Nr為10時(shí),需要1408比特.AES解密算法InvSubBytes中逆S盒逆行移位運(yùn)算InvShiftRows

字節(jié)的循環(huán)右移位運(yùn)算,第1行~第4行字節(jié)分別向右移動(dòng)0~3列.逆列運(yùn)算InvMixColumns的線性變換矩陣0E0B0D09090E0B0D0D090E0B0B0D090E這是因?yàn)?0E0B0D09090E0B0D0D090E0B0B0D090E020301010102030101010203030101021000010000100001=算法密鑰長(zhǎng)度迭代次數(shù)數(shù)學(xué)運(yùn)算應(yīng)用DES5616XOR,S-BoxKerberos,SET3DES112,16848XOR,S-BoxPGP,S/MIMEIDEA1288XOR,+,

PGPBlowFish最大44816XOR,S-Box,+RC5最大2048<255+,-,XORCAST-12840-12816+,-,S-BoxPGP4.對(duì)稱密碼算法小結(jié)優(yōu)點(diǎn):效率高,算法簡(jiǎn)單,系統(tǒng)開銷小,適合加密大量數(shù)據(jù)缺點(diǎn):需要以安全方式進(jìn)行密鑰交換,密鑰管理復(fù)雜2.3序列密碼算法RC4算法

RonRivest在1987年為RSA數(shù)據(jù)安全公司開發(fā)的可變密鑰長(zhǎng)度的序列密碼,廣泛應(yīng)用于商業(yè)密碼產(chǎn)品中.是一個(gè)面向字節(jié)的流密碼;RC4的密碼序列獨(dú)立于明文;RSA聲稱RC4對(duì)線性和差分分析具有免疫力;由于RC4是流密碼,必須避免重復(fù)使用密鑰;所需要代碼少,比DES快10倍.RC4算法中密鑰序列與明文相互獨(dú)立,有一個(gè)256字節(jié)的S盒:

S0,S1,…,S255,其值是0到255之間不重復(fù)的值,是一個(gè)可變長(zhǎng)度密鑰的函數(shù).特點(diǎn)RC4算法描述算法i=j=0;i=(i+1)mod256j=(j+Si)mod256

交換Si和Sjt=(Si+Sj)mod256k=St

k即為密鑰流,為產(chǎn)生的隨機(jī)字節(jié).

i=j=0;

i=(i+1)mod256;j=(j+Si)mod256交換Si和Sj

t=(Si+Sj)mod256;k=St

107c64k17C8CS盒初始化S0=0,S1=1,…,S255=255然后用初始密鑰key填充另一個(gè)256字節(jié)的數(shù)組,不斷重復(fù)密鑰直至填充整個(gè)數(shù)組;

j=0

對(duì)于i=0至255

j=(j+Si+ki)mod256

交換Si和Sj最后得到用密鑰初始化的S盒.問題:為什序列密碼的密鑰流不能重復(fù)使用?分析:

原始明文:P1P2P3P4新明文:P1P’P2P3P4

原始密鑰:k1k2k3k4密鑰:k1k2k3k4k5

原始密文:C1C2C3C4新密文:C1C2’C3’C4’C5’由于Mallory知道P’,他可以根據(jù)k2=P’⊕C2’

得到k2,P2=C2⊕k2k3=P2⊕C3’

得到k3,P3=C3⊕k3以此類推,從而確定整個(gè)明文.P’2.4數(shù)字摘要算法2.4.1散列函數(shù)2.4.2MD5算法2.4.3SHA算法解決方法：數(shù)字摘要如何實(shí)現(xiàn)完整性？篡改公共網(wǎng)絡(luò)AliceBobEve1.散列函數(shù)描述是一個(gè)公開的函數(shù),它將任意長(zhǎng)的信息映射成一個(gè)固定長(zhǎng)度的信息.(公開性)為了保證安全,要求是單向的無碰撞的散列函數(shù).即找不到y(tǒng),當(dāng)x≠y時(shí),使得h(x)=h(y).(無碰撞性)預(yù)映射值單個(gè)位的改變,將引起散列值中一半的位發(fā)生改變.(擴(kuò)散性)計(jì)算上的單向性.

易

難

x

h(x)作用:保證消息的完整性;用在數(shù)字簽名中,提高簽名效率.無法篡改z消息篡改公共網(wǎng)絡(luò)AliceBobm,zm,zz=hk(m)y=hk(m)Eve如果y≠zm被篡改消息鑒別碼MAC:與密鑰有關(guān)的單向散列函數(shù)稱為消息鑒別碼.傳送的消息為{m,z=hk(m)},接收方收到消息后計(jì)算y=hk(m),將y與z比較即可知道消息有無篡改.2.數(shù)字摘要算法-MD5亦稱消息摘要(MessageDigest)或雜湊函數(shù),由美國(guó)的RonaldRivest1992年開發(fā).輸入任意長(zhǎng)度消息x,輸出為128位的消息摘要值.算法描述:算法包括5個(gè)步驟.(1)附加填充比特在消息x后填充串1000…,使得消息的長(zhǎng)度滿足:|x|≡448mod512

填充比特總是有效,填充數(shù)為1~512.由4個(gè)32比特的寄存器A,B,C,D表示,其初始值:A=0x01234567B=0x89abcdefC=0xfedcba98D=0x76543210(2)附加長(zhǎng)度

將原始消息的長(zhǎng)度(64比特)附加到填充后的消息后面.令X[0,1,…,n-1]為填充后消息的各字(每字32比特),填充后消息的總長(zhǎng)為512的倍數(shù).

所以,n能被16整除.(3)初始化MD緩沖區(qū)主循環(huán)有4輪,每輪進(jìn)行16次操作.(4)按每塊16字(512比特)對(duì)數(shù)據(jù)進(jìn)行處理輪數(shù)X[k]的k值

10,1,2,3,…,1521,6,11,0,…,1235,8,11,14,…,240,7,14,5,…,9X[k]:消息塊X的第k個(gè)子分組(0~15);T[i]:為232×abs(sin(i))的整數(shù)部分,i為弧度;4輪的操作:a=b+((a+(g(b,c,d)+X[k]+T[i])<<<s)g在每輪中分別為F,G,H,I邏輯函數(shù)如第1輪的操作為:a=b+((a+(F(b,c,d)+X[k]+T[i])<<<s)s值(5)輸出A=(A+a)mod232B=(B+b)mod232C=(C+c)mod232D=(D+d)mod232

說明3.數(shù)字摘要算法-SHASHA由NIST開發(fā)并于1993年采納為安全雜湊標(biāo)準(zhǔn),其基礎(chǔ)是MD4,因此其設(shè)計(jì)與MD5類似.SHA-1是1995年的修改版,輸入為長(zhǎng)度小于264比特的消息,輸出為160比特的消息摘要.有5個(gè)32比特的緩沖區(qū)寄存器,其初始值分別為:A=0x67452301B=0xefcdab89C=0x98badcfeD=0x10325476E=0xc3d2e1f0以分組512比特為單位對(duì)消息進(jìn)行4輪壓縮處理,每輪處理過程對(duì)緩沖區(qū)進(jìn)行20次迭代運(yùn)算.230×sqrt(2)=0x5a827999,0

t<20230×sqrt(3)=0x6ed9eba1,20

t<40230×sqrt(5)=0x8f1bbcdc,30

t<60230×sqrt(10)=0xca62c1d6,60

t<80Kt=(B∧C)∨(B∧D),0

t<20B⊕C⊕D,20

t<40(B∧C)∨(B∧D)∨(C∧D),40

t<60B⊕C⊕D,60

t<80ft=f(t,B,C,D)=Sk:循環(huán)左移k位與MD5不同的是,直接對(duì)輸入分組X的16個(gè)字進(jìn)行迭代,而SHA是將16個(gè)字?jǐn)U展為80個(gè)字后進(jìn)行迭代.

X[t]0

t<16(Wt-16⊕Wt-14⊕Wt-8⊕Wt-3)<<<1,16

t<80Wt=W1W2W3W4W5W6W7W8W9W10W11W0W12W13W14W15W17W18…W16算法安全性Dobbertin在1996年找到了兩個(gè)不同的512bit塊,它們?cè)贛D5計(jì)算下產(chǎn)生相同的hash;王小云教授于2004年8月和2005年2月分別破譯MD5和SHA-1;實(shí)際運(yùn)用中Hash函數(shù)算法通常與其他密碼技術(shù)混合使用,偽造有意義的電子簽名需要更尖端的技術(shù).SHA和MD5的比較:

2.5公鑰密碼算法2.5.1RSA算法2.5.2ElGamal算法2.5.3ECC算法什么是公鑰密碼算法特點(diǎn)加密密鑰和解密密鑰不同,因而可以將加密密鑰公開,將解密密鑰保密.公鑰密碼的思想1976年被提出.代表性算法:RSA,ElGamal,Knapsnack,ECC等.密鑰管理簡(jiǎn)單,運(yùn)算速度較慢.安全性基于數(shù)學(xué)難題.Knapsnack:背包問題RSA:因子分解難題ELGamal算法:離散對(duì)數(shù)難題ECC算法:橢圓曲線點(diǎn)群上的離散對(duì)數(shù)難題1977年由RonRivest,AdiShamir和LenAdleman發(fā)明,1978年正式公布.RSA是一種分組加密算法.明文和密文在0~n-1之間,n是一個(gè)正整數(shù).該算法的數(shù)學(xué)基礎(chǔ)是初等數(shù)論中的Euler(歐拉)定理,并建立在大整數(shù)因子的困難性之上.目前應(yīng)用最廣泛的公鑰密碼算法.只在美國(guó)申請(qǐng)專利,且已于2000年9月到期.既能加密又可簽名,易理解和實(shí)現(xiàn),因而最流行.1.公鑰密碼算法-RSA(LefttoRight:RonRivest,AdiShamir,LenAdleman)2002年圖靈獎(jiǎng)獲得者--RSA-2002RSA算法過程選擇兩個(gè)大素?cái)?shù)p和q,計(jì)算:n=pq以及

(n)=(p-1)×(q-1)選擇隨機(jī)數(shù)1<e<

(n),gcd(e,

(n))=1,計(jì)算:d=e-1mod

(n)公鑰(e,n),私鑰(d,p,q);加密m:c=memodn

解密c:m=cdmodnx

(n)=1modnRSA算法可解性分析歐拉定理:

如果gcd(x,n)=1,則有:歐拉定理要求明文x與模數(shù)n互素但不互素的概率很小:

根據(jù)歐拉定理可以很容易地得出:cdmodn

m在選擇e時(shí),也要考慮與

(n)互素,一般選e為3,

17,

65537等等RSA算法安全性分析依賴于將整數(shù)n分解為素因子的難度公鑰私鑰的關(guān)系:

d=e-1mod

(n);已知e和n,要得到d,需要知道

(n),由

(n)的計(jì)算公式

(n)=(p-1)×(q-1)可知需要知道n的因子分解.當(dāng)n很大時(shí),這是一個(gè)難題.從安全性考慮,p與q必為足夠大的素?cái)?shù)使n的分解無法在多項(xiàng)式時(shí)間內(nèi)完成;要求n至少要有1024或者2048比特(十進(jìn)制的308位或616位).針對(duì)協(xié)議的攻擊密鑰使用不當(dāng)c=meAliceEveBobyk選r<n，計(jì)算t=r-1modn，x=remodn，y=x·cmodn簽名u=ydmodn計(jì)算tu=r-1yd=r-1(x·c)d=r-1·r·mmodn得到m共用模數(shù)n攻擊者獲得n,e1,e2,c1,c2c1=me1modnc2=me2modn若e1和e2互素,有re1+se2=1,則可以根據(jù)

((c1)-1)-r×(c2)s=mre1+se2=mmodn

選取素?cái)?shù)p>10150,一個(gè)模p的原根g以及隨機(jī)整數(shù)d(1<d<p),計(jì)算e=gdmodp,則公鑰為(e,g,p),私鑰為d

1985年發(fā)表,既可用于數(shù)字簽名又用于加密.其安全性依賴于離散對(duì)數(shù)難題.ElGamal算法過程密鑰的生成

選擇隨機(jī)數(shù)k,得到密文對(duì)(a,b)為:(a=gkmodp,b=m·ekmodp)加密m:

b·a-dmodp=m·ek·(gk)-dmodp=m解密m:

2.公鑰密碼算法-ElGamal(1)Bob選擇隨機(jī)數(shù)k=4,計(jì)算得到的密文:a=gkmodp=24mod11=5b=m·ekmodp=3·54mod11=5(2)Alice對(duì)收到的密文(5,5)解密：

b·a-dmodp=5·5-4mod11=3

選p=11,g=2,私鑰d=4,則公鑰e=gdmodp=5Bob要將消息m=3傳送給Alice.【舉例】特點(diǎn):通過選擇不同的隨機(jī)數(shù)k,即使是相同的加密密鑰,也可以將相同的明文加密成不同的密文對(duì).

1985年N.Koblitz和V.Miller分別獨(dú)立提出了橢圓曲線密碼體制(ECC),其安全性依賴于定義在橢圓曲線點(diǎn)群上的離散對(duì)數(shù)問題(ECDLP)的難解性.橢圓曲線的基本概念已知有限域GF(p)(p=qn,q>3)上的橢圓曲線群

Ep(a,b):y2=x3+ax+b(modp),a,b∈GF(p)4a3+27b2≠0PQS-S=P+QS+P+Q=O,O為無窮點(diǎn)3.公鑰密碼算法-ECC選取EP(a,b)和生成元G,公開.將明文消息m通過編碼嵌入到曲線上的點(diǎn)Pm.ECC算法過程密鑰的生成：Bob選取私鑰d,公鑰為e=dGAliceBob隨機(jī)選kCm={kG,Pm+ke}計(jì)算Pm+ke-dkG=Pm加解密過程：Alice將消息Pm發(fā)送給Bob.MIPS年表示用每秒完成100萬條指令的計(jì)算機(jī)所需工作的年數(shù)RSA與ECC比較應(yīng)用前景非常好,特別在移動(dòng)通信,無線設(shè)備上的應(yīng)用.【參考文獻(xiàn)】1.ECDLP,百度百科

2.劉淳等.基于智能卡的RSA與ECC算法的比較與實(shí)現(xiàn),計(jì)算機(jī)工程與應(yīng)用,2007,43(4):96-99公鑰/私鑰對(duì)是對(duì)應(yīng)的,公鑰公開,私鑰保密;公鑰加密的消息只能用私鑰解密,反之用私鑰加密的消息只能用對(duì)應(yīng)的公鑰解密;用于加密:任何人用Bob的公鑰對(duì)消息m加密,只有Bob才能用私鑰解密.公共網(wǎng)絡(luò)AliceBobBob公鑰kBp密碼分析Evec=EBp(m)其他人沒有私鑰kBv,故無法解密cBob私鑰kBv公鑰密碼算法小結(jié)用于數(shù)字簽名:Alice用自己的私鑰加密消息m,其他任何人(如Bob)都可以用Alice的公鑰進(jìn)行驗(yàn)證.公共網(wǎng)絡(luò)AliceBobAlice私鑰kAv偽造簽名Evem+sBob用Alice公鑰kAp驗(yàn)證s確認(rèn)mAlice公鑰kAps=EAv(m)其他人沒有Alice私鑰,無法偽造s或篡改m3.5數(shù)字簽名算法3.5.1RSA簽名算法3.5.2DSA簽名算法3.5.3離散對(duì)數(shù)簽名方案數(shù)字簽名算法但RSA算法的供應(yīng)商RSADSI反對(duì):DSA不能用于加密或者密鑰分配;由NSA研制,可能有陷門;DSA速度比RSA慢;RSA是事實(shí)上的標(biāo)準(zhǔn).1994年該標(biāo)準(zhǔn)被頒布.1998年12月規(guī)定DSA或RSA簽名方案都可用于美國(guó)各機(jī)構(gòu)生成數(shù)字簽名,2000年NIST又頒布一個(gè)新的標(biāo)準(zhǔn),指出橢圓曲線數(shù)字簽名算法ECDSA也可用于簽名.1991年,NIST提出DSA用于數(shù)字簽名標(biāo)準(zhǔn)DSS中;2000年美國(guó)通過法律,數(shù)字簽名和傳統(tǒng)簽名具有同等法律效力;我國(guó)于2005年也頒布了此法律.1.RSA簽名算法算法描述設(shè)模數(shù)為n,簽名私鑰為d,驗(yàn)證公鑰為e.對(duì)消息m簽名:s=mdmodn驗(yàn)證簽名s:semodn是否等于m安全性分析:利用指數(shù)的特點(diǎn)攻擊ed=1mod(n)

y=xemodn,m'=y·mmodn

Trent對(duì)m'簽名:s(m')=(m')d=yd·md=x·mdmodn

從而獲得m的簽名：

s(m)=mdmodn=s(m')·x-1modn盲簽名的思想e=gdmodp2.DSA簽名算法簽名密鑰:簽名私鑰為d,驗(yàn)證公鑰為e;對(duì)消息m簽名:選k(gcd(k,p-1)=1),計(jì)算簽名對(duì)(r,s):r=gkmodp,m=(dr+ks)modp-1驗(yàn)證:若errsmodp=gmmodp,則簽名有效.ElGamal簽名算法數(shù)字簽名算法DSA(Digitalsignature

algorithm)是ElGamal簽名方案的變形.1994年被美國(guó)NIST采納作為數(shù)字簽名標(biāo)準(zhǔn)DSS),使用SHA作為散列函數(shù).p:L位長(zhǎng)的素?cái)?shù),512

L

1024,64|Lq:160位的素?cái)?shù)且q|p-1g:g=h(p-1)/qmodp,1<h<p-1,g>1用戶私鑰:d,0<d<q用戶公鑰:e,e=gdmodpDSA算法描述密鑰參數(shù)Alice(r,s),H(m)Bob選k<p,計(jì)算m的簽名(r,s)r=(gkmodp)modqs=(k-1(H(m)+dr))modq簽名與驗(yàn)證過程驗(yàn)證:w=s-1modqu1=(H(m)×w)modqu2=(rw)modqr==((gu1eu2)modp)modq?d=s1=(k-1(H(m1)+dr))s2=(k-1(H(m2)+dr))s1s2H(m1)+drH(m2)+drDSA算法安全性512位的DSA不能提供長(zhǎng)期的安全性,

至少要2048位.若Eve獲得同一個(gè)k簽名的兩個(gè)消息,則可恢復(fù)d結(jié)論:k的隨機(jī)產(chǎn)生很關(guān)鍵.3.離散對(duì)數(shù)簽名方案DSA是離散對(duì)數(shù)簽名方案的一種.選擇大素?cái)?shù)p和q,q|p-1;選擇g滿足:1<g<p且gq=1modp;選私鑰d<p,則公鑰e=gdmodp;對(duì)消息m簽名和驗(yàn)證:a,b,c的值是r’,m,s的組合,產(chǎn)生多達(dá)13000種變型.選擇隨機(jī)數(shù)k<p,r=gkmodp,r’=rmodq.簽名等式:ak=b+cdmodq.驗(yàn)證等式:ramodp是否等于gbecmodp3.1基本的密碼協(xié)議3.2中級(jí)協(xié)議3.3高級(jí)協(xié)議3.經(jīng)典的密碼協(xié)議3.1基本的密碼協(xié)議3.1.1什么是密碼協(xié)議3.1.2仲裁協(xié)議和裁決協(xié)議3.1.3保密通信協(xié)議3.1.4數(shù)字簽名協(xié)議3.1.5密鑰協(xié)商協(xié)議3.1.6身份鑒別協(xié)議3.1.7秘密共享協(xié)議1.什么是密碼協(xié)議cryptographicprotocol

又稱為安全協(xié)議,是網(wǎng)絡(luò)安全的一個(gè)重要組成部分,以密碼學(xué)為基礎(chǔ)進(jìn)行消息交換,在網(wǎng)絡(luò)環(huán)境中提供各種安全服務(wù),防止或發(fā)現(xiàn)竊聽和欺騙.協(xié)議的特點(diǎn):協(xié)議中各方都必須同意并遵循它;協(xié)議必須清楚,每一步須明確定義,無歧義;協(xié)議必須是完整的,對(duì)每種可能的情況必須規(guī)定具體的動(dòng)作;協(xié)議的安全性.協(xié)議的目的:保證公平和安全,避免欺騙.2.仲裁協(xié)議和裁決協(xié)議

密碼學(xué)中典型的兩類協(xié)議,區(qū)別在于在裁決協(xié)議中仲裁者不直接參與協(xié)議執(zhí)行過程,只是確定協(xié)議是否正常執(zhí)行.仲裁者:是在完成協(xié)議的過程中,值得信賴的公正的第三方,能幫助互不信任的雙方完成協(xié)議.如律師,銀行,公證人等.仲裁者的選擇要考慮:可信任度;仲裁協(xié)議的延遲與安全;仲裁者的數(shù)目與費(fèi)用折中問題.密碼協(xié)議示例【舉例】:Alice向Bob借50萬,仲裁人為法官.基于對(duì)稱密碼機(jī)制的協(xié)議--仲裁協(xié)議Alice?法官?BobEk(50萬)Ek(10萬)Ek(50萬)Ek(50萬)Ek(80萬)Ek(10萬)Ek(80萬)k①Alice狡辯:借10萬②Bob狡辯:借80萬Alice向Bob借50萬解決方法:Alice?法官?BobEkAv(50萬)EkAv(10萬)EkAv(50萬)EkAv(50萬)EkAv(80萬)EkAv(10萬)EkAv(80萬)Alice?法官?BobEk(50萬)Ek(10萬)Ek(50萬)Ek(50萬)Ek(80萬)Ek(50萬)k基于非對(duì)稱密碼機(jī)制的協(xié)議--裁決協(xié)議①Alice狡辯借10萬,Bob出示50萬借據(jù)②Bob狡辯借80萬,無法提供80萬借據(jù)Alice向Bob借50萬協(xié)議的安全性

可以對(duì)密碼算法和協(xié)議的密碼技術(shù)進(jìn)行攻擊,也可以對(duì)協(xié)議本身進(jìn)行攻擊.被動(dòng)攻擊:竊聽協(xié)議的一部分或全部,目的是獲取消息,不影響協(xié)議的執(zhí)行.主動(dòng)攻擊:改變協(xié)議以對(duì)自己有利,插入,刪除和修改消息,破壞通信等等.騙子:協(xié)議中的一方,不遵守協(xié)議或者破壞協(xié)議.協(xié)議的安全性舉例

公鑰密碼算法本身較安全,若在協(xié)議中使用不當(dāng)將會(huì)有安全隱患.【舉例】

在同一組用戶之間共享RSA算法的公共模數(shù)n((c1)-1)-r×(c2)s=mre1+se2

mmodn攻擊者獲得Carol發(fā)給Alice和Bob的同一個(gè)消息m的密文c1和c2;攻擊者很容易知道n,e1,e2c1=me1modnc2=me2modn若e1和e2互素,有re1+se2=1,則可以根據(jù)①AliceBob加密解密mcm密鑰密鑰系統(tǒng)②③④⑤3.保密通信協(xié)議可能的攻擊:竊聽:唯密文攻擊;破壞,偽造:通信雙方能發(fā)現(xiàn).所以:好的密碼系統(tǒng)的安全性只與密鑰有關(guān),可以公開算法,因此,密鑰的管理是非常重要的.會(huì)話密鑰混合密碼系統(tǒng)用公鑰密碼機(jī)制來保護(hù)和分發(fā)會(huì)話密鑰k,會(huì)話密鑰采用對(duì)稱密碼算法,對(duì)通信的消息m進(jìn)行加密,通信結(jié)束后銷毀會(huì)話密鑰.Bob明文密文密文明文數(shù)字信封制作數(shù)字信封解開數(shù)字信封Alice網(wǎng)絡(luò)保密通信的典型應(yīng)用:----數(shù)字信封對(duì)稱密鑰加密對(duì)稱密鑰解密公鑰加密私鑰解密AliceBob明文明文摘要摘要摘要制作數(shù)字簽名驗(yàn)證數(shù)字簽名信息可審查性的典型應(yīng)用:----數(shù)字簽名摘要操作數(shù)字簽名摘要操作私鑰加密公鑰解密比較?相同->通過不相同->失敗通信信道加密理論上,加密可以在開放系統(tǒng)互連OSI通信模型的任何層進(jìn)行.實(shí)際上加密一般在最低層或較高層進(jìn)行.鏈-鏈加密(link-by-linkencryption)加密在物理層進(jìn)行;包括數(shù)據(jù),路由信息,協(xié)議信息等都被加密,亦稱流量保密,攻擊者不知道通信信息是否是有效信息;密鑰管理簡(jiǎn)單,鏈路相鄰節(jié)點(diǎn)之間有共享密鑰;中間節(jié)點(diǎn)需要進(jìn)行數(shù)據(jù)解密和加密處理,有安全隱患,而且開銷大.E12()節(jié)點(diǎn)1PD34()節(jié)點(diǎn)4D12()節(jié)點(diǎn)2E23()D23()節(jié)點(diǎn)3E34()P端-端加密(end-to-endencryption)數(shù)據(jù)被選擇加密(傳輸層信息),只在接收端解密,數(shù)據(jù)保密級(jí)別高;易受流量分析攻擊,因?yàn)槁酚尚畔⑽幢患用?密鑰管理復(fù)雜,每個(gè)用戶之間需有共同的密鑰.EAB()節(jié)點(diǎn)1PDAB()節(jié)點(diǎn)4PEAB()節(jié)點(diǎn)2EAB()節(jié)點(diǎn)3用戶A用戶B比較:

鏈-鏈加密端-端加密優(yōu)點(diǎn):

易操作,安全保密級(jí)別更高密鑰管理簡(jiǎn)單軟件更易完成缺點(diǎn):

中間節(jié)點(diǎn)數(shù)據(jù)易密鑰管理困難被暴露,開銷大允許流量分析4.數(shù)字簽名協(xié)議在計(jì)算機(jī)中:復(fù)制,剪裁,粘貼等修改可以不留下痕跡,如何保證簽名的性質(zhì)？否認(rèn)公共網(wǎng)絡(luò)AliceBobTrent誰是正確的？舉報(bào)簽名的性質(zhì):可信,不可偽造,不可重用,不可改變,不可抵賴.基于對(duì)稱密碼機(jī)制的數(shù)字簽名協(xié)議前提:Trent是一個(gè)權(quán)威可信的仲裁者,和Alice共享密鑰KA,和Bob共享密鑰KB;KA①AliceBobDB(c2)m2c2m2②③④⑤KBm2=S(A)+m1+c1EB(m2)KBTrentEA(m1)m1c1m1KADA(c1)分析簽名的性質(zhì)？(1)簽名可信:由Trent提供S(A)證明;(2)簽名不可偽造:只有Alice知道KA;(3)簽名不可重用,簽名文件不能改變:m2包含了文件消息m1和c1,m1的改變將使得其與c1不匹配;(4)簽名不可抵賴:由S(A)和c1證明.基于非對(duì)稱密碼機(jī)制的數(shù)字簽名協(xié)議基于對(duì)稱密碼機(jī)制的數(shù)字簽名協(xié)議存在的問題:Trent必須是完全可信和安全的;存在通信瓶頸,密鑰管理等問題.分析簽名的性質(zhì)？用私鑰加密文件,擁有安全的簽名:協(xié)議簡(jiǎn)單,不需要Trent進(jìn)行驗(yàn)證,只要保證公鑰是可靠的.KApAliceBobEAv(m)mcKAvDAp(c)m(1)簽名可信,不可偽造:由Alice私鑰保證;(2)簽名不可重用:簽名是文件的函數(shù);(3)被簽名的文件不能改變:由Alice私鑰保證;(4)簽名不可抵賴:只有Alice擁有私鑰.基于非對(duì)稱密碼機(jī)制的數(shù)字簽名協(xié)議存在的問題:重放攻擊;注意加密與簽名密鑰不能共用;文件大時(shí),效率低.解決方法:時(shí)間標(biāo)記:重放攻擊對(duì)合同來說問題不大,但是對(duì)于銀行支票問題就大了,加入時(shí)間標(biāo)記.單向散列函數(shù):簽名和文件可以分開保存;存儲(chǔ)量要求大大降低.Carol根據(jù)m1=m2判斷①Carols1②③④SAv(m1)m1AliceH(m)mms1VAp(s1)H(m)m1m2①Bobc②③④Bob公鑰EBp(s)sAlice簽名mSAv(m)AliceAlice公鑰VAp(s)sBob解密DBv(c)m采用離散對(duì)數(shù)簽名方案:私鑰x,公鑰y=gxmodp例如:Alice對(duì)消息m簽名,z=mxmodp,Bob驗(yàn)證.d=ctmodpBobAlice選a,bc=za·yb計(jì)算t=x-1modp-1驗(yàn)證d=ma·gbmodp其他簽名方案帶加密的數(shù)字簽名:簽名者參與驗(yàn)證的數(shù)字簽名:AliceBobm’=mk1modn可以恢復(fù)m：(m’)k2k3modn可以添加自己的簽名：

m’’=(m’)k2=(m)k1k2modn事例:在一個(gè)網(wǎng)絡(luò)中,Alice和Bob同時(shí)簽名或者加密消息m,讓接收者驗(yàn)證或者解密.RSA推廣:模數(shù)n=pq,k1×k2×…×km≡1mod

(n)用其中若干個(gè)ki加密的消息可以用剩下的kj解密舉例:Alice有k1,Bob有k2,k3公開多個(gè)參與者的數(shù)字簽名:Alice請(qǐng)求一個(gè)與Bob的會(huì)話密鑰kTrentBobm1k產(chǎn)生隨機(jī)會(huì)話密鑰km1=EKA(k)m2=EKB(k)m2①②③④⑤5.密鑰協(xié)商協(xié)議產(chǎn)生會(huì)話密鑰,以對(duì)每一次單獨(dú)的會(huì)話加密.基于對(duì)稱密碼機(jī)制(如WideMouthFrog協(xié)議)該協(xié)議假設(shè)網(wǎng)絡(luò)用戶Alice,Bob和KDC共享一個(gè)秘密密鑰.安全性分析該協(xié)議依賴于Trent的安全性;Trent參與每一次密鑰交換,容易形成瓶頸.m2也可由Alice傳給Bob,如Kerberos協(xié)議中用k通信①②③AliceBobEBp(k)kcDBv(c)kAliceBobkApMallorykMpkBpkMp當(dāng)Alice和Bob互傳公鑰時(shí),Mallory截獲,用自己的公鑰取代,從而能用私鑰解密雙方傳送的消息.基于非對(duì)稱密碼機(jī)制中間人攻擊解決方法:保證公鑰的可信,公鑰證書.Diffie-Hellman密鑰協(xié)商協(xié)議1976年發(fā)明,基于離散對(duì)數(shù)難題,用于密鑰分配.

協(xié)議描述Alice和Bob協(xié)商一個(gè)大的素?cái)?shù)p和準(zhǔn)原根g.DH密鑰交換協(xié)議很容易擴(kuò)充到三人或者更多人.選xgxmodpgymodp選y攻擊公共網(wǎng)絡(luò)AliceBobEve共享密鑰為gxymodp橢圓曲線上的DH密鑰協(xié)商協(xié)議

先選取滿足方程y2=x3+ax+b(modp),4a3+27b2≠0的橢圓曲線以及其上面的點(diǎn)構(gòu)成的Abel群EP(a,b),G是EP(a,b)的生成元.選xxGyG選y攻擊公共網(wǎng)絡(luò)AliceBobEve

共享密鑰為xyGShamir的三次傳輸協(xié)議

允許Alice和Bob在互不知道對(duì)方密鑰的情況下通信,不能防止中間人攻擊.

協(xié)議描述Alice和Bob有各自的密鑰kA和kB;E為可交換的加密算法(如異或,指數(shù)).AliceBob選kEA(k)解密將收到的信息加密EB(EA(k))EB(k)用kB解密獲得kAliceBob產(chǎn)生kAp/kAvA,Ep(kAp)解密得k,選RA解密得到kAp,選kEp(EAp(k))Ek(RA)解密獲得RA,選RBEk(RA,RB)解密得RA和RB驗(yàn)證RAEk(RB)解密并驗(yàn)證RB通過則采用k加密密鑰交換EKE協(xié)議

SteveBellovin和MichaelMerritt設(shè)計(jì),用共享密鑰加密隨機(jī)產(chǎn)生的公開密鑰,建立會(huì)話密鑰.前提:Alice和Bob共享公共口令p,要生成臨時(shí)的會(huì)話密鑰k.基于雙線性對(duì)的密鑰協(xié)商協(xié)議

雙線性對(duì)(Weilpairing)雙線性:對(duì)于任意P,Q,RG1和a,bZqx,有(1)ê(P,P)

1;(2)ê(P+Q,R)=ê(P,R)ê(Q,P);(3)ê(R,P+Q)=ê(R,P)ê(P,Q);(4)ê(aP,bQ)=ê(abP,Q)=ê(P,abQ)=ê(P,Q)ab;非退化性:存在P,Q

G1,使得ê(P,Q)1.可計(jì)算性:對(duì)于任意的P,Q

G1,存在一個(gè)高效的算法計(jì)算ê(P,Q).Alice公鑰為QA,私鑰為sQABob公鑰為QB,

私鑰為sQBAliceBob隨機(jī)選rrG計(jì)算ê(rG,sQB)計(jì)算ê(rsG,QB)

雙線性對(duì)用于密鑰分配PKG選擇s,公開G,sG;給用戶分配私鑰:PKG公開G;網(wǎng)絡(luò)用戶選擇私鑰分別為a,b,c,計(jì)算對(duì)應(yīng)的公鑰PA=aG,PB=bG,PC=cG公開.三方協(xié)商的共享密鑰為k:

k=ê(PB,PC)a=ê(PA,PC)b=ê(PA,PB)cAliceKDCEAp(EKp(k))用私鑰解密獲得kEAp(k)匿名密鑰分配協(xié)議

密鑰的安全性很重要,由可信的KDC產(chǎn)生和分配.如何避免KDC知道用戶選擇的密鑰？思想:KDC產(chǎn)生足夠長(zhǎng)的連續(xù)的密鑰序列,用自己的公鑰加密傳到網(wǎng)上.用戶選擇:Alice的公鑰為kAp,KDC的公鑰為kKp如何鑒別通信對(duì)象的身份？公共網(wǎng)絡(luò)AliceBob假冒Eve身份鑒別:就是確認(rèn)實(shí)體是它所聲明的,身份鑒別服務(wù)提供關(guān)于某個(gè)實(shí)體身份的保證,以對(duì)抗假冒攻擊.6.身份鑒別協(xié)議解決方法:使用散列函數(shù),數(shù)據(jù)庫中保持用戶口令的散列值.計(jì)算機(jī)如何識(shí)別登錄用戶？口令安全信道Alice服務(wù)器攻擊:Eve侵入服務(wù)器數(shù)據(jù)庫,竊取用戶口令.竊取Eve段桂華duangh@口令安全信道Alice服務(wù)器猜測(cè)Eve口令選擇:人們?cè)谶x擇自己的口令時(shí),通常選擇一個(gè)弱口令,如選擇的是zs111而不是*9(hH/A.字典攻擊:首先嘗試最可能的密鑰,非常有效,能破譯一般計(jì)算機(jī)上40％的口令.段桂華duangh@常用的攻擊方式：用戶姓名,簡(jiǎn)寫字母,帳戶等有關(guān)個(gè)人信息;從各種數(shù)據(jù)庫中得到的單詞;各種單詞的不同置換形式,如大小寫,誤寫;嘗試詞組.要求:密鑰既容易記憶,又難以被猜中.【舉例】Standhighandseefar.→^Shasf^

Chuanguoshuiwuhen.→~Cgswh~建議:加入標(biāo)點(diǎn)符號(hào);由較長(zhǎng)的短語的首字母組成字母串.口令公共網(wǎng)絡(luò)Alice服務(wù)器截獲Eve重放攻擊:Eve在公共網(wǎng)絡(luò)上截獲Alice的口令,進(jìn)行重放登錄.解決方法:一次性口令.數(shù)據(jù)庫中需保存很多口令散列值段桂華duangh@Alice服務(wù)器Alice,R保管計(jì)算f(xi),與xi+1比較,匹配成功則用xi代替xi+1保存Alice,xn+1x1,x2,…,xn登錄Alice,xi確認(rèn)取消xix1=f(R)x2=f(x1):xn+1=f(xn)SKEY協(xié)議由于每個(gè)數(shù)只用一次,因此對(duì)數(shù)據(jù)庫攻擊用處不大;節(jié)約存儲(chǔ)開銷.解決方法:密碼技術(shù)通信雙方如何鑒別對(duì)方的身份？公共網(wǎng)絡(luò)AliceBob假冒Eve身份鑒別:就是確認(rèn)實(shí)體是它所聲明的,身份鑒別服務(wù)提供關(guān)于某個(gè)實(shí)體身份的保證,以對(duì)抗假冒攻擊.使用對(duì)稱密碼技術(shù)鑒別前提：假設(shè)Alice和Bob共享密鑰k.鑒別：擁有密鑰k的人即是確認(rèn)身份的人.AliceBobRA選隨機(jī)數(shù)RB,Hk(RA,RB,B)RB,Hk(RA,RB,B)計(jì)算并比較Hk(RA,RB,B)Hk(RB,A)計(jì)算并比較Hk(RB,A)①②③④⑤使用公鑰密碼技術(shù)鑒別前提:用戶保存自己的私鑰,公開公鑰文件.鑒別:擁有與公鑰kp對(duì)應(yīng)的私鑰kv的人即是可確認(rèn)身份的人.AliceBob請(qǐng)求對(duì)r加密在數(shù)據(jù)庫中查找Alice的公鑰驗(yàn)證隨機(jī)數(shù)rAlice,EAv(r)7.秘密共享協(xié)議

秘密共享又稱為門限方案,保證在協(xié)議中只有當(dāng)足夠多的一組成員達(dá)成一致時(shí)才能共享一個(gè)秘密.(k,n)門限方案:在n個(gè)人中,每人共享秘密m的部分信息Di

任何k-1部分信息不能恢復(fù)m

由任何k部分信息Di可以很容易計(jì)算出m

具有代表性的有Shamir門限方案和Asmuth-Bloom門限方案.則m=f(0)Shamir門限方案方案描述:構(gòu)建k-1次多項(xiàng)式f(x)=m+a1x+a2x2+…+ak-1xk-1modp計(jì)算D1=f(1),D2=f(2),…Dn=f(n)從其中選k個(gè)即可恢復(fù)m,給定k個(gè)Dj1,Dj2,…,Djk,=88-1

(x-3)(x-5)+10(-4)-1

(x-1)(x-5)+118-1

(x-1)(x-3)mod17=120(x2-8x+15)+40(x2-6x+5)+165(x2-4x+3)mod17=2x2+10x+13mod17所以:m=f(0)=13【舉例】設(shè)m=13,n=5,k=3,p=17，構(gòu)建的k-1次多項(xiàng)式

f(x)=13+10x+2x2mod17

則各秘密份額為:D1=8,D2=7,D3=10,D4=0,D5=11取D1,D3,D5Bloom門限方案方案描述:選取t個(gè)嚴(yán)格遞增的m1,m2,…,mn,滿足gcd(mi,mj)=1計(jì)算

M=m1

m2

…

mn

Hk=m1

m2

…

mk-1

mk

hk-1=mn

mn-1

…

mn-(k-1)+1

要求Hk(N+1)hk-1,N為一個(gè)大的整數(shù)對(duì)于任意的秘密x(hk-1<x<Hk)計(jì)算：ai=x%mi，則{(a1,m1),(a2,m2),…(an,mn)}是一個(gè)(k,n)門限方案.分析根據(jù)中國(guó)剩余定理

m1,m2,…,mn兩兩互素,同余方程組

x=a1modm1

x=a2modm2

…

x=anmodmn

x的解等價(jià)于:x=a1T1M1+…+anTnMnmodM

其中M=m1

m2

…

mn

Mi=M/mi

Ti=Mi-1modmi

則可構(gòu)建k項(xiàng)的同余方程組

x=a1modm1

x=a2modm2

…

x=akmodmk假設(shè)已知(a1,m1),(a2,m2),…(ak,mk)1

k

nx=a1T’1M’1+…+akT’kM’kmodM’根據(jù)前面已知的Hk為k個(gè)不同mi的最小乘積,而hk-1為k-1個(gè)不同mi的最大乘積,則有:M’

Hk>x

故可以通過上式獲得x.

則可構(gòu)建k-1項(xiàng)的同余方程組

x=a1modm1

x=a2modm2

…

x=ak-1modmk-1假設(shè)已知(a1,m1),(a2,m2),…(ak-1,mk-1)1

k

n根據(jù)前面已知的Hk為k個(gè)不同mi的最小乘積,而hk-1為k-1個(gè)不同mi的最大乘積,則有:x=a1T’’1M’’1+…+ak-1T’’k-1M’’k-1modM’’M’’

hk-1<x

故不能通過上式獲得x,x可能的值有:

hk-1<x<Hk

(Hk-hk-1)/hk-1=N個(gè)舉例則消息x=500的(3,4)門限方案為:a1=500mod9=5a2=500mod11=5a3=500mod13=6a4=500mod14=10{(5,9)(5,11)(6,13)(10,14)}已知k=3,t=4,m1=9,m2=11,m3=13,m4=14，假設(shè)已知(5,9)(5,11)(6,13),構(gòu)造方程:x=5mod9=a1modm1x=5mod11=a2modm2x=6mod13=a3modm3M=91113=1287

M1=1113=143M2=913=117M3=911=99T1=143-1mod9=8-1mod9=-1T2=117-1mod11=7-1mod11=8T3=99-1mod13=8-1mod13=5所以x=5143(-1)+51178+6995mod1287=500mod1287假設(shè)已知(5,9)(6,13),構(gòu)造方程:x=5mod9=a1modm1x=6mod13=a2modm2

x=513(13-1mod9)+69(9-1mod13)=617mod117=32mod117

所以x可能的值為：266,383,500,617,734,…3.2中級(jí)密碼協(xié)議3.2.1數(shù)字時(shí)間標(biāo)記協(xié)議3.2.2閾下信道3.2.3安全計(jì)算協(xié)議3.2.4位承諾協(xié)議3.2.5智力撲克協(xié)議3.2.6密鑰托管協(xié)議3.2.7密鑰分發(fā)協(xié)議1.數(shù)字時(shí)間標(biāo)記協(xié)議

數(shù)字時(shí)間標(biāo)記的性質(zhì)數(shù)據(jù)本身必須有時(shí)間標(biāo)記;文件的改變很明顯;不可能用不同于當(dāng)前日期和時(shí)間來標(biāo)記文件.缺點(diǎn):無保密性;數(shù)據(jù)庫巨大;存在傳輸錯(cuò)誤;Trent可信.事件:在版權(quán)和專利爭(zhēng)端中,需要標(biāo)記時(shí)間.仲裁解決辦法策略:AliceTrent文件副本在文件副本上簽時(shí)間標(biāo)記并保存副本特點(diǎn):散列值可保密;Trent不用保存文件副本;可驗(yàn)證簽名.缺點(diǎn):Alice和Trent合謀.解決方法是:將Alice的時(shí)間標(biāo)記同以前由Trent產(chǎn)生的時(shí)間標(biāo)記鏈接起來.改進(jìn)的仲裁解決辦法策略:使用散列函數(shù)和數(shù)字簽名AliceTrenthash(m)對(duì)加上時(shí)間標(biāo)記的文件副本簽名STv(hash(m)+T)2.閾下信道協(xié)議要求:Walter和Bob都能驗(yàn)證m;Water無法發(fā)現(xiàn)s.Alice私鑰為d,公鑰為e=gdmodp,gcd(s,p-1)=1

Alice和Bob在Walter的監(jiān)控下通過傳送簽名消息m來傳送秘密s.基于ElGamal協(xié)議:p