【文章內(nèi)容簡介】 計算模 n ＝ pq ? 找 ed≡1 mod (p1)(q1) – 選取數(shù) e，用擴展 Euclid算法求數(shù) d ? 公布公鑰 (e, n)，保密私鑰 (d, n) ? 加密明文分組 m(被視為整數(shù)須小于 n) c=me mod n ? 解密 m=cd mod n RSA加密解密計算實例 ? 選 p＝ 7， q＝ 17 則 n＝ pq＝ 119 且 φ(n)＝ (p1)(q1)＝ 616＝ 96 ? 取 e＝ 5 則 d＝ 77 (5 77＝ 385＝ 4 96＋ 1≡1 mod 96) ? 公鑰（ 5， 119），私鑰（ 77， 119） ? 加密 m＝ 19 則 c＝ me mod n= 195 mod 119 = 66 mod 119 ? 解密 c＝ 66 m＝ cd mod n = 6677mod 119＝ 19 mod 119 關(guān)于大數(shù)的模冪乘： X^Y mod Z ? 關(guān)于提速與芯片 ? 計算 a8 % m 8次累乘： a a a a a a a a % m 3次平方： ((a2)2)2 % m 進一步： ((a2%m)2%m)2%m ? 再比如 a47 % m a47 ＝ a32+8+4+2+1% m ＝ a32a8a4a2a1% m ＝ … RSA的安全性 ? 分解整數(shù)： 一般數(shù)域篩法 For an ordinary puter, the general number field sieve (GNFS) is the best published algorithm for large n (more than about 100 digits). For a bbit number n, its running time is: PKCS1, RFC ? ? PKCS系列標準 ? PKCS1，關(guān)于 RSA算法的工業(yè)規(guī)范 – 密鑰產(chǎn)生、消息編碼 – 加密 /解密 – 簽名 /驗證 ? 其他 PKCS ? RFC 2313 PKCS 1: RSA Encryption Version ? RFC 2437 PKCS 1: RSA Cryptography Specifications Version ? RFC 3447 PKCS 1: RSA Cryptography Specifications Version 其他公鑰加密算法 ? 兩個密碼算法依賴的數(shù)學難解問題 – 大數(shù)分解問題：分解 n=pq – 離散對數(shù)問題：求解 y=g^x mod p中的 x ? DSA、 ECDSA: FIPS PUB 1863: Digital Signature Standard 其他公鑰加密算法 ? 新方向：橢圓曲線密碼算法 (ECC) – 以橢圓曲線上點的加法運算為背景的離散對數(shù)問題 – 在達到相同安全強度的前提下， ECC速度快很多 混合密碼體制：使用公鑰傳遞會話密鑰 ? 公鑰算法太慢 – 典型情況，對稱算法比公鑰算法快 1000倍 ? 只用來傳遞會話密鑰 ? (假設(shè) A已經(jīng)有 B的公鑰 KeB) – A發(fā)起和 B的通信 – A產(chǎn)生會話密鑰 Ks，并用 KeB加密后傳給 B – B能用自己的私鑰 KdB解開 ? 其他人不會知道 Ks – 使用 Ks和對稱算法處理批量數(shù)據(jù) 混合密碼體制應用實例 ? PKCS5 PasswordBased Cryptography Standard ? SSL/TLS ? PGP 消息認證 why？ （此前一直討論加密） ? 消息加密后可以抵抗竊聽。因為沒有密鑰，攻擊者無法讀懂密文。 ? 但是密文仍可以被惡意篡改，而且接收方解密后未必一定能發(fā)現(xiàn)這種攻擊。 ? 問題：對密文的篡改，能否一定被察覺？ 密文不能提供完整性保護 ? 兩個例子 （ 1）解密后能發(fā)現(xiàn)異常 （ 2）解密后不能發(fā)現(xiàn)異常 消息認證 身份認證 ? 認證和加密是兩種不同的技術(shù) (服務 )，有的場合 – 需要不加密 – 需要保護完整性 ? 認證技術(shù)涉及消息認證和身份認證兩個方面 – 消息認證：鑒別消息來源，保護消息的完整性 – 身份認證：提供身份真實性鑒別服務 消息認證碼 MAC ? 認證碼 (Message Authentication Code) – 離線：表明消息是完整的（未被篡改） – 在線：表明自己 /對方是真實的（未被假冒） ? 生成 MAC也需要密鑰，有兩個思路產(chǎn)生 – 基于加密的方法，比如 CBD模式最后一個密文分組（ FIPS113） – 基于 Hash函數(shù)的方法（ HMAC） CBCMAC： CBC模式最后一個分組 ? 把消息明文和 CN一起傳送，以表明消息的真實性 – FIPS PUB 113 HMAC ? 從概念上講， HMAC可以這樣理解 HMAC = Hash（ M || Key） – 引出 Hash函數(shù) ? 相關(guān)的標準： HMAC， RFC2104 Hash函數(shù) ? 輸入任意長度 (或 2^64)報文 ? 輸出固定長度 n=128/160/224/256/384/512bits ? 函數(shù)特性 – 單向性質(zhì) 對給定的 h，找 x滿足 H(x)＝ h是困難的 – 弱抗碰撞特性 對于給定的 y，找 x滿足 H(x)＝ H(y)是困難的 – 強抗碰撞特性（生日攻擊） 找 x和 y滿足 H(x)＝ H(y)是困難的 常用的 Hash函數(shù) ? MD5 – 輸出 128bits ? SHA0， FIPS PUB 180 ? SHA1， FIPS PUB 1801 – 輸出 160bits ? SHA2 – 輸出 192/224/256/384/512bits MD5 Overview ? RFC 1321 MD5 ? MD5 crack ? 2023年的國際密碼討論年會（ CRYPTO）尾聲，王小云及其研究同工展示了 MD SHA0及其他相關(guān)雜湊函數(shù)的雜湊沖撞。所謂雜湊沖撞指兩個完全不同的訊息經(jīng)雜湊函數(shù)計算得出完全相同的雜湊值。根據(jù)鴿巢原理，以有長度限制的雜湊函數(shù)計算沒有長度限制的訊息是必然會有沖撞情況出現(xiàn)的。可是，一直以來，電腦保安專家都認為要任意制造出沖撞需時太長，在實際情況上不可能發(fā)生，而王小云等的發(fā)現(xiàn)可能會打破這個必然性。 ? 2023年 2月，王小云與其同事提出 SHA1雜湊函數(shù)的雜湊沖撞。由于 SHA1雜湊函數(shù)被廣泛應用于現(xiàn)今的主流電腦保安產(chǎn)品，其影響可想而知。王小云所提的雜湊沖撞算法只需少于 269步驟，少于生日攻擊法（ Birthday Attack）所需的 280步。同年 8月，王小云、姚期智，以及姚期智妻子姚儲楓聯(lián)手于國際密碼討論年會提出SHA1雜湊函數(shù)雜湊沖撞算法的改良版。此改良版使破解 SHA1時間縮短為 263步。 [1] Collisions in the MD5 M D 5 沖突的兩個有意義的文件 . z ipHMAC ? HMAC(K,M) = H[(K+⊕ opad) || H[(K+⊕ ipad) || M]] 身份認證：使用公鑰算法 ? 如果你已經(jīng)有他的公鑰 Ke，則可鑒別他的身份 ? 取隨機秘密消息 P加密 C = E（ P， Ke） ? 把密文 C交給所謂的 ”他 ”，請他來解密 – 除非 ”他 ”擁有 K