Bài giảng An toàn dữ liệu và mật mã: Chương 5 - Trường ĐH Nguyễn Tất Thành

Bài giảng An toàn dữ liệu và mật mã: Chương 5 Các giải thuật mã hóa khóa bất đối xứng, được biên soạn gồm các nội dung chính sau: Tổng quan; Lý thuyết nền tản hệ mật mã công khai; Các giải thuật mã hóa khóa bất đối xứng; RSA. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng An toàn dữ liệu và mật mã: Chương 5 - Trường ĐH Nguyễn Tất Thành TRƯỜNG ĐẠI HỌC NGUYỄN TẤT THÀNH KHOA CÔNG NGHỆ THÔNG TIN AN TOÀN DỮ LIỆU VÀ MẬT MÃ Data security and encryption Giảng Viên: ThS. Dương Minh Tuấn Email: dmtuan@ntt.edu.vn 1 Chương V. Các giải thuật mã hóa KHÓA BẤT ĐỐI XỨNG 1. Tổng quan 2. Lý thuyết nền tản hệ mật mã công khai 3. Các giải thuật mã hóa khóa bất đối xứng 4. RSA 2 1. Tổng quan ▪ Hệ mật mã khóa đối xứng không đáp ứng được 2 mục tiêu an toàn • Xác thực - Alice và Bob trao đổi thông tin bí mật - Alice cần phải biết thông tin chắc chắn đến từ Bob, và ngược lại • Chống phủ nhận - Alice và Bob trao đổi thông tin bí mật - Nếu Alice đã gửi thông tin nào đó cho Bob thì Alice không thể chối bỏ thông tin đó là của mình ▪ Quản lý khóa đối xứng là một vấn đề nan giải • Trong các hệ khóa đối xứng, mỗi cặp người dùng phải có khóa riêng • N người dùng cần N * (N-1)/2 khóa • Việc quản lý khóa trở nên phức tạp khi số lượng người dùng tăng 3 1. Tổng quan Khái niệm ▪ Mỗi người dùng có 1 khóa riêng và 1 khóa công khai • Khóa riêng bí mật • Khóa công khai có thể chia sẻ ▪ Quản lý khóa • N người dùng cần N khóa công khai được xác thực • Hạ tầng khóa công khai PKI 4 1. Tổng quan Khái ▪ Mã niệm hóa dùng khóa công khai k • C = E(k,M) ▪ Giải mã dùng khóa riêng K • M = D(K,C) 5 1. Tổng quan Khái niệm hóa dùng khóa riêng K ▪ Mã • C = E(K,M) ▪ Giải mã dùng khóa công khai k • M = D(k,C) 6 1. Tổng quan Khóa bí mật & khóa công khai 7 2. Lý thuyết nền tản Hệ mật mã khóa công khai Độ phức tạp Độ phức tạp tính toán (thời gian) ▪ •Vấn đề “dễ”: lớp P •Vấn đề “khó”: lớp NP ▪ Giải quyết các vấn đề P •Số trường hợp phải xét đến là một hàm đa thức ▪ Giải quyết các vấn đề NP •Số trường hợp phải xét đến là hàm lũy thừa “Các hệ mật mã khóa công khai dựa trên độ khó/phức tạp của giải thuật bẻ khóa” 8 2. Lý thuyết nền tản Hệ mật mã khóa công khai Số học đồng dư• a mod n ▪ a mod n • a op b mod n • Số dư của a chia n • op = +, -, *, /, ^ ▪ a + b mod n • Số dư của a + b chia n ▪ Ví dụ: • 40 mod 6 = 4 ▪ a - b mod n • 5 + 2 mod 6 = 1 • Số dư của a - b chia n • 9 – 4 mod 3 = 2 ▪ a * b mod n • 5 * 3 mod 6 = 3 • Số dư của a * b chia n • 4/2 mod 3 = 2 ▪ a ^ b mod n • 2^4 mod 6 = 4 • Thủ tục bình phương ▪ a / b mod n 9 • Giải thuật Euclide mở rộng 2. Lý thuyết nền tản Hệ mật mã khóa công khai Thủ tục bình phương vào tính chất ▪ Dựa • a*b mod n = ((a mod n)*(b mod n)) mod n ▪ Tính a^25 • a^25 = a^(11001) • a^(11001) = a^(10000+1000+1) • a^(10000+1000+1) = a^10000 * a^1000 * a^1 • a^10000 * a^1000 * a^1 = a^16 * a^8 * a^1 ▪ Độ phức tạp (O(logb*(logs)^2)) ▪ Hiệu quả hơn phương pháp tính lũy thừa bằng phép nhân đồng dư (O(b*(logs)^2)) 10 2. Lý thuyết nền tản Hệ mật mã khóa công khai Thủ tục bình phương ▪ ModExp1(a,b, s) ▪ Vào: • 3 số nguyên dương a,b,s sao cho a < s • bn-1 ···b1b0 là biểu diễn nhị phân của b, n = [logb] ▪ Ra: a^b mod s 11 2. Lý thuyết nền tản Hệ mật mã khóa công khai Ví dụ: ▪ Tính 6^73 mod 100 • 73 = 2^0 + 2^3 + 2^6 • 6^73 = 6 * 6^(2^3)*6^(2^6) • 6 = 6 mod 100 • 6^(2^3) = 16 mod 100 • 6^(2^6) = -4 mod 100 • 6^73 = 6 * (16) * (-4) = 16 mod 100 12 3.Các giải thuật mã hóa khóa bất đối xứng ❖Các giải thuật mã hóa khóa bất đối xứng (asymmetric key encryption) ▪ Còn gọi là mã hóa khóa công khai (public key encryption): ▪ Sử dụng một cặp khóa (key pair): • một khóa (public key) cho mã hóa • một khóa (private key) cho giải mã. 13 3. Các giải thuật mã hóa khóa bất đối xứng ❖Đặc điểm: ▪ Kích thước khóa lớn (1024 – 3072 bít) ▪ Tốc độ chậm • Phần lớn do khóa có kích thước lớn. ▪ Độ an toàn cao ▪ Thuận lợi trong quản lý và phân phối khóa: • Do khóa mã hóa là công khai và có thể trao đổi dễ dàng. ❖ Các giải thuật mã hóa khóa bất đối xứng điển hình: ▪ RSA ▪ Rabin ▪ ElGamal ▪ McEliece ▪ Knapsack 14 4. Giải thuật mã hóa khóa bất đối xứng RSA ❖ Trong mật mã học, RSA là một thuật toán mật mã hóa khóa công khai. Đây là thuật toán đầu tiên phù hợp với việc tạo ra chữ ký điện tử đồng thời với việc mã hóa. Nó đánh dấu một sự tiến bộ vượt bậc của lĩnh vực mật mã học trong việc sử dụng khóa công cộng. ❖ RSA đang được sử dụng phổ biến trong thương mại điện tử và được cho là đảm bảo an toàn với điều kiện độ dài khóa đủ lớn. ❖ Thuật toán được Ron Rivest, Adi Shamir và Len Adleman mô tả lần đầu tiên vào năm 1977 tại Học viện Công nghệ Massachusetts (MIT). Được 3 nhà khoa học Ronald Rivest, Adi Shamir và Leonard Adleman phát minh năm 1977; ▪ Tên giải thuật RSA lấy theo chữ cái đầu của tên 3 ông. ❖ Độ an toàn của RSA dựa trên tính khó của việc phân tích số nguyên rất lớn: ...