現(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ò)熱點研究中的應(yīng)用,掌握解決計算機網(wǎng)絡(luò)安全問題的基本方法和策略.

教輔材料：

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

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

計算機樓413

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

2.1密碼機制分類2.2對稱密碼算法

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

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

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

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

4.1概述4.2ECB模式

4.3CBC模式4.4CFB模式

4.5OFB模式5密碼管理

5.1密鑰管理概述5.2對稱密鑰的管理

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

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

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

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

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

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

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

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

f(Ri-1,ki)

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

0=1,0

1=1,0

0=0,1

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

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

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

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

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

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

128比特的明文分組被分成4×4的字節(jié)矩陣.字節(jié)替換SubBytes.非線性置換,獨立作用于狀態(tài)中的每一個字節(jié).移位行運算ShiftRows.字節(jié)的循環(huán)移位運算,第1行~第4行字節(jié)分別向左移動0~3列.混合列運算MixColumns.由一個線性變換對狀態(tài)的每一列進行變換.02030101010203010101020303010102輪密鑰加密AddRoundKey.與相應(yīng)的密鑰進行異或.線性變換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),如分組長度Nb為128比特,輪數(shù)Nr為10時,需要1408比特.AES解密算法InvSubBytes中逆S盒逆行移位運算InvShiftRows

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

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

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

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

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

k即為密鑰流,為產(chǎn)生的隨機字節(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填充另一個256字節(jié)的數(shù)組,不斷重復(fù)密鑰直至填充整個數(shù)組;

j=0

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

易

難

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)},接收方收到消息后計算y=hk(m),將y與z比較即可知道消息有無篡改.2.數(shù)字摘要算法-MD5亦稱消息摘要(MessageDigest)或雜湊函數(shù),由美國的RonaldRivest1992年開發(fā).輸入任意長度消息x,輸出為128位的消息摘要值.算法描述:算法包括5個步驟.(1)附加填充比特在消息x后填充串1000…,使得消息的長度滿足:|x|≡448mod512

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

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

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

10,1,2,3,…,1521,6,11,0,…,1235,8,11,14,…,240,7,14,5,…,9X[k]:消息塊X的第k個子分組(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è)計與MD5類似.SHA-1是1995年的修改版,輸入為長度小于264比特的消息,輸出為160比特的消息摘要.有5個32比特的緩沖區(qū)寄存器,其初始值分別為:A=0x67452301B=0xefcdab89C=0x98badcfeD=0x10325476E=0xc3d2e1f0以分組512比特為單位對消息進行4輪壓縮處理,每輪處理過程對緩沖區(qū)進行20次迭代運算.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不同的是,直接對輸入分組X的16個字進行迭代,而SHA是將16個字擴展為80個字后進行迭代.

X[t]0

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

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

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

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

(n),gcd(e,

(n))=1,計算: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時,也要考慮與

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

17,

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

d=e-1mod

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

(n),由

(n)的計算公式

(n)=(p-1)×(q-1)可知需要知道n的因子分解.當(dāng)n很大時,這是一個難題.從安全性考慮,p與q必為足夠大的素數(shù)使n的分解無法在多項式時間內(nèi)完成;要求n至少要有1024或者2048比特(十進制的308位或616位).針對協(xié)議的攻擊密鑰使用不當(dāng)c=meAliceEveBobyk選r<n，計算t=r-1modn，x=remodn，y=x·cmodn簽名u=ydmodn計算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

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

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

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

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

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

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

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

1985年N.Koblitz和V.Miller分別獨立提出了橢圓曲線密碼體制(ECC),其安全性依賴于定義在橢圓曲線點群上的離散對數(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為無窮點3.公鑰密碼算法-ECC選取EP(a,b)和生成元G,公開.將明文消息m通過編碼嵌入到曲線上的點Pm.ECC算法過程密鑰的生成：Bob選取私鑰d,公鑰為e=dGAliceBob隨機選kCm={kG,Pm+ke}計算Pm+ke-dkG=Pm加解密過程：Alice將消息Pm發(fā)送給Bob.MIPS年表示用每秒完成100萬條指令的計算機所需工作的年數(shù)RSA與ECC比較應(yīng)用前景非常好,特別在移動通信,無線設(shè)備上的應(yīng)用.【參考文獻】1.ECDLP,百度百科

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

y=xemodn,m'=y·mmodn

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

從而獲得m的簽名：

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

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

L

1024,64|Lq:160位的素數(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,計算m的簽名(r,s)r=(gkmodp)modqs=(k-1(H(m)+dr))modq簽名與驗證過程驗證: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不能提供長期的安全性,

至少要2048位.若Eve獲得同一個k簽名的兩個消息,則可恢復(fù)d結(jié)論:k的隨機產(chǎn)生很關(guān)鍵.3.離散對數(shù)簽名方案DSA是離散對數(shù)簽名方案的一種.選擇大素數(shù)p和q,q|p-1;選擇g滿足:1<g<p且gq=1modp;選私鑰d<p,則公鑰e=gdmodp;對消息m簽名和驗證:a,b,c的值是r’,m,s的組合,產(chǎn)生多達13000種變型.選擇隨機數(shù)k<p,r=gkmodp,r’=rmodq.簽名等式:ak=b+cdmodq.驗證等式:ramodp是否等于gbecmodp3.1基本的密碼協(xié)議3.2中級協(xié)議3.3高級協(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ò)安全的一個重要組成部分,以密碼學(xué)為基礎(chǔ)進行消息交換,在網(wǎng)絡(luò)環(huán)境中提供各種安全服務(wù),防止或發(fā)現(xiàn)竊聽和欺騙.協(xié)議的特點:協(xié)議中各方都必須同意并遵循它;協(xié)議必須清楚,每一步須明確定義,無歧義;協(xié)議必須是完整的,對每種可能的情況必須規(guī)定具體的動作;協(xié)議的安全性.協(xié)議的目的:保證公平和安全,避免欺騙.2.仲裁協(xié)議和裁決協(xié)議

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

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

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

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

mmodn攻擊者獲得Carol發(fā)給Alice和Bob的同一個消息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),可以公開算法,因此,密鑰的管理是非常重要的.會話密鑰混合密碼系統(tǒng)用公鑰密碼機制來保護和分發(fā)會話密鑰k,會話密鑰采用對稱密碼算法,對通信的消息m進行加密,通信結(jié)束后銷毀會話密鑰.Bob明文密文密文明文數(shù)字信封制作數(shù)字信封解開數(shù)字信封Alice網(wǎng)絡(luò)保密通信的典型應(yīng)用:----數(shù)字信封對稱密鑰加密對稱密鑰解密公鑰加密私鑰解密AliceBob明文明文摘要摘要摘要制作數(shù)字簽名驗證數(shù)字簽名信息可審查性的典型應(yīng)用:----數(shù)字簽名摘要操作數(shù)字簽名摘要操作私鑰加密公鑰解密比較?相同->通過不相同->失敗通信信道加密理論上,加密可以在開放系統(tǒng)互連OSI通信模型的任何層進行.實際上加密一般在最低層或較高層進行.鏈-鏈加密(link-by-linkencryption)加密在物理層進行;包括數(shù)據(jù),路由信息,協(xié)議信息等都被加密,亦稱流量保密,攻擊者不知道通信信息是否是有效信息;密鑰管理簡單,鏈路相鄰節(jié)點之間有共享密鑰;中間節(jié)點需要進行數(shù)據(jù)解密和加密處理,有安全隱患,而且開銷大.E12()節(jié)點1PD34()節(jié)點4D12()節(jié)點2E23()D23()節(jié)點3E34()P端-端加密(end-to-endencryption)數(shù)據(jù)被選擇加密(傳輸層信息),只在接收端解密,數(shù)據(jù)保密級別高;易受流量分析攻擊,因為路由信息未被加密;密鑰管理復(fù)雜,每個用戶之間需有共同的密鑰.EAB()節(jié)點1PDAB()節(jié)點4PEAB()節(jié)點2EAB()節(jié)點3用戶A用戶B比較:

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

易操作,安全保密級別更高密鑰管理簡單軟件更易完成缺點:

中間節(jié)點數(shù)據(jù)易密鑰管理困難被暴露,開銷大允許流量分析4.數(shù)字簽名協(xié)議在計算機中:復(fù)制,剪裁,粘貼等修改可以不留下痕跡,如何保證簽名的性質(zhì)？否認公共網(wǎng)絡(luò)AliceBobTrent誰是正確的？舉報簽名的性質(zhì):可信,不可偽造,不可重用,不可改變,不可抵賴.基于對稱密碼機制的數(shù)字簽名協(xié)議前提:Trent是一個權(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證明.基于非對稱密碼機制的數(shù)字簽名協(xié)議基于對稱密碼機制的數(shù)字簽名協(xié)議存在的問題:Trent必須是完全可信和安全的;存在通信瓶頸,密鑰管理等問題.分析簽名的性質(zhì)？用私鑰加密文件,擁有安全的簽名:協(xié)議簡單,不需要Trent進行驗證,只要保證公鑰是可靠的.KApAliceBobEAv(m)mcKAvDAp(c)m(1)簽名可信,不可偽造:由Alice私鑰保證;(2)簽名不可重用:簽名是文件的函數(shù);(3)被簽名的文件不能改變:由Alice私鑰保證;(4)簽名不可抵賴:只有Alice擁有私鑰.基于非對稱密碼機制的數(shù)字簽名協(xié)議存在的問題:重放攻擊;注意加密與簽名密鑰不能共用;文件大時,效率低.解決方法:時間標(biāo)記:重放攻擊對合同來說問題不大,但是對于銀行支票問題就大了,加入時間標(biāo)記.單向散列函數(shù):簽名和文件可以分開保存;存儲量要求大大降低.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采用離散對數(shù)簽名方案:私鑰x,公鑰y=gxmodp例如:Alice對消息m簽名,z=mxmodp,Bob驗證.d=ctmodpBobAlice選a,bc=za·yb計算t=x-1modp-1驗證d=ma·gbmodp其他簽名方案帶加密的數(shù)字簽名:簽名者參與驗證的數(shù)字簽名:AliceBobm’=mk1modn可以恢復(fù)m：(m’)k2k3modn可以添加自己的簽名：

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

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

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

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

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

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

協(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驗證RAEk(RB)解密并驗證RB通過則采用k加密密鑰交換EKE協(xié)議

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

雙線性對(Weilpairing)雙線性:對于任意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.可計算性:對于任意的P,Q

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

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

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

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

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

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

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

具有代表性的有Shamir門限方案和Asmuth-Bloom門限方案.則m=f(0)Shamir門限方案方案描述:構(gòu)建k-1次多項式f(x)=m+a1x+a2x2+…+ak-1xk-1modp計算D1=f(1),D2=f(2),…Dn=f(n)從其中選k個即可恢復(fù)m,給定k個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次多項式

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

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

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為一個大的整數(shù)對于任意的秘密x(hk-1<x<Hk)計算：ai=x%mi，則{(a1,m1),(a2,m2),…(an,mn)}是一個(k,n)門限方案.分析根據(jù)中國剩余定理

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

x=a1modm1

x=a2modm2

…

x=anmodmn

x的解等價于:x=a1T1M1+…+anTnMnmodM

其中M=m1

m2

…

mn

Mi=M/mi

Ti=Mi-1modmi

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

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個不同mi的最小乘積,而hk-1為k-1個不同mi的最大乘積,則有:M’

Hk>x

故可以通過上式獲得x.

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

x=a1modm1

x=a2modm2

…

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

k

n根據(jù)前面已知的Hk為k個不同mi的最小乘積,而hk-1為k-1個不同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個舉例則消息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中級密碼協(xié)議3.2.1數(shù)字時間標(biāo)記協(xié)議3.2.2閾下信道3.2.3安全計算協(xié)議3.2.4位承諾協(xié)議3.2.5智力撲克協(xié)議3.2.6密鑰托管協(xié)議3.2.7密鑰分發(fā)協(xié)議1.數(shù)字時間標(biāo)記協(xié)議

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