Nghiên cứu phương pháp tấn công chuẩn mật mã khối (DES) nhờ hệ thống tính toán hiệu năng cao

  • Số trang: 76 |
  • Loại file: PDF |
  • Lượt xem: 29 |
  • Lượt tải: 0
tailieuonline

Đã đăng 27700 tài liệu

Mô tả:

MỤC LỤC Trang phụ bìa ..................................................................................................................... Lời cam đoan .................................................................................................................... i Lời cảm ơn .......................................................................................................................ii Mục lục .......................................................................................................................... iii Danh mục các từ viết tắt tiếng Anh ................................................................................ vi Danh mục các bảng .......................................................................................................vii Danh mục các hình vẽ, đồ thị ...................................................................................... viii MỞ ĐẦU ........................................................................................................................ 1 Chƣơng I. GIỚI THIỆU VỀ CHUẨN MÃ HÓA DỮ LIỆU DES (DATA ENCRYPTION STANDARD) ....................................................................................... 3 1.1. Giới thiệu về Thuật toán mã hoá DES .................................................................. 3 1.2. Quy trình mã hóa theo DES .................................................................................. 4 1.3. Lập mã và giải mã DES.......................................................................................... 4 1.3.1. Quy trình lập mã DES ....................................................................................... 4 1.3.2. Thực hiện mã hóa DES theo sơ đồ.................................................................... 6 1.3.3. Tính các khóa con k1, k2, ..., k16 từ khóa gốc K ................................................ 7 1.3.4. Tính hàm f(Ri-1, ki) ............................................................................................ 9 1.3.5. Quy trình giải mã DES .................................................................................... 12 1.3.6. Độ an toàn của Chuẩn mã hóa dữ liệu DES .................................................... 12 1.4. Các chế độ mã hóa của DES ................................................................................ 13 1.4.1. Chế độ bản mã cơ bản (EBC) ......................................................................... 13 1.4.2. Chế độ liên kết khối mã (CBC) ....................................................................... 14 Chƣơng II. CÁC PHƢƠNG PHÁP THÁM MÃ CHUẨN MÃ HÓA DỮ LIỆU DES, CÁC HỆ THỐNG CHUYÊN DỤNG PHỤC VỤ THÁM MÃ DES ............................ 15 2.1. Một số khái niệm cơ bản ...................................................................................... 15 2.2. Các phƣơng pháp thám mã ................................................................................. 16 2.2.1. Thám mã đƣờng tắt ......................................................................................... 16 2.2.1.1. Thám mã vi sai......................................................................................... 16 iii 2.2.1.2. Thám mã tuyến tính ................................................................................. 19 2.2.1.3. Thám mã phi tuyến .................................................................................. 19 2.2.1.4. Thám mã vi sai tuyến tính ....................................................................... 20 2.2.1.5. Một số phƣơng pháp thám mã đƣờng tắt khác ........................................ 20 2.2.2. Thám mã hộp đen (vét cạn để tìm khóa) ......................................................... 20 2.3. Các hệ thống chuyên dụng phục vụ thám mã .................................................... 21 2.3.1. Các phần cứng chuyên dụng ........................................................................... 21 2.3.2. Các hệ thống tính toán hiệu năng cao ............................................................. 22 Chƣơng III. NGHIÊN CỨU, ĐỀ XUẤT PHƢƠNG PHÁP THÁM MÃ DES............. 24 3.1. Mô tả bài toán thám mã DES .............................................................................. 24 3.1.1. Các giả thiết của bài toán ................................................................................ 24 3.1.2. Chi tiết hóa bài toán và các yếu tố đầu vào..................................................... 24 3.2. Xây dựng thuật toán nhận dạng bản rõ tiếng Anh ........................................... 25 3.2.1. Vai trò của nhận dạng bản rõ tự động trong thám mã “vét cạn” ................... 26 3.2.2. Một số phƣơng pháp nhận dạng bản rõ tự động ............................................. 26 3.2.2.1. Nhận dạng dựa vào từ điển ...................................................................... 26 3.2.2.2. Nhận dạng dựa trên tập hợp từ, cụm từ giả định ..................................... 27 3.2.2.3. Nhận dạng dựa vào phƣơng pháp thống kê đặc trƣng ngôn ngữ ............. 27 3.2.3. Xây dựng thuật toán nhận dạng bản rõ dựa vào phƣơng pháp thống kê đặc trƣng ngôn ngữ .......................................................................................................... 28 3.2.3.1. Một số khái niệm cơ sở về “bản rõ” ........................................................ 28 3.2.3.2. Thuật toán nhận dạng bản rõ ................................................................... 29 3.3. Tìm hiểu thuật toán di truyền (GAs) .................................................................. 36 3.3.1. Giới thiệu......................................................................................................... 36 3.3.2. Thuật toán di truyền nhị phân ......................................................................... 36 3.3.2.1. Thuật toán di truyền nhị phân - sự chọn lọc tự nhiên trên máy tính ....... 36 3.3.2.2. Các thành phần của thuật toán di truyền nhị phân ................................... 37 3.4. Đề xuất phƣơng pháp thám mã DES .................................................................. 46 3.4.1. Xây dựng thuật toán di truyền dò tìm khóa .................................................... 46 3.4.1.1. Xác định hàm phù hợp (hàm chi phí) ...................................................... 47 iv 3.4.1.2. Tạo lập họ khóa khởi tạo ......................................................................... 48 3.4.1.3. Giải mã bản mã cho trƣớc với các khóa trong họ .................................... 49 3.4.1.4. Tính mức độ phù hợp của các khóa ......................................................... 50 3.4.1.5. Chọn lọc ................................................................................................... 50 3.4.1.6. Ghép cặp .................................................................................................. 50 3.4.1.7. Kết hợp..................................................................................................... 51 3.4.1.8. Đột biến.................................................................................................... 51 3.4.1.9. Thế hệ tiếp theo ....................................................................................... 52 3.4.1.10. Kiểm tra hội tụ ....................................................................................... 53 3.4.2. Vai trò của hệ thống tính toán song song ........................................................ 53 3.4.3. Ƣớc lƣợng thời gian, độ phức tạp của tính toán ............................................. 56 KẾT LUẬN ................................................................................................................... 58 TÀI LIỆU THAM KHẢO ............................................................................................. 59 PHỤ LỤC 1. Bảng trọng số tần suất bộ đôi chữ cái tiếng Anh..................................... 60 PHỤ LỤC 2. Mã nguồn chƣơng trình thám mã DES áp dụng thuật toán di truyền chạy trên máy tính đơn ........................................................................................................... 61 v DANH MỤC CÁC TỪ VIẾT TẮT TIẾNG ANH Viết tắt DES Viết đầy đủ Nghĩa tiếng Việt Data Encryption Standard Chuẩn mã hoá dữ liệu Fast Data Encipherment Algorithm Thuật toán mã hóa dữ liệu nhanh AES Advanced Encryption Standard Chuẩn mã hoá tiến bộ IDEA International Algorithm 3 DES Triple Data Encryption Standard Một phiên bản mới của DES GA Genetic Algorithm Thuật toán di truyền ECB Electronic Codebook Chế độ mã hoá cơ bản CBC Cipher Block Chaining Chế độ mã hoá liên kết khối mã FEAL Data Encryption Thuật toán mã hoá dữ liệu quốc tế vi DANH MỤC CÁC BẢNG Số hiệu Tên bảng Trang Bảng 2.1 Tổng hợp về khả năng tấn công thám mã vi sai đối với DES 18 Bảng 3.1 Ví dụ về trình diễn mã hóa nhị phân 39 Bảng 3.2 Ví dụ về tiến trình ghép cặp và giao phối theo hình thức lai ghép điểm đơn 43 Bảng 3.3 Tính toán mức độ phù hợp của các khoá trong một thế hệ 50 vii DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Số hiệu Tên hình vẽ, đồ thị Trang Hình 1.1 Mô phỏng sự mã hoá (a) và giải mã (b) theo DES 3 Hình 1.2 Sơ đồ quy trình lập mã DES 5 Hình 1.3 Sơ đồ quy trình tính các khóa con k1, k2, ..., k16 7 Hình 1.4 Sơ đồ quy trình tính hàm f (Ri-1, ki) 9 Hình 1.5 Mã hóa và giải mã theo chế độ mã hóa cơ bản (EBC) 13 Hình 1.6 Mã hóa và giải mã theo chế độ liên kết khối mã (CBC) 14 Hình 2.1 So sánh mức an toàn giữa DES và AES dƣới góc độ thám mã vi sai 19 Hình 3.1 Mô tả giả thiết và bài toán thám mã DES 24 Hình 3.2 So sánh thám mã dựa trên nhận dạng bản rõ thủ công và nhận dạng bản rõ tự động 25 Hình 3.3 Mô phỏng về xác suất chuyển giữa hai chữ cái liền kề trong chữ viết tiếng Anh 28 Hình 3.4 Sự tƣơng tự giữa thuật toán di truyền và di truyền sinh học 36 Hình 3.5 Biểu đồ luồng của thuật toán di truyền nhị phân 37 Hình 3.6 Biểu diễn giao phối với hình thức lai ghép điểm đơn 42 Hình 3.7 Quy trình thám mã dựa trên thuật toán di truyền 46 Hình 3.8 Quy trình tạo lập tập khóa khởi tạo P (Npop) gồm 100 khóa 49 Hình 3.9 Mức độ tăng tốc theo lý thuyết của GA với Npop = 100 54 Hình 3.10 Mô hình của một GA song song master - slave 54 Hình 3.11 Số lƣợng bộ vi xử lý tối ƣu khi áp dụng mô hình GA master - slave theo tỷ lệ Tf/Tc và Npop viii 55 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.. 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 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 Chƣơng I. GIỚI THIỆU VỀ CHUẨN MÃ HÓA DỮ LIỆU - DES (DATA ENCRYPTION STANDARD) [4] 1.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. Khoá K 56 bit Bản rõ 64 bit Bản mã 64 bit Thuật toán mã hóa DES Thuật toán giải mã DES-1 Bản mã 64 bit Bản rõ 64 bit a. Quy trình mã hoá Khoá K 56 bit b. Quy trình giải mã Hình 1.1. Mô phỏng sự mã hoá (a) và giải mã (b) theo DES 3 1.2. 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ố Giai đoạn 2: “bản 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ố Giai đoạn 5: Bản Mã số Bản Mã chữ (Dạng nhị phân) Các đoạn 64 bit Rõ số (Dạng nhị phân) 1.3. LẬP MÃ VÀ GIẢI MÃ DES 1.3.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 “bản rõ”: 64 bit IP R0 L0 f k1 R1 = L0 ⊕ f (R0, k1) L1 = R0 f R2 = L1 ⊕ f (R1, k2) L1 = R0 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.2. Sơ đồ quy trình lập mã DES 5 k2 1.3.2. 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). 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 toán hoặc loại trừ của hai dãy bit (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 R16L16, thu đƣợc bản mã y. Y = IP-1 (R16L16). (Lƣu ý thứ tự bit R16 và L16). * 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 * 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.3.3. 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 LS2 LS2 C2 LS16 C16 D12 PC-2 K1 PC-2 K2 PC-2 K16 LS16 D16 Hình 1.3. Sơ đồ quy trình tính các khóa con k1, k2, ..., k16 7 * 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. Bởi vậy mỗi sai sót đơn lẻ đƣợc xác định trong mỗi nhóm 8 bit. - Tính khóa ki nhƣ sau: + Với khóa K có độ 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 chuyển dịch vòng 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ị i 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 8 1.3.4. Tính hàm f(Ri-1, ki) Ri-1 k1 32 bit E 48 bit E(Ri-1) 48 bit + B1 B2 B3 B4 B5 B6 B7 B8 S1 S2 S3 S4 S5 S6 S7 S8 C1 C2 C4 C5 C3 C6 C7 C8 P f (Ri-1, ki) Hình 1.4. Sơ đồ quy trình tính hàm f (Ri-1, ki) Để cho đơn giản, ta không ghi chỉ số i-1, i, và mô tả cách tính f(R, k): a) 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 của R xuất hiện lần thứ 2. b) Tính E(R) ⊕ k, trong đó E(R) (48 bit) và k (48 bit) Kết quả gồm 8 xâu Bj có 6 bit (8 * 6 = 48): B = B1 B2 B3 B4 B5 B6 B7 B8 9 c) 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) d) Thực hiện 8 lần c), ta nhận đƣợc xâu C = C1 C2 ... C8 (32 bit). Sau hoán vị P, cho kết quả P(C), đó chính là f(R, k). * Phép hoán vị mở rộng E 32 4 8 12 16 20 24 28 1 5 9 13 17 21 25 29 2 6 10 14 18 22 26 30 3 7 11 15 19 23 27 31 4 8 12 16 20 24 28 32 * Phép hoán vị P 5 9 13 17 21 25 29 1 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25 * Các bảng S1, S2, ..., S8: S1 1 0 0 1 1 6 0 1 0 1 0 14 0 4 15 1 4 15 1 12 2 13 7 14 8 3 1 4 8 2 4 2 14 13 4 5 15 2 6 9 6 11 13 2 1 7 8 1 11 7 8 3 10 15 5 9 10 6 12 11 10 6 12 9 3 11 12 11 7 14 12 5 9 3 10 13 9 5 10 0 14 0 3 5 6 15 7 8 0 13 12 0 1 0 1 0 15 3 0 13 1 1 13 14 8 2 8 4 7 10 3 14 7 11 1 4 6 15 10 3 5 11 2 4 15 6 3 8 13 4 7 4 14 1 2 8 9 12 5 11 9 7 0 8 6 10 2 1 12 7 11 13 10 6 12 12 12 6 9 0 13 0 9 3 5 14 5 11 2 14 15 10 5 15 9 S2 7 0 0 1 1 10 S3 1 0 0 1 1 6 0 1 0 1 0 10 13 13 1 1 0 7 6 10 2 9 0 4 13 3 14 9 9 0 4 6 3 8 6 5 3 4 15 9 6 15 6 3 8 7 5 10 0 7 8 1 2 11 4 9 13 8 1 15 10 12 5 2 14 11 7 14 12 3 12 11 12 5 11 13 4 11 10 5 14 2 15 14 2 15 8 1 7 12 6 0 1 0 1 0 7 13 10 3 1 13 8 6 15 2 14 11 9 0 3 3 5 0 6 4 0 6 12 10 5 6 15 11 1 6 9 0 7 13 7 10 3 13 8 8 1 4 15 9 9 2 7 1 4 10 8 2 3 5 11 5 12 14 11 12 11 1 5 12 13 12 10 2 7 14 4 14 8 2 15 15 9 4 14 6 0 1 0 1 0 2 14 4 11 1 12 11 2 8 2 4 2 1 12 3 1 12 11 7 4 7 4 10 1 5 10 7 13 14 6 11 13 7 2 7 6 1 8 13 8 8 5 15 6 9 5 0 9 15 10 3 15 12 0 11 15 10 5 9 12 13 3 6 10 13 0 9 3 4 14 14 8 0 5 15 9 6 14 3 6 0 1 0 1 0 12 10 9 4 1 1 15 14 3 2 10 4 15 2 3 15 2 5 12 4 9 7 2 9 5 2 12 8 5 6 6 9 12 15 7 8 5 3 10 8 0 6 7 11 9 13 1 0 14 10 3 13 4 1 11 4 14 10 7 12 14 0 1 6 13 7 11 13 0 14 5 3 11 8 15 11 8 6 13 6 0 1 0 1 0 4 13 1 6 1 11 0 4 11 2 2 11 11 13 3 14 7 13 8 4 15 4 12 1 5 0 9 3 4 6 8 1 7 10 7 13 10 14 7 8 3 14 10 9 9 12 3 15 5 10 9 5 6 0 11 7 12 8 15 12 5 2 0 14 13 10 15 5 2 14 6 8 9 3 15 1 6 2 12 6 0 1 0 1 0 13 1 7 2 1 2 15 11 1 2 8 13 4 14 3 4 8 1 7 4 6 10 9 4 5 15 3 12 10 6 11 7 14 8 7 1 4 2 13 8 10 12 0 15 9 9 5 6 12 10 3 6 10 9 11 14 11 13 0 12 5 0 15 3 13 0 14 3 5 14 12 9 5 6 15 7 2 8 11 S4 1 0 0 1 1 S5 1 0 0 1 1 S6 1 0 0 1 1 S7 1 0 0 1 1 S8 1 0 0 1 1 11 * Quy định lập bảng Sj: - Mỗi hàng của bảng 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ự thay đổi ít nhất 2 bit ra của nó. - Nếu 2 xâu vào của một bảng S giống nhau ở 2 bit đầu và 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 1 bit 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 đó. 1.3.5. 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 sử dụng các khóa theo thứ tự ngƣợc lại: k16, k15, ..., k1. Xuất phát từ bản mã Y (đầu vào), kết quả là “bản rõ” X (đầu ra). 1.3.6. Độ an toàn của Chuẩn mã hóa DES a) Độ an toàn của Chuẩn mã hóa DES có liên quan đến các bảng 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 hai đầu ra cũng giống nhƣ phép hoặc loại trừ của hai đầ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 độ an toàn 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 có thể 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 an toàn của hệ mật DES. b) 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ụ tấn công với một cặp “bản rõ” - bản mã đã 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 12 “bản rõ” X và bản mã Y tƣơng ứng (64 bit), mỗi khóa có thể đƣợc kiểm tra cho tới khi tìm đƣợc một khóa K thỏa mãn ek(X) = Y. 1.4. CÁC CHẾ ĐỘ MÃ HÓA DES [15] Các hệ mật mã khối nói chung và chuẩn mã hóa khối DES có 6 (sáu) chế độ mã hóa chính, gồm chế độ mã hoá cơ bản (ECB - electronic codebook mode), chế độ liên kết khối mã (CBC - cipher block chaining mode), chế độ phản hồi mã (CFB - cipher feedback mode), PCBC (propagating cipher-block chaining), OFB (output feedback), CTR (counter). Trong đó, chế độ mã hóa cơ bản ECB là đơn giản nhất. Dƣới đây là sơ đồ mô tả chế độ mã hoá cơ bản và chế độ mã hoá liên kết khối mã. 1.4.1. Chế độ mã cơ bản (ECB - electronic codebook) Bản rõ Khoá Mã hoá mã khối Bản rõ Khoá Bản mã Mã hoá mã khối Bản rõ Khoá Bản mã Mã hoá mã khối Bản mã a. Mã hoá Bản mã Khoá Giải mã mã khối Bản rõ Bản mã Khoá Giải mã mã khối Bản rõ Bản mã Khoá Giải mã mã khối Bản rõ b. Giải mã Hình 1.5. Mã hóa (a) và giải mã (b) theo chế độ mã cơ bản (ECB) 13 1.4.2. Chế độ liên kết khối mã (CBC - cipher block chaining) Bản rõ Bản rõ Bản rõ Vector khởi tạo (Initialization Vector – IV) Khoá Mã hoá mã khối Khoá Bản mã Mã hoá mã khối Khoá Mã hoá mã khối Bản mã Bản mã Bản mã Bản mã a. Mã hoá Bản mã Vector khởi tạo (Initialization Vector – IV) Khoá Giải mã mã khối Khoá Bản rõ Giải mã mã khối Bản rõ Khoá Giải mã mã khối Bản rõ b. Giải mã Hình 1.6. Mã hóa (a) và giải mã (b) theo chế độ liên kết khối mã (CBC) DES có thể áp dụng một trong các chế độ mã hoá nhƣ đã nói trên. Nhƣng để giới hạn phạm vi nghiên cứu của đề tài, khi thực hiện hiện công việc thám mã đƣơng nhiên chúng ta giả định bản mã cho trƣớc đƣợc mã hóa bởi chuẩn mã hóa DES, đồng thời cũng giả định rằng bản mã đƣợc mã hóa theo chế độ mã cơ bản (ECB). Tức là “bản rõ” đƣợc chia nhỏ thành các khối độc lập, mỗi khối 64 bit. Mỗi khối này đƣợc mã hóa bởi cùng một khóa k nào đó để tạo ra các khối mã 64 bit độc lập. Ngày nay, Thuật toán mã hóa dữ liệu (DEA - Data Encryption Algorithm) của Chuẩn mã hóa dữ liệu DES đã đƣợc công bố chi tiết, cho nên các chƣơng trình mã hóa DES, các thƣ viện mã nguồn mở vể DES đƣợc công bố rộng rãi. Phụ lục 1 của Luận văn là một ví dụ về sử dụng Thƣ viện mã nguồn mở Chilkat.Crypt2 về DES để thực hiện mã hóa, giải mã một thông điệp, với các chế độ mã hóa cơ bản (ECB), chế độ mã hóa liên kết khối mã (CBC). 14
- Xem thêm -