Nghiên cứu tính toán mềm và ứng dụng

độ thích nghi (fitness) của nó trên bánh xe. Giả sử các chuỗi của quần thể ban đầu đã khởi tạo trong bài toán hộp đen có các giá trị hàm thích nghi như trong bảng sau. Lấy tổng độ thích nghi của 4 chuỗi, chúng ta được 1170. Ta có tỉ lệ % độ thích nghi của từng chuỗi trong quần thể: STT Chuỗi Độ thích nghi % trong tổng số 1 01101 169 14.4 2 11000 576 49.2 3 01000 64 5.5 4 10001 361 30.9 Tổng cộng 1170 100.0 Các chuỗi của bài toán mẫu và các giá trị thích nghi Bánh xe roulette được đánh trọng số phù hợp cho sự tái tạo của thế hệ này được thể hiện trên hình sau: 49.2% 2 5.5% 3 30.9% 4 14.4% 1 Sự sinh sản đơn giản phân bố các chuỗi con cháu nhờ sử dụng bánh xe Roulette với các khe hở tỉ lệ với độ thích nghi. Với bài toán hộp đen, để sinh sản chúng ta chỉ cần quay bánh xe Roulette 4 lần. Đối với bài toán cụ thể thì: Chuỗi 1 có giá trị thích nghi là 169 đại diện cho 0.144. Tương tự với các chuỗi còn lại, bằng cách này chuỗi thích nghi hơn sẽ có một lượng con cháu lớn hơn trong thế hệ tiếp theo. Lai ghép Mỗi khi một chuỗi được chọn để sinh ra, một bản sao chính xác của các chuỗi đó sẽ được tạo ra. Các bản sao này được đưa vào bể ghép đôi (mating pool). Toán tử lai ghép đơn giản có thể được tiến hành theo hai bước: Bước 1: Chọn ngẫu nhiên hai (hay nhiều) cá thể bất kỳ trong quần thể. Giả sử NST của cha mẹ đều có m gene Bước 2: Tạo một số ngẫu nhiên trong khoảng từ 1 đến m-1 (ta gọi là điểm lai). Điểm lai chia các chuỗi cha mẹ dài m thành 2 nhóm con dài m1 và m2. Hai chuỗi NST con mới là m11 + m22 và m12 + m21 Đưa hai cá thể mới này vào quần thể để tham gia các quá trình tiến hóa tiếp theo. Ví dụ: Về phép lai một điểm với xác suất Pc có thể mô phỏng như sau: Ví dụ về phép lai (lấy từ [4]) Cơ chế sinh sản và lai ghép chéo đơn giản, bao gồm các việc sinh số ngẫu nhiên, sao chép chuỗi và trao đổi các chuỗi thành phần. Tuy nhiên, điểm cần nhấn mạnh là điểm sinh sản và trao đổi thông tin có cấu trúc (dù là một cách ngẫu nhiên) cả quá trình ghép chéo làm cho giải thuật di truyền tăng thêm sức mạnh. Đột biến Đột biến là hiện tượng cá thể con mang một số tính trạng không có trong mã di truyền của cha mẹ. Mục đích của phép đột biến trong thuật toán di truyền là giúp cho thuật toán tránh được các cực trị cục bộ. Phép đột biến xảy ra với xác suất Pm nhỏ hơn rất nhiều so với xác suất Pc. Một phép đột biến có thể mô tả như sau: Bước 1: Chọn ngẫu nhiên một cá thể cha mẹ bất kỳ trong quần thể. Giả sử NST của cha mẹ đều có m gene Bước 2: Tạo một số ngẫu nhiên k trong khoảng từ 1 đến m (1 ≤ k ≤ m). Thay đổi gene thứ k và trả cá thể này về quần thể để tham gia quá trình tiến hóa tiếp theo Ví dụ về phép đột biến với xác suất Pm: 01101==> 01111 Đột biến tại bít thứ 4 Nếu sự sinh sản theo độ thích nghi kết hợp với sự ghép chéo làm cho giải thuật di truyền có năng lực xử lý tốt hơn, thì sự đột biến đóng vai trò quyết định thứ 2 trong hoạt động của giải thuật di truyền. Sự đột biến là cần thiết bởi vì: cho dù sự sinh sản và ghép chéo đã tìm kiếm hiệu quả và tái kết hợp lại các gene với nhau, nhưng thỉnh thoảng chúng có thể làm mất một vài gene hữu ích nào đó (ví dụ bít 1 hay bít 0 tại những vị trí đặc biệt). Trong các hệ thống gene nhân tạo, toán tử đột biến sẽ chống lại sự mất mát không được khôi phục đó. Trong thuật toán di truyền đơn giản, đột biến là sự thay đổi ngẫu nhiên và không thường xuyên (với xác suất nhỏ) trị số vị trí của một chuỗi. Trong việc mã hóa nhị phân của bài toán hộp đen có nghĩa là chỉ cần đổi 1 thành 0 và ngược lại. Tự thân nó sự đột biến là một hoạt động ngẫu nhiên trong không gian chuỗi, khi được dùng cùng với sự sinh sản và ghép chéo nó sẽ là một chính sách bảo hiểm chống lại nguy cơ mất mát những gene quan trọng. SƠ ĐỒ GIẢI THUẬT DI TRUYỀN Giải thuật di truyền bao gồm các bước sau: Bước 1: Khởi tạo quần thể (population) ban đầu của các NST. Bước 2: Xác định giá trị hàm mục tiêu cho mỗi chuỗi NST. Bước 3: Tạo các chuỗi NST mới bằng sinh sản từ các chuỗi NST hiện tại, có tính đến ghép chéo và đột biến xảy ra (nếu có). Bước 4: Xác định hàm mục tiêu cho các chuỗi NST mới, và đưa nó vào trong một dân số mới. Bước 5: Nếu điều kiện kết thúc thuật toán đã thỏa mãn thì dừng lại, và trả về chuỗi NST tốt nhất cùng với giá trị hàm mục tiêu của nó, nếu không thì quay về bước 3. Sơ đồ giải thuật di truyền đơn giản: Tạo quần thể ban đầu của các chuỗi NST Xác định giá trị hàm mục tiêu của các chuỗi NST Tính toán các giá trị mục tiêu của chuỗi NST mới và đưa nó vào quần thể mới Tạo các chuỗi NST bằng cách sinh sản từ các chuỗi NST hiện tại (có tính đến ghép chéo và đột biến xảy ra) Kiểm tra điều kiện kết thúc thuật toán thỏa mãn chưa? Kết thúc N Y MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN DI TRUYỀN ĐƠN GIẢN Cải tiến phương pháp chọn lọc Thuật toán di truyền đơn giản áp dụng phương pháp chọn lọc dùng bánh xe Roulette như đã trình bày ở trên. Cùng với sự phát triển của thuật toán di truyền các nhà nghiên cứu đã đề xuất một số phương pháp chọn lọc khác: chọn lọc sắp xếp hạng, chọn lọc cạnh tranh… Chọn lọc xếp hạng (Rank Selection) Phương pháp này sắp hạng cá thể dựa trên độ thích nghi của chúng. Cá thể xấu nhất có độ thích nghi 1, kế tiếp là 2,3…. Cá thể tốt nhất có độ thích nghi n (n là số NST có trong quần thể). Chọn lọc cạnh tranh (Tournament selection) Chọn lọc cạnh tranh 2: Hai NST khác nhau được chọn ngẫu nhiên và được so sánh với NST tồn tại. Nếu NST i1 không tốt hơn NST i2 nghĩa là f(i1) ≤ f(i2), thì NST i1 chết đi và bị loại ra khỏi quần thể (liên kết được phá vỡ tùy ý). Quá trình này lặp lại cho đến hết NST còn lại. Chọn lọc cạnh tranh 3: Giống như trên, 3 NST khác nhau được chọn ngẫu nhiên và được so sánh. Nếu chúng ta có f(i1) ≤ f(i2) ≤ f(i3) thì NST i1 sẽ chết và bị loại ra khỏi quần thể. Quá trình này lặp lại cho đến hết NST còn lại. Cải tiến toán tử lai ghép Lai ghép ánh xạ từng phần (PMX – Partial Mappel Crossover) Lai ghép ánh xạ từng phần có thể xem như một biến đổi của lai ghép 2 điểm giao nhau bằng cách kết hợp với các thủ tục sửa chữa đặc biệt để giải quyết tính không chính đáng (illegitimacy) có thể có. PMX gồm các bước sau: Chọn ngẫu nhiên 2 điểm cách nhau cùng với một chuỗi. Chuỗi con được định nghĩa bởi 2 điểm cắt nhau được định nghĩa là ánh xạ từng phần. Trao đổi hai chuỗi con giữa các cá thể cha mẹ để tạo ra các thể con. Xác định quan hệ ánh xạ giữa các thành phần ánh xạ Hợp thức cá thể con với các quan hệ ánh xạ. Ví dụ: Bài toán người chào hàng với 9 thành phố. Một NST biểu diễn toàn bộ đường đi. Cá thể cha: 93|8571|642 Cá thể mẹ: 35|2614|879 Đầu tiên hoán vị giữa cá thể cha (parent 1) và cá thể mẹ (parent 2) Cá thể con 1: xx|2614|xxx Cá thể con 2: xx|8571|xxx. Ký hiệu “x” có thể được xem như ẩn số (unknown) Hoán vị này cũng được định nghĩa một chuỗi những ánh xạ 2->8, 6 ->5, 1->7, 4->1. Cuối cùng điều chỉnh với quan hệ ánh xạ, ta có thể điền thêm các thành phố (từ cá thể cha mẹ ban đầu), mà không có vấn đề mâu thuẫn. Cá thể con thứ 1: 93|2614|xxx Cá thể con thứ 2: 3x|8571|xx9 “x” đầu tiên trong cá thể con thứ 1 (sẽ là 6 nhưng vẫn có mâu thuẫn) được thay bởi 5, tương tự ta áp dụng với mọi ẩn x chưa biết còn lại, ta được: Cá thể con thứ 1: 93|2614|578 Cá thể con thứ 1: 36|8571|249 Lai ghép có trật tự (OX – Order Crossover) Lai ghép có trật tự có thể được xem như một biến thể của PMX sử dụng thủ tục sửa chữa khác, OX gồm các bước sau: Chọn ngẫu nhiên 1 chuỗi con từ cá thể cha mẹ. Đưa ra một cá thể con bằng cách sao chép chuỗi con vào những vị trí tương ứng trong cá thể cha mẹ. Xóa tất cả các ký tự từ cá thể cha mẹ thứ 2, lúc này đã có trong chuỗi con. Chuỗi còn lại chứa ký hiệu mà cá thể con cần. Đặt các ký hiệu vào những vị trí không cố định của các cá thể con từ trái sang phải theo trật tự của chuỗi để tạo ra cá thể con. Ví dụ: Cá thể cha: 93|8571|642 Cá thể mẹ: 35|2614|879 Đầu tiên phân đoạn giữa để cắt các điểm được sao chép vào cá thể con: Cá thể con 1: xx|8571|xxx Cá thể con 2: xx|2614|xxx Chuỗi bắt đầu từ điểm cắt thứ 2 của cá thể mẹ là: 8-7-9-3-5-2-6-1-4 Chuỗi sau khi loại các thành phố 8, 5, 7, 1 cũng ở trong cá thể con đầu tiên là: 9-3-2-6-4 Cuối cùng chuỗi này được đặt vào cá thể con 1 đầu tiên để tạo ra cá thể con (bắt đầu từ điểm cắt thứ 2). Cá thể con 1: 64|8571|932 Tương tục chúng ta được cá thể con khác: Cá thể con 2: 57|2614|938. Lai ghép dựa trên vị trí (Possition Base Crossover) Lai ghép dựa trên vị trí thực chất là một loại đồng nhất cho mã hóa theo nghĩa đột biến kết hợp với một thủ tục để sửa chữa. Trước tiên nó phát sinh ngẫu nhiên một mặt nạ sau đó trao đổi các gene liên quan giữa cá thể cha và mẹ theo mặt nạ. Một mặt nạ lai ghép là một chuỗi nhị phân đơn giản có kích thước NST như nhau. Sự tương đương của mỗi bit tương ứng trong cá thể con, xác định cá thể cha mẹ nào sẽ cung cấp bit đó. Bởi vì lai ghép đồng nhất sẽ tạo ra cá thể con bất hợp lệ cho mã hóa đột biến, lai ghép đột biến sẽ sử dụng một thủ tục sửa chữa để giải quyết tính bất hợp lệ. Lai ghép dựa trên vị trí gồm các bước sau: Chọn ngẫu nhiên một tập hợp các vị trí từ một cá thể cha mẹ. Tạo ra một cá thể con bằng cách sao chép các ký hiệu từ cá thể cha mẹ tùy thuộc vào bit của mặt nạ tại vị trí đó vào cá thể con. Xóa các ký hiệu, lúc này đã được chọn từ cá thể cha mẹ thứ 2. Chuỗi kết quả chỉ chứa các ký hiệu cá thể con cần. Đặt các ký hiệu vào những vị trí không cố định của cá thể con từ trái sang phải tương ứng với trật tự của chuỗi để tạo ra một cá thể con. Ví dụ: Cá thể cha: 93|8751|642 Cá thể mẹ: 35|2614|879 Giả sử chúng ta có một mặt nạ như sau: 010011101. Bit thứ nhất của mặt nạ là 0. Như vậy cá thể con thứ nhất nhận ký hiệu từ cá thể mẹ (trong chuỗi từ trái sang phải). Cá thể con 1: 3xxxxxxxx Bit thứ 2 của mặt nạ là 1. Như vậy cá thể con thứ nhất nhận các ký hiệu tiếp theo từ cá thể cha (cũng trong chuỗi từ trái sang phải). Đây là ký hiệu 9 không có trong cá thể con thứ 1. (Có nghĩa là ký hiệu 9 chưa tồn tại trong cá thể con thứ 1). Cá thể con 1: 39xxxxxxx Tiếp theo các bit thứ 3 và 4 là 0. Như vậy cá thể con thứ 1 nhận 2 ký hiệu từ các cá thể cha mẹ là 2 và 5 không có trong cá thể con thứ 2. Cá thể con 1: 3952xxxxx Bit thứ 5 là 1. Như vậy cá thể con thứ 1 không thể nhận giá trị 3 từ cá thể cha bởi bản thân cá thể con thứ nhất đã chứa giá trị 3, nên nó sẽ nhận giá trị 8 từ cá thể cha (giá trị 8 chưa có trong cá thể con thứ 1). Tương tự và cuối cùng ta được: Cá thể con 1: 395287164 Cá thể con 2: 938526174 Lai ghép dựa trên thứ tự (Order – Base Crossover) Lai ghép dựa trên thứ tự là một thay đổi nhỏ của lai ghép dựa trên vị trí, trong đó thứ tự của các ký hiệu vị trí được chọn trong cá thể cha tác động lên vị trí tương ứng trong cá thể mẹ. Ví dụ: Cá thể cha: 93|8751|642 Cá thể mẹ: 35|2614|879 Giả sử rằng những vị trí được chọn là 3, 4, 6, 9. Thứ tự của các thành phố trong các vị trí từ cá thể cha sẽ tác động lên cá thể mẹ. Các thành phố tại những vị trí này (theo thứ tự cho trước) trong cá thể mẹ là 2, 6, 4 và 9. Cá thể con thứ nhất là bản sao của cá thể cha trên mọi vị trí ngoại trừ những thành phố 2, 4, 6, 9. Cá thể con 1: x38571xxx Tất cả các thành phần khác được điền theo thứ tự của cá thể mẹ ngoại trừ những thành phố đã có trong cá thể cha. Cá thể con 1: 238571649 Tương tự ta có cá thể con thứ 2: 385614279. Lai ghép có chu trình (CX – Cycle Crossover) Giống như lai ghép dựa trên vị trí, nó chọn một số ký hiệu từ một cá thể cha hoặc mẹ và các ký hiệu còn lại từ cá thể cha hoặc mẹ khác. Điểm khác nhau là các ký hiệu lấy từ cá thể cha không được chonl một cách ngẫu nhiên và chỉ những ký hiệu được chọn mới xác định một chu trình tương ứng với những vị trí tương ứng giữa các cá thể cha mẹ. CX là việc như sau: Tìm một chu trình được xác định bởi những vị trí tương ứng của các ký hiệu giữa các cá thể cha mẹ. Sao chép các ký hiệu trong chu trình vào một cá thể con bởi những vị trí tương ứng trong một cá thể cha hoặc mẹ. Xác định các ký hiệu còn lại cho cá thể con bằng cách xóa những ký hiệu này, bây giờ đã là chu trình từ một cá thể cha mẹ khác. Điền cá thể con với các ký hiệu còn lại. Ví dụ: Cá thể cha: 93|8751|642 Cá thể mẹ: 35|2614|879 Cá thể con thứ 1 chọn thành phố đầu tiên từ cá thể cha. Cá thể con 1: 9xxxxxxxx Thành phố thứ 2 được xem xét phải là thành phố thứ 3 từ cá thể mẹ. Trong cá thể cha thành phố này ở vị trí thứ 2 và như vậy: Cá thể con 1: 93xxxxxxx Đến thành phố thứ 3 được xem xét là thành phố thứ 5 từ cá thể mẹ. Trong cá thể cha thành phố này ở vị trí thứ 4, ta có: Cá thể con 1: 93x5xxxxx Như vậy thành phố thứ 3 trong cá thể con thứ nhất được lấy từ vị trí thứ 3 của cá thể cha: Cá thể con 1: 9385xxxxx Tương tự chúng ta có một chu trình đầy đủ. Cá thể con 1: 9385xx6x2 Các thành phố còn lại được điền từ cá thể cha mẹ còn lại: Cá thể con 1: 938514672 Tương tự chúng ta có cá thể con thứ 2: 356271849. Lai ghép thứ tự tuyến tính (LOX – Linea Order Crossover) LOX được phát triển như một sửa đổi của lai ghép thứ tự. Lai ghép thứ tự có khuynh hướng truyền những vị trí tương đối của các gene, thay vì những vị trí tuyệt đối. Trong lai ghép thứ tự, NST được xem xét xoay vòng hay không xoay vòng tùy thuộc vào từng bài toán. Vì lý do này, người ta phát triển một biến thể của OX gọi là lai ghép tuyến tính (LOX), trong đó NST được xem xét tuyến tính, thay vì xoay vòng. LOX làm việc như sau: Chọn chuỗi con từ cá thể cha mẹ một cách ngẫu nhiên. Loại bỏ chuỗi con 2 (Sup_string2) từ cá thể cha, giữ lại một số lỗ (holes_đánh dấu bằng h) và sau đó đẩy các lỗ từ đầu đến tâm cho đến khi chúng gặp miền giao nhau. Tương tự chúng ta loại bỏ chuỗi con 1 từ cá thể mẹ và đẩy các lỗ đến miền giao (cross setion). Đưa chuỗi con 1 vào các lỗ của cá thể mẹ để tạo thành cá thể con thứ 1 và đưa chuỗi con 2 vào các lỗ của cá thể cha để tạo thành cá thể con thứ 2. Toán tử lai ghép có thể giữ quan hệ giữa các vị trí tuyệt đối cũng như quan hệ đối với những điểm đầu của cá thể cha mẹ càng nhiều càng tốt. Các điểm đầu ứng với các hoạt động có độ ưu tiên thấp hoặc cao. Ví dụ: Cá thể cha: 93|8751|642. Cá thể mẹ: 35|2614|879 Đầu tiên phân đoạn giữa các điểm cắt được sao chép vào cá thể con. Cá thể con 1: xx|8571|xxx. Cá thể con 2: xx|2614|xxx Sau đó loại bỏ ký hiệu trong phân đoạn giữa 2 điểm cắt, cá thể mẹ giữ lại một số lỗ. Cá thể mẹ: 3h|264h|hh9 Đẩy các lỗ cho đến khi chúng gặp miền giao nhau. Cá thể mẹ 32|hhhh|649 Cuối cùng đưa cá thể con 1 vào lỗ trong cá thể mẹ để tạo ra cá thể con thứ nhất. Cá thể con 1: 32|8571|649 Tương tự chúng ta được: Cá thể con 2: 93|2614|857 Cải tiến về hàm mục tiêu Chuyển đổi hàm mục tiêu thành hàm thích nghi Ở đây các bài toán được xét đến đều giả thiết rằng: hàm mục tiêu có miền giá trị thuộc tập số dương và ta chỉ xét các bài toán tối ưu tìm giá trị lớn nhất của hàm. Nhưng bài toán gặp trong thực tế là rất đa dạng, vì vậy để giải quyết vấn đề này ta xét 2 trường hợp sau: Trường hợp 1: Nếu bài toán tối ưu yêu cầu tìm cực tiểu hàm f(x), ta đưa về tìm cực đại hàm g(x) với g(x) = -f(x). Khi đó giá trị xopt làm cực đại hàm g(x) cũng chính là điểm cực tiểu hàm f(x). Trường hợp 2: Nếu hàm mục tiêu f có cả giá trị âm và dương thì ta có thể cộng thêm một hằng số dương c nào đó sao cho f(x) có miền giá trị thuộc tập dương. Phép sửa đổi hàm thích nghi theo từng bước lặp Phương pháp sửa đổi này có liên quan đến tính chất của hàm cần được tối ưu. Có nhiều hướng tiếp cận vấn đề này, chẳng hạn: phương pháp luyện kim kỹ thuật thay đổi Entropy của hệ. Ở phương pháp này người ta đã điều khiển tốc độ hội tụ của quần thể bằng cách biến đổi nhiệt động học với một tham số nhiệt độ toàn cục. Phương pháp được nhiều người quan tâm nhất là: biến đổi hàm phù hợp bằng cách đưa ra một phép vị tự để thay đổi hàm phù hợp. Goldberg đã phân phép vị tự thành 3 loại sau: Phép vị tự tuyến tính Hàm phù hợp f’i = a*fi + b, trong đó fi là giá trị ban đầu của hàm phù hợp,a, b là các tham số. Thường các tham số a, b được chọn sao cho: Độ thích nghi trung bình trước sửa đổi fi(avg) và độ thích nghi trung bình sau sửa đổi f’i(avg) là tương ứng sao cho không làm ảnh hưởng tới pha chọn lọc, bởi vì trong pha này những cá thể có độ thích nghi trên trung bình có nhiều khả năng để chọn tái sinh hơn. Độ thích nghi cao nhất có một khoảng cách nhất định với độ thích nghi trung bình. Hạn chế của phương pháp này là: Trong các thế hệ sau có thể nảy sinh các độ thích nghi âm. Hơn nữa, tham số a, b thường là cố định và không liên quan gì đến bài toán. Phép vị tự làm tròn xích ma: Đây là phương pháp cải tiến của phép vị tự tuyến tính, nhằm xử lý các giá trị thích nghi âm và đưa được các dữ liệu của bài toán vào hàm đánh giá. Giá trị sửa đổi của hàm phù hợp f’i = fi + (f – c*σ). Trong đó c là một số nguyên dương cho trước (thường chọn từ 1->5), σ là độ chênh lệch tiêu chuẩn của quần thể, f là giá trị trung bình của hàm phù hợp, các giá trị âm (nếu có) của f’ được gán bằng 0. Phép vị tự lũy thừa: Hàm phù hợp f’i được sửa đổi giá trị theo công thức: f’i = fkiTrong đó k là một số gần bằng 1. Một số nghiên cứu cho rằng nên chọn k tùy theo bài toán (Ví dụ: k=1.005 đã cho kết quả khả quan).  BÀI TOÁN TỐI ƯU HÀM SỐ Cần làm cực đại hàm số: f(x) = x2 trong đó x Є D[0…30] Cách giải: Theo phương pháp truyền thống: Có một số phương pháp giải bài toán tối ưu đối với hàm số mang tính truyền thống như sau: Phương pháp “vét cạn”: Duyệt tất cả các điểm nằm trong vùng khảo sát D để tìm ra điểm cực trị của nó. Phương pháp này không thích hợp khi dữ liệu đầu vào quá lớn. Phương pháp giải tích: Tìm điểm cực trị bằng cách tính đạo hàm của hàm số không liên tục hoặc không có đạo hàm. Phương pháp “giải thuật di truyền”: Miền xác định của x có độ dài 30 trong đoạn [0…30] cần chia thành ít nhất 30 đoạn bằng nhau 24<30<25 Vậy NST cần 5 bít để biểu diễn. Tất cả 5 bít của NST đều được khởi tạo ngẫu nhiên. Giả sử sau khi khởi tạo ta được tập NST: V1= 01101 V2= 11000 V3=01000 V4=10011 Trong pha đánh giá, giải mã từng NST và tính giá trị hàm thích nghi ta được: Eval(v1) = f(13) = 169 Eval(v3) = f(8) = 64 Eval(v2) = f(24) = 576 Eval(v4) = f(19) = 361 Dễ thấy v2 là NST tốt nhất, v3 là NST tồi nhất. Tiếp theo ta xây dựng vòng Roulette cho quá trình chọn lọc. Tổng độ thích nghi của quần thể NST: F = ∑ Eval(vi) = 1170 Xác suất chọn lọc của mỗi NST là: P1=eval(v1)/f = 0.14 P2=eval(v2)/f = 0.49 P3=eval(v3)/f = 0.06 P4=eval(v4)/f = 0.31 Xác suất tích lũy của mỗi NST là: q1= 0.58 q2= 1.97 q3= 0.22 q4= 1.23 STT Chuỗi Độ thích nghi % trong tổng số 1 01101 169 14.4 2 11000 576 49.2 3 01000 64 5.5 4 10001 361 30.9 Tổng cộng 1170 100.0 Các chuỗi của bài toán mẫu và các giá trị thích nghi Bánh xe roulette được đánh trọng số phù hợp cho sự tái tạo của thế hệ này được thể hiện trên hình sau: 49.2% 2 5.5% 3 30.9% 4 14.4% 1 Sự sinh sản đơn giản phân bố các chuỗi con cháu nhờ sử dụng bánh xe Roulette với các khe hở tỉ lệ với độ thích nghi. Với bài toán hộp đen, để sinh sản chúng ta chỉ cần quay bánh xe Roulette 4 lần. Đối với bài toán cụ thể thì: Chuỗi 1 có giá trị thích nghi là 169 đại diện cho 0.144. Tương tự với các chuỗi còn lại, bằng cách này chuỗi thích nghi hơn sẽ có một lượng con cháu lớn hơn trong thế hệ tiếp theo. Chương 3: HỆ MÃ HÓA DỮ LIỆU DES HỆ MÃ HÓA Thuật toán mã hóa chuẩn DES là ánh xạ 1-1, tức là với mỗi bản rõ và khoá cho trước, tồn tại duy nhất một bản mã tương ứng, ngược lại với mỗi bản mã và khoá cho trước, tồn tại duy nhất một bản rõ tương ứng. Ký hiệu r là bản rõ (8 byte), m là bản mã (8 byte), k là khoá (56 bit) Î K = {0, 1}56. P là không gian các bản rõ, C là không gian các bản mã, E là hàm lập mã, D là hàm giải mã. Ta có m = Ek (r) và r = Dk(m), trong đó r = Dk (Ek (r)). A ={a, b,…, z} là bảng chữ cái của ngôn ngữ nào đó (Ví dụ tiếng Anh),B = {00, 01,…, FF}. Cho đơn giản ta giả thiết bản rõ r gồm chỉ các chữ cái thường (không viết hoa). Như vậy ta có A = {a, b, …, z} = {61, 62, …, 7ª}. Ở đây A Ì B. Bản rõ được biểu diễn bởi các ký tự trong A, bản mã được biểu diễn bởi các ký tự trong B. 3.1.1. Khái niệm mã hóa 1/. Mã hóa: là quá trình chuyển thông tin có thể đọc được (gọi là bản rõ) thành thông tin “khó” thể đọc được theo cách thông thường (gọi là bản mã). Đó là một trong những kỹ thuật để bảo mật thông tin. 2/. Giải mã: là quá trình chuyển thông tin ngược lại từ bản mã thành bản rõ. 3/. Thuật toán mã hóa hay giải mã là thủ tục tính toán để thực hiện mã hóa hay giải mã. 4/. Khóa mã hóa là một giá trị làm cho thuật toán mã hóa thực hiện theo cách riêng biệt và sinh ra bản rõ riêng. Thông thường khóa càng lớn thì bản mã càng an toàn. Phạm vi các giá trị có thể có của khóa được gọi là Không gian khóa. 5/. Hệ mã hóa là tập các thuật toán, các khóa nhằm che giấu thông tin, cũng như làm rõ nó. 3.1.2. Phân loại mã hóa Hiện nay có 2 loại mã hóa chính: mã hóa khóa đối xứng và khóa công khai. Hệ mã hóa khóa đối xứng có khóa lập mã và khóa giải mã “giống nhau”, theo nghĩa biết được khóa này thì “dễ” tính được khóa kia. Vì vậy phải giữ bí mật cả 2 khóa. Hệ mã hóa khóa công khai thì có khóa lập mã khác khóa giải mã (ke kd), biết được khóa này cũng “khó” tính được khóa kia. Vì vậy chỉ cần bí mật khóa giải mã, còn công khai khóa lập mã. 3.1.2.1. Hệ mã hóa khóa đối xứng 1/. Khái niệm Hệ mã hóa khóa đối xứng là hệ mã hóa mà biết được khóa lập mã thì có thể “dễ” tính được khóa giải mã và ngược lại. Đặc biệt một số hệ mã hóa có khóa lập mã và khóa giải mã trùng nhau (ke = kd), như hệ mã hóa “dịch chuyển” hay DES. Hệ mã hóa khóa đối xứng còn gọi là Hệ mã hóa khóa bí mật, hay khóa riêng, vì phải giữ bí mật cả 2 khóa.Trước khi dùng hệ mã hóa khóa đối xứng, người gửi và người nhận phải thỏa thuận thuật toán mã hóa và khóa chung (lập mã hay giải mã), khóa phải được bí mật. Độ an toàn của Hệ mã hóa loại này phụ thuộc vào khóa, nếu để lộ ra khóa này nghĩa là bất kỳ người nào cũng có thể mã hóa và giải mã thông báo trong hệ thống mã hóa. Sự mã hóa và giải mã của hệ thống mã hóa khóa đối xứng biểu thị bởi: Ek: P → C và Dk: C → P 2/. Ví dụ: Hệ mã hóa cổ điển là Mã hóa khóa đối xứng: dễ hiểu, dễ thực thi, nhưng có độ an toàn không cao. Vì giới hạn tính toán chỉ trong phạm vi bảng chữ cái, sử dụng trong bản tin cần mã, ví dụ Z26 nếu dùng các chữ cái tiếng anh. Với hệ mã hóa cổ điển, nếu biết khóa lập mã hay thuật toán lập mã, có thể “dễ” xác định được bản rõ, vì “dễ” tìm được khóa giải mã. Hệ mã hóa DES (1973) là Mã hóa khóa đối xứng hiện đại, có độ an toàn cao. 3/. Đặc điểm. Ưu điểm: Hệ mã hóa khóa đối xứng: mã hóa và giải mã nhanh hơn Hệ mã hóa khóa công khai. Hạn chế: (i). Mã hóa khóa đối xứng chưa thật an toàn với lý do sau: Người mã hóa và người giải mã có “chung” một khóa. Khóa phải được giữ bí mật tuyệt đối, vì biết khóa này “dễ” xác định được khóa kia và ngược lại. (ii). Vấn đề thỏa thuận khóa và quản lý khóa chung là khó khăn và phức tạp. Người gửi và người nhận phải luôn thống nhất với nhau về khóa. Việc thay đổi khóa là rất khó và dễ bị lộ. Khóa chung phải được gửi cho nhau trên kênh an toàn. Mặt khác khi hai người (lập mã, giải mã) cùng biết “chung” một bí mật, thì càng khó giữ được bí mật! 4/. Nơi sử dụng hệ mã hóa khóa đối xứng. Hệ mã hóa khóa đối xứng thường được sử dụng trong môi trường mà khóa chung có thể dễ dàng trao chuyển bí mật, chẳng hạn trong cùng một mạng nội bộ. Hệ mã hóa khóa đối xứng thường dùng để mã hóa những bản tin lớn, vì tốc độ mã hóa và giải mã nhanh hơn hệ mã hóa công khai. 3.1.2.2. Hệ mã hóa khóa phi đối xứng (hệ mã hóa khóa công khai) 1/. Khái niệm Hệ mã hóa khóa phi đối xứng là Hệ mã hóa có khóa lập mã và khóa giải mã khác nhau (ke kd), biết được khóa này cũng “khó” tính được khóa kia. Hệ mã hóa này còn được gọi là Hệ mã hóa khóa công khai vì: + Khóa lập mã cho công khai, gọi là khóa công khai (Public key). + Khóa giải mã giữ bí mật, còn gọi là khóa riêng (Private key) hay khóa bí mật. Một người bất kỳ có thể dùng khóa công khai để mã hóa bản tin, nhưng chỉ người nào có đúng khóa giải mã thì mới có khả năng đọc được bản rõ. Hệ mã hóa khóa công khai hay Hệ mã hóa phi đối xứng do Diffie và Hellman phát minh vào những năm 1970. 2/. Ví dụ Hệ mã hóa RSA, hệ mã hóa ELGAMAL,…. 3/. Đặc điểm. Ưu điểm: (i). Thuật toán được viết một lần, công khai cho nhiều lần dùng, cho nhiều người dùng, họ chỉ cần giữ bí mật cho khóa riêng của mình. (ii). Khi biết các tham số ban đầu của hệ mã hóa, việc tính ra cặp khóa công khai và bí mật phải là “dễ” , tức là trong thời gian đa thức. Người gửi có bản rõ P và khóa công khai, thì “dễ” tạo ra bản mã C. Người nhận có bản mã C và khóa bí mật, thì “dễ” giải được thành bản rõ P. (iii). Người mã hóa dùng khóa công khai, người giải mã giữ khóa bí mật. Khả năng lộ khóa bí mật khó hơn vì chỉ có một người giữ gìn. Nếu thám mã biết khóa công khai, cố gắng tìm khóa bí mật, thì chúng phải đương đầu với bài toán “khó”. (iv). Nếu thám mã biết khóa công khai và bản mã C, thì việc tìm ra bản rõ P cũng là bài toán “khó”, số phép thử là vô cùng lớn, không khả thi. Nhược điểm: Hệ mã hóa khóa công khai: mã hóa và giải mã chậm hơn hệ mã hóa khóa đối xứng. 4/. Nơi sử dụng hệ mã hóa khóa công khai. Hệ mã hóa khóa công khai thường được sử dụng chủ yếu trên các mạng công khai như Internet, khi mà việc trao đổi chuyển khóa bí mật tương đối khó khăn. Đặc trưng nổi bật của hệ mã hóa công khai là khóa công khai (public key) và bản mã (ciphertext) đều có thể gửi đi trên một kênh truyền tin không an toàn. Có biết cả khóa công khai và bản mã, thì thám mã cũng không dễ khám phá được bản rõ. Nhưng vì có tốc độ mã hóa và giải mã chậm, nên hệ mã hóa khóa công khai chỉ dùng để mã hóa những bản tin ngắn, ví dụ như mã hóa khóa bí mật gửi đi. Hệ mã hóa khóa công khai thường được sử dụng cho cặp người dùng thỏa thuận khóa bí mật của hệ mã hóa khóa riêng. 3.2. HỆ MÃ HÓA DES 3.2.1. Giới thiệu hệ mã hóa DES Hiện nay có nhiều hệ mã hóa đối xứng loại mới, mục này trình bày Chuẩn mã hóa dữ liệu DES (Data Encryption Standard). 15/05/1973, Ủy ban tiêu chuẩn quốc gia Mỹ (NBS) (được sự thẩm định của cục an ninh quốc gia (NAS) đã công bố một khuyến nghị về hệ mã hóa chuẩn: Hệ mã hóa phải có độ an toàn cao. Hệ mã hóa phải được định nghĩa đầy đủ và dễ hiểu. Độ an toàn của Hệ mã hóa phảo nằm ở khóa, không nằm ở thuật toán. Hệ mã hóa phải sẵn sàng cho mọi người dùng ở các lĩnh vực khác nhau. Hệ mã hóa phải xuất khẩu được. DES được ABM phát triển, là một cải biên của hệ mật LUCIPHER DES, nó được công bố lần đầu tiên vào ngày 17/03/1975. Sau nhiều cuộc tranh luận công khai, cuối cùng DES được công nhận như một chuẩn liên bang vào ngày 23/11/1976 và được công bố vào ngày 15/01/1977. Năm 1980, “Cách dùng DES” được công bố. Từ đó chu kỳ 5 năm DES được xem xét lại một lần bởi Ủy ban tiêu chuẩn Quốc gia Mỹ, lần gần đây nhất là năm 2004. Các giai đoạn mã hóa theo DES: Giai đoạn 1: Bản rõ chữ ====è Bản rõ số (Dạng nhị phân) Chia thành Giai đoạn 2: Bản rõ số ====è Các đoạn 64 bit rõ số Giai đoạn 3: 64 bít rõ số ====è 64 bít mã số Kết nối Giai đoạn 4: Các đoạn 64 bít Mã số ====è Bản mã số (Dạng nhị phân) Giai đoạn 5: Bản Mã số ====è Bản mã chữ. 3.2.2. Quy trình mã hóa DES Thuật toán DES tập trung thực hiện giai đoạn 3 của quy trình mã hóa. Đó là chuyển đổi bản rõ số với 64 bít thành bản mã với 64 bít. Sơ đồ: R0 Bản rõ: 64 bit L1 = R0 L2 = R1 L15 = R14 L16 = R15 Bản mã: 64 bit IP-1 R16=L15 f(R15, k16) R1= L0 f (R0, k1) R2 = L1 f (R1, k2) R15=L14 f (R14, k15) f f f L0 IP k1 k2 k16 3.2.2.2. Thực hiện mã hóa theo sơ đồ * Bản rõ là xâu x, bản mã là xâu y, khóa là xâu K, đều có độ dài 64 bit. * Thuật toán mã hóa DES thực hiện qua 3 bước chính như sau: Bước 1: Bản rõ x được hoán vị theo phép hoán vị IP, thành IP(x). IP(x) = L0R0, trong đó L0 là 32 bit đầu (Left), R0 là 32 bit cuối (Right). (IP(x) tách thành L0R0). Bước 2: Thực hiện 16 vòng mã hóa với những phép toán giống nhau. Dữ liệu được kết hợp với khóa thông qua hàm f: Li = Ri-1; Ri = Li-1 f(Ri-1, ki). Trong đó: là phép hoặc loại trừ của 2 xâu bít (Cộng theo modulo 2). K1, k2, …, k16 là các khóa con (48 bit) được tính từ khóa gốc K. Bước 3: Thực hiện phép hoán vị ngược IP-1 cho xâu: L16R16, thu được bản mã y. y = IP-1(L16R16). Lưu ý thứ tự bit L16 và R16 * Bảng hoán vị ban đầu IP: Bít 1 của IP(x) là bit 58 của x. Bít 2 của IP(x) là bit 50 của x. 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 *Bảng hoán vị cuối cùng IP-1 40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25 3.2.2.3. Tính các khóa con k1, k2,…, k16 từ khóa gốc K. Sơ đồ: K PC _ 1 D0 C0 LS1 LS1 D1 C1 k1 PC - 2 LS2 LS2 D2 C2 k2 PC - 2 …………………………………. LS16 LS16 L16 C16 k3 PC - 2 * Tính khóa ki (48 bit) 1). Khóa K là xâu dài 64 bit, trong đó 56 bit là khóa và 8 bit để kiểm tra tính chẵn lẻ nhằm phát hiện sai, các bit này không tham gia vào quá trình tính toán. Các bit kiểm tra tính chẵn lẻ nằm ở vị trí 8, 16, 24,…, 64 được xác định, sao cho mỗi byte chứa một số lẻ các số 1. Bởi vậy mỗi sai sót đơn lẻ được xác định trong mỗi nhóm 8 bit. 2). Tính khóa ki như sau: Với khóa K độ dài 64 bit, ta loại bỏ các bit kiểm tra tính chẵn lẻ, hoán vị 56 bit còn lại theo phép hoán vị PC–1: PC–1(K) = C0D0 Trong đó C0 là 28 bit đầu, D0 là 28 bit cuối cùng của PC-1(K) Với i = 1, 2, …, 16, ta tính: Ci = LSi (Ci-1), Di = LSi (Di-1). Trong đó: LSi là phép dịch chuyển vòng sang trái: Dịch 1 vị trí nếu i = 1, 2, 9, 16. Dịch 2 vị trí với những giá trị khác. Với i = 1, 2,…, 16. Khóa ki được tính theo phép hoán vị PC-2 từ CiDi: ki = PC-2 (CiDi) (48 bit). * Phép hoán vị PC-1 * Phép hoán vị PC-2 57 49 41 33 25 17 9 14 17 11 24 1 5 1 58 50 42 34 26 18 3 28 15 6 21 10 10 2 59 51 43 35 27 23 19 12 4 26 8 19 11 3 60 52 44 36 16 7 27 20 13 2 63 55 47 39 31 23 15 41 52 31 37 47 55 7 62 54 46 38 30 22 30 40 51 45 33 48 14 6 61 53 45 37 29 44 49 39 56 34 53 21 13 5 28 20 12 4 46 42 50 36 29 32 3.2.2.4. Tính hàm f(Ri-1, ki) Sơ đồ ki Ri-1 E E(Ri-1) + B1 B2 B3 B4 B5 B6 B7 B8 S1 S2 S3 S4 S5 S6 S7 S8 C1 C2 C3 C4 C5 C6 C7 C8 P f (Ri-1, ki) Tính hàm f(Ri-1, ki) Để cho đơn giản ta không ghi chỉ số i-1, i, mà mô phỏng cách tính f(R, k): 1). Mở rộng xâu R (32 bit) thành xâu 48 bit, theo hàm mở rộng E E: R(32 bit) --à E(R) (48 bit) E(R) gồm 32 bit cũ của R và 16 bit mới của R mới xuất hiện lần thứ 2. 2). Tính E(R) k, trong đó E(R) (48 bit) và k (48 bit). Kết quả gồm 8 xâu Bj, mỗi xâu Bj có 6 bit (8*6 = 48): B = B1 B2 B3 B4 B5 B6 B7 B8. 3). Tính Cj = Sj (Bj), j = 1, …. ,8. Dùng 8 bảng S1, S2, …, S8. Sj là bảng cố định với r*c số nguyên từ 0 ->15, (0 ≤ r ≤ 3, 0 ≤ c ≤ 15). Sj thể hiện việc thay thế mỗi Bj thành Cj (Cj là xâu 4 bit) theo quy tắc sau: Giả sử Bj = b1 b2 b3 b4 b5 b6 (6 bit) + b1 b6 xác định biểu diễn nhị phân của hàng r trong Sj (0 ≤ r ≤ 3). + b2 b3 b4 b5 xác định biểu diễn nhị phân của cột c trong Sj (0 ≤ c ≤ 15). Xâu Cj (4 bit) được định nghĩa là biểu diễn nhị phân của phần tử Sj (r,c). 4). Thực hiện 8 lần 3). Ta nhận được xâu C=C1 C2 … C8 (32 bit) Sau hoán vị P, cho kết quả P(R), đó chính là f(R, k). * Phép hoán vị mở rộng E: * Phép hoán vị P: 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 10 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 31 27 3 9 19 13 30 6 22 11 4 25 Các bảng S1, S2, …,S8: S1 1 6 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 1 0 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 1 1 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 S2 7 12 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10 0 1 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5 1 0 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15 1 1 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9 S3 13 18 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8 0 1 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1 1 0 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7 1 1 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12 19 24 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 8 0 1 13 8 11 5 6 15 0 3 1 7 2 12 1 10 14 9 1 0 10 6 9 0 12 11 4 13 15 1 3 14 5 2 8 4 1 1 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14 S4 S5 25 30 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9 0 1 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6 1 0 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14 1 1 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3 S6 31 36 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11 0 1 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8 1 0 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6 1 1 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13 37 42 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1 0 1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6 1 0 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2 1 1 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12 S7 S8 43 48 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7 0 1 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2 1 0 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8 1 1 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11 * Quy định lập bảng Sj: Mỗi hàng của S phải là một hoán vị của 0,1,…, 15. Không có bẳng S nào là hàm tuyến tính hay Apphin của các đầu vào của nó. Thay đổi 1 bit vào ở một bảng S, sẽ gây ra sự thây đổi ít nhất 2 bít ra của nó. Nếu 2 xâu vào của một bảng S giống nhau ở 2 bít đầu và 2 bít cuối, thì 2 xâu ra phải khác nhau ít nhất tại 2 bit. Nếu 2 xâu vào của một bảng S khác nhau ở 2 bit đầu và giống nhau ở 2 bit cuối, thì 2 xâu ra phải khác nhau. Với mỗi bảng S, nếu cố định 1 bit vào, xét giá trị của 2 bít ra nào đó, thì số các xâu vào tạo ra giá trị 0 ở bit ra đó cũng phải xấp xỉ bằng số các xâu vào tạo ra giá trị 1 ở bit ra đó. Quy trình giải mã DES Quy trình giải mã của DES tương tự như quy trình lập mã, nhưng theo dùng các khóa có thứ tự ngược lại: k16, k15,…, k1. Xuất phát (đầu vào) từ bản mã y, kết quả (đầu ra) là bản rõ x. Ví dụ Bản rõ: X= 0123456789ABCDEF = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 50 58 Bước 1: Bản rõ x được hoán vị theo phép hoán vị IP, thành IP(x). IP(x) = L0R0, trong đó L0 là 32 bit đầu (Left), R0 là 32 bit cuối (Right). (IP(x) tách thành L0R0). L0 = 1100 1100 0000 0000 1100 1001 1111 1111 (32 bit) R0 = 1111 0000 1010 1010 1111 0000 1010 1010 (32 bit). Ví dụ: Theo hoán vị IP, bit 1 của L0 là bit 58 của x, bit 2 của L0 là bit 50 của x. Bước 2: Thực hiện 16 vòng mã hóa với những phép toán giống nhau. Dữ liệu được kết hợp với khóa thông qua hàm f: Li = Ri-1 Ri = Li-1 f(Ri-1, ki), trong đó: k1, k2,…, k16 là các khóa con (48 bit) từ khóa gốc K. a). Tính khóa con k1 (48 bit) từ khóa gốc K = 133457799BBCDFF1 (64 bit) = 0001 0011 0011 0100 0101 0111 0111 1001 1001 1011 1011 1100 1101 1111 1111 0001. * Hoán vị PC-1: K-> C0D0 (Từ K qua PC-1, nhận được C0D0). C0 = 1111000 0110011 0010101 0101111 (28 bit) D0 = 0101010 1011001 1001111 0001111 (28 bit) C1 = LS1(C0) = 1110000 1100110 0101010 1011111 (28 bit) D1 = LS1(D0) = 1010101 0110011 0011110 0011110 (28 bit). * Hoán vị PC-2: C1D1 ->k1 (48 bit) k1 = 000110 110000 001011 101111 111111 000111 000001 110010 b). Tính hàm f(R0, k1). Theo bước 1: R0 = 1111 0000 1010 1010 1111 0000 1010 1010 (32 bit). 1). Mở rộng xâu R0 (32 bit) thành xâu E(R0) (48 bit), theo hàm mở rộng E: Hoán vị E: R0 -> E(R0): E(R0) = 011110 100001 010101 010101 011110 100001 010101 010101(48 bit). Theo a): k1 = 000110 110000 001011 101111 111111 000111 000001 110010 (48 bit). 2). Tính E(R0) k1 = B1 B2 B3 B4 B5 B6 B7 B8 (48 bit). 011000 010001 011110 111010 100001 100110 010100 100111 3). Tính C1 = S1 (B1), dùng bảng S1. S1 thể hiện việc thay thế B1 (6 bit) thành C1 (4 bit) theo quy tắc sau: B1 = b1 b2 b3 b4 b5 b6 = 011000 + b1 b6 = (00)2 = (00)10 = Hàng 0 trong S1. + b2 b3 b4 b5= (1100)2 = (12)10 = Cột 12 trong S1. Xâu C1 (4 bit) được định nghĩa là biểu diễn nhị phân của phần tử S1(0, 12). C1 = S1(0, 12) = (5)10 = (0101)2 Tương tự ta tính được Cj, j=2, 3,…, 8. 4). Thực hiện 8 lần 3). Ta nhận được xâu C = C1 C2…C8 (32 bit). C = 0101 1100 1000 0010 1011 0101 1001 0111 Sau hoán vị P, cho kết quả P(C), đó chính là f(R0, k1). f(R0, k1) = P(C) = 0010 0011 0100 1010 1010 1001 1011 1011 Bước 3: Kết quả là bản mã 85E813540F0AB405. Độ an toàn của Hệ mã hóa DES 1). Độ an toàn của Hệ mã hóa DES có liên quan đến các hàm Sj: Ngoại trừ các bằng S, mọi tính toán trong DES đều tuyến tính, tức là việc tính phép hoặc loại trừ của 2 đầu ra cũng giống như phép hoặc loại trừ của 2 đầu vào, rồi tính toán đầu ra. Các bảng S chứa đựng nhiều thành phần phi tuyến của hệ mật, là yếu tố quan trọng nhất đối với độ mật của hệ thống. Khi mới xây dựng hệ mật DES, thì tiêu chuẩn xây dựng các hộp S không được biết đầy đủ. Và có thể các hộp S này chứa các “cửa sập ” được giấu kín. Và đó cũng là một điểm đảm bảo tính bảo mật của hệ DES. 2). Hạn chế của DES chính là kích thước không gian khóa: Số khóa có thể là 256, không gian này là nhỏ để đảm bảo an toàn thực sự. Nhiều thiết bị chuyên dụng đã được đề xuất nhằm phục vụ cho phép tấn công với bản rõ đã biết. Phép tấn công này chủ yếu thực hiện theo phương pháp “vét cạn ”. Tức là với bản rõ x và bản mã y tương ứng (64 bit), mỗi khóa có thể đều được kiểm tra cho tới khi tìm được một khóa K thỏa mãn ek(x) = y. Chương 4: PHƯƠNG PHÁP THỐNG KÊ NGÔN NGỮ HỌC VÀ GIẢI THUẬT DI TRUYỀN ĐỂ DÒ TÌM KHÓA MẬT 4.1. TẦN XUẤT XUẤT HIỆN CỦA CÁC CHỮ CÁI TRONG BẢN RÕ TIẾNG ANH 4.1.1. Các kí tự hiếm gặp (Có tần suất xuất hiện thấp): z, q, j, x, k, v. Qua thống kê một số lượng lớn các thông báo (bản rõ) tiếng Anh, người ta thấy các kí tự sau rất ít gặp: z, q, j, x, k, v. Tổng xác xuất xuất hiện của chúng xấp xỉ 2,23 % (0,0223). Áp dụng tiêu chuẩn thống kê 3s, người ta chứng minh được rằng:với 8 byte rõ (đọc được) (theo cơ số 16), thì tổng số lần xuất hiện (tần số)các kí tự z, q, j, x, k, v không thể vượt quá 2. Nếu tổng đó lớn hơn 2, thì bytes đã cho là bytes mã (khó đọc được). Do đó trong thực hành có thể cho rằng trên văn bản ngắn không xuất hiện 1 trong các kí tự z, q, j, x, k, v. Bây giờ ta loại kí tự v ra, chỉ xét 5 kí tự còn lại z, q, j, x, k, thì tổng xác suất xuất hiện của 5 kí tự đó chỉ còn là p = p(z)+p(q)+p(j)+ p(x)+ p(k) ≥ 0,0123. Như vậy với 8 byte bản rõ (gồm các ký tự cơ số 16), thì tổng tần số xuất hiện của các kí tự z, q, j, x, k, không vượt quá 1 với xác suất sai là 0,005. Như vậy trong thực hành, với văn bản độ dài 8 byte (mã cơ số 16), thì có không quá 1 ký tự nêu trên có mặt trên 1 lần. Các kí tự hay gặp (Có tần suất xuất hiện cao). Ta xét bảng 21 chữ cái (theo mã cơ số 16) (không có z, q, j, x, k) để biểu diễn bản rõ: A1 = {a, b, c, d, e, f, g, h, i, l, m, n, o, p, r, s, t, u, v, w, y } = {61, 62, 63, 64, 65, 66, 67, 68, 69, 6C, 6D, 6E, 6F, 70, 72, 73, 74, 75, 76, 77, 79}. Trong thực hành khi kiểm tra một mẫu “ứng cử viên” (candidate) độ dài 8 bytes, mà có một kí tự không thuộc A1, thì ta có thể loại ngay mẫu đó cùng với khoá tương ứng. Bằng phương pháp này ta chỉ cần giải một khối mã (8 bytes), khoá nào cho kết quả giải mã là bản rõ, mà chỉ chứa ký tự thuộc A1 thì được giữ lại, và sẽ là khóa “ứng cử viên” phục vụ việc “lọc” khóa lần thứ 2. Nhờ nhận xét trên chúng ta có thể xây dựng thuật toán 1 để “lọc thô” (“lọc” lần 1). Với thuật toán này ta chỉ cần kiểm tra một khối mã (8 byte) là đủ để loại bỏ hay chấp nhận một khoá mật là đúng hay sai. Trong không gian khoá 2 56 ~ 1017 , thuật toán này có khả năng loại 92 % số khoá chắc chắn không phải là khoá đúng với xác xuất sai là 0,005. Số lượng khoá còn lại sẽ được “lọc” bởi thuật toán thứ 2. a). Tần suất xuất hiện 1 ký tự trong tiếng Anh. Bằng thống kê hàng ngàn văn bản khác nhau trong tiếng Anh, người ta thấy có 10 ký tự trong tiếng Anh xuất hiện nhiều nhất theo thứ tự như sau: ( È là ký tự giãn cách 2 từ). 1. È: 0,1809 2. e: 0,1250 3. t: 0,0925 4. a: 0,0804 5. o: 0,0760 6. i: 0,0726 7. n: 0,0709 8. s: 0,0654 9. r: 0,0612 10. h: 0,0549 Như vậy tần xuất xuất hiện các ký tự trong tập G1 = {È, e, t, a, o, i, n, s, r, h} tổng cộng là 0,8798 ~ 0,88 Nói cách khác, trong văn bản tiếng Anh độ dài N = 100, thì các ký tự trong tập G1 xuất hiện xấp xỉ 88 lần, các ký tự còn lại chỉ xuất hiện 12 lầṇ. b). Tần suất xuất hiện bộ 2 ký tự trong tiếng Anh. Trong tiếng Anh, có 15 bộ đôi (2 chữ cái) xuất hiện nhiều nhất là: 1. an: 0,0181 2. at: 0,0151 3. ed: 0,0132 4. en: 0,0153 5. er: 0,0213 6. es: 0,0136 7. he: 0,0305 8. in: 0,0230 9. on: 0,0183 10. or: 0,0128 11. re: 0,0190 12. st: 0,0122 13. te: 0,0130 14. th: 0,0321 15. ti: 0,0128 Tổng số lần xuất hiện của 15 bộ đôi đó là 0,2703 ~ 0,27 Nếu tính cả dấu cách (È), thì có thêm ba bộ đôi với tần suất xuất hiện như sau: 16. eÈ: 0,0202 17. sÈ: 0,0129 18. Èt: 0,0160 Như vậy tần xuất xuất hiện các ký tự trong tập gồm 18 bộ đôi xuất hiện nhiều nhất: G2 = {an, at, ed, en, er, es, he, in, on, or, re, st, te, th, ti, eÈ, sÈ, Èt } là 0, 3194 ~ 0, 32. Nói cách khác, trong văn bản tiếng Anh gồm 100 ký tự, thì số lần xuất hiện của các bộ đôi trong G2 là xấp xỉ 32. Nếu chúng xuất hiện ít đến mức nào đó, thì ta coi văn bản này không phải là bản rõ tiếng Anh tự nhiên. c). Cận dưới của tần suất xuất hiện 1 ký tự và bộ 2 ký tự trong tiếng Anh. G1 = {È, e, t, a, o, i, n, s, r, h } G2 = {an, at, ed, en, er, es, he, in, on, or, re, st, te, th, ti, eÈ, sÈ, Èt }. Dựa vào thống kê tần suất xuất hiện các ký tự trên hai tập chữ cái tiếng Anh G1 và G2, áp dụng tiêu chuẩn 3s với mức sai lầm (quyết định sai) a = 0, 005, người ta tìm được cận dưới ST, mà với nó trong một bản rõ bất kỳ độ dài N thì: Số lần xuất hiện các ký tự trong tập G1 và G2 không bé hơn ( ≥ ) ST. Nếu Số lần xuất hiện các ký tự trên bé hơn (<) ST, thì văn bản đó “khó ” hiểu được. Cận dưới ST đó là S(N) + T(N), trong đó S(N) = 0,88 N – 2,805 √ N (1) T(N) = 0,32 (N-1) – 1,399 √ (N -1) (2) S(N) + T(N) còn gọi là Hàm phù hợp (fitness), để “đo” sự gần gũi giữa các ký tự rõ với ký tự mã tương ứng. DÒ TÌM KHÓA BẰNG THỐNG KÊ NGÔN NGỮ HỌC VÀ THUẬT TOÁN GA Thuật toán: Input: Bản mã m độ dài N được mã hóa bằng Hệ mật DES. Output: Khóa mật k. Thuật toán gồm 2 giai đoạn :: Giai đoạn 1 “Lọc thô”: Loại 92 % số khoá chắc chắn không phải là khoá đúng. (Bằng phương pháp thống kê ngôn ngữ học) Giai đoạn 2: “Lọc” 8 % các khoá còn lại bằng thuật toán GA . Giai đoạn 1: Input: Bản mã m độ dài N được mã hóa bằng Hệ mật DES. Output: Là tập các khóa k Î K1 thỏa mãn tính chất F(k) > S(N) + T(N). (Ghi trong tập khóa K) 1/. Bước 1: Ta xét bảng chữ cái (theo mã cơ số 16) (không có z, q, j, x, k) để biểu diễn bản rõ: A1 = {a, b, c, d, e, f, g, h, i, l, m, n, o, p, r, s, t, u, v, w, y } = {61, 62, 63, 64, 65, 66, 67, 68, 69, 6C, 6D, 6E, 6F, 70, 72, 73, 74, 75, 76, 77, 79}. Trong thực hành khi kiểm tra một mẫu văn bản độ dài 8 byte, mà có một kí tự không thuộc A1, thì ta có thể loại ngay mẫu đó cùng với khoá để giải mã. Bằng phương pháp này ta chỉ cần giải một khối mã (8 bytes) của m, khoá nào cho kết quả giải mã là bản rõ, mà chỉ chứa ký tự thuộc A1 thì được giữ lại, và sẽ là khóa “ứng cử viên” phục vụ việc “lọc” khóa giai đoạn 2. Bước 2: “Lọc”các khóa trong tập K1. B1: Lấy khóa tuỳ ý k1 Î K1 . B2: Giải bản mã m bằng thuật toán DES và khóa k1. Kết quả là bản rõ r = D (m, k1). B3: Tính tần số xuất hiện của các ký tự thuộc G1 và kí hiệu là: f1, f2 , ... , f10 . Tính tần số xuất hiện của các cặp ký tự thuộc G2 và kí hiệu là f1,1, f1,2, … , f1,18. B4: Tính Độ phụ thuộc (fitness) theo bản rõ r = D (m, k1) là: F(k1) = ∑ i 10 fi + ∑ i 18 f 1, i B5: Nếu F(k1) > S(N) + T (N) thì k1 là khóa “ứng cử viên”. Kết quả: Là tập các khóa k Î K1 thỏa mãn tính chất F(k) > S(N) + T(N). Kết quả giai đoạn 1 có khả năng loại 92 % số khoá chắc chắn không phải là khoá đúng với xác xuất sai là 0,005. Gọi K là tập gồm 8 % các khoá còn lại sau lần “lọc” của giai đoạn 1. Ví dụ: Bản mã có độ dài N = 101. 1). Tính cận dưới ST = S(N) + T(N) = 61 + 18 = 79, trong đó: S(N) = S(101) = 0,88 * 101 - 2,8 * √ 101 ~ 89 – 28 = 61 T(N) = T(101) = 0,32 * (101 – 1) - 1,399 * √ (101-1) = 32 – 13, 99 ~ 32 – 14 = 18 Khoá ki được chấp nhận nếu: Độ phụ thuộc F(ki) = ∑ i 10 fi + ∑ i 18 f 1, i > S(N) + T(N) = 61 + 18 = 79. 2). Cho bản mã m, ta thử khóa k1 Î K1. Dùng DES với khóa k1 giải mã m, ta nhận được bản rõ: r = “77652077652061677265656420746F20656469746F7220 7468697320626F6F6B20666F722061207365636F6E6420 65646974696F6F207765206C6F6F6B656420666F727761 6420746F206120626974206F66207570646174696E6720 616E6420696E636C75”. Ta nhận được thống kê sau: + Tần số xuất hiện các ký tự trong G1 là 20: 20 lần 61: 6 65: 9 68: 2 69: 6 6E: 6 6F: 11 72: 4 73: 2 74: 7 Số lần xuất hiện các ký tự đơn trong G1 là S(N) = 73. + Tần số xuất hiện các cặp ký tự trong G2 là 616E: 1 lần 6174: 1 6564: 4 656E: 1 6572: 0 6573: 0 6574: 1 696E: 2 6F6E: 2 6F72: 2 7265: 1 7374: 0 7465: 0 7468: 1 7469: 2 6520: 1 7320: 1 2074: 3 Số lần xuất hiện các bộ đôi ký tự trong G2 là T(N) = 23. Độ phụ thuộc F(k1) = ∑ i10 fi + ∑ i18 f1, i > S(N) + T(N) = 73 + 23 = 96 > 79. Như vậy mẫu r là bản rõ có nghĩa. Giai đoạn 2 Input: Bản mã m độ dài N được mã hóa bằng Hệ mật DES. Output: Khóa mật k. Giai đoạn 2 cũng gồm có 2 bước. Bước 1 : Giống như trong giai đoạn 1. Bước 2 để “lọc” 8 % khóa còn lại (ghi trong tập khóa K) bằng thuật toán GA. Bước 2: B1: Chọn hàm đánh giá (Fitness) Fit. Chọn p là số chẵn. B2: Trong tập khóa K, chọn ngẫu nhiên bộ khóa gồm p khóa k1, k2, … , kp. (Ví dụ p=10). Dùng các khóa này để giải mã m, sẽ nhận được p “bản rõ” r1, r2, … , rp. Tính Độ phụ thuộc Fi = F(ki) =∑ i10 fi + ∑ i18 f 1, i cho từng khóa ki theo “bản rõ ” ri. B3: Chọn cách “lai ghép” 2 khóa với nhau. B4: Chọn cách “đột biến” cho mỗi khóa. B5: Nhận được bộ khóa gồm p khóa mới k11, k12, …, k1p. (Ví dụ p=10 khóa). B6: Dùng các khóa này để giải mã m, sẽ nhận được p “bản rõ” r11, r12, …, r1p. Tính Độ phụ thuộc F1i = F(k1i) cho từng khóa k1i theo “bản rõ” r1i. B7: Xác định p giá trị lớn nhất FT1, FT2, …, FTp trong số 2 p giá trị Fi và F1i. Tương ứng với p giá trị lớn nhất FT1, FT2, …, FTp là p khóa kt1, kt2, …, ktp. (Các khóa còn lại sẽ bị loại). B8: Kiểm tra sự hội tụ: Nếu F max = Max {FTi / i = 1, 2, …, p} ≥ Fit thì tương ứng với Fmax ta Tính được khóa k cần tìm. Nếu Fmax = < Fit thì quay trở lại thực hiện từ B3. Ví dụ: “Lai ghép” 2 khóa Khóa “cha” kA= {10001 …….101}. Khóa “mẹ” kB= {01101 …….111} gồm 56 bit. Hai khóa “con” được sinh ra như sau: Chọn ngẫu nhiên một vị trí i (1 ≤ i ≤ 56), sau đó hoán vị bit thứ i của khóa “cha” và “mẹ”. Ví dụ nếu chọn i = 2, thì Khóa “con” 1 là AB1 = {010001 …….101}.Khóa “con” 2 là AB2 = {001101 …….111}. Ví dụ: “Đột biến” 1 khóa Khóa “gốc” kX = {10001 …….101}, gồm 56 bit. Khóa “đột biến” được sinh ra như sau: Chọn ngẫu nhiên một vị trí i (1 ≤ i ≤ 56), sau đó thay đổi giá trị bit thứ i của khóa “gốc”. Ví dụ nếu chọn i = 4, thì khóa “đột biến” là kY = {10011 …….101}. KẾT LUẬN Thuật giải di truyền (GA) là kỹ thuật chung giúp giải quyết bài toán bằng cách mô phỏng sự tiến hóa của con người, hay của sinh vật nói chung (dựa trên thuyết tiến hóa muôn loài của Darwin) trong điều kiện quy định sẵn của môi trường. GA là một thuật giải, nghĩa là mục tiêu của GA không nhằm đưa ra lời giải chính xác mà là đưa ra lời giải tương đối tối ưu. Kết quả chính của đồ án tốt nghiệp là tìm hiểu và nghiên cứu qua tài liệu để hệ thống lại các vấn đề sau: 1/. Tính toán mềm 2/. Giải thuật di truyền. 3/. Hệ mã hóa dữ liệu DES. 4/. Phương pháp thống kê ngôn ngữ học và giải thuật di truyền để dò tìm khóa mật. TÀI LIỆU THAM KHẢO Hồ Văn Canh, Trịnh Nhật Tiến, Đào Ngọc Phong. “Thử nghiệm ứng dụng giải thuật di truyền để dò tìm khóa mã thay thế đơn”. Data Structures + Algorithms = Programings. Statistical Distributions of E.Text The online literature library. www.genetic-programming.com Tính toán mềm và ứng dụng – Nguyễn Như Phong – NXB KHKT. www.ittk.ac.in/kangal. www.math.princeton.edu.