公匙加密技術(shù)和認證

1、2022-3-261加密技術(shù)簡介加密技術(shù)簡介 公匙加密技術(shù)和認證公匙加密技術(shù)和認證2022-3-262公匙加密技術(shù)和認證公匙加密技術(shù)和認證數(shù)據(jù)的完整性和信息認證的要求哈希函數(shù)和信息認證碼（MAC）公開密鑰原理公開密鑰算法信息的認證 數(shù)字簽名 密鑰管理2022-3-263數(shù)據(jù)的完整性和信息認證的要求IntegritySoftware manufacturer wants to ensure that the executable file is received by users without modification.Encryption protects against passive a

2、ttack (eavesdropping).A different requirement is to protect against active attack (falsification of data and transactions).The goal is integrity, not secrecyMessage authentication is a procedure that allows communication parties to verify that the content of of the message has not been altered, and

3、is came from its alleged source.2022-3-264Integrity vs. SecrecyIntegrity: attacker cannot modify or tamper with messageEncryption per se does not guarantee integritylIntuition: attacker may able to modify message under encryption without learning what it islThis is recognized by industry standards (

4、e.g., PKCS)l“RSA encryption is intended primarily to provide confidentiality It is not intended to provide integrity” (from RSA Labs Bulletin)lSome encryption schemes provide secrecy AND integrity2022-3-265信息認證的要求must be able to verify that:1. （可鑒別性）Message came from apparent source or author,2. （完整

5、性）Contents have not been altered,3. （時效性）Sometimes, it was sent at a certain time or sequence.4. （不可抵賴性） Proof that communication or transaction took placeProtection against active attack (falsification of data and transactions)2022-3-266信息認證的方法Authentication Using Conventional EncryptionMessage Aut

6、hentication without Message Encryption. An authentication tag is generated and appended to each messagelMessage Authentication CodelOne-Way hash function(單向哈希函數(shù)單向哈希函數(shù)/散散列函數(shù)列函數(shù))2022-3-267信息認證的方法- Authentication Using Conventional EncryptionAuthentication Using Conventional EncryptionlOnly the sender

7、and receiver should share a key（可鑒別性）lIf the message includes an error-detection code and a sequence number, the receiver is assured that no alterations have been made and the sequencing is proper.（完整性）lAdded a timestamp can also indicates that the message has not been delayed beyond that normally e

8、xpected for network transit. （完整性）2022-3-268信息認證的方法- Authentication Without Encryption某些場合只需要認證不需要加密，例如l加密的代價太高l對于可執(zhí)行程序，認證比加密更現(xiàn)實，因為不加密的程序可以執(zhí)行，加密后不能夠執(zhí)行加密和認證有不同的算法來執(zhí)行更有優(yōu)勢。用加密來保證信息的保密性，用單獨的認證手段來保證信息的完整性這類認證方法一般采用生成一個信息摘要的方法，然后把它和原來的信息以啟發(fā)送出去。接受端利用這個信息摘要來驗證信息的完整性。兩種方式：MAC和單向哈希函數(shù)2022-3-269信息認證的方法- MACTwo

9、party A and B shared a secret key to be used to generate Message Authentication Code (MAC)When A sends a message to B, it calculates the MAC as a function of the message and the key. MAC = F(K, M).2022-3-2610信息認證的方法- MAC 2022-3-2611信息認證的方法- MACWhen B received the message, it apply the same calculati

10、on on the message and key, and generate its own MAC.B compares its MAC with the MAC received form A, if the code calculated matches the received code.2022-3-2612信息認證的方法- MACMAC達到的效果：lmessage has not been altered, because the attacker is assumed not to know the secret keylthe message is from A, becau

11、se only A knows the keylthe message is in the proper sequence (If the message includes a sequence number), because an attacker cannot successfully alter the sequence number.2022-3-2613信息認證的方法- One-Way Hash FunctionUsed to provide integrity of a messagePurpose is to produce a fixed-size hash-value:wh

12、ere h is the hash valueH is the hash functionM is the messageAny change in M, however small, should produce a different h-valueh = H(M)2022-3-2614信息認證的方法- One-Way Hash Function Hash Value (fixed-size; e.g. 160 bits)HhMMessage(any size)Hash Function2022-3-2615信息認證的方法- One-Way Hash Function Message ca

13、n be of any size One-Way Hash Function H(M) produces a fixed-length output (e.g. 160 bits) H(M) easy to compute for any message M One-way property:lGiven h, computationally infeasible to find M such that H(M) = h2022-3-2616Secure HASH Functions M can be of any size (i.e. arbitrary msg) H(M) produces

14、 a fixed-length (e.g. 160 bits) message digest (信息摘要) H(M) easy to compute for any message M2022-3-2617Secure HASH Functions單向性lGiven h, computationally infeasible to find M such that H(M) = h唯一性lFor any given block x, it is computationally infeasible to find with H(y) = H(x).lIt is computationally

15、infeasible to find any pair (x, y) such that H(x) = H(y)2022-3-2618Common Hash FunctionsMD5l128-bit outputlDesigned by Ron Rivest, used very widelylCollision-resistance broken (summer of 2004)RIPEMD-160l160-bit variant of MD-5SHA-1 (Secure Hash Algorithm)l160-bit outputlUS government (NIST) standard

16、 as of 1993-95lAlso the hash algorithm for Digital Signature Standard (DSS)2022-3-2619How Strong Is SHA-1?Every bit of output depends on every bit of inputlVery important property for collision-resistanceBrute-force inversion requires 2160 ops, birthday attack on collision resistance requires 280 op

17、sSome very recent potential weaknesseslCollisions in SHA-0 and 36-step SHA-1 announced at CRYPTO 2004lActual SHA-1 uses 80 steps2022-3-2620HMACConstruct MAC by applying a cryptographic hash function such as SHA-1. lCryptographic hash functions executes faster in software than encryptoin algorithms s

18、uch as DESlLibrary code for hash functions widely availablelCan easily replace one hash function with anotherlNo export restrictions from the USInvented by Bellare, Canetti, and Krawczyk (1996)lHMAC strength established by cryptographic analysisMandatory for IP security, also used in SSL/TLS2022-3-2

19、621對稱加密算法對稱加密算法信息認證的的局限性的局限性對稱加密算法的局限性對稱加密算法的局限性:lKey Distribution ProblemlHow do we reach a point where both parties have the same key (chicken-and-egg situation)?lNot suitable for authentication: receiver can forge message & claim it came from sender由公開密鑰算法來完成由公開密鑰算法來完成lAlso known as Asymmetric En

20、cryption公開密鑰算法給予發(fā)送端和接受端持有不同密公開密鑰算法給予發(fā)送端和接受端持有不同密鑰鑰2022-3-2622公開密鑰原理公開密鑰算法有六要素:lPlaintextlEncryption algorithmlPublic key lprivate keylCiphertextlDecryption algorithm2022-3-2623公開密鑰加密算法被認為是被認為是3000年加密歷史上的最重要的一步年加密歷史上的最重要的一步 每一方都有兩個密鑰每一方都有兩個密鑰:l一個可能為每一個人都知道的公有密鑰用來對信息加密一個可能為每一個人都知道的公有密鑰用來對信息加密和驗證數(shù)字簽名和驗

21、證數(shù)字簽名l一個只有自己知道的私有密鑰用來對信息解密和創(chuàng)建數(shù)一個只有自己知道的私有密鑰用來對信息解密和創(chuàng)建數(shù)字簽名字簽名是數(shù)論的一個非常聰明的應用是數(shù)論的一個非常聰明的應用是對于對稱加密算法的補充，而不是取代它是對于對稱加密算法的補充，而不是取代它2022-3-2624公開密鑰加密系統(tǒng)的應用三種應用領(lǐng)域三種應用領(lǐng)域:lEncryption/decryption: lAnyone can encrypt a messagelWith symmetric crypto, must know secret key to encryptlOnly someone who knows private k

22、ey can decryptlKey management is simpler (maybe)lSecret is stored only at one site: good for open environmentslDigital signature: lCan “sign” a message with your private key.lKey echange: lExchange messages to create a secret session keylThen switch to symmetric cryptography (why?)有些公開密鑰算法可以用于所有的領(lǐng)域，

23、有些只能用于其中的一個領(lǐng)域2022-3-2625用公開密鑰加密2022-3-2626用公開密鑰加密Bob sends message to Alice by encrypting with her (Alices) public keyMessage can only be decrypted with Alices corresponding private key (known only to her)多個人向一個人送信息，只有接受者可以打開這一信息（保密性，接受端的可選擇性）2022-3-2627用公開密鑰加密2022-3-2628用公開密鑰加密Bob sends message to

24、Alice encrypting it with his own private key (i.e. he signs the message)Everyone with Bobs public key can decrypt the message. A message that can be decrypted with Bobs public key must have come from Bob.一個人可以向多個人送信息，可以證明信息確是來自這位發(fā)送信息的人（保密性、發(fā)送端的可鑒別性和不可拒絕性）（數(shù)字簽名）2022-3-2629對公開密鑰加密算法的要求方便性Computational

25、ly easy for a party B to generate a pair (public key KUb, private key KRb)Easy for sender to generate ciphertextEasy for the receiver to decrypt ciphertect using private key)()(MEDCDMKUbKRbKRb)(MECKUb2022-3-2630對公開密鑰加密算法的要求安全性Computationally infeasible to determine private key (KRb) knowing public k

26、ey (KUb)Computationally infeasible to recover message M, knowing KUb and ciphertext （單向性）（單向性）2022-3-2631對公開密鑰加密算法的要求可交換性Either of the two keys can be used for encryption, with the other used for decryption:)()(MEDMEDMKRbKUbKUbKRb2022-3-2632公開密鑰加密算法RSA and Diffie-Hellman RSA - Ron Rives, Adi Shamir

27、and Len Adleman at MIT, in 1977.l用于密鑰交換/數(shù)字簽名和SSLlRSA 是一種數(shù)據(jù)塊加密算法l是一種使用最廣泛的公開密鑰加密算法Diffie-Hellman l用于密鑰交換（也叫密鑰交換協(xié)議）2022-3-2633RSA公開密碼系統(tǒng)的原理將兩個大素數(shù)相乘非常容易，但是將他們的乘積分解成原來的大素數(shù)是非常困難的。 （單向性）如果這一乘積足夠大，那么要從乘積找到兩個大素數(shù)是計算上不現(xiàn)實的。因此可以將乘積公開出去作為加密的密鑰。2022-3-2634RSA公開密碼系統(tǒng)的原理Key generation:lGenerate large primes p, qlSay,

28、 1024 bits each lCompute n=pq and (n)=(p-1)(q-1)lChoose small e, relatively prime to (n)lTypically, e=3 (may be vulnerable) or e=216+1=65537 lCompute unique d such that ed = 1 mod (n)lPublic key = (e,n); private key = d2022-3-2635RSA加密算法Plaintext:MnCiphertext:C = M (mod n)e2022-3-2636RSA解密算法Plaintex

29、t:CCiphertext:M = C (mod n)d2022-3-2637RSA公開密碼系統(tǒng)的安全性RSA公開密碼系統(tǒng)的安全性隨著密鑰的長度的增加而增強加密解密的運算量太大，無論硬件或軟件實現(xiàn)均比對稱加密算法慢得多，因此只適用于少量數(shù)據(jù)的加密和解密。一般用RSA交換密鑰，然后用對稱算法對數(shù)據(jù)加密。存在著利用非分解因子的方法破譯RSA的可能性；但是自1977年提出這一算法以來，還沒有一種方法可以破解RSA2022-3-2638RSA公開密碼系統(tǒng)的局限性產(chǎn)生密鑰很麻煩加密解密的運算量太大，無論硬件或軟件實現(xiàn)均比對稱加密算法慢得多，因此只適用于少量數(shù)據(jù)的加密和解密。一般用RSA交換密鑰，然后用對

30、稱算法對數(shù)據(jù)加密。單獨使用RSA不能夠保證數(shù)據(jù)的完整性，必須與哈希函數(shù)結(jié)合才一起才能夠保證數(shù)據(jù)的完整性。RSA有專利保護2022-3-2639Diffie-HellmanDiffie-Hellman密碼交換算法的原理大素數(shù)模的指數(shù)運算比較容易，但是大素數(shù)模的離散對數(shù)運算是非常困難的。 （單向性）大素數(shù)模的離散對數(shù)運算與大素數(shù)的因子分解的難度相當Diffie-Hellman算法主要用于算法主要用于用于密鑰交換（也叫密鑰交換協(xié)議）2022-3-2640其他公開密鑰加密算法Digital Signature Standard (DSS)lMakes use of the SHA-1lNot for

31、encryption or key echangelLow confidence level, compared with RSAElliptic-Curve Cryptography (ECC)lGood for smaller bit sizelLow confidence level, compared with RSAlVery complex2022-3-2641Advantages of Public-Key CryptoConfidentiality without shared secretslVery useful in open environmentslNo “chick

32、en-and-egg” key establishment problemlWith symmetric crypto, two parties must share a secret before they can exchange secret messagesAuthentication without shared secretslUse digital signatures to prove the origin of messagesReduce protection of information to protection of authenticity of public ke

33、yslNo need to keep public keys secret, but must be sure that Alices public key is really her true public key2022-3-2642Disadvantages of Public-Key CryptoCalculations are 2-3 orders of magnitude slowerlModular exponentiation is an expensive computationlTypical usage: use public-key cryptography to es

34、tablish a shared secret, then switch to symmetric cryptolWell see this in IPSec and SSLKeys are longerl1024 bits (RSA) rather than 128 bits (AES)Relies on unproven number-theoretic assumptionslWhat if factoring is easy?lFactoring is believed to be neither P, nor NP-complete2022-3-2643公用密鑰加密算法的應用數(shù)字簽名

35、（ Digital Signatures ）數(shù)字證書（ Digital Certificates ）密鑰的管理和分發(fā)（Key Management and Key Distribution）2022-3-2644Digital SignaturesWith public key cryptography, a message can be encrypted with the senders private key.lIn this case, the entire message serves as a digital signaturelDisadvantages: speed & sto

36、rage requirementsAlternative:lAdd a small authentication block to the messagele.g. take the hash of the message and encrypt just the hash with the senders private keylThe result is a much more compact signature2022-3-2645Typical Use of Hash Function with Dig. Sig. Just sign the hash lmuch more effic

37、ient than signing full messageKRa: Senders Private KeyKUa: Senders Public Key這個符號表示將兩個信息拼在一起 2022-3-2646(Public) Key ManagementQ. How can you be sure of authenticity of origin of a received public key?A. In the following situations:lIf the received public key is digitally signed by someone whose own

38、 public key you have and are sure is correct.lUsually also required that the public key has been signed fairly recently2022-3-2647Digital Certificates在使用公用密鑰加密系統(tǒng)時，一個重要的問題是保證你的獲得的密鑰確實是來自信息接受方，而不是一個偽造的密鑰。這在 你與你認識的人之間進行親手交接密鑰時是沒有問題的但是假如你需要和一個你沒有見過的人交換密鑰，怎樣才能保證你得到的是一個正確的密鑰呢？2022-3-2648Digital Certificates數(shù)字證書可以為用戶提供認證，以便通訊（或交易）的雙方可以 互相確認身份和密碼數(shù)字證書是由所有用戶信任的第三方，證書權(quán)威機構(gòu)Certificate Authority (CA)，使用它的私有密鑰簽發(fā)的通常符合X.509標準 CA的公開密鑰可能得到另一個更高層的CA的認證2022-3-2649Digital Certificates用戶產(chǎn)生自己的密鑰對，然后把公用密鑰和自己的其他識別信息提交給CA。當CA對用戶審查合格后，就將用戶的公用密鑰制成信息摘要，然后用CA自己的私