Luận án Nghiên cứu xây dựng một lớp hàm băm mở rộng mới và khả năng ứng dụng

, )H id MD MD của từng lần thay đổi, cuối cùng tính được khoảng cách Hamming trung bình giữa các giá trị băm với giá trị băm ban đầu là: 71 128 ( ) 1 1 1 ( , ) 64,12 128 H tb H i i d d MD MD    (2.27) Bảng 2.10 là kết quả tính toán phân bố của hàm băm khi thay đổi khóa khởi tạo K, mỗi khóa khác với khóa đầu tiên 2 bit. Sở dĩ ta phải thay đổi 2 bit (tương ứng thay đổi 2 vị trí) là để đảm bảo đa thức sinh của khóa có trọng số lẻ [32]. Bản tin đầu vào gồm 10 khối 128 bit được tạo ngẫu nhiên. Chú ý, chiều dài của khóa tạo từ CGP là 53 bit, do đó khi mô tả khóa bằng ký tự hexa thì có thể cần đến 14 ký tự nhưng thực tế chỉ có 13 ký tự đầu là dạng hexa, còn ký tự cuối cùng chỉ có 1 bit nên nó nhận giá trị “1” hoặc “0”. Chọn phần tử đầu của cấp số nhân tạo khóa là: 21aK x x   Tương tự cách tính khóa như trên ta có khóa đầu tiên 1K là: 1(hex)K 123456789ABCD.0 với 1( ( ) 25)W K  Các khóa iK khác khóa đầu tiên 1K 2 bit trong một số hexa. Vị trí các bit “1” trong các khóa iK tương ứng là số mũ của x trong đa thức sinh tạo khóa. Ví dụ: 1(hex) hex bin(12...D. ) (1000.0100....1011. )K  0 0 5 48 50 51 1 1 ...K x x x x       K1(BIN) = 1000.0100.1100.0010.1010.0110.1110.0001.1001.0101.1101.0011.1011.0 Các khóa iK khác khóa đầu tiên 1K 2 bit trong một số hexa. Vị trí các bit “1” trong các khóa iK tương ứng là số mũ của x trong đa thức sinh tạo khóa. Ví dụ: 1(hex) hex binK (12...D. ) (1000.0100....1011. )0 0  5 48 50 51 1 1 ...K x x x x       1 2 3 4 5 6 7 8 9 A B C D Bít 53 72 Bảng 2.10. Khoảng cách Hamming dH(MD1, MDi) giữa các cặp giá trị băm khi thay đổi khóa TT Khóa Giá trị băm 0 123456789ABCD.0 FFC215A088719270AFE7D1535C98BF4E 0 1 023456789ABCD.1 A0A9F69E88EF6FE00D19FE1E04CFC2B1 76 2 323456789ABCD.1 9D9CA7FA00A2AD5961554019984527C6 61 3 523456789ABCD.1 903879DD547A57CD115BF0A5A4E3217A 78 4 923456789ABCD.1 658B4B7B81B0A41CDB3A97ECBAE24949 70 5 133456789ABCD.1 72ACDC838C13030E1B7AE1EB8CAF9AE6 58 6 103456789ABCD.1 8CDC97B7EA3E03E6AF9BB9144BA1914F 65 7 163456789ABCD.1 A0975CBB501473AE143B2B5B68C42744 65 8 1A3456789ABCD.1 A6D9CE85D043C7D329BA8BE0B55699E9 66 9 122456789ABCD.1 E4727086AF7B2E34DB3F2A0AE17158BF 68 10 121456789ABCD.1 F16949BB8650EF12A2131F6B893CFCCD 60 11 127456789ABCD.1 DEDD2F574B94A8A8B9CA02D33ECE662A 63 12 12B456789ABCD.1 CCEA1145FE3F9AFDBBBEFBE04C28A299 54 13 123556789ABCD.1 563B5678E476AD4E01D5E12FD342E604 67 14 123656789ABCD.1 797E775AADEA08BB5CCAC60207540C28 69 15 123056789ABCD.1 CFC2568BA4A3E54F1FE80C5CBFC452A1 67 16 123C56789ABCD.1 BBD9F700F3BEF31408F40042E445DC3A 62 17 123446789ABCD.1 C9FE79619790ED396EAD78BE6FB6DBE7 65 18 123476789ABCD.1 84AB66A5F1138336074C3CF93A4454B2 69 19 123416789ABCD.1 C472234312843C1599E6C35A0868D589 61 20 1234D6789ABCD.1 B3DE39087C5D5AEDAFADF1F73A216754 51 21 123457789ABCD.1 46DA05181A755CDFB779C733FB59C9CD 55 22 123454789ABCD.1 9DAE3221FD706F19089932969E99884E 59 23 123452789ABCD.1 4DE9888DF46405447442A1482FCE6D7A 66 24 12345E789ABCD.1 FAFDE0BBCA1B02062E0C41EA51EAA4CA 59 iK iMD 1( , )H id MD MD 73 25 123456689ABCD.1 5647C707690A665C8116D164156436EF 63 26 123456589ABCD.1 DB844A2E5087617FAD802DE7B725F43B 72 27 123456389ABCD.1 99D83BC5E452CF8C220F3820F57056FE 67 28 123456F89ABCD.1 02691B4BAF2C19D4C2BE0A13118FA8D7 69 29 123456799ABCD.1 94C0AE07C7FD69D0A29A3712DD1E46D9 66 30 1234567A9ABCD.1 C5931124D96A37042A1747C7B2C38C07 57 31 1234567C9ABCD.1 B1230E29431CE4E5AB1FAF3156463412 65 32 123456709ABCD.1 66294D4112E28815F28A8961C090F57A 59 33 123456788ABCD.1 0A26094962B080258C1109D8BD45AEB2 67 34 12345678BABCD.1 1687BB788377B56AF3C3140EA7B8583C 62 35 12345678DABCD.1 AA620AADE21389501DB22F4281F0D87A 60 36 123456781ABCD.1 C2ED02CC3FEF80EACB2D9DDD0E9FF6A9 64 37 123456789BBCD.1 88B925269AD39CA9B8AC3D1625A1C381 66 38 1234567898BCD.1 CABC30D0FEACB816F470754EACB77855 69 39 123456789EBCD.1 E3CBAEE9C7BA6683BB6F6F46A107494D 69 40 1234567892BCD.1 C23FFF533ABD9CAF11CE8BD3B7DE4A46 71 41 123456789AACD.1 49225C04B405E2C2BED98B6F8F8BDCFE 59 42 123456789A9CD.1 7B0E7D93EC5D639AAAF2AC7C73139D8F 59 43 123456789AFCD.1 3F15D9AE032B43BF01218A1B79296C65 65 44 123456789A3CD.1 44B6283EEDACE7A3D39153A18700E9A8 75 45 123456789ABDD.1 66390EDB9633D9DD84EABE37DA6D3F80 67 46 123456789ABED.1 B76FEF9E0599154730853DFEB268F128 72 47 123456789AB8D.1 2E20F17397ECD59C88DC48F4EBA669EC 73 48 123456789AB4D.1 E736E98379F0DF6113E44E6151DA5426 59 49 123456789ABCC.1 2B5BC05B31AAD3467EAC83A06C820722 67 50 123456789ABCF.1 03F5B238816A4C288E6A8D7617902635 62 51 123456789ABC9.1 31C16ED3723753980EDF50036D49EBFD 59 52 123456789ABC5.1 3241034DEE9B6DF8A646133F3EB58FC1 62 74 Khoảng cách Hamming trung bình: 52 ( ) 0 1 1 ( , ) 64,40 52 H tb H i i d d MD MD    (2.28) Nhận xét: Như vậy bằng việc sử dụng cấu trúc nhóm nhân và cấp số nhân cyclic trên vành đa thức để tạo khóa cho mật mã khối, ta có thể xây dựng một hàm băm MDC-2 với khối mật mã dựa trên cơ sở mạng hoán vị Feistel với một số ưu điểm sau: - Hàm băm có độ khuếch tán rất tốt, thể hiện ở các khoảng cách Hamming đã tính được theo các biểu thức (2.27) và (2.28). - Số lượng khóa tìm được rất nhiều ( 522 1kN   ) theo công thức tính toán [4] đáp ứng yêu cầu thực tế (vì khóa có độ dài 53 bít). - Việc tính toán khá đơn giản, các khóa được tạo từ các cấp số nhân cyclic và có thể thực hiện được dễ dàng khi thiết kế và xây dựng mạch phần cứng (do ở đây, việc mã hóa có thể được thực hiện được chỉ với thuật toán nhân và bình phương đa thức). 2.5. KẾT LUẬN CHƯƠNG II Trong chương này nghiên cứu sinh đề xuất một số hệ mật và hàm băm mới. Với hàm băm xây dựng dựa trên hệ mật theo sơ đồ Lai-Massey thì độ khuếch tán của hàm băm tạo ra đạt khoảng trên dưới 32 bít (Khi độ dài mã băm được tạo ra là 64 bít). Với hệ mật lai ghép để xây dựng hàm băm 64 bít, trong đó hàm mã hóa sử dụng phép mã hóa của hệ mật Pohlig-Hellman và sơ đồ mã hóa theo mạng Feistel cân bằng thì độ khuếch tán đạt được cũng xấp xỉ 32 bít. Và cuối cùng là hàm băm dạng MDC-2 (128 bít) được xây dựng với khối mật mã dựa trên cấp số nhân cyclic và lưu đồ thuật toán Feistel có sửa đổi với một số ưu điểm: Số khóa nhiều; mạch điện phần cứng đơn giản, đễ dàng tính toán và thiết kế; hàm băm cũng có độ khuếch tán rất tốt, thể hiện ở các khoảng cách Hamming đã tính được xấp xỉ 64 bít (tức là cũng khoảng một nửa chiều dài mã băm). 75 Các kết quả nghiên cứu này được trình bày ở các bài báo và bài hội thảo số [2], [3], [5] trong Danh mục các công trình công bố của tác giả. Với các kết quả bước đầu này, nghiên cứu sinh tiếp tục đề xuất xây dựng các hàm băm mở rộng mới ở chương sau. 76 CHƯƠNG 3. XÂY DỰNG MỘT LỚP CÁC HÀM BĂM MỞ RỘNG MỚI 3.1. GIỚI THIỆU Ở chương II, NCS đã xây dựng các hệ mật và hàm băm mới có độ dài nhỏ (64 bít đến 128 bít), các kết quả này nhằm mục đích khảo sát các thuật toán và lưu đồ trước khi xây dựng các hàm băm có độ dài lớn hơn. Kết quả mô phỏng ở chương II đều cho thấy các hàm băm mới này đều có được các đặc tính ưu việt: Độ khuếch tán tốt, số lượng khóa tạo ra nhiều, mạch điện phần cứng đơn giản dễ thiết kế và xây dựng, ... Trên cơ sở việc khảo sát đó, trong chương III này, nghiên cứu sinh đề xuất xây dựng một số hàm băm mở rộng mới: - Xây dựng hàm băm mở rộng mới MDC-3 với độ dài mã băm tạo ra là 384 bít (Dựa trên hệ mật mã khối với 128 bít vào và 128 bít ra. Sơ đồ hàm băm gồm 3 nhánh, mỗi nhánh có một hàm mã hóa, dữ liệu đầu vào và đầu ra ở mỗi nhánh đều có độ dài là 128 bít). - Xây dựng hàm băm mở rộng mới dạng MDC-4 (Không giống như hàm băm kép MDC-4 thông thường chỉ là cách lặp lại 2 lần của hàm băm MDC-2 và chỉ có độ dài mã băm 128 bít). Ở đây hàm băm MDC-4 được xây dựng với sơ đồ gồm 4 nhánh, mỗi nhánh 128 bít, mã băm cuối cùng được tạo ra là cách kết hợp móc xích của các nửa mã băm ở các nhánh theo từng đôi một để tạo ra sự phụ thuộc lẫn nhau. Hàm băm mở rộng này có độ dài 512 bít, lớn hơn rất nhiều so với các hàm băm kép truyền thống trước đây (thường chỉ có độ dài 128 bít). - Xây dựng hàm băm mở rộng mới MDC 512 bít: Với mục đích nghiên cứu và phát triển các hàm băm, ở đây nghiên cứu sinh đề xuất thêm một sơ đồ hàm băm mở rộng thực hiện theo sơ đồ Miyaguchi - Preneel [4]. Sơ đồ mã hóa thực hiện theo mạng 77 Feistel bốn nhánh không cân bằng, hàm mã hóa và các khóa con của các vòng mã hóa dựa trên các cấp số nhân cyclic của vành đa thức chẵn 2 [ ]/ 1nx x  với 62 64.n  Các hàm băm này sử dụng các lưu đồ mã hóa khác nhau (Feistel; Lai-Massey; Lai-Massey và Feistel kết hợp). Mục đích chỉ khảo sát tính khuếch tán của hàm băm (sử dụng lưu đồ nào cũng được). 3.2. XÂY DỰNG HÀM BĂM MỞ RỘNG MỚI MDC-3 Từ hàm băm dạng MDC-2 ở chương II, ở đây, nghiên cứu sinh đề xuất một phương pháp xây dựng hàm băm mới có độ dài đầu ra là 384 bit dựa trên các cấp số nhân cyclic của vành đa thức, sơ đồ như ở hình 3.1. Hình 3.1. Sơ đồ hàm băm MDC-3 đề xuất xi g E H1i-1 H1i A B A D Out 1 g E H2i A B A D Out 2 g E H3i A B A D Out 3 H2i-1 H3i-1 Hi 78 Hình 3.2. Sơ đồ khối mật mã E Dữ liệu bản rõ (128 bít) Dữ liệu mã hóa (128 bít)  L0(64) R0(64) L1(64) R1(64) K1 f  L16(64) R16(64) L15(64) R15(64) f IP IP-1 Hoán vị ban đầu Hoán vị đảo K16 79 Bảng 3.1. Bảng hoán vị ban đầu (IP) 122 114 106 98 90 82 74 66 58 50 42 34 26 18 10 2 124 116 108 100 92 84 76 68 60 52 44 36 28 20 12 4 126 118 110 102 94 86 78 70 62 54 46 38 30 22 14 6 128 120 112 104 96 88 80 72 64 56 48 40 32 24 16 8 121 113 105 97 89 81 73 65 57 49 41 33 25 17 9 1 123 115 107 99 91 83 75 67 59 51 43 35 27 19 11 3 125 117 109 101 93 85 77 69 61 53 45 37 29 21 13 5 127 119 111 103 95 87 79 71 63 55 47 39 31 23 15 7 Khối E sẽ mã hóa cho chuỗi bit có độ dài 128. Trong sơ đồ hình 3.2 các hoán vị IP và hoán vị đảo 1IP được xây dựng và phát triển từ các bảng IP và 1IP của hệ mật DES, cho trong bảng 3.1 và bảng 3.2. Khối mật mã E trong sơ đồ này được xây dựng theo dạng mô hình mạng hoán vị thay thế Feistel với một số thay đổi như trong hình 3.2. Tương tự như hàm băm MDC-2 ở chương II, hàm mã hóa f được xây dựng trên cơ sở hệ mật sử dụng các CGP trên vành đa thức 2[ ]/ 1 nx x với 6 642n Trong sơ đồ ở hình 3.1, các khối bít đầu ra ở mỗi nhánh (128 bít) được tách ra hai nửa (mỗi nửa 64 bít để) ghép móc xích với nhau với mong muốn đầu ra sẽ thay đổi một nửa chiều dài mã băm. Kết quả cụ thể sẽ được khảo sát bằng việc mô phỏng dưới đây. Các khóa Ki là các phần tử trong một cấp số nhân xây dựng trên vành đa thức có hai lớp kề cyclic và được chọn như sau [7]: 61 0 mod 1;( 1...16) i i aK K K x i   (3.1) 80 Bảng 3.2. Bảng hoán vị đảo (IP-1) 80 16 96 32 112 48 128 64 79 15 95 31 111 47 127 63 78 14 94 30 110 46 126 62 77 13 93 29 109 45 125 61 76 12 92 28 108 44 124 60 75 11 91 27 107 43 123 59 74 10 90 26 106 42 122 58 73 9 89 25 105 41 121 57 72 8 88 24 104 40 120 56 71 7 87 23 103 39 119 55 70 6 86 22 102 38 118 54 69 5 85 21 101 37 117 53 68 4 84 20 100 36 116 52 67 3 83 19 99 35 115 51 66 2 82 18 98 34 114 50 65 1 81 17 97 33 113 49 với Ka là một đa thức có trọng số lẻ tùy ý sao cho: deg 61aK ; 0K là một phần tử nguyên thủy của nhóm nhân cyclic có cấp bằng 602 1 và cũng là một đa thức có trọng số lẻ [23]. Giả sử ta chọn khóa 30 1K x x Phần tử đầu là 21aK x x . Phần tử đầu của cấp số nhân và cũng là khóa đầu tiên tính được như sau: 4 5 1 0 1 (045)aK K K x x     (3.2) (Ghi chú: (045) là dạng biểu diễn số mũ của đa thức). Sơ đồ khối bộ mã hóa f với khóa 1 K như hình 3.3. 81 Hình 3.3. Sơ đồ khối mã hóa f với khóa 4 5 1 1K x x Một khâu mã hóa được thực hiện theo quy tắc: 1 1 1( , ) i i i i i i i L R K R L f R K         (3.3) Khối g trong sơ đồ hình 3.1 thực hiện việc trích chọn các khóa cho các vòng tiếp theo của quá trình băm. Khối mật mã E trong sơ đồ sử dụng các khóa có độ dài 61 bit. Trong 61 bit khóa ở bước thứ i do khối g tạo ra thì 60 bit đầu tiên sẽ được trích chọn từ 128 bit của 1iH còn bit thứ 61 là bit kiểm tra chẵn lẻ. Việc trích chọn được lấy liên tục các bit cách nhau 2 vị trí trong 1iH (trong khoảng bit 1 đến bit 120). Dưới đây là một vài kết quả đánh giá của hàm băm xây dựng trên các cấp số nhân cyclic. Bảng 3.3 là kết quả tính toán phân bố của 8 giá trị băm khi thay đổi duy nhất một bit dữ liệu bản tin rõ so với bản tin ban đầu [31], để thuận tiện cho việc quan sát ở đây chúng ta chỉ thay đổi 1 bit trong khối bản tin đầu tiên (Cụ thể là thay đổi lần lượt 8 bit đầu tiên). Mỗi bản tin bao gồm 10 khối bản tin, mỗi khối có độ dài 384 bit. Các hàm băm sử dụng cùng một bộ khóa IVK khởi tạo như sau: Chọn phần tử sinh của khóa khởi tạo cho các hàm băm là đa thức sau: 19 27 45 541iK x x x x (3.4) Vào Ra (63) (4) (3) (2) (1) (0) ................... 64 bít 64 bít (5) 82 Phần tử đầu là: 21aK x x Phần tử đầu của cấp số nhân (khóa đầu tiên) cũng là khóa khởi tạo sẽ là: 18 19 20 27 1 28 29 45 46 47 54 55 56 aiIVK K K K x x x x x x x x x x x x (3.5) Bản tin rõ đầu tiên được xây dựng như sau: Khối bản tin đầu tiên gồm 96 ký tự dạng hexa (tương ứng 384 bit vì mỗi ký gồm 4 bit) được chọn là: M0=0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0123456789 ABCDEF0123456789ABCDEF0123456789ABCDEF Các khối bản tin tiếp theo (từ 2 đến 10) được tạo một cách ngẫu nhiên [31]. Bảng 3.3. Khoảng cách Hamming dH(MD0, MDi) khi các bản tin dữ liệu khác bản tin ban đầu 1 bit TT Bản rõ iM Giá trị băm iMD 0( , )iHd MD MD 0 0123456789ABCDEF0123456789ABCDEF 0123456789ABCDEF0123456789ABCDEF 0123456789ABCDEF0123456789ABCDEF 7ECE10DB17D1D602020BAEDDCB5F7156 AEB620E7E2D66FE846E64F5CBBA1164D 402B9B64C1924FC6EC3D581FA0A02CAB 0 1 1123456789ABCDEF0123456789ABCDEF 0123456789ABCDEF0123456789ABCDEF 0123456789ABCDEF0123456789ABCDEF 6A015AA71AC4DBD8E89319958FF7F5C8 EF1D2479AF24B358F77B1B9E699770DD 9D5AE5F266254C5A8B5721488554C9EC 190 2 2123456789ABCDEF0123456789ABCDEF 0123456789ABCDEF0123456789ABCDEF 0123456789ABCDEF0123456789ABCDEF 6513440305C13EDCEDFF906359467E3B 2091676950CA2A41F89FD5CCB73A5C04 77F4C239EEAB4524A72BF7E98E01C36C 202 3 4123456789ABCDEF0123456789ABCDEF 0123456789ABCDEF0123456789ABCDEF 0123456789ABCDEF0123456789ABCDEF 60137994C8749F533EB118F636E84E5E BC640D132F52B5AB759D9FBC92E21259 57B9726AA009A95EF4AD4E9B7BAE71E1 186 83 4 8123456789ABCDEF0123456789ABCDEF 0123456789ABCDEF0123456789ABCDEF 0123456789ABCDEF0123456789ABCDEF 08B805C4A9CE3FAAFDBBA60FC0246050 163785DF6194774F2C710EE2D5AFF64E 04CAE51DA40A6AE0298AF00C90791304 186 5 0023456789ABCDEF0123456789ABCDEF 0123456789ABCDEF0123456789ABCDEF 0123456789ABCDEF0123456789ABCDEF C2252DDE50F4B32D71987C4D34A0FCDC 96744860A259007A8F986276BA2A4501 C015A2663C3F09C462681ED18C3380B2 186 6 0323456789ABCDEF0123456789ABCDEF 0123456789ABCDEF0123456789ABCDEF 0123456789ABCDEF0123456789ABCDEF 090C76EBE74B45FCC82C9A28246DF6DA E81DF39FCA9F21C0282035B158E605C1 C5301F9EE97D5EE004FA4C975FC28073 192 7 0523456789ABCDEF0123456789ABCDEF 0123456789ABCDEF0123456789ABCDEF 0123456789ABCDEF0123456789ABCDEF 1D506129653F7F851886702343CA6BAF 3966DB41633D3F7B3E8C7A06BF5864F0 C9285E90DEA037739E0E0A2E6E1D579F 202 8 0923456789ABCDEF0123456789ABCDEF 0123456789ABCDEF0123456789ABCDEF 0123456789ABCDEF0123456789ABCDEF FA583602F0CDF37B6E52D04FF5EDA698 653B5A4485F55AC2A5141887F64F7363 E7839362E8DD08B4E83A43A33B1CD90E 200 (Ghi chú: Trong bảng 3.3 và bảng 3.4, các ký tự hexa được in đậm chứa các bit thay đổi). Tiến hành thay đổi lần lượt từng bit từ bit 1 đến bit 384 của khối bản tin đầu tiên 0M , tính khoảng cách Hamming 0( , )iHd MD MD của từng lần thay đổi, cuối cùng tính được khoảng cách Hamming trung bình giữa các giá trị băm: 384 0( ) 1 192,26 1 ( , ) 384 iHH tb i d d MD MD    Ta thấy khoảng cách Hamming trung bình đạt xấp xỉ một nửa (192 bit) độ dài hàm băm. Bảng 3.4 là kết quả tính toán phân bố của 8 giá trị băm khi thay đổi khóa khởi tạo 1 K , mỗi khóa khác với khóa đầu tiên 2 bit. Sở dĩ ta phải thay đổi 2 bit (tương ứng thay đổi 2 vị trí) là để đảm bảo đa thức sinh của khóa có trọng số lẻ. Bản tin đầu vào gồm 10 khối 384 bit (MD0 đến MD9) được tạo ngẫu nhiên [31]. 84 Để cho tiện minh họa ta chọn phần tử đầu của cấp số nhân tạo khóa là: Ka = 1 Phần tử sinh tạo khoá cũng là khoá đầu tiên 1K là: 1( ) 123456789ABCDEF.1 hex K Ta có trọng số của khóa 1K : 1W( ) 33K đảm bảo là một số lẻ. Ghi chú: - Do chiều dài của khóa là 61 bit, nên khi mô tả khóa bằng 16 ký tự hexa thì thực tế chỉ có 15 ký tự đầu là dạng hexa, còn ký tự cuối cùng chỉ gồm 1 bit nên nó nhận giá trị “1” hoặc “0”. - Vị trí các bit “1” trong các khóa 1 K tương ứng là số mũ của x trong đa thức sinh tạo khóa: 1 (123... .1) (1000.0100.....1111.1)hex binK F  5 56 57 58 601 ...x x x x x       Tiến hành thay đổi lần lượt từng bit từ bit 1 đến bit 60 của khóa 1K , bit 61 của khóa dùng để kiểm tra chẵn lẻ, sau đó tính được khoảng cách Hamming trung bình giữa các giá trị băm với giá trị băm ban đầu như sau: 60 0( ) 1 193,43 1 ( , ) 60 iHH tb i d d MD MD    Bảng 3.4. Khoảng cách Hamming dH(MD0, MDi) của 8 mã băm với mã băm ban đầu khi các khóa khác khóa 1K 2 bit. TT Khóa Ki Giá trị băm MDi 0( , )H id MD MD 0 123456789ABCDEF1 102DFDDAF8977EBA12BC607A6486DEEAE7E6630BC8D8CD7A 9EC9EDFE90898CECE6B2ECB21D6A0B3CABE2D3E4BC639289 0 1 023456789ABCDEF0 20CAB1621589205B111C4B02F210C81AADEF4D74C8301A78 815E2CF878ABA440C92F4EDBFF6CD12FDF1EF332740F2783 176 2 323456789ABCDEF0 A2395333805933D04DEBC207E276A3E136AA351A76A1ED48 1669420D2BE16AD929CB59121A3FEF3126D41238C34AA888 194 3 523456789ABCDEF0 6DBF778AD492EDBC21B9DE2B77D9DA8C6EAF90FC7960B177 184 85 D572A93A8BE4EAAD438EE1C9502D7694489F0F88EEE23AA5 4 923456789ABCDEF0 BE4625E74277F79725E64CE043C29D768A76EA2E15339D75 5991CE630671427D1D26903590F45B67A4D6AEA18C94AA0E 194 5 133456789ABCDEF0 ED0567AD1F80DAC26CDBBBA8D8319DF611602A2F3527BD29 CB94CC8897EEE4B205ECD5B8AD57A2F3739DCBF1859167E7 212 6 103456789ABCDEF0 79EBDE78580DA8D2AF3043136B5519C19618C40FA383AF10 54AE3364958586354C06AC251C79578DCD2BD029B4632AEC 176 7 163456789ABCDEF0 4EB307D302DFBC7192BE0C1F9E27B2CA3A7B881C52420A67 9F46423A66BFEF9ECAA0AFC79967BB118064E05971AE6822 192 8 1A3456789ABCDEF0 CD8ED0204F01D809D5B9FE8D9D2B77F30D44E57715A1272D 23D9B48E75C402A9D0F07ABE5D7C9424DE92A764A2FB9A2F 291 Bảng 3.5 là liệt kê trọng số (chiều dài) của các khóa trong các bước băm, thực hiện với 3 lần thay đổi khóa đầu tiên. Chú ý, do bản tin có 10 khối nên sẽ có 10 khóa tương ứng với 10 bước băm, tuy nhiên khóa đầu tiên đã được chọn trước. Từ bảng 3.5 ta thấy tất cả các khóa ở các bước băm đều có trọng số lẻ, đảm bảo điều kiện để tạo khóa. Bảng 3.5. Trọng số của các khóa tại các bước băm Khóa khởi đầu Ki 123456789ABCDEF1 023456789ABCDEF0 323456789ABCDEF0 TT Trọng số của khóa tại các bước băm Khối mã hóa 1 ( H ) Khối mã hóa 2 ( H ) Khối mã hóa 3 ( H ) Khối mã hóa 1 ( H ) Khối mã hóa 2 ( H ) Khối mã hóa 3 ( H ) Khối mã hóa 1 ( H ) Khối mã hóa 2 ( H ) Khối mã hóa 3 ( H ) 1 1( )W K 31 31 31 29 29 29 29 29 29 2 2( )W K 29 25 31 31 35 31 25 33 33 3 3( )W K 35 35 31 33 35 29 37 29 31 4 4( )W K 27 29 23 31 29 29 29 33 29 5 5( )W K 25 27 27 31 29 31 33 27 27 86 6 6( )W K 31 29 29 31 31 25 33 29 35 7 7( )W K 27 29 25 29 31 33 31 27 37 8 8( )W K 33 37 31 29 33 37 35 35 31 9 9( )W K 27 33 31 25 27 29 29 31 23 10 10( )W K 29 31 29 27 29 27 29 37 31 Như vậy với mục đích tăng độ dài mã băm nhằm hạn chế phép tấn công ngày sinh nhật, NCS đã đưa ra được một lược đồ hàm băm mới (MDC-3) với độ dài mã băm 384 bit. Hàm mật mã sử dụng trong lược đồ xây dựng theo các cấp số nhân cyclic trên vành đa thức, với các ưu điểm như: Số lượng khóa tạo được rất nhiều (được tính toán theo [4]), mạch điện phần cứng đơn giản (vì chỉ gồm các thanh ghi dịch và bộ cộng module 2). Các kết quả mô phỏng đánh giá hàm băm đề xuất cho thấy độ khuếch tán rất tốt, đạt xấp xỉ một nửa chiều dài mã băm khi ta thay đổi dữ liệu vào hoặc thay đổi khóa (khoảng cách mã Hamming trung bình đạt xấp xỉ 192 bít). Tuy nhiên, để có đánh giá toàn diện hơn cần có thêm các nghiên cứu khác như khả năng xung đột 3.3. HÀM BĂM DỰA TRÊN HỆ MẬT MÃ KHỐI KẾT HỢP SƠ ĐỒ LAI-MASSEY VỚI FEISTEL Các hàm băm phổ biển hiện nay đều là các hàm băm thuộc họ MD như HAVAL, MD4, MD5, PANAMA, RIPEMD, SHA, VEST, [35, 37, 51] Trong đó nổi bật là MD5 và SHA-1, hai hàm băm này có số vòng mã hóa khá nhiều (64 vòng đối với MD5 và 80 vòng đối với SHA-1), các hàm mật mã thường trải qua nhiều khâu, do đó phải có yêu cầu nhất định về tài nguyên phần cứng cũng như tốc độ xử lý. Với mục đích xây dựng một hệ mật đơn giản nhưng vẫn đảm bảo một số yêu cầu như: độ khuếch tán tốt, dễ dàng mã hóa và giải mã [15, 16, 25], nghiên cứu sinh đề xuất một hệ mật mã khối kết hợp sơ đồ Lai - Massey với sơ đồ Feistel, và sau đó sử dụng hệ mật này vào xây dựng hàm băm. 87 3.3.1. Hệ mật mã khối kết hợp sơ đồ LAI-MASSEY và FEISTEL Như ta đã biết sơ đồ mã hóa Feistel cân bằng có ưu điểm: (1) Quá trình mã hóa và giải mã sử dụng chung một sơ đồ, chỉ khác nhau ở thứ tự khóa con, điều này sẽ tiết kiệm được tài nguyên khi thực hiện thuật toán trên phần cứng, (2) hàm mã hóa f có thể chọn với độ khó bất kỳ, vì không phải tìm hàm nghịch đảo. Tuy nhiên nó lại có nhược điểm: vì mỗi vòng mã chỉ thực hiện biến đổi một nửa khối dữ liệu, nên cần số vòng mã hóa lớn để đảm bảo độ khuếch tán của hệ mật, điều này làm giảm đáng kể tốc độ mã hóa. Ngoài ra các hệ mật xây dựng trên cơ sở mạng Feistel tồn tại lớp khóa tương đương, nên làm không gian khóa giảm đi một nửa. Trong khi đó với sơ đồ Lai-Massey, mỗi vòng mã hóa được thực hiện trên cả hai nửa dữ liệu làm tốc độ khuếch tán nhanh, và cũng không phải tính hàm ngược của hàm mã hóa f. Trên cơ sở các ưu điểm của cả hai sơ đồ này, nghiên cứu sinh đề xuất một hệ mật xây dựng theo sơ đồ kết hợp, trong đó mười sáu vòng mã hóa được đan xen luân phiên giữa sơ đồ Lai-Massey và sơ đồ Feistel như hình 3.4. Các vòng mã hóa lẻ được thực hiện theo sơ đồ Lai-Massey và có thuật toán như sau [31]: 1 1 1 1 1 1 ) ) ( , ( , i ii i i i ii i i L L f L R k R R f L R k                      (3.6) Và các vòng mã hóa chẵn thực hiện theo sơ đồ Feistel với thuật toán như sau [31]: 1 1 1( , ) i i i ii i L R R L f R k (3.7) 88 Hình 3.4. Sơ đồ mã hóa của hệ mật Các hàm mã hóa f trong sơ đồ sử dụng các CGP trên vành đa thức 2[ ]/ 1 nx x với 2sn đây là vành đặc biệt không được xem xét đến trong lý thuyết mã sửa sai [8], tuy nhiên ta có thể áp dụng các vành đa thức này trong mật mã, với hệ mật đề xuất chọn 62 64n  và như thế f sẽ hoạt động với các khối 64 bit và là các CGP có dạng sau: 89  ( ). ; 0,63iA a x x i  (3.8) thực chất đây là một lớp biến đổi đặc biệt được đặc trưng bởi ma trận luân hoàn như sau [8]: 0 0 1 63 1 63 0 62 63 1 2 0 64 64 ( ). ( ). A ; (2) ( ). i a x x a a a a a aa x x a GF a a aa x x     (3.9) Ở đây, các hàng của ma trận A tương ứng với một đa thức. Các phần tử i a trong một hàng của A là các hệ số của ix trong đa thức tương ứng. Ví dụ ở hàng 1 của A là đa thức 0 7 35 60( ). 1a x x x x x x     thì các hệ số i a trong hàng này sẽ là: 1ia  với 0,1,7,35,60i  và 0ia  với các i còn lại, tương tự như thế với tất cả các hàng của A. Nếu ta chọn a(x) thuộc nhóm nhân G và có trọng số lẻ thì ma trận A sẽ tồn tại ma trận nghịch đảo 1A [7, 8]. Nếu sử dụng ma trận A để mã hóa thì ta hoàn toàn có thể giải mã được bằng ma trận nghịch đảo 1A và ma trận nghịch đảo này được xác định như sau: 1 1n A A (3.10) Điều này là do A có cấp n tức là: n A I hay 1n AA I , với I là ma trận đơn vị. Sơ đồ mạch mã hóa với CGP có số hạng đầu là đa thức 7 35 60( ) 1a x x x x x     và công bội x như trong hình 3.5. Các khóa con ki trong sơ đồ hình 3.4 cũng được tạo từ các CGP nhưng trên các vành đa thức có hai lớp kề cyclic [23]. Thực chất các khóa ki này đóng vai trò là các đa thức đầu ( )a x của các ma trận mã hóa A, do đó các khóa ki phải có trọng số lẻ [8]. Các vành đa thức có hai lớp kề cyclic được phân tích duy nhất thành tích của hai đa thức bất khả quy như sau [29]: 1 0 1 (1 ) n n i i x x x       (3.11) 90 Sở dĩ chọn cách tạo khóa trên vành đa thức có hai lớp kề cyclic là vì các đa thức trên vành đa thức này có cấp cực đại được xác định là [29]: 1max ( ) 2 1