lecture03-公鑰加密與hash函數(shù)

1、1公鑰加密與公鑰加密與Hash函數(shù)函數(shù)王麗蘋王麗蘋華東師范大學(xué)軟件學(xué)院華東師范大學(xué)軟件學(xué)院2022年年7月月4日日2outlinen公鑰密碼體制的基本原理（公鑰密碼體制的基本原理（Chapter6）nRSA算法的簡(jiǎn)介（算法的簡(jiǎn)介（Chapter6）n消息認(rèn)證和消息認(rèn)證和hash函數(shù)（函數(shù)（Chapter8）3公鑰密碼體制的基本原理公鑰密碼體制的基本原理n對(duì)稱密鑰算法的不足對(duì)稱密鑰算法的不足（1）密鑰管理量的困難：傳統(tǒng)密鑰管理：兩兩分別用一密鑰管理量的困難：傳統(tǒng)密鑰管理：兩兩分別用一個(gè)密鑰，則個(gè)密鑰，則n個(gè)用戶需要個(gè)用戶需要c（n,2) =n(n-1)/2個(gè)密鑰，個(gè)密鑰，當(dāng)用戶量增大時(shí)，密鑰空間

2、急劇增大。如：當(dāng)用戶量增大時(shí)，密鑰空間急劇增大。如： n = 100 時(shí)，時(shí)， c（100，2）= 4.995 n = 5000時(shí)，時(shí)，c（5000，2）=12，497，500（2）密鑰必須通過(guò)某一信道協(xié)商，對(duì)這個(gè)信道的安全性密鑰必須通過(guò)某一信道協(xié)商，對(duì)這個(gè)信道的安全性的要求比正常的傳送消息的信道的安全性要高的要求比正常的傳送消息的信道的安全性要高（3）數(shù)字簽名的問(wèn)題：傳統(tǒng)加密算法無(wú)法實(shí)現(xiàn)抗抵賴的數(shù)字簽名的問(wèn)題：傳統(tǒng)加密算法無(wú)法實(shí)現(xiàn)抗抵賴的要求。要求。4公鑰密碼體制的基本原理公鑰密碼體制的基本原理n起源：起源：n公鑰密碼又稱為雙鑰密碼和非對(duì)稱密碼，是公鑰密碼又稱為雙鑰密碼和非對(duì)稱密碼，是197

3、6年由Diffie和Hellman在其“密碼學(xué)新方向”文中提出的，見劃時(shí)代的文獻(xiàn)：nW.Diffie and M.E.Hellman, New Directrions inCryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654nRSA公鑰算法公鑰算法是由Rivest,Shamir和Adleman在1978年提出來(lái)的，見n1978 Communitions of the ACM. Vol.21.No.2.5公鑰密碼體制的基本原理公鑰密碼體制的基本原理n公鑰密碼體制的重要特性：

4、公鑰密碼體制的重要特性：n加密與解密由不同的密鑰完成加密與解密由不同的密鑰完成:n加密加密: X-Y:Y=EKU(X) /KU為公鑰，為公鑰，KR為私鑰為私鑰n解密解密: Y-X:X=DKR(Y)=DKR(EKU(X) n知道加密算法知道加密算法,從加密密鑰得到解密密鑰在計(jì)算從加密密鑰得到解密密鑰在計(jì)算上是不可行的上是不可行的n兩個(gè)密鑰中任何一個(gè)都可以用作加密而另一個(gè)兩個(gè)密鑰中任何一個(gè)都可以用作加密而另一個(gè)用作解密用作解密nX=DKR(EKU(X)=EKU(DKR(X)6公鑰密碼體制的加密過(guò)程公鑰密碼體制的加密過(guò)程7公鑰密碼體制的加密過(guò)程公鑰密碼體制的加密過(guò)程n用公鑰密碼實(shí)現(xiàn)保密用公鑰密碼實(shí)現(xiàn)

5、保密n用戶擁有自己的密鑰對(duì)用戶擁有自己的密鑰對(duì)(KU,KR)n公鑰公鑰KU公開公開,私鑰私鑰KR保密保密.nA-B:Y=E KUb(X).nB: DKRb(Y)=DKRb(EKUb(X)=X8公鑰密碼體制的認(rèn)證過(guò)程公鑰密碼體制的認(rèn)證過(guò)程9公鑰密碼體制的認(rèn)證過(guò)程公鑰密碼體制的認(rèn)證過(guò)程n用公鑰密碼實(shí)現(xiàn)鑒別用公鑰密碼實(shí)現(xiàn)鑒別n條件條件:兩個(gè)密鑰中任何一個(gè)都可以用作加密而另兩個(gè)密鑰中任何一個(gè)都可以用作加密而另一個(gè)用作解密一個(gè)用作解密n鑒別鑒別:nA-ALL:Y=D KRa(X)nALL: EKUa(Y) = EKUa(DKRa(X) = X.n鑒別鑒別+保密保密:nA-B: Z = EKUb(DKRa

6、(X)nB: EKUa(DKRb(Z) = X10思考思考n如何通過(guò)互聯(lián)網(wǎng)進(jìn)行可靠的郵件傳輸？如何通過(guò)互聯(lián)網(wǎng)進(jìn)行可靠的郵件傳輸？n假設(shè)甲要寄信給乙，他們互相知道對(duì)方的公鑰。假設(shè)甲要寄信給乙，他們互相知道對(duì)方的公鑰。n甲就用乙的公鑰加密郵件寄出，乙收到后就可以用自己的私鑰甲就用乙的公鑰加密郵件寄出，乙收到后就可以用自己的私鑰解密出甲的原文。由于別人不知道乙的私鑰，所以即使是甲本解密出甲的原文。由于別人不知道乙的私鑰，所以即使是甲本人也無(wú)法解密那封信，這就解決了信件保密的問(wèn)題。人也無(wú)法解密那封信，這就解決了信件保密的問(wèn)題。 n由于每個(gè)人都知道乙的公鑰，他們都可以給乙發(fā)信，那由于每個(gè)人都知道乙的公鑰

7、，他們都可以給乙發(fā)信，那么乙怎么確信是不是甲的來(lái)信呢？么乙怎么確信是不是甲的來(lái)信呢？n需要用到基于加密技術(shù)的數(shù)字簽名。需要用到基于加密技術(shù)的數(shù)字簽名。過(guò)程：過(guò)程：甲用自己的私鑰將簽名內(nèi)容加密，附加在郵件后，再用甲用自己的私鑰將簽名內(nèi)容加密，附加在郵件后，再用乙的公鑰將整個(gè)郵件加密（注意這里的次序，如果先加密再簽乙的公鑰將整個(gè)郵件加密（注意這里的次序，如果先加密再簽名的話，別人可以將簽名去掉后簽上自己的簽名，從而篡改了名的話，別人可以將簽名去掉后簽上自己的簽名，從而篡改了簽名）。這樣這份密文被乙收到以后，乙用自己的私鑰將郵件簽名）。這樣這份密文被乙收到以后，乙用自己的私鑰將郵件解密，得到甲的原文

8、和數(shù)字簽名，然后用甲的公鑰解密簽名，解密，得到甲的原文和數(shù)字簽名，然后用甲的公鑰解密簽名，這樣一來(lái)就可以確保兩方面的安全了。這樣一來(lái)就可以確保兩方面的安全了。11公鑰密鑰的應(yīng)用范圍公鑰密鑰的應(yīng)用范圍n加密加密/解密解密n數(shù)字簽名（身份鑒別）數(shù)字簽名（身份鑒別）n密鑰交換密鑰交換12outlinen公鑰密碼體制的基本原理（公鑰密碼體制的基本原理（Chapter9）nRSA算法的簡(jiǎn)介（算法的簡(jiǎn)介（Chapter9）n消息認(rèn)證和消息認(rèn)證和hash函數(shù)（函數(shù)（Chapter11）13RSA算法簡(jiǎn)介算法簡(jiǎn)介nRAS算法是由算法是由Rivest, Shamir和和Adleman在在1978年提出來(lái)的。年提

9、出來(lái)的。n是一種分組加密算法：是一種分組加密算法：n分組的大小可以變，但是不能夠超過(guò)密鑰的長(zhǎng)度。分組的大小可以變，但是不能夠超過(guò)密鑰的長(zhǎng)度。n應(yīng)用最廣泛的公鑰算法應(yīng)用最廣泛的公鑰算法n在美國(guó)申請(qǐng)專利，且已于在美國(guó)申請(qǐng)專利，且已于2000年年9月到期。月到期。14RSA算法描述算法描述Key GenerationSelect p, q p and q both prime, p !=qCalculate n = p * qCalculate (n) = (p 1)(q 1)Select integer e gcd(n), e) = 1; 1 e (n) Calculate d d = e-1 m

10、od (n) 等價(jià)于等價(jià)于 de = 1 mod (n)Public key KU = e, nPrivate key KR = d, nEncryptionPlaintext: M nCiphertext: C = Me (mod n)DecryptionCiphertext: CPlaintext: M = Cd (mod n)15RSA算法描述算法描述nRSA體制是一種分組密碼，明文需要按照體制是一種分組密碼，明文需要按照分組來(lái)加密。分組來(lái)加密。n其明文和密文都是其明文和密文都是0至至n-1之間的整數(shù)。之間的整數(shù)。n通常通常n的大小為的大小為1029位的二進(jìn)制位或者位的二進(jìn)制位或者309

11、位位十進(jìn)制位。十進(jìn)制位。16RSA算法算法Examplen1.選擇素?cái)?shù)選擇素?cái)?shù):p=17&q=11（保密）（保密）n2.計(jì)算計(jì)算n=pq=1711=187n3.計(jì)算計(jì)算(n)=(p1)(q-1)=1610=160n4.選擇選擇e使其與使其與(n)互素且小于互素且小于(n): gcd(e,160)=1; 選選擇擇e=7n5.確定確定 d: de = 1 mod 160 and d160，d=23因?yàn)橐驗(yàn)?37=161=1160+1（保密）（保密）n6.公鑰公鑰 KU=7,187n7.私鑰私鑰 KR=23,17,11（保密）（保密）17RSA實(shí)現(xiàn)中的問(wèn)題實(shí)現(xiàn)中的問(wèn)題n（1）如何計(jì)算）如何計(jì)

12、算ab mod nn中間結(jié)果非常大中間結(jié)果非常大n冪運(yùn)算的效率冪運(yùn)算的效率n（2）密鑰產(chǎn)生）密鑰產(chǎn)生n如何找到足夠大的素?cái)?shù)如何找到足夠大的素?cái)?shù)p和和q?n選擇選擇e或或d計(jì)算另外一個(gè)計(jì)算另外一個(gè)18對(duì)對(duì)RSA算法的攻擊算法的攻擊n(1) 強(qiáng)力攻擊（窮舉法）：嘗試所有可能的強(qiáng)力攻擊（窮舉法）：嘗試所有可能的私有密鑰私有密鑰n(2)數(shù)學(xué)分析攻擊：各種數(shù)學(xué)方法，等價(jià)與數(shù)學(xué)分析攻擊：各種數(shù)學(xué)方法，等價(jià)與兩個(gè)素?cái)?shù)乘積的因子分解兩個(gè)素?cái)?shù)乘積的因子分解n(3) 對(duì)對(duì)RSA實(shí)現(xiàn)的攻擊實(shí)現(xiàn)的攻擊19加密算法小結(jié)加密算法小結(jié)n對(duì)稱密碼算法對(duì)稱密碼算法n運(yùn)算速度快、密鑰短、多種用途（隨機(jī)數(shù)產(chǎn)生、運(yùn)算速度快、密鑰短、

13、多種用途（隨機(jī)數(shù)產(chǎn)生、Hash函數(shù)）、歷史悠久函數(shù)）、歷史悠久n密鑰管理困難（分發(fā)、更換）密鑰管理困難（分發(fā)、更換）n對(duì)稱的，通信方是平等的（不能為發(fā)送者提供保護(hù)）對(duì)稱的，通信方是平等的（不能為發(fā)送者提供保護(hù)）.n非對(duì)稱密碼算法非對(duì)稱密碼算法n只需保管私鑰、可以相當(dāng)長(zhǎng)的時(shí)間保持不變、需要的數(shù)只需保管私鑰、可以相當(dāng)長(zhǎng)的時(shí)間保持不變、需要的數(shù)目較小目較小n運(yùn)算速度慢、密鑰尺寸大、歷史短運(yùn)算速度慢、密鑰尺寸大、歷史短n非對(duì)稱的，通信方是不平等的，因?yàn)榧用芟⒑万?yàn)證簽非對(duì)稱的，通信方是不平等的，因?yàn)榧用芟⒑万?yàn)證簽名的人不能解密同一信息和產(chǎn)生同樣的簽名名的人不能解密同一信息和產(chǎn)生同樣的簽名20加密算法

14、小結(jié)加密算法小結(jié)n公鑰算法加密解密速度慢，對(duì)稱密鑰技術(shù)公鑰算法加密解密速度慢，對(duì)稱密鑰技術(shù)速度比較快，所以經(jīng)常使用公鑰算法加密速度比較快，所以經(jīng)常使用公鑰算法加密少量的數(shù)據(jù)如簽名、身份驗(yàn)證信息等，而少量的數(shù)據(jù)如簽名、身份驗(yàn)證信息等，而對(duì)稱密鑰算法用來(lái)加密大批量的數(shù)據(jù)。對(duì)稱密鑰算法用來(lái)加密大批量的數(shù)據(jù)。n誤區(qū)誤區(qū):n公開密鑰密碼算法更安全（公開密鑰密碼算法更安全（error）n公開密鑰密碼使對(duì)稱密鑰密碼過(guò)時(shí)了（公開密鑰密碼使對(duì)稱密鑰密碼過(guò)時(shí)了（error）n公鑰的分發(fā)是簡(jiǎn)單和一目了然的（公鑰的分發(fā)是簡(jiǎn)單和一目了然的（error）21outlinen公鑰密碼體制的基本原理（公鑰密碼體制的基本原理（

15、Chapter9）nRSA算法的簡(jiǎn)介（算法的簡(jiǎn)介（Chapter9）n消息認(rèn)證和消息認(rèn)證和hash函數(shù)簡(jiǎn)介（函數(shù)簡(jiǎn)介（Chapter11）n消息認(rèn)證消息認(rèn)證nHash函數(shù)函數(shù)22基本的概念基本的概念n消息認(rèn)證（消息認(rèn)證（Message Authentication)：是一個(gè)證實(shí)收到的消息來(lái)自可信的源點(diǎn)且是一個(gè)證實(shí)收到的消息來(lái)自可信的源點(diǎn)且未被篡改的過(guò)程。未被篡改的過(guò)程。n 散列函數(shù)（散列函數(shù)（ Hash Functions)：一個(gè)散列一個(gè)散列函數(shù)以一個(gè)變長(zhǎng)的報(bào)文作為輸入，并產(chǎn)生函數(shù)以一個(gè)變長(zhǎng)的報(bào)文作為輸入，并產(chǎn)生一個(gè)定長(zhǎng)的散列碼，有時(shí)也稱報(bào)文摘要，一個(gè)定長(zhǎng)的散列碼，有時(shí)也稱報(bào)文摘要，作為輸出。

16、作為輸出。n數(shù)字簽名（數(shù)字簽名（Digital Signature）是一種防是一種防止源點(diǎn)或終點(diǎn)抵賴的鑒別技術(shù)。止源點(diǎn)或終點(diǎn)抵賴的鑒別技術(shù)。23消息認(rèn)證消息認(rèn)證n認(rèn)證的主要目的有兩個(gè)方面：認(rèn)證的主要目的有兩個(gè)方面：n第一，驗(yàn)證信息的發(fā)送者是真正的，而不是冒充的，此第一，驗(yàn)證信息的發(fā)送者是真正的，而不是冒充的，此為信源識(shí)別；為信源識(shí)別；n第二，驗(yàn)證信息的完整性，在傳送或存儲(chǔ)過(guò)程中未被篡第二，驗(yàn)證信息的完整性，在傳送或存儲(chǔ)過(guò)程中未被篡改，重放或延遲等。改，重放或延遲等。n認(rèn)證模型認(rèn)證模型n一個(gè)單純認(rèn)證系統(tǒng)的模型一個(gè)單純認(rèn)證系統(tǒng)的模型24消息認(rèn)證消息認(rèn)證n消息認(rèn)證系統(tǒng)組成：消息認(rèn)證系統(tǒng)組成：n首先要

17、選好恰當(dāng)?shù)氖紫纫x好恰當(dāng)?shù)恼J(rèn)證函數(shù)認(rèn)證函數(shù)，該函數(shù)產(chǎn)生一個(gè)鑒別標(biāo)識(shí)，該函數(shù)產(chǎn)生一個(gè)鑒別標(biāo)識(shí)，然后在此基礎(chǔ)上，給出合理的認(rèn)證協(xié)議然后在此基礎(chǔ)上，給出合理的認(rèn)證協(xié)議(Authentication Protocol)，使接收者完成消息的鑒別。，使接收者完成消息的鑒別。n認(rèn)證函數(shù)：認(rèn)證函數(shù)：可用來(lái)做認(rèn)證的函數(shù)分為三類：可用來(lái)做認(rèn)證的函數(shù)分為三類：n(1) 消息加密函數(shù)消息加密函數(shù)(Message encryption)用完整信息的用完整信息的密文作為對(duì)信息的認(rèn)證。密文作為對(duì)信息的認(rèn)證。n(2) 消息認(rèn)證碼消息認(rèn)證碼MAC(Message Authentication Code)公開函數(shù)公開函數(shù)+密鑰產(chǎn)

18、生一個(gè)固定長(zhǎng)度的值作為認(rèn)證標(biāo)識(shí)密鑰產(chǎn)生一個(gè)固定長(zhǎng)度的值作為認(rèn)證標(biāo)識(shí)n(3) 散列函數(shù)散列函數(shù)(Hash Function)是一個(gè)公開的函數(shù)，它將是一個(gè)公開的函數(shù)，它將任意長(zhǎng)的信息映射成一個(gè)固定長(zhǎng)度的信息。任意長(zhǎng)的信息映射成一個(gè)固定長(zhǎng)度的信息。25Message Authentication Coden使用一個(gè)雙方共享的秘密密鑰生成一個(gè)固定大小的使用一個(gè)雙方共享的秘密密鑰生成一個(gè)固定大小的小數(shù)據(jù)塊，并加入到消息中，稱小數(shù)據(jù)塊，并加入到消息中，稱MAC，或密碼校，或密碼校驗(yàn)和驗(yàn)和(cryptographic checksum)n用戶用戶A和用戶和用戶B，共享密鑰，共享密鑰K，對(duì)于，對(duì)于消息消息M，

19、 MAC=CK(M)n如果接收方計(jì)算的如果接收方計(jì)算的MAC與收到的與收到的MAC匹配，則匹配，則n接收者可以確信消息接收者可以確信消息M未被改變未被改變n接收者可以確信消息來(lái)自所聲稱的發(fā)送者接收者可以確信消息來(lái)自所聲稱的發(fā)送者n如果消息中含有序列號(hào)，則可以保證正確的消息順序如果消息中含有序列號(hào)，則可以保證正確的消息順序nMAC函數(shù)類似于加密函數(shù)，但不需要可逆性。因函數(shù)類似于加密函數(shù)，但不需要可逆性。因此在數(shù)學(xué)上比加密算法被攻擊的弱點(diǎn)要少此在數(shù)學(xué)上比加密算法被攻擊的弱點(diǎn)要少26MAC的基本用法的基本用法(a，b)nAB: M | CK(M)提供認(rèn)證但不能提供保密性提供認(rèn)證但不能提供保密性nAB

20、: EK2 M | CK1(M) 提供認(rèn)證和保密性，提供認(rèn)證和保密性，加密算法在加密算法在MAC之后之后27MAC的基本用法的基本用法(c)nAB: EK2 M | CK1(EK2 M)n提供認(rèn)證和保密性，加密算法在提供認(rèn)證和保密性，加密算法在MAC之前之前28討論：討論：n對(duì)稱加密可以提供認(rèn)證為什么還要使用分離對(duì)稱加密可以提供認(rèn)證為什么還要使用分離的消息認(rèn)證？的消息認(rèn)證？n后者適用于將同一消息廣播給很多接受者。后者適用于將同一消息廣播給很多接受者。n消息通信過(guò)程中，接受方負(fù)荷很大，沒有時(shí)間消息通信過(guò)程中，接受方負(fù)荷很大，沒有時(shí)間解密收到的消息，可以隨機(jī)的選擇性的對(duì)消息解密收到的消息，可以隨機(jī)

21、的選擇性的對(duì)消息認(rèn)證。認(rèn)證。n對(duì)明文形式的計(jì)算機(jī)程序進(jìn)行認(rèn)證是一種很有對(duì)明文形式的計(jì)算機(jī)程序進(jìn)行認(rèn)證是一種很有意義的服務(wù)。有些應(yīng)用關(guān)心的是消息的認(rèn)證而意義的服務(wù)。有些應(yīng)用關(guān)心的是消息的認(rèn)證而不是保密性。不是保密性。n認(rèn)證和保密性分離開，可使層次結(jié)構(gòu)更加靈活。認(rèn)證和保密性分離開，可使層次結(jié)構(gòu)更加靈活。n可以延長(zhǎng)對(duì)消息的保護(hù)時(shí)間?？梢匝娱L(zhǎng)對(duì)消息的保護(hù)時(shí)間。29Hash FunctionnMAC需要對(duì)全部數(shù)據(jù)進(jìn)行加密需要對(duì)全部數(shù)據(jù)進(jìn)行加密nMAC速度慢速度慢nHash是一種直接產(chǎn)生認(rèn)證碼的方法是一種直接產(chǎn)生認(rèn)證碼的方法nHash函數(shù)函數(shù): h=H(x), 要求要求:n可作用于任何尺寸數(shù)據(jù)且均產(chǎn)生定長(zhǎng)

22、輸出可作用于任何尺寸數(shù)據(jù)且均產(chǎn)生定長(zhǎng)輸出nH(x)能夠快速計(jì)算能夠快速計(jì)算n單向性單向性: 給定給定h，找到，找到x使使h=H(x)在計(jì)算上不可行在計(jì)算上不可行nWeak Collision Resistance (WCR):給定給定x，找到，找到y(tǒng) x使使H(x)=H(y)在在計(jì)算上不可行計(jì)算上不可行nStrong Collision Resistance (SCR): 找到找到y(tǒng) x使使H(x)=H(y)在在計(jì)算上不可行計(jì)算上不可行30散列函數(shù)的基本用法（散列函數(shù)的基本用法（a、b)31散列函數(shù)的基本用法（散列函數(shù)的基本用法（c)n用公鑰密碼中發(fā)送方的私鑰僅對(duì)用公鑰密碼中發(fā)送方的私鑰僅對(duì)Hash碼加密：可碼加密：可認(rèn)證，并提供數(shù)字簽名功能認(rèn)證，并提供數(shù)字簽名功能32散列函數(shù)的基本用法（散列函數(shù)的基本用法（d)n保密加簽名：發(fā)送方的私鑰對(duì)保密加簽名：發(fā)送方的私鑰對(duì)Hash碼加密（簽碼加密（簽名），再用對(duì)稱密碼中的密鑰對(duì)整體加密（保密性）名），再用對(duì)稱密碼中的密鑰對(duì)整體加密（保密性）33