Luận Văn: Nghiên Cứu Xây Dựng Thuật Toán Mã Khối An Toàn Và Hiệu Quả

Luận văn nghiên cứu xây dựng thuật toán mã khối an toàn hiệu quả, tập trung vào phát triển giải pháp bảo mật tối ưu cho hệ thống thông tin hiện đại.

• Người hướng dẫn: Ts. Trần Văn Trường
• Chuyên ngành: Bảo mật và phát triển công nghệ thông tin
• Đề tài: Nghiên cứu xây dựng thuật toán mã khối an toàn và hiệu quả
• Loại tài liệu: Báo cáo kết quả nghiên cứu
• Năm xuất bản: 2004
• Địa điểm: Hà Nội

Tóm tắt

I. Giới thiệu về thuật toán mã khối

Thuật toán mã khối là một phần quan trọng trong lĩnh vực bảo mật thông tin và mã hóa dữ liệu. Chương này giới thiệu tổng quan về các hệ mã khối, bao gồm các khái niệm cơ bản như hệ mã khối khóa bí mật, độ an toàn của các hệ mã khối, và các nguyên lý thiết kế mã khối. Các hệ mã khối được chia thành hai loại chính: hệ mã khối và hệ mã dòng, trong đó mã khối xử lý dữ liệu theo từng khối lớn, thường là 128-bit. Ưu điểm của mã khối là khả năng chuẩn hóa dễ dàng và độ chính xác cao trong quá trình giải mã.

1.1. Hệ mã khối khóa bí mật

Hệ mã khối khóa bí mật yêu cầu người gửi và người nhận chia sẻ một khóa bí mật chung. Khóa này được sử dụng để mã hóa và giải mã dữ liệu. Mô hình Shannon được sử dụng để mô tả quá trình này, trong đó khóa bí mật được phân phối qua kênh an toàn. Hệ mã khối khóa bí mật được coi là an toàn nếu thám mã không thể truy cập được khóa bí mật.

1.2. Độ an toàn của các hệ mã khối

Độ an toàn của các hệ mã khối được đánh giá dựa trên khả năng chống lại các tấn công thám mã. Các tấn công phổ biến bao gồm tấn công chỉ biết bản mã, tấn công bản rõ đã biết, và tấn công bản rõ lựa chọn. Độ an toàn vô điều kiện và độ an toàn tính toán là hai khái niệm quan trọng trong việc đánh giá độ an toàn của các hệ mã khối.

II. Các cấu trúc mã khối cơ bản

Chương này tập trung vào các cấu trúc mã khối cơ bản, bao gồm cấu trúc Feistel, cấu trúc Matsui, và cấu trúc cộng-nhân. Các cấu trúc này là nền tảng cho việc thiết kế các thuật toán mã khối hiện đại. Cấu trúc Feistel là một trong những cấu trúc phổ biến nhất, được sử dụng trong nhiều thuật toán mã khối như DES. Cấu trúc này chia dữ liệu thành hai nửa và áp dụng các hàm vòng để mã hóa.

2.1. Cấu trúc Feistel

Cấu trúc Feistel chia dữ liệu thành hai nửa và áp dụng các hàm vòng để mã hóa. Mỗi vòng sử dụng một khóa con khác nhau, đảm bảo tính bảo mật cao. Cấu trúc này được sử dụng rộng rãi trong các thuật toán mã khối như DES và Blowfish.

2.2. Cấu trúc Matsui

Cấu trúc Matsui là một biến thể của cấu trúc Feistel, được thiết kế để tăng cường độ an toàn của các thuật toán mã khối. Cấu trúc này sử dụng các phép biến đổi phức tạp hơn để đảm bảo tính bảo mật cao hơn.

III. Thám mã và các tấn công phổ biến

Chương này phân tích các phương pháp thám mã và các tấn công phổ biến đối với các hệ mã khối. Các tấn công được đề cập bao gồm thám mã vi sai, thám mã tuyến tính, và thám mã phi tuyến. Thám mã vi sai là một phương pháp tấn công mạnh, đặc biệt hiệu quả đối với các hệ mã khối lặp như DES. Thám mã tuyến tính sử dụng các xấp xỉ tuyến tính để tìm ra khóa bí mật.

3.1. Thám mã vi sai

Thám mã vi sai là một phương pháp tấn công dựa trên sự khác biệt giữa các bản rõ và bản mã. Phương pháp này đặc biệt hiệu quả đối với các hệ mã khối lặp như DES. Thám mã vi sai yêu cầu một số lượng lớn các cặp bản rõ/bản mã để tìm ra khóa bí mật.

3.2. Thám mã tuyến tính

Thám mã tuyến tính sử dụng các xấp xỉ tuyến tính để tìm ra khóa bí mật. Phương pháp này dựa trên việc tìm kiếm các mối quan hệ tuyến tính giữa các bit của bản rõ và bản mã. Thám mã tuyến tính đòi hỏi một số lượng lớn các phép tính toán nhưng có thể hiệu quả đối với các hệ mã khối yếu.

IV. Khảo sát các đặc trưng của mã khối

Chương này khảo sát các đặc trưng của mã khối dựa trên các độ đo giải tích. Các đặc trưng được đề cập bao gồm hộp thế, hàm vòng, và độ an toàn thực tế của các hệ mã khối. Hộp thế là một thành phần quan trọng trong các hệ mã khối, đảm bảo tính phi tuyến và độ an toàn cao. Hàm vòng là các phép biến đổi được áp dụng trong mỗi vòng mã hóa, đảm bảo tính bảo mật của hệ mã.

4.1. Hộp thế trong mã khối

Hộp thế là một thành phần quan trọng trong các hệ mã khối, đảm bảo tính phi tuyến và độ an toàn cao. Hộp thế thực hiện các phép thay thế phi tuyến trên các bit dữ liệu, làm tăng độ phức tạp của quá trình thám mã.

4.2. Hàm vòng trong các mã khối lặp

Hàm vòng là các phép biến đổi được áp dụng trong mỗi vòng mã hóa, đảm bảo tính bảo mật của hệ mã. Các hàm vòng thường sử dụng các phép toán như XOR, cộng, và nhân để tạo ra các biến đổi phức tạp trên dữ liệu.

V. Xây dựng thuật toán mã khối MK_KC 01 01

Chương này trình bày quá trình xây dựng thuật toán mã khối MK_KC-01-01, một thuật toán được thiết kế để đảm bảo độ an toàn và hiệu quả cao. Thuật toán này bao gồm các thành phần chính như phần ngẫu nhiên hóa dữ liệu, lược đồ khóa, và các thông số an toàn lý thuyết và thực nghiệm. Thuật toán MK_KC-01-01 được thiết kế để chống lại các tấn công thám mã phổ biến và đảm bảo tính bảo mật cao.

5.1. Phần ngẫu nhiên hóa dữ liệu

Phần ngẫu nhiên hóa dữ liệu là một thành phần quan trọng trong thuật toán MK_KC-01-01, đảm bảo tính ngẫu nhiên và độ an toàn cao. Phần này sử dụng các tham số cụ thể để tạo ra các biến đổi ngẫu nhiên trên dữ liệu, làm tăng độ phức tạp của quá trình thám mã.

5.2. Lược đồ khóa

Lược đồ khóa trong thuật toán MK_KC-01-01 được thiết kế để đảm bảo tính bảo mật cao. Lược đồ này sử dụng các phép biến đổi phức tạp trên khóa để tạo ra các khóa con, đảm bảo tính an toàn của hệ mã.

Trích đoạn nội dung tài liệu

Ch−¬ng tr×nh KC-01: §Ò tµi KC-01-01: Nghiªn cøu khoa häc Nghiªn cøu mét sè vÊn ®Ò b¶o mËt vµ ph¸t triÓn c«ng nghÖ th«ng tin an toµn th«ng tin cho c¸c m¹ng dïng vµ truyÒn th«ng giao thøc liªn m¹ng m¸y tÝnh IP B¸o c¸o kÕt qu¶ nghiªn cøu §¶m b¶o to¸n häc cho c¸c hÖ mËt QuyÓn 3C: “Nghiªn cøu x©y dùng thuËt to¸n m· khèi an toµn hiÖu qu¶” Hµ NéI-2004 B¸o c¸o kÕt qu¶ nghiªn cøu §¶m b¶o to¸n häc cho c¸c hÖ mËt QuyÓn 3C: “Nghiªn cøu x©y dùng thuËt to¸n m· khèi an toµn hiÖu qu¶” Chñ tr× nhãm nghiªn cøu T.S TrÇn V¨n Tr−êng Môc lôc Sè trang ch−¬ng 1: Më ®Çu vÒ m· khèi 1 I. Giíi thiÖu chung 1 1. HÖ m· khèi kho¸ bÝ mËt 1 2. §é an toµn cña c¸c hÖ m· khèi 3 3.

Nguyªn lý thiÕt kÕ m· khèi 9 4. C¸c m· khèi lÆp 10 II. C¸c cÊu tróc m· khèi c¬ b¶n 11 1. CÊu tróc m· Feistel 11 2.

CÊu tróc Matsui 13 3. CÊu tróc céng-nh©n 15 4. Giíi thiÖu mét sè lo¹i h×nh m· khèi 15 ch−¬ng 2: Th¸m m· khèi 19 I. Th¸m m· vi sai ®èi víi DES vµ c¸c hÖ m· khèi lÆp DES-like 19 1.

Th¸m m· vi sai ®èi víi c¸c m· khèi lÆp 19 3. S¬ bé vÒ tÊn c«ng vi sai trªn DES 25 II. Th¸m m· tuyÕn tÝnh ®èi víi hÖ DES 30 1. Nguyªn lý chung cña ph−¬ng ph¸p th¸m m· tuyÕn tÝnh 30 2.

XÊp xØ tuyÕn tÝnh c¸c hép nÐn 33 3. XÊp xØ tuyÕn tÝnh hÖ m· DES 35 4. TÊn c«ng b¶n râ ®· biÕt ®èi víi DES 39 III. Th¸m m· phi tuyÕn 40 1.

ThiÕt lËp c¸c quan hÖ bËc hai cña S-hép 41 2. ¸p dông vµo th¸m m· phi tuyÕn 42 3. Sö dông xÊp xØ tuyÕn tÝnh nhiÒu lÇn 43 4. ¸p dông tæ hîp xÊp xØ nhiÒu lÇn vµ xÊp xØ phi tuyÕn ®Ó tÊn c«ng DES 44 5.

ThuËt to¸n c¶i tiÕn ®Ó tÊn c«ng DES 16-vßng 45 6. Thùc hµnh tÊn c«ng phi tuyÕn víi DES t×m ®ñ 56 bÝt kho¸ 46 IV. TÊn c«ng vi sai bËc cao 52 1. TÊn c«ng sö dông vi sai bËc cao 53 -iii- V.

TÊn c«ng néi suy 56 VI. TÊn c«ng kho¸ quan hÖ 60 VII. C¸c ®Æc tr−ng an toµn c¬ b¶n cña hÖ m· khèi 66 ch−¬ng 3: kh¶o s¸t hÖ m· khèi an toµn theo c¸c ®Æc tr−ng 68 ®é ®o gi¶i tÝch I. Hép thÕ trong m· khèi 69 1.

Mét sè ®« ®o phi tuyÕn cña hép thÕ 69 2. Kh¶o s¸t mét sè líp hµm cô thÓ 73 II. Hµm vßng trong c¸c m· khèi lÆp 78 1. C¸c ®é ®o an toµn cña hµm vßng phô thuéc kho¸ 78 2.

Mét sè d¹ng hµm vßng an toµn-chøng minh ®−îc 83 III. §é an toµn thùc tÕ cña m· Feistel 88 1. §é an toµn thùc tÕ cña cÊu tróc Feistel (cÊu tróc ngoµi cïng) 88 2. Mét kiÓu thiÕt kÕ hµm vßng 2-SPN (cÊu tróc gi÷a) 90 IV.

L−îc ®å kho¸, c¸c phÐp biÕn ®æi ®Çu vµo ®Çu ra 91 cña hÖ m· khèi 1. Ph©n lo¹i l−îc ®å kho¸ cña c¸c hÖ m· khèi 91 2. Mét sè l−îc ®å kho¸ m¹nh 94 3. ViÖc sö dông ho¸n vÞ trong c¸c hµm vßng, c¸c phÐp 95 biÕn ®æi ®Çu vµo ®Çu ra cña mét hÖ m· khèi ch−¬ng 4: kh¶o s¸t m· khèi theo nhãm sinh cña c¸c 97 hµm m· ho¸ I.

Nhãm sinh cña c¸c hµm m· ho¸ 98 II. Mét sè tÝnh chÊt c¬ b¶n cña G 98 1. Nhãm con bÊt ®éng trªn mét tËp 98 2. TÝnh ph¸t t¸n cña G 98 3.

TÝnh nguyªn thuû cña G 98 III. Quan hÖ gi÷a c¸c tÝnh chÊt c¬ b¶n cña G víi tÝnh 101 an toµn cña hÖ mËt 1. TÝnh yÕu cña c¸c m· khèi cã G lµ kh«ng nguyªn thuû 102 IV. Mét sè ®iÒu kiÖn ®ñ ®Ó nhãm c¸c phÐp thÕ cã tÝnh 103 ph¸t t¸n vµ nguyªn thuû -iii- V.

Mét sè ph©n tÝch thªm vÒ tÝnh t-ph¸t t¸n 105 1. Kh¸i niÖm t-ph¸t t¸n m¹nh 105 2. Mét sè tÝnh chÊt 107 ch−¬ng 5: kh¶o s¸t c¸c ®Æc tr−ng cña m· khèi 112 theo quan ®iÓm xÝch markov I. Mét sè c¬ së to¸n häc 112 1.

§å thÞ ngÉu nhiªn 115 II. MËt m· Markov vµ th¸m l−îng sai 116 1. Th¸m l−îng sai 121 III. Th¸m tuyÕn tÝnh 132 1.

XÝch ®Ó th¸m tuyÕn tÝnh 134 2. TÝnh ergodic ®èi víi c¸c hµm vßng ngÉu nhiªn 135 IV. MËt m· Markov vµ c¸c nhãm lu©n phiªn 136 1. C¸c ®iÒu kiÖn lý thuyÕt nhãm cho hµm mét vßng 136 2.

øng dông cho DES 137 3. øng dông cho IDEA 137 V. KÕt luËn 138 ch−¬ng 6: x©y dùng thuËt to¸n m· khèi MK_KC-01-01 140 I. PhÇn ngÉu nhiªn ho¸ d÷ liÖu 140 1.

C¸c tham sè cô thÓ 143 II. PhÇn l−îc ®å kho¸ 144 III. C¸c th«ng sè an toµn lý thuyÕt vµ thùc nghiÖm 145 Phô lôc A: Listing ch−¬ng tr×nh th¸m m· DES-8 vßng 147 Phô lôc B: Listing ch−¬ng tr×nh thuËt to¸n m· khèi 165 MK_KC-01-01 Tµi liÖu tham kh¶o 176 -iii- Ch−¬ng 1: Më ®Çu vÒ M· KHèI I. Giíi thiÖu chung I.

HÖ m· khèi khãa bÝ mËt Mét khèi l−îng lín c¸c th«ng tin ®−îc truyÒn trªn c¸c kªnh th«ng tin vµ m¹ng m¸y tÝnh hiÖn nay ®ang ngµy cµng gia t¨ng ®Æc biÖt ®ßi hái cÇn ph¶i ®−îc b¶o vÖ khái c¸c dß dØ kh«ng mong muèn, tøc lµ ®¶m b¶o tÝnh bÝ mËt, ®ång thêi còng cÇn ph¶i ®−îc b¶o vÖ tr¸nh sù gi¶ m¹o vµ sù tõ chèi tr¸ch nhiÖm, tøc lµ ®¶m b¶o tÝnh x¸c thùc. Kü thuËt mËt m· ®−îc ph¸t triÓn vµ vËn dông ®Ó ®¶m b¶o c¶ tÝnh bÝ mËt vµ tÝnh x¸c thùc ®ã. C¸c hÖ mËt hiÖn nay ®−îc chia thµnh hai lo¹i: hÖ mËt khãa bÝ mËt vµ hÖ mËt khãa c«ng khai. Trong hÖ mËt khãa bÝ mËt, nh÷ng ng−êi sö dông hîp ph¸p (ng−êi göi vµ ng−êi nhËn) ph¶i chia sÎ mét khãa bÝ mËt chung vµ khãa ®ã kh«ng ®−îc biÕt ®èi víi th¸m m· ®èi ph−¬ng.

Trong hÖ mËt khãa c«ng khai, ng−êi sö dông hîp ph¸p chØ cÇn c¸c th«ng tin trung thùc c«ng khai nµo ®ã. MÆc dï c¸c hÖ mËt khãa c«ng khai tá ra lµ lý t−ëng ®èi víi nhiÒu øng dông mËt m·, nh−ng tèc ®é thÊp vµ gi¸ thµnh cao ®· ng¨n c¶n viÖc sö dông chóng trong nhiÒu tr−êng hîp. Trong phÇn nµy chóng ta chØ th¶o luËn vÒ c¸c hÖ mËt khãa bÝ mËt. Chóng ta sÏ sö dông m« h×nh hÖ mËt cña Shannon trong H×nh 1.

Trong m« h×nh nµy, khãa bÝ mËt Z ®−îc ph©n phèi tíi ng−êi göi vµ ng−êi nhËn theo mét kªnh an toµn. Khãa nµy sau ®ã ®−îc sö dông ®Ó m· hãa b¶n râ X thµnh b¶n m· Y bëi ng−êi göi vµ ®−îc dïng ®Ó gi¶i m· b¶n m· Y thµnh b¶n râ X bëi ng−êi nhËn. B¶n m· ®−îc truyÒn trªn kªnh kh«ng an toµn, vµ chóng ta gi¶ thiÕt lµ th¸m m· ®èi ph−¬ng lu«n cã thÓ truy nhËp ®Ó nhËn ®−îc c¸c b¶n m·. TÊt nhiªn th¸m m· kh«ng thÓ truy nhËp ®−îc tíi khãa bÝ mËt.

HÖ mËt khãa bÝ mËt nh− thÕ ®−îc gäi lµ hÖ mËt ®èi xøng ®Ó ph©n biÖt víi hÖ mËt khãa c«ng khai kh«ng ®èi xøng trong ®ã c¸c khãa kh¸c nhau ®−îc sö dông bëi ng−êi m· vµ ng−êi dÞch. Chó ý r»ng X, Y, vµ Z trong m« h×nh nµy lµ c¸c biÕn ngÉu nhiªn. Trong m« h×nh nµy chóng ta còng lu«n gi¶ thiÕt b¶n râ X vµ khãa Z lµ ®éc lËp thèng kª. C¸c hÖ mËt khãa bÝ mËt th−êng ®−îc chia thµnh c¸c hÖ m· khèi vµ hÖ m· dßng.

§èi víi m· khèi b¶n râ cã d¹ng c¸c khèi "lín" (ch¼ng h¹n 128-bit) vµ d·y c¸c khèi ®Òu ®−îc m· bëi cïng mét hµm m· hãa, tøc lµ bé 1 m· hãa lµ mét hµm kh«ng nhí. Trong m· dßng, b¶n râ th−êng lµ d·y c¸c khèi "nhá" (th−êng lµ 1-bit) vµ ®−îc biÕn ®æi bëi mét bé m· hãa cã nhí. C¸c hÖ m· khèi cã −u ®iÓm lµ chóng cã thÓ ®−îc chuÈn hãa mét c¸ch dÔ dµng, bëi v× c¸c ®¬n vÞ xö lý th«ng tin hiÖn nµy th−êng cã d¹ng block nh− bytes hoÆc words. Ngoµi ra trong kü thuËt ®ång bé, viÖc mÊt mét block m· còng kh«ng ¶nh h−ëng tíi ®é chÝnh x¸c cña viÖc gi¶i m· cña c¸c khèi tiÕp sau, ®ã còng lµ mét −u ®iÓm kh¸c cña m· khèi.

th¸m m· nguån râ X Bé m· hãa Y Bé gi¶i m· X n¬i nhËn EK(.) Z Z kªnh an toµn nguån khãa H×nh 1.1: M« h×nh hÖ mËt khãa bÝ mËt Nh−îc ®iÓm lín nhÊt cña m· khèi lµ phÐp m· hãa kh«ng che dÊu ®−îc c¸c mÉu d÷ liÖu: c¸c khèi m· gièng nhau sÏ suy ra c¸c khèi râ còng gièng nhau. Tuy nhiªn nh−îc ®iÓm nµy cã thÓ ®−îc kh¾c phôc b»ng c¸ch ®−a vµo mét l−îng nhá cã nhí trong qu¸ tr×nh m· hãa, tøc lµ b»ng c¸ch sö dông c¸ch thøc mãc xÝch khèi m· (CBC-Cipher Block Channing mode) trong ®ã hµm m· hãa kh«ng nhí ®−îc ¸p vµo tæng XOR cña block râ vµ block m· tr−íc ®ã. PhÐp m· lóc nµy cã kiÓu c¸ch kü thuËt nh− m· dßng ¸p dông ®èi víi c¸c khèi "lín". Gi¶ sö F2 lµ tr−êng Galois hai phÇn tö.

Ký hiÖu F2m lµ kh«ng gian vÐc t¬ c¸c bé m-tuples c¸c phÇn tö cña F2. Trong phÇn nµy chóng ta gi¶ thiÕt kh«ng mÊt tæng qu¸t r»ng, b¶n râ X, b¶n m· Y lÊy c¸c gi¸ trÞ trong 2 kh«ng gian vÐc t¬ F2m, cßn khãa Z lÊy gi¸ trÞ trong kh«ng gian vÐc t¬ F2k. Nh− vËy m-lµ ®é dµi bÝt cña c¸c khèi râ vµ m·, cßn k-lµ ®é dµi bit cña khãa bÝ mËt. HÖ m· khèi khãa bÝ mËt lµ mét ¸nh x¹ E: F2m x Sz → F2m, sao cho víi mçi z ∈ Sz, E(., z) lµ mét ¸nh x¹ cã ng−îc tõ F2m vµo F2m., z) ®−îc gäi lµ hµm m· hãa t−¬ng øng víi khãa z.

¸nh x¹ nghÞch ®¶o cña E(., z) ®−îc gäi lµ hµm gi¶i m· t−¬ng øng víi khãa z vµ sÏ ®−îc ký hiÖu lµ D(. Chóng ta viÕt Y = E(X, Z) ®èi víi mét m· khèi cã nghÜa lµ b¶n m· Y ®−îc x¸c ®Þnh bëi b¶n râ X vµ khãa bÝ mËt Z theo ¸nh x¹ E. Tham sè m ®−îc gäi lµ ®é dµi khèi cßn tham sè k ®−îc gäi lµ ®é dµi khãa cña hÖ m· khèi ®ã. Cì khãa ®óng cña hÖ m· khèi ®−îc x¸c ®Þnh bëi sè kt = log2 (#(Sz)) bit.

Nh− vËy ®é dµi khãa sÏ b»ng cì khãa ®óng nÕu vµ chØ nÕu Sz = F2k, tøc lµ mäi bé k-bit nhÞ ph©n ®Òu lµ mét khãa cã hiÖu lùc. Ch¼ng h¹n ®èi víi chuÈn m· d÷ liÖu DES, ®é dµi khãa lµ k = 64 bit, trong khi cì khãa ®óng cña nã lµ kt = 56 bit. Chó ý r»ng ë ®©y ta xem xÐt c¸c m· khèi cã ®é dµi khèi m· b»ng ®é dµi khèi râ. §é an toµn cña c¸c hÖ m· khèi Nh− ®· nãi ë trªn, mét m· khèi ®−îc sö dông nh»m b¶o vÖ chèng sù dß dØ kh«ng mong muèn cña b¶n râ.