Bài giảng Các phương pháp mã hóa thông tin

Nội dung text: Bài giảng Các phương pháp mã hóa thông tin

1. Chương 3: Các phương pháp mã hóa thông tin 1. Giới thiệu 2. Lược sử phát triển 3. Các khái niệm cơ sở 1
2. Mật mã học ⚫ Mật mã (Cryptography) là ngành khoa học nghiên cứu các kỹ thuật toán học nhằm cung cấp các dịch vụ bảo vệ thông tin. W. Stallings (2003), Cryptography and Network Security: Principles and Practice, Third Edition, Prentice Hall 2
3. Một số thuật ngữ ⚫ 1. Bản rõ X được gọi là là bản tin gốc. Bản rõ có thể được chia nhỏ có kích thước phù hợp. ⚫ 2. Bản mã Y là bản tin gốc đã được mã hoá. Ở đây ta thường xét phương pháp mã hóa mà không làm thay đổi kích thước của bản rõ, tức là chúng có cùng độ dài. ⚫ 3. Mã là thuật toán E chuyển bản rõ thành bản mã. Thông thường chúng ta cần thuật toán mã hóa mạnh, cho dù kẻ thù biết được thuật toán, nhưng không biết thông tin về khóa cũng không tìm được bản rõ. ⚫ 4. Khoá K là thông tin tham số dùng để mã hoá, chỉ có người gửi và nguời nhận biết. Khóa là độc lập với bản rõ và có độ dài phù hợp với yêu cầu an toàn. ⚫ 5. Mã hoá là quá trình chuyển bản rõ thành bản mã, thông thường bao gồm việc áp dụng thuật toán mã hóa và một số quá trình xử lý thông tin kèm theo. 3
4. Một số thuật ngữ ⚫ 6. Giải mã chuyển bản mã thành bản rõ, đây là quá trình ngược lại của mã hóa. ⚫ 7. Mật mã là chuyên ngành khoa học của Khoa học máy tính nghiên cứu về các nguyên lý và phương pháp mã hoá. Hiện nay người ta đưa ra nhiều chuẩn an toàn cho các lĩnh vực khác nhau của công nghệ thông tin. ⚫ 8. Thám mã nghiên cứu các nguyên lý và phương pháp giải mã mà không biết khoá. Thông thường khi đưa các mã mạnh ra làm chuẩn dùng chung giữa các người sử dụng, các mã đó được các kẻ thám mã cũng như những người phát triển mã tìm hiểu nghiên cứu các phương pháp giải một phần bản mã với các thông tin không đầy đủ. ⚫ 9. Lý thuyết mã bao gồm cả mật mã và thám mã. Nó là một thể thống nhất, để đánh giá một mã mạnh hay không, đều phải xét từ cả hai khía cạnh đó. Các nhà khoa học mong muốn tìm ra các mô hình mã hóa khái quát cao đáp ứng nhiều chính sách an toàn khác nhau. 4
5. Mật mã học??? Cách hiểu truyền thống: giữ bí mật nội dung trao đổi Alice và Bob trao đổi với nhau trong khi Eve tìm cách “nghe lén” Alice Bob Eve 5
6. Một số vấn đề chính trong bảo vệ thông tin ⚫ Bảo mật thông tin (Secrecy): đảm bảo thông tin được giữ bí mật. ⚫ Toàn vẹn thông tin (Integrity): bảo đảm tính toàn vẹn thông tin trong liên lạc hoặc giúp phát hiện rằng thông tin đã bị sửa đổi. ⚫ Xác thực (Authentication): xác thực các đối tác trong liên lạc và xác thực nội dung thông tin trong liên lạc. ⚫ Chống lại sự thoái thác trách nhiệm (Non-repudiation): đảm bảo một đối tác bất kỳ trong hệ thống không thể từ chối trách nhiệm về hành động mà mình đã thực hiện 6
7. Xác thực (Authentication) ⚫ Ví dụ: ⚫ Bob chờ Alice “xác nhận” khi đến thời điểm thực hiện công việc ⚫ Cần đảm bảo rằng Eve không can thiệp để tạo “xác nhận” giả 7
8. Tính toàn vẹn thông tin (Integrity) ⚫ Ví dụ: ⚫ Bob cần đảm bảo là nhận chính xác nội dung mà Alice đã gửi ⚫ Cần đảm bảo rằng Eve không can thiệp để sửa nội dung thông điệp mà Alice gửi cho Bob ⚫ Tính toàn vẹn thông tin (Integrity) Alice Bob Eve 8
9. Kênh truyền không an toàn A’s ? A’s 9
10. Chống lại sự thoái thác trách nhiệm ⚫ Ví dụ: ⚫ Bob nhận được 1 thông điệp mà Alice đã gửi ⚫ Alice không thể “chối” rằng không gửi thông điệp này cho Bob ⚫ Chống lại sự thoái thác trách nhiệm (Non- repudiation) Alice Bob 10
11. Vài nét về lịch sử, phát triển Ai Cập cổ đại, World war I, II 2000 năm trước CN 11
12. Ứng dụng Smart cards Embedded enigma systems 12
13. Mô hình trao đổi thông điệp mật attacker Encrypt(m) = c Decrypt(c) = m m Alice Bob 13
14. Hai kỹ thuật mã hóa chủ yếu ⚫ Mã hóa đối xứng ⚫ Bên gửi và bên nhận sử dụng chung một khóa ⚫ Còn gọi là ⚫ Mã hóa truyền thống ⚫ Mã hóa khóa riêng / khóa đơn / khóa bí mật ⚫ Là kỹ thuật mã hóa duy nhất trước những năm 70 ⚫ Hiện vẫn còn được dùng rất phổ biến ⚫ Mã hóa khóa công khai (bất đối xứng) ⚫ Mỗi bên sử dụng một cặp khóa ⚫ Một khóa công khai + Một khóa riêng ⚫ Công bố chính thức năm 1976 14
15. Một số cách phân loại khác ⚫ Theo phương thức xử lý ⚫ Mã hóa khối ⚫ Mỗi lần xử lý một khối văn bản thô và tạo ra khối văn bản mã hóa tương ứng (chẳng hạn 64 hay 128 bit) ⚫ Mã hóa luồng ⚫ Xử lý dữ liệu đầu vào liên tục (chẳng hạn mỗi lần 1 bit) ⚫ Theo phương thức chuyển đổi ⚫ Mã hóa thay thế ⚫ Chuyển đổi mỗi phần tử văn bản thô thành một phần tử văn bản mã hóa tương ứng ⚫ Mã hóa hoán vị ⚫ Bố trí lại vị trí các phần tử trong văn bản thô 15
16. Mô hình hệ mã hóa đối xứng Khóa bí mật dùng chung Khóa bí mật dùng chung bởi bên gửi và bên nhận bởi bên gửi và bên nhận Văn bản mã hóa truyền đi Văn bản thô Văn bản thô đầu vào đầu ra Giải thuật mã hóa Giải thuật giải mã Mã hóa Giải mã Y = EK(X) X = DK(Y) 16
17. Mô hình hệ mã hóa đối xứng ⚫ Gồm có 5 thành phần ⚫ Văn bản thô ⚫ Giải thuật mã hóa ⚫ Khóa bí mật ⚫ Văn bản mã hóa ⚫ Giải thuật giải mã ⚫ An toàn phụ thuộc vào sự bí mật của khóa, không phụ thuộc vào sự bí mật của giải thuật 17
18. Phá mã ⚫ Là nỗ lực giải mã văn bản đã được mã hóa không biết trước khóa bí mật ⚫ Có hai phương pháp phá mã ⚫ Vét cạn ⚫ Thử tất cả các khóa có thể ⚫ Dùng kỹ thuật ⚫ Khai thác những nhược điểm của giải thuật ⚫ Dựa trên những đặc trưng chung của văn bản thô hoặc một số cặp văn bản thô - văn bản mã hóa mẫu 18
19. Phương pháp phá mã vét cạn ⚫ Về lý thuyết có thể thử tất cả các giá trị khóa cho đến khi tìm thấy văn bản thô từ văn bản mã hóa ⚫ Dựa trên giả thiết có thể nhận biết được văn bản thô cần tìm ⚫ Tính trung bình cần thử một nửa tổng số các trường hợp có thể ⚫ Thực tế không khả khi nếu độ dài khóa lớn 19
20. Thời gian tìm kiếm trung bình Kích thước Số lượng khóa Thời gian cần thiết Thời gian cần thiết khóa (bit) (1 giải mã/μs) (106 giải mã/μs) 32 232 = 4,3 x 109 231 μs = 35,8 phút 2,15 ms 56 256 = 7,2 x 1016 255 μs = 1142 năm 10,01 giờ 128 2128 = 3,4 x 1038 2127 μs = 5,4 x 1024 năm 5,4 x 1018 năm 168 2168 = 3,7 x 1050 2167 μs = 5,9 x 1036 năm 5,9 x 1030 năm 26 ký tự 26! = 4 x 1026 2 x 1026 μs = 6,4 x 106 năm (hoán vị) 6,4 x 1012 năm Khóa DES dài 56 bit Tuổi vũ trụ : ~ 1010 năm Khóa AES dài 128+ bit Khóa 3DES dài 168 bit 20
21. Mã hóa thay thế cổ điển ⚫ Các chữ cái của văn bản thô được thay thế bởi các chữ cái khác, hoặc các số, hoặc các ký hiệu ⚫ Nếu văn bản thô được coi như một chuỗi bit thì thay thế các mẫu bit trong văn bản thô bằng các mẫu bit của văn bản mã hóa 21
22. Hệ mã hóa Caesar ⚫ Là hệ mã hóa thay thế xuất hiện sớm nhất và đơn giản nhất ⚫ Sử dụng đầu tiên bởi Julius Caesar vào mục đích quân sự ⚫ Dịch chuyển xoay vòng theo thứ tự chữ cái ⚫ Khóa k là số bước dịch chuyển ⚫ Với mỗi chữ cái của văn bản ⚫ Đặt p = 0 nếu chữ cái là a, p = 1 nếu chữ cái là b, ⚫ Mã hóa : C = E(p) = (p + k) mod 26 ⚫ Giải mã : p = D(C) = (C - k) mod 26 ⚫ Ví dụ : Mã hóa "meet me after class" với k = 3 22
23. Phép thay thế - Mã Caesar K=3 23
24. Phá mã hệ mã hóa Caesar ⚫ Phương pháp vét cạn ⚫ Khóa chỉ là một chữ cái (hay một số giữa 1 và 25) ⚫ Thử tất cả 25 khóa có thể ⚫ Dễ dàng thực hiện ⚫ Ba yếu tố quan trọng ⚫ Biết trước các giải thuật mã hóa và giải mã ⚫ Chỉ có 25 khóa để thử ⚫ Biết và có thể dễ dàng nhận ra được ngôn ngữ của văn bản thô ⚫ Ví dụ : Phá mã "GCUA VQ DTGCM" 24
25. Hệ mã hóa đơn bảng ⚫ Thay một chữ cái này bằng một chữ cái khác theo trật tự bất kỳ sao cho mỗi chữ cái chỉ có một thay thế duy nhất và ngược lại ⚫ Khóa dài 26 chữ cái ⚫ Ví dụ ⚫ Khóa a b c d e f g h i j k l m n o p q r s t u v w x y z M N B V C X Z A S D F G H J K L P O I U Y T R E W Q ⚫ Văn bản thô i love you 25
26. Phá mã hệ mã hóa đơn bảng ⚫ Phương pháp vét cạn ⚫ Khóa dài 26 ký tự ⚫ Số lượng khóa có thể = 26! = 4 x 1026 ⚫ Rất khó thực hiện ⚫ Khai thác những nhược điểm của giải thuật ⚫ Biết rõ tần số các chữ cái tiếng Anh ⚫ Có thể suy ra các cặp chữ cái thô - chữ cái mã hóa ⚫ Ví dụ : chữ cái xuất hiện nhiều nhất có thể tương ứng với 'e' ⚫ Có thể nhận ra các bộ đôi và bộ ba chữ cái ⚫ Ví dụ bộ đôi : 'th', 'an', 'ed' ⚫ Ví dụ bộ ba : 'ing', 'the', 'est' 26
27. Các tần số chữ cái tiếng Anh Tần Tần số tương đối (%) 27
28. Ví dụ phá mã hệ đơn bảng ⚫ Cho văn bản mã hóa UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ ⚫ Tính tần số chữ cái tương đối ⚫ Đoán P là e, Z là t ⚫ Đoán ZW là th và ZWP là the ⚫ Tiếp tục đoán và thử, cuối cùng được it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the viet cong in moscow 28
29. Hệ mã hóa Playfair (1) ⚫ Là một hệ mã hóa nhiều chữ ⚫ Giảm bớt tương quan cấu trúc giữa văn bản mã hóa và văn bản thô bằng cách mã hóa đồng thời nhiều chữ cái của văn bản thô ⚫ Phát minh bởi Charles Wheatstone vào năm 1854, lấy tên người bạn Baron Playfair ⚫ Sử dụng 1 ma trận chữ cái 5x5 xây dựng trên cơ sở 1 từ khóa ⚫ Điền các chữ cái của từ khóa (bỏ các chữ trùng) ⚫ Điền nốt ma trận với các chữ khác của bảng chữ cái ⚫ I và J chiếm cùng một ô của ma trận 29
30. Hệ mã hóa Playfair (2) ⚫ Ví dụ ma trận với từ khóa MONARCHY M O N A R C H Y B D E F G I/J K L P Q S T U V W X Z ⚫ Mã hóa 2 chữ cái một lúc ⚫ Nếu 2 chữ giống nhau, tách ra bởi 1 chữ điền thêm ⚫ Nếu 2 chữ nằm cùng hàng, thay bởi các chữ bên phải ⚫ Nếu 2 chữ nằm cùng cột, thay bởi các chữ bên dưới ⚫ Các trường hợp khác, mỗi chữ cái được thay bởi chữ cái khác cùng hàng, trên cột chữ cái cùng cặp 30
31. Phá mã hệ mã hóa Playfair ⚫ An toàn đảm bảo hơn nhiều hệ mã hóa đơn chữ ⚫ Có 26 x 26 = 676 cặp chữ cái ⚫ Việc giải mã từng cặp khó khăn hơn ⚫ Cần phân tích 676 tần số xuất hiện thay vì 26 ⚫ Từng được quân đội Anh, Mỹ sử dụng rộng rãi ⚫ Văn bản mã hóa vẫn còn lưu lại nhiều cấu trúc của văn bản thô ⚫ Vẫn có thể phá mã được vì chỉ có vài trăm cặp chữ cái cần giải mã 31
32. Hệ mã hóa Vigenère ⚫ Là một hệ mã hóa đa bảng ⚫ Sử dụng nhiều bảng mã hóa ⚫ Khóa giúp chọn bảng tương ứng với mỗi chữ cái ⚫ Kết hợp 26 hệ Ceasar (bước dịch chuyển 0 - 25) ⚫ Khóa K = k1k2 kd gồm d chữ cái sử dụng lặp đi lặp lại với các chữ cái của văn bản ⚫ Chữ cái thứ i tương ứng với hệ Ceasar bước chuyển i ⚫ Ví dụ ⚫ Khóa : deceptivedeceptivedeceptive ⚫ Văn bản thô : wearediscoveredsaveyourself ⚫ Mã hóa : ZICVTWQNGRZGVTWAVZHCQYGLMGJ 32
33. Phá mã hệ mã hóa Vigenère ⚫ Phương pháp vét cạn ⚫ Khó thực hiện, nhất là nếu khóa gồm nhiều chữ cái ⚫ Khai thác những nhược điểm của giải thuật ⚫ Cấu trúc của văn bản thô được che đậy tốt hơn hệ Playfair nhưng không hoàn toàn biến mất ⚫ Chỉ việc tìm độ dài khóa sau đó phá mã từng hệ Ceasar ⚫ Cách tìm độ dài khóa ⚫ Nếu độ dài khóa nhỏ so với độ dài văn bản, có thể phát hiện 1 dãy văn bản lặp lại nhiều lần ⚫ Khoảng cách giữa 2 dãy văn bản lặp là 1 bội số của độ dài khóa ⚫ Từ đó suy ra độ dài khóa 33