Bài giảng Phân tích và Thiết kế giải thuật nâng cao: Chương 6 - PGS.TS. Trần Cao Đệ

Bài giảng Phân tích và Thiết kế giải thuật nâng cao: Chương 6 trình bày các kiến thức về mã hóa như phân biệt mã hóa đối xứng và mã hóa bất đối xứng, giới thiệu về hàm một chiều trong mã hóa bất đối xứng, mã hóa SRA.
Nội dung trích xuất từ tài liệu:
Bài giảng Phân tích và Thiết kế giải thuật nâng cao: Chương 6 - PGS.TS. Trần Cao Đệ Chương 6 Mã hóa Cryptography Copyright©TheMcGrawHillCompanies,Inc.Permissionrequiredforreproductionordisplay.10.1 Chapter 10 Objectives Phânbiệtmãhóađốixứngvàmãhóabấtđối xứng Giớithiệuvềhàmmộtchiềutrongmãhóabất đốixứng MãhóaRSA10.2 10-1 INTRODUCTION Mã hóa đối xứng và mã hóa bất đối xứng là hai cáchtiếpcậncùngtồntạisongsongtronglĩnhvực mãhóa •Mãhóađốixứng:cùngchiasẻbímật vídụmậtmãCaesark=3 ABCDEF…Z DEFGHI…C •Mãhóabấtđốixứng:bímậtcánhân •Mãhóa:khóacôngkhai •Giảimã:khóabímật10.3 10.1.1Keys Mãhóabấtđốixứngdùnghaikhóa: •Mộtkhóacôngkhai(publickey) •Mộtkhóabímật(privatekey) Figure10.1khóavàmởkhóatronghệmãbấtđốixứng10.4 10.1.2GeneralIdea Figure10.2ýtưởngchínhcủahệmãbấtđốixứng10.5 10.1.2Continued Bảnrõvàbảnmã(Plaintext/Ciphertext) Bảnrõ(P)làbảnchưamãhóa Bảnmã(C)làbảnđãmãhóa Mãhóavàgiảimã(Encryption/Decryption)tronghệmã bấtđốixứngdùnghaihàmvàhaikhóariêngbiệt C=f(Kpublic,P)P=g(Kprivate,C)10.6 10.1.4TrapdoorOneWayFunction Hệ mã bất đối xứng dùng hàm bẫy một chiều (trapdooronewayfunction). Hàm Figure10.3hàmlàmộtquitắcánhxạmộtmiềnxácđịnh vàomộtmiềngiátrị10.7 10.1.4Continued Hàmmộtchiều(OneWayFunction(OWF)) 1.fdễdàngtínhđược. 2. f −1 tính cực kỳ khó (không thể tính được). Hàm bẫy một chiều (Trapdoor OneWay Function (TOWF)) 3.Choyvàmộtcáibẫythìxtính đượcdễdàng10.8 10.1.4Continued Vídụ10.1 Khi n đủ lớn, n = p × q là hàm một chiều. Cho p và q , tính n dễ dàng; Cho n, rất khó để tính được p và q. Vídụ10.2 Khi n đủ lớn, y = xk mod n là một hàm bẫy 1 chiều. Cho x, k và n, dễ dàng tính y. Cho y, k và n, rất khó tính x. Tuy nhiên nếu biết cái bẫy k′ sao cho k × k ′ = 1 mod (n) Ta tính được x dễ dàng x = yk′ mod n.10.9 10-2 RSA CRYPTOSYSTEM HệmãRSA RSA lấy tên của những người phát minh (Rivest, Shamir,andAdleman). Topicsdiscussedinthissection: 10.2.1 Introduction 10.2.2 Procedure 10.2.3 SomeTrivialExamples 10.2.4 AttacksonRSA 10.2.5 Recommendations 10.2.6 OptimalAsymmetricEncryptionPadding(OAEP) 10.2.7 Applications10.10 10.2.1Giớithiệu Figure10.5độphứctạptrongthuậttoánRSA10.11 10.2.2Quitrình Figure10.6mãhóa,giảimãvàsinhkhóatrongRSA10.12 10.2.2SinhkhóaRSA10.13 10.2.2Continued Mãhóa(Encryption)10.14 10.2.2Continued Giảimã(Decryption)10.15 10.2.2Continued ProofofRSA10.16 10.2.3vídụđơngiản Vídụ10.5 Bob chọn p=7 và q=11, tính được n = pxq = 77. Tính (n) = (7 − 1)(11 − 1) = 60. Bob chọn e và d trong Z60∗ sao cho ed = 1 mod 60. (ví dụ e = 13, d = 37) Bob công bố khóa công khai (13,77) giữ bí mật d = 37 Alice muốn gởi P= 5 tới Bob. Cô ta dùng e=13 để mã hóa 5. Bob nhận C=26 từ Alice Bob dùng d = 37 để giải mã: http://www.strangeattractor.ca/RSAdemo.html10.17 10.2.3vídụđơngiản(tt) Vídụ10.6 Giả sử John muốn gởi nội dung P=63 cho Bob. John dùng khóa công khai của Bob đã công bố (13,77) Bob nhận được C = 28 và dùng khóa bí mật d = 37 để giải mã:10.18 10.2.3vídụcáchápdụng Example10.7 Jennifer chọn p = 397 và q = 401. Cô ta tính được n = 159197 và (n) = 158400 Cô ta chọn e = 343 và tính d = 12007. Jennifer công bố (343,159197) là khóa công khai Giữ bí mật d=12007 Ted muốn gởi thông báo “NO” cho Jennifer. Anh ta đổi kí tự ra số Ví dụ ABC..Z đổi thành số 0…25  NO=1314. Vậy xem như là số P=131410.19 10.2.3Continued Figure10.7mãhóavàgiảimãtrongvídụ10.20 ...