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

1、2022-3-261加密技術(shù)簡(jiǎn)介加密技術(shù)簡(jiǎn)介 公匙加密技術(shù)和認(rèn)證公匙加密技術(shù)和認(rèn)證2022-3-262公匙加密技術(shù)和認(rèn)證公匙加密技術(shù)和認(rèn)證數(shù)據(jù)的完整性和信息認(rèn)證的要求哈希函數(shù)和信息認(rèn)證碼（MAC）公開(kāi)密鑰原理公開(kāi)密鑰算法信息的認(rèn)證 數(shù)字簽名 密鑰管理2022-3-263數(shù)據(jù)的完整性和信息認(rèn)證的要求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信息認(rèn)證的要求must be able to verify that:1. （可鑒別性）Message came from apparent source or author,2. （完整

5、性）Contents have not been altered,3. （時(shí)效性）Sometimes, it was sent at a certain time or sequence.4. （不可抵賴(lài)性） Proof that communication or transaction took placeProtection against active attack (falsification of data and transactions)2022-3-266信息認(rèn)證的方法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信息認(rèn)證的方法- 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信息認(rèn)證的方法- Authentication Without Encryption某些場(chǎng)合只需要認(rèn)證不需要加密，例如l加密的代價(jià)太高l對(duì)于可執(zhí)行程序，認(rèn)證比加密更現(xiàn)實(shí)，因?yàn)椴患用艿某绦蚩梢詧?zhí)行，加密后不能夠執(zhí)行加密和認(rèn)證有不同的算法來(lái)執(zhí)行更有優(yōu)勢(shì)。用加密來(lái)保證信息的保密性，用單獨(dú)的認(rèn)證手段來(lái)保證信息的完整性這類(lèi)認(rèn)證方法一般采用生成一個(gè)信息摘要的方法，然后把它和原來(lái)的信息以啟發(fā)送出去。接受端利用這個(gè)信息摘要來(lái)驗(yàn)證信息的完整性。兩種方式：MAC和單向哈希函數(shù)2022-3-269信息認(rèn)證的方法- 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信息認(rèn)證的方法- MAC 2022-3-2611信息認(rèn)證的方法- 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信息認(rèn)證的方法- MACMAC達(dá)到的效果：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信息認(rèn)證的方法- 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信息認(rèn)證的方法- One-Way Hash Function Hash Value (fixed-size; e.g. 160 bits)HhMMessage(any size)Hash Function2022-3-2615信息認(rèn)證的方法- 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對(duì)稱(chēng)加密算法對(duì)稱(chēng)加密算法信息認(rèn)證的的局限性的局限性對(duì)稱(chēng)加密算法的局限性對(duì)稱(chēng)加密算法的局限性: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由公開(kāi)密鑰算法來(lái)完成由公開(kāi)密鑰算法來(lái)完成lAlso known as Asymmetric En

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

21、證數(shù)字簽名l一個(gè)只有自己知道的私有密鑰用來(lái)對(duì)信息解密和創(chuàng)建數(shù)一個(gè)只有自己知道的私有密鑰用來(lái)對(duì)信息解密和創(chuàng)建數(shù)字簽名字簽名是數(shù)論的一個(gè)非常聰明的應(yīng)用是數(shù)論的一個(gè)非常聰明的應(yīng)用是對(duì)于對(duì)稱(chēng)加密算法的補(bǔ)充，而不是取代它是對(duì)于對(duì)稱(chēng)加密算法的補(bǔ)充，而不是取代它2022-3-2624公開(kāi)密鑰加密系統(tǒng)的應(yīng)用三種應(yīng)用領(lǐng)域三種應(yī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?)有些公開(kāi)密鑰算法可以用于所有的領(lǐng)域，

23、有些只能用于其中的一個(gè)領(lǐng)域2022-3-2625用公開(kāi)密鑰加密2022-3-2626用公開(kāi)密鑰加密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)多個(gè)人向一個(gè)人送信息，只有接受者可以打開(kāi)這一信息（保密性，接受端的可選擇性）2022-3-2627用公開(kāi)密鑰加密2022-3-2628用公開(kāi)密鑰加密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.一個(gè)人可以向多個(gè)人送信息，可以證明信息確是來(lái)自這位發(fā)送信息的人（保密性、發(fā)送端的可鑒別性和不可拒絕性）（數(shù)字簽名）2022-3-2629對(duì)公開(kāi)密鑰加密算法的要求方便性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對(duì)公開(kāi)密鑰加密算法的要求安全性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對(duì)公開(kāi)密鑰加密算法的要求可交換性Either of the two keys can be used for encryption, with the other used for decryption:)()(MEDMEDMKRbKUbKUbKRb2022-3-2632公開(kāi)密鑰加密算法RSA and Diffie-Hellman RSA - Ron Rives, Adi Shamir

27、and Len Adleman at MIT, in 1977.l用于密鑰交換/數(shù)字簽名和SSLlRSA 是一種數(shù)據(jù)塊加密算法l是一種使用最廣泛的公開(kāi)密鑰加密算法Diffie-Hellman l用于密鑰交換（也叫密鑰交換協(xié)議）2022-3-2633RSA公開(kāi)密碼系統(tǒng)的原理將兩個(gè)大素?cái)?shù)相乘非常容易，但是將他們的乘積分解成原來(lái)的大素?cái)?shù)是非常困難的。 （單向性）如果這一乘積足夠大，那么要從乘積找到兩個(gè)大素?cái)?shù)是計(jì)算上不現(xiàn)實(shí)的。因此可以將乘積公開(kāi)出去作為加密的密鑰。2022-3-2634RSA公開(kāi)密碼系統(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公開(kāi)密碼系統(tǒng)的安全性RSA公開(kāi)密碼系統(tǒng)的安全性隨著密鑰的長(zhǎng)度的增加而增強(qiáng)加密解密的運(yùn)算量太大，無(wú)論硬件或軟件實(shí)現(xiàn)均比對(duì)稱(chēng)加密算法慢得多，因此只適用于少量數(shù)據(jù)的加密和解密。一般用RSA交換密鑰，然后用對(duì)稱(chēng)算法對(duì)數(shù)據(jù)加密。存在著利用非分解因子的方法破譯RSA的可能性；但是自1977年提出這一算法以來(lái)，還沒(méi)有一種方法可以破解RSA2022-3-2638RSA公開(kāi)密碼系統(tǒng)的局限性產(chǎn)生密鑰很麻煩加密解密的運(yùn)算量太大，無(wú)論硬件或軟件實(shí)現(xiàn)均比對(duì)稱(chēng)加密算法慢得多，因此只適用于少量數(shù)據(jù)的加密和解密。一般用RSA交換密鑰，然后用對(duì)

30、稱(chēng)算法對(duì)數(shù)據(jù)加密。單獨(dú)使用RSA不能夠保證數(shù)據(jù)的完整性，必須與哈希函數(shù)結(jié)合才一起才能夠保證數(shù)據(jù)的完整性。RSA有專(zhuān)利保護(hù)2022-3-2639Diffie-HellmanDiffie-Hellman密碼交換算法的原理大素?cái)?shù)模的指數(shù)運(yùn)算比較容易，但是大素?cái)?shù)模的離散對(duì)數(shù)運(yùn)算是非常困難的。 （單向性）大素?cái)?shù)模的離散對(duì)數(shù)運(yùn)算與大素?cái)?shù)的因子分解的難度相當(dāng)Diffie-Hellman算法主要用于算法主要用于用于密鑰交換（也叫密鑰交換協(xié)議）2022-3-2640其他公開(kāi)密鑰加密算法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公用密鑰加密算法的應(yīng)用數(shù)字簽名

35、（ Digital Signatures ）數(shù)字證書(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這個(gè)符號(hào)表示將兩個(gè)信息拼在一起 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)時(shí)，一個(gè)重要的問(wèn)題是保證你的獲得的密鑰確實(shí)是來(lái)自信息接受方，而不是一個(gè)偽造的密鑰。這在 你與你認(rèn)識(shí)的人之間進(jìn)行親手交接密鑰時(shí)是沒(méi)有問(wèn)題的但是假如你需要和一個(gè)你沒(méi)有見(jiàn)過(guò)的人交換密鑰，怎樣才能保證你得到的是一個(gè)正確的密鑰呢？2022-3-2648Digital Certificates數(shù)字證書(shū)可以為用戶(hù)提供認(rèn)證，以便通訊（或交易）的雙方可以 互相確認(rèn)身份和密碼數(shù)字證書(shū)是由所有用戶(hù)信任的第三方，證書(shū)權(quán)威機(jī)構(gòu)Certificate Authority (CA)，使用它的私有密鑰簽發(fā)的通常符合X.509標(biāo)準(zhǔn) CA的公開(kāi)密鑰可能得到另一個(gè)更高層的CA的認(rèn)證2022-3-2649Digital Certificates用戶(hù)產(chǎn)生自己的密鑰對(duì)，然后把公用密鑰和自己的其他識(shí)別信息提交給CA。當(dāng)CA對(duì)用戶(hù)審查合格后，就將用戶(hù)的公用密鑰制成信息摘要，然后用CA自己的私