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

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