Bài giảng Mật mã và Ứng dụng

12/31/2014 Hải V. Phạm Bộ môn HTTT – Viện CNTT&TT H BKHN Mật mã học (Cryptology) ◦ Mật mã (Cryptography) ◦ Mã thám (Cryptanalysis) Mật mã ◦ Tăng cường các tính chất Bí mật và Toàn vẹn thông tin: các phép mã hóa ◦ Xây dựng các kỹ thuật trao đổi thông tin bí mật: các giao thức mật mã Mã thám ◦ Phá mã Giai đoạn “Tiền sử” (~ 2000, TCN) ◦ Những dấu hiệu đầu tiên của Mật mã xuất hiện ở bên bờ sông Nile, Ai Cập Giai đoạn “Mật mã thủ công” (~ 50, TCN) ◦ Phép mã hóa Ceasar Giai đoạn “Mật mã cơ học” (cho đến Thế chiến 2) ◦ Máy Enigma ở ức ◦ Các nghiên cứu về Giải mã ở Anh Giai đoạn “Mật mã điện tử” ◦ Dựa vào Toán học và Tin học ◦ ược đặt nền móng bởi Shanon, Diffie và Hellman ◦ Khóa bí mật (DES, AES,…), Khóa công khai (RSA, ElGamal, …) 1 12/31/2014 Alice và Bob trao đổi thông tin bí mật, được mã hóa Eve và Charlie tấn công bằng giải mã Eve Tấn công thụ động Alice Bob Charlie Tấn công chủ động Bí mật (Confidentiality) Toàn vẹn (Integrity) Xác thực (Authentication) Chống phủ nhận (Non-repudiation) … Cơ sở toán học Hệ Mật mã không khóa Hệ Mật mã khóa bí mật (đối xứng) Hệ Mật mã khóa công khai (bất đối xứng) Hàm băm, chữ ký số Quản lý khóa, giao thức mật mã,… 2 12/31/2014 Số nguyên tố, số học đồng dư là cơ sở toán học của lý thuyết mật mã, có vai trò rất quan trọng trong lý thuyết mật mã. 7 ịnh nghĩa Modulo Cho số tự nhiên n và số nguyên a. Ta định nghĩa: a mod n là phần dư dương khi chia a cho n. ịnh nghĩa quan hệ tương đương trên tập số nguyên a ≡ b mod n khi và chỉ khi a và b có phần dư như nhau khi chia cho n. 8 Các phép toán số học trên Modulo Hai V Pham hai@spice.ci.ritsumei.ac.jp 9 3 12/31/2014 Ước số chung lớn nhất: Bài toán tìm ước chung lớn nhất của hai số nguyên dương là bài toán chung của lý thuyết số GCD(a, b) là ước số chung dương lớn nhất của a và b; Ví dụ: GCD(60,24) = 12 ; GCD (6, 15) = 3; GCD(8, 21) = 1 Nguyên tố cùng nhau. Ta thấy 1 bao giờ cũng là ước sốchung của hai số nguyên dương bất kỳ. Nếu GCD(a, b) = 1, thì a, b đựơc gọi là hai số nguyên tố cùng nhau: Ví dụ: GCD(8,15) = 1, tức là 8 và 15 là hai số nguyên tố cùng nhau 10 Tìm ước chung lớn nhất: GCD(a,b) = GCD(b, a mod b) 11 Thuật toán Euclide mở rộng 12 4 12/31/2014 Một số thuật toán trên Zn ịnh nghĩa: Phần tử nghịch đảo 13 ... - tailieumienphi.vn