MỞ ĐẦU DES (viết tắt của Data Encryption Standard, hay Chuẩn mã hóa dữ liệu) là một hệ mật mã khóa đối xứng do Công ty IBM thiết kế dựa trên hệ mật mã do chính họ đã nghiên cứu trƣớc đó - hệ mật mã Lucifer và đƣợc FIPS (Tiêu chuẩn xử lý thông tin Liên bang Hoa Kỳ) chọn làm chuẩn chính thức vào năm 1976. Sau đó, Chuẩn này đƣợc sử dụng rộng rãi trên phạm vi thế giới. Ngay từ đầu, thuật toán của nó đã gây ra rất nhiều tranh luận liên quan đến các thành phần thiết kế mật, độ dài khóa tƣơng đối ngắn. Do đó, DES đã đƣợc giới nghiên cứu xem xét rất kỹ lƣỡng, việc này đã thúc đẩy hiểu biết hiện đại về mật mã khối (block cipher) và các phƣơng pháp tấn công (hay thám mã) tƣơng ứng.
Có thể nói, sự xuất hiện của DES đã tạo nên một làn sóng, một nguồn cảm hứng nghiên cứu trong giới khoa học về lĩnh vực mật mã học, đặc biệt là các phƣơng pháp thám mã mã khối. Với DES, giới khoa học đã có một thuật toán mật mã để nghiên cứu. Mặc dù trong thời gian qua đã có rất nhiều kết quả nghiên cứu về thám mã DES đã đƣợc công bố, DES có thể bị phá khoá bởi các hệ thống chuyên dụng trong vòng chƣa đầy 24 giờ, nhƣng việc nghiên cứu thám mã DES vẫn có ý nghĩa để hƣớng tới thám mã các hệ mật mã khối có độ dài khóa mật lớn hơn, đã và đang dần thay thế DES nhƣ AES, IDEA, 3 DES, RC4, RC5,. Phân tích mật mã hay thám mã còn đƣa ra những khuyến cáo, phản hồi cho các chuyên gia trong thiết kế lại các hệ mật mã để chống lại các dạng tấn công mới.
Đồng thời, nó cũng có ý nghĩa trong hỗ trợ công tác tình báo, phản gián v. Với lý do trên, tác giả chọn đề tài: “Nghiên cứu phƣơng pháp thám mã Chuẩn mật mã DES nhờ hệ thống tính toán hiệu năng cao”. Trong phạm vi nghiên cứu của đề tài này, bài toán đặt ra là với một bản mã đƣợc mã hoá từ một thông điệp tiếng Anh bởi Thuật toán mã hoá DES, với giả thiết ngƣời thám mã có thể truy cập đến chức năng mã hóa/giải mã của DES. Từ giả thiết này, yêu cầu ứng dụng hệ thống tính toán hiệu năng cao, thuật toán di truyền (Genetic Algorithm) để xây dựng thuật toán dạng thám mã “hộp đen” để tìm ra khoá mật đã sử dụng để mã hoá thông điệp đó trong thời gian ngắn (dự kiến khoảng 8 đến 15 phút).
Tác giả đã nghiên cứu, trình bày Luận văn thành ba chƣơng. Nội dung chính, kết quả nghiên cứu của các chƣơng nhƣ sau: Chƣơng I: Giới thiệu về chuẩn mã hoá dữ liệu - DES (Data Encryption Standard). Chƣơng II: Các phƣơng pháp thám mã Chuẩn mã hoá dữ liệu DES, các hệ thống chuyên dụng phục vụ thám mã DES. 1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chƣơng III: Nghiên cứu, đề xuất phƣơng pháp thám mã DES Do mức độ phức tạp của công việc thám mã là rất lớn nên bài toán đặt ra với giả thiết ngƣời thám mã biết đƣợc các thông tin về bản mã đƣợc mã hóa bởi DES (chế độ ECB) từ “bản rõ” tƣơng ứng là một thông điệp tiếng Anh.
Từ giả thiết này, xây dựng thuật toán di truyền để xác định khóa mật k đã sử dụng để mã hóa cũng nhƣ tìm ra “bản rõ” tƣơng ứng. Để giải quyết yêu cầu đặt ra và các bài toán nói trên, bài toán đƣợc chia thành các bài toán con để gải quyết vấn đề: - Xây dựng thuật toán nhận dạng “bản rõ” và “tiêu chuẩn bản rõ” là cơ sở xác định hàm “phù hợp”, một thành phần quan trọng của thuật toán di truyền nói chung và của thuật toán di truyền thám mã nói riêng. - Tìm hiểu về thuật toán di truyền, xây dựng thuật toán di truyền để thực hiện tìm kiếm khoá mật với phƣơng pháp “vét cạn có định hƣớng” trong không gian khoá (K2) xác định khoảng 209 tỷ khóa. Độ phức tạp của phƣơng pháp này chủ yếu phụ thuộc sự phán đoán, nhận dạng ngôn ngữ của “bản rõ” tƣơng ứng với bản mã và phụ thuộc độ dài của khóa (số lƣợng bit khóa), hoàn toàn không phụ thuộc vào thuật toán mã hóa khối mã của DES.
Vì vậy, để đạt đƣợc kết quả, mục tiêu nghiên cứu, tác giả đã sử dụng phƣơng pháp thống kê đặc trƣng ngôn ngữ và áp dụng thuật toán di truyền. Đề tài tập trung nghiên cứu, xây dựng thuật toán nhận dạng bản rõ và thuật toán di truyền. Đồng thời, tác giả đã đề xuất ứng dụng mô hình hệ thống tính toán song song, mô hình GA master - slave giúp rút ngắn thời gian thám mã khoảng 100 lần. Để đạt đƣợc kết quả thám mã một cách tốt nhất, đòi hỏi phải có đƣợc một hệ thống tính toán song song và kỹ năng lập trình song song.
Tuy nhiên, với điều kiện và khả năng thực tế, tác giả đã xây dựng dựng chƣơng trình thám mã thử nghiệm bằng ngôn ngữ Visual Basic .NET 2008 chạy trên một máy tính đơn, và giả định thuật toán di truyền hội tụ sau hai triệu thế hệ thì tổng thời gian thám mã ƣớc lƣợng khoảng 19,4 giờ. 2 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chƣơng I. GIỚI THIỆU VỀ CHUẨN MÃ HÓA DỮ LIỆU - DES (DATA ENCRYPTION STANDARD) [4] 1. GIỚI THIỆU VỀ THUẬT TOÁN MÃ HOÁ DES DES đƣợc phân biệt giữa hai khái niệm là Chuẩn mã hoá dữ liệu (DES - Data Encryption Standard) và Thuật toán mã hoá dữ liệu (DEA - Data Encryption Algorithm).
Thuật toán mã hoá là thành phần cơ bản của Chuẩn mã hoá. Việc nghiên cứu, phân tích về DES chính là nghiên cứu, phân tích về thuật toán của nó. Trong lĩnh vực mật mã học, có hai loại hệ mật mã thƣờng đƣợc đề cập đến, đó là mật mã khoá công khai (khoá bất đối xứng) và mật mã khoá bí mật (khoá đối xứng). Riêng đối với hệ mật mã đối xứng lại chia ra làm hai loại là mã hoá, giải mã theo khối và mã hoá, giải mã theo dòng.
DES (Data Encryption Standard) hay Chuẩn mã hóa dữ liệu thuộc hệ mật mã khoá đối xứng và thực hiện mã hoá, giải mã theo khối. Độ dài của khối thông tin mã hoá, giải mã là 64 bit. Quy trình mã hoá, giải mã khối gồm hai thuật toán là mã hoá (ký hiệu là E) và giải mã (ký hiệu là D). Cả hai thuật toán đều tác động lên một khối đầu vào 64 bit sử dụng khoá 56 bit để cho ra khối 64 bit.
Đối với bất kỳ khoá nào, giải mã là hàm ngƣợc của mã hoá, nghĩa là: - Mã hoá khối: Ek(M), - Giải mã khối: M = Dk(Ek(M)), trong đó, M là khối thông tin 64 bit và k là khoá 56 bit. Bản rõ 64 bit Bản mã 64 bit Khoá K Thuật toán mã hóa Thuật toán giải mã Khoá K 56 bit DES DES-1 56 bit Bản mã 64 bit Bản rõ 64 bit a. Quy trình mã hoá b. Quy trình giải mã Hình 1.
Mô phỏng sự mã hoá (a) và giải mã (b) theo DES 3 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. QUY TRÌNH MÃ HÓA THEO DES Quy trình mã hoá của mật mã khối nói chung và mã hoá theo DES nói riêng đƣợc thực hiện qua năm giai đoạn sau: Giai đoạn 1: “bản rõ” chữ “bản rõ” số (Dạng nhị phân) Các đoạn 64 bit Giai đoạn 2: “bản rõ” số Rõ số Giai đoạn 3: 64 bit Rõ số 64 bit Mã số Giai đoạn 4: Các đoạn 64 bit Mã số Bản Mã số (Dạng nhị phân) Giai đoạn 5: Bản Mã số Bản Mã chữ 1. LẬP MÃ VÀ GIẢI MÃ DES 1. Quy trình lập mã 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 bit thành bản Mã số với 64 bit. 4 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com “bản rõ”: 64 bit IP L0 R0 f k1 L1 = R0 R1 = L0 ⊕ f (R0, k1) k2 f L1 = R0 R2 = L1 ⊕ f (R1, k2) L15 = R14 R15 = L14 ⊕ f (R14, k15) f k16 R16 = L15 ⊕ f (R15, k16) L16 = R15 IP Bản mã: 64 bit Hình 1. Sơ đồ quy trình lập mã DES 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Thực hiện mã hóa DES 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 sau: Bƣớc 1: “bản rõ” x đƣợc hoán vị theo hoán vị IP, thành IP (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 đó: ⊕ là phép toán hoặc loại trừ của hai dãy bit (cộng theo modulo 2)., 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 R16L16, thu đƣợc bản mã y. * Hoán vị ban đầu IP + bit 1 của IP(x) là bit 58 của x 58 50 42 34 26 18 10 2 + bit 2 của IP(x) là bit 50 của x 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 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com * 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 1.
Tính các khóa con k1, k2, ., k16 từ khóa gốc K Sơ đồ K PC-1 C0 D0 LS1 LS1 C1 D1 PC-2 K1 LS2 LS2 C2 D12 PC-2 K2 LS16 LS16 C16 D16 PC-2 K16 Hình 1. Sơ đồ quy trình tính các khóa con k1, k2, ., k16 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com * Tính khóa ki (48 bit): - Khóa K là xâu 64 bit, trong đó 56 bit là khóa và 8 bit để kiểm tra 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, 32, 40, 48, 56, 64, sao cho mỗi byte chứa một số lẻ các bit 1.