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 Đệ

Chia sẻ: Lê Kim Luông | Ngày: | Loại File: PPT | Số trang:25

Thêm vào BST

Báo xấu

96
lượt xem 9
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 © The McGrawHill Companies, Inc. Permission required for reproduction or display. 10.1
Chapter 10 Objectives  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 RSA 10.2
10-1 INTRODUCTION Mã hóa đối xứng và mã hóa bất đối xứng là hai cách tiếp cận cùng tồn tại song song trong lĩnh vực mã hóa •Mã hóa đối xứng: cùng chia sẻ bí mật ví dụ mật mã Caesar k=3 ABCDEF…Z DEFGHI…C •Mã hóa bất đối xứng: bí mật cá nhân •Mã hóa: khóa công khai •Giải mã: khóa bí mật 10.3
10.1.1 Keys Mã hóa bất đối xứng dùng hai khóa: •Một khóa công khai (public key) •Một khóa bí mật (private key) Figure 10.1 khóa và mở khóa trong hệ mã bất đối xứng 10.4
10.1.2 General Idea Figure 10.2 ý tưởng chính của hệ mã bất đối xứng 10.5
10.1.2 Continued Bản rõ và bản mã (Plaintext/Ciphertext) Bản rõ (P) là bản chưa mã hóa Bản mã (C) là bản đã mã hóa Mã hóa và giải mã (Encryption/Decryption) trong hệ mã bất đối xứng dùng hai hàm và hai khóa riêng biệt C = f (Kpublic , P) P = g(Kprivate , C) 10.6
10.1.4 Trapdoor OneWay Function Hệ mã bất đối xứng dùng hàm bẫy một chiều (trapdoor oneway function). Hàm Figure 10.3 hàm là một qui tắc ánh xạ một miền xác định vào một miền giá trị 10.7
10.1.4 Continued Hàm một chiều (OneWay Function (OWF)) 1. f dễ dàng tí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. Cho y và một cái bẫy thì x tính được dễ dàng 10.8
10.1.4 Continued 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, and Adleman). Topics discussed in this section: 10.2.1 Introduction 10.2.2 Procedure 10.2.3 Some Trivial Examples 10.2.4 Attacks on RSA 10.2.5 Recommendations 10.2.6 Optimal Asymmetric Encryption Padding (OAEP) 10.2.7 Applications 10.10
10.2.1 Giới thiệu Figure 10.5 độ phức tạp trong thuật toán RSA 10.11
10.2.2 Qui trình Figure 10.6 mã hóa, giải mã và sinh khóa trong RSA 10.12
10.2.2 Sinh khóa RSA 10.13
10.2.2 Continued Mã hóa (Encryption) 10.14
10.2.2 Continued Giải mã (Decryption) 10.15
10.2.2 Continued Proof of RSA 10.16
10.2.3 ví dụ đơn giả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.html 10.17
10.2.3 ví dụ đơn giả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.3 ví dụ cách áp dụng Example 10. 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=1314 10.19
10.2.3 Continued Figure 10.7 mã hóa và giải mã trong ví dụ 10.20