Báo cáo đề tài: Tìm hiểu về mật mã hóa thông tin

Báo cáo đề tài Nhóm I - lớp 09LT Vương Trung Kiên Vũ Phúc Huyên Nguyễn Tuấn Thành Tìm hiểu về mật mã hóa thông tin MẬT MÃ HÓA I. Giới thiệu II. Một số phép mật mã cơ bản III. Bẻ gãy một hệ thống mật mã IV. Kết hợp các phương pháp mật mã hóa Phần bài học chúng ta đã nêu ra được những khái niệm về mã hiệu, mã mật và một số khái niệm cơ bản về mã hóa kênh. Trong bài báo cáo này sẽ mô tả một cách tổng quan hơn về mật mã hóa, bao gồm những khái niệm về mật mã hóa thông tin và các thuật toán của nó. I. Giới thiệu Mật mã hóa Mật mã hóa là việc biến đổi một thông báo sao cho nó không thể hiểu nổi với bất kỳ ai, ngoại trừ người nhận được mong muốn Để thuận tiện trình bày, chúng ta sẽ định nghĩa và ký hiệu cho các khái niệm cơ bản Thông báo (message) Thông báo là một chuỗi hữu hạn ký hiệu lấy từ một bảng chữ cái ∑ và thường được ký hiệu là m. Ở đây ∑ thường là bảng chữ cái tiếng Anh gồm 26 ký tự, đôi khi có thêm ký tự khoảng trắng Phép mật mã hóa e(m) e(m) là ký hiệu biểu diễn việc mật mã hóa m Trong thực tế, mật mã hóa được xem như 1 hàm, ánh xạ hay giải thuật với 1 tập các thông số. Từ đây chúng ta có khái niệm khóa. Khóa (key) Khóa là 1 thông số đầu vào của phép mã hóa mà không phải là thông báo và được ký hiệu là k. Một phép mã hóa có thể có nhiều khóa Chuỗi mật mã (cipher) c = e(m,k) được gọi là chuỗi mật mã. Phép giải mật mã d(c,k) d(c,k) là ký hiệu biểu diễn việc giải mật mã hóa. Hệ thống mật mã Một cách hình thức, một hệ thống mật mã được định nghĩa là một bộ ba (M, K, C). Trong đó M là tập hợp các thông báo m trên các bảng chữ cái ∑, K là tập hữu hạn các khóa k, C là tập hợp các chuỗi mật mã c, ngoài ra còn có thêm giả thiết rằng tồn tại các hàm hay giải thuật e và d sao cho: e: M x K  C d: C x K  M Và đối với mỗi cặp (m, k) ∈ M x K d(e(m, k), k) = m 2.1 Phép thay thế đơn giản 2.2 Phép thay thế n-gram 2.3 Phép hoán vị bậc d 2.4 Phương pháp Vigenère và Caesar II. Một số phép mật mã cơ bản 2.1 Phép thay thế đơn giản Trong phép này, khóa là một hoán vị π của bảng chữ cái ∑ và mỗi ký hiệu của thông báo được thay bằng ảnh của nó qua hoán vị π. Thông thường, khóa được biểu diễn như một chuỗi 26 ký tự, chẳng hạn nếu khóa là UXE…, thì nó hiển thị rằng bất kỳ sự xuất hiện của A trong thông báo thì được thay bằng U, B được thay bằng X, C được thay bằng E…, các khoảng trắng được giữ nguyên không bị thay thế. 2.2 Phép thay thế n-gram Thay vì thay thế từ ký tự, người ta có thể thay thế cho từng cụm 2 ký tự, 3 ký tự hoặc tổng quát cho từng cụm n ký tự (gọi là n-gram). Nếu bảng chữ cái ∑ gồm 26 ký tự thì phép thay thế n-gram sẽ có khóa là một hoán vị của 26^n n-gram khác nhau Ví dụ bảng 2 chiều sau được biểu thị AA được thay bằng EG, AB được thay bằng RS… 2.3 Phép hoán vị bậc d Đối với 1 số nguyên dương d bất kỳ, chia thông báo m thành từng khối có chiều dài d. Rồi lấy 1 hoán vị π của 1, 2,…, d và áp dụng π tới mỗi khối. Chẳng hạn, nếu d = 5 và π =(4 1 3 2 5), thì có nghĩa là hoán vị ( 1 2 3 4 5) được thay bằng hoán vị mới (4 1 3 2 5). Ví dụ nếu chúng ta có thông báo m = JOHN |IS A |GOOD | ACTOR thì qua phép mật mã này sẽ trở thành như sau: c = NJOH |AI S |DGOO | OATCR 2.4 Phương pháp Vigenère và Caesar Trong phương pháp này, khóa bao gồm một chuỗi của d ký tự. Chúng được viết lặp lại bên dưới thông báo và được cộng modulo 26, chú ý rằng bảng chữ cái được đánh số từ A=0 đến Z=25. Các khoảng trắng sẽ được giữ nguyên không cộng. 2.4 Phương pháp Vigenère và Caesar Chẳng hạn với d = 3, nếu chuỗi khóa là ABC thì thông báo m = với khóa k = trở thành c = Trong trường hợp d = 1, như vậy khóa chỉ là 1 ký tự đơn, thì được gọi là phương pháp Caesar Bẻ gãy một hệ thống mật mã có nghĩa là gì? Những chuyên gia mật mã hay những kẻ tấn công thường được giả thiết biết đầy đủ thông tin về hàm mã hóa e và hàm giải mã d. Thêm vào đó, họ cũng có thể có nhiều thông tin hỗ trợ như các thống kê về ngôn ngữ, kiến thức về ngữ cảnh… Họ sẽ chắc chắn có một chuỗi mật mã nào đó, và tất cả những gì mà họ thiếu là khóa k, từ đó họ có thể sử dụng d để giải mã c một cách chính xác. III. Bẻ gãy một hệ thống mật mã Điều đó có thể được biểu diễn bằng hình ảnh bên dưới: III. Bẻ gãy một hệ thống mật mã Bộ mã hóa e Bộ phát sinh khóa k Bộ giải mã d k k c = e(m, k) m m Những kẻ tấn công Có 3 khả năng tấn công của đối phương vào hệ thống của chúng ta: Tấn công dựa trên chuỗi mật mã: Đây là trường hợp đã được mô tả ở trên trong đó đối phương chỉ biết một vài mẫu chuỗi mật mã c Tấn công dựa trên văn bản đã biết: Trong trường hợp này những người tấn công được giả thiết biết một độ dài đáng kể của văn bản thông báo và chuỗi mật mã tương ứng, và từ đó cố gắng tìm ra khóa. III. Bẻ gãy một hệ thống mật mã Khả năng thứ 3 là: Tấn công dựa trên văn bản được chọn Trong trường hợp này, những người tấn công có thể đã có được một số lượng tùy ý của các cặp thông báo và chuỗi mật mã tương ứng (m, c). Không khó để thấy rằng không có hệ thống hay phương pháp mật mã nào đã môt tả ở trên có thể chống đỡ một cuộc tấn công dựa trên văn bản được chọn. III. Bẻ gãy một hệ thống mật mã Chẳng hạn ta xét hệ thống đơn giản nhất - hệ thống dùng phương pháp thay thế đơn giản - sao cho khóa k là môt hoán vị của 26 chữ cái trong đóA  P, B  F,… Bây giờ nếu thông báo m được gửi là ”message” bao gồm chữ A được lặp lại n lần, thì trong mật mã c tương ứng chữ P sẽ được lặp lại n lần. Không thành vấn đề n lớn bao nhiêu, chuỗi mật mã này sẽ không sinh khóa k. Không khó để tin rằng, nếu đã cho một chiều dài vừa đủ của chuỗi mật mã, bất kỳ hệ thống hay phương pháp mật mã ở trên đều có thể bị bẻ gãy. III. Bẻ gãy một hệ thống mật mã Một cách tự nhiên để tăng tính bảo mật là kết hợp nhiều phương pháp mật mã hóa với nhau (được Shannon làm đầu tiên 1949), tạo nên cơ sở của nhiều hệ thống mật mã thực tế. Đó là: IV. Kết hợp các phươngpháp mật mã hóa - Cách dùng tổng trọng số: Nếu S1, S2,…, Sn là các hệ thống hay phương pháp mật mã hóa có dùng không gian thông báo và 0 < pi < 1 và thì tổng của chúng là hệ thống mật mã dùng Si với xác suất pi IV. Kết hợp các phươngpháp mật mã hóa - Cách dùng tích: Áp dụng các hệ thống hay phương pháp nối tiếp nhau, đầu ra của hệ thống này là đầu vào của hệ thống kế tiếp. Dĩ nhiên tập hợp đầu ra của hệ thống đi trước phải là tập con của tập hợp đầu vào của hệ thống đi sau kế tiếp. IV. Kết hợp các phươngpháp mật mã hóa Thanks for listening