Tóm tắt Luận án tiến sĩ Kỹ thuật: 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

Chia sẻ: Trần Văn Yan | Ngày: | Loại File: PDF | Số trang:27

Thêm vào BST

Báo xấu

36
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu nghiên cứu nhằm xây dựng được một số các hàm băm mới (khảo sát trước khi xây dựng các hàm băm mở rộng). Xây dựng được một lớp các hàm băm mở rộng mới (là lớp hàm băm có độ khuếch tán cao) với mục đích mở rộng chiều dài mã băm qua việc ghép móc xích để tạo ra sự phụ thuộc các bít đầu ra với các khối bít đầu vào (có kiểm chứng qua mô phỏng). Đồng thời đề xuất khả năng ứng dụng các hàm băm mở rộng mới xây dựng.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận án tiến sĩ Kỹ thuật: 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

BỘ THÔNG TIN VÀ TRUYỀN THÔNG HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG ******************************************** NGUYỄN TOÀN THẮNG 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 Chuyên ngành : Kỹ thuật Điện tử Mã số : 62.52.02.03 TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT HÀ NỘI – 2017
Công trình được hoàn thành tại: HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Người hướng dẫn khoa học: GS.TSKH. Nguyễn Xuân Quỳnh Phản biện 1: Phản biện 2: Phản biện 3: Luận án được bảo vệ trước Hội đồng chấm luận án cấp Học viện họp tại: ................................................................................................................ ................................................................................................................ Vào hồi: ngày tháng năm Có thể tìm hiểu luận án tại: 1. Thư viện Quốc gia 2. Thư viện Học viện Công nghệ Bưu chính Viễn thông
-1- MỞ ĐẦU 1. Mở đầu Thông tin được truyền trên mạng ngày càng chịu nhiều tác động, các thám mã có mặt ở khắp nơi, luôn rình rập để lấy cắp thông tin hoặc làm thay đổi thông tin một cách có chủ đích. Để bảo vệ bản tin, người ta cần tăng cường bảo vệ tính bí mật và tính toàn vẹn dữ liệu của bản tin. Bên cạnh đó nhiều thông tin cũng cần phải có tính xác thực. Và cùng với sự phát triển của các kỹ thuật mật mã thì hàm băm cũng ra đời. Hàm băm tạo ra các mã băm được sử dụng cho nhiều mục đích. Các ứng dụng điển hình của hàm băm mật mã bao gồm: Xác thực, đảm bảo tính toàn vẹn của dữ liệu, tạo chữ ký số, ... Việc nghiên cứu xây dựng các hàm băm mở rộng mới và đưa ra ý tưởng về khả năng ứng dụng sẽ góp phần tăng được tính bảo mật, tính xác thực, đảm bảo tính toàn vẹn, an toàn cho thông tin dữ liệu. 2. Tình hình nghiên cứu Trên thế giới hiện nay, hàm băm có nhiều loại, có những loại đơn giản, có loại phức tạp, có hàm băm đơn, có hàm băm kép, có những hàm băm chuyên dụng, thương mại. Một cách tổng quan, có những sơ đồ hàm băm phổ biến sau đây: * Hàm băm có độ dài đơn: Sơ đồ M-M-O, sơ đồ D-M, sơ đồ M-P. * Hàm băm có độ dài kép: MDC-2, MDC-4 Các hàm băm thông dụng trên thế giới hiện nay là hàm băm họ MD và họ SHS. Họ MD có MD4, MD5, MD6, ... họ SHS có SHA-1, SHA-2, SHA-256, ... Ở nước ta hiện nay, việc nghiên cứu các hệ mật được thực hiện từ nhiều năm qua và cũng đã có một số công trình nghiên cứu về hệ mật có giá trị. Tuy nhiên, việc sử dụng các hệ mật này cho các lược đồ xây dựng hàm băm còn là vấn đề tương đối mới.
-2- Các công trình nghiên cứu về hàm băm còn chưa nhiều, một số đồ án tốt nghiệp đại học, luận văn tốt nghiệp thạc sỹ có nghiên cứu, giới thiệu về hàm băm nhưng hầu hết là những tìm hiểu mang tính chất lý thuyết tổng quan. Một số bài báo và luận án tiến sĩ có đề cập đến hàm băm nhưng chưa đề cập nhiều đến tính khuếch tán và các hàm băm mở rộng. 3. Lý do chọn đề tài Hàm băm có 2 tính chất cơ bản là tính chất nén và tính dễ dàng tính toán, ngoài ra hàm băm còn có 3 tính chất khác bổ sung là tính khó tìm nghịch ảnh, khó tìm nghịch ảnh thứ hai và kháng va chạm. Trong số các tính chất đó thì hai tính chất dễ dàng tính toán và khó tìm nghịch ảnh rất gần với đặc điểm của phép biến đổi mật mã, nhất là đối với mật mã khối khoá bí mật, cho nên việc dùng các thuật toán mật mã khối khoá bí mật vào việc tạo ra các hàm băm là một hướng đi rất hiệu quả. Việc phát triển theo hướng các hàm băm chuyên dụng như họ MD, SHS thường rất tốn kém, cần cả một tổ chức quốc tế với đội ngũ hùng hậu để thực hiện và thực hiện trong nhiều năm. Vì sự khó khăn và tốn kém đó, NCS thấy rằng hướng phát triển xây dựng các hàm băm mở rộng dựa trên các thuật toán mã hoá có sẵn là phù hợp với khuôn khổ của một luận án tiến sỹ kỹ thuật ở Việt Nam. Do yêu cầu bài toán tấn công ngày sinh nhật thường cần mã băm có độ dài 384-512 bit để chống lại thám mã nên việc tạo ra các hàm băm mở rộng có độ dài bit lớn là hết sức cần thiết. Trong luận án này, NCS tập trung vào xây dựng các hàm băm mở rộng mới, đồng thời đề xuất ý tưởng về khả năng ứng dụng của các hàm băm mới. 4. Mục tiêu nghiên cứu - Xây dựng được một số các hàm băm mới (khảo sát trước khi xây dựng các hàm băm mở rộng).
-3- - Xây dựng được một lớp các hàm băm mở rộng mới (là lớp hàm băm có độ khuếch tán cao) với mục đích mở rộng chiều dài mã băm qua việc ghép móc xích để tạo ra sự phụ thuộc các bít đầu ra với các khối bít đầu vào (có kiểm chứng qua mô phỏng). Đồng thời đề xuất khả năng ứng dụng các hàm băm mở rộng mới xây dựng. 5. Đối tượng nghiên cứu - Lý thuyết đại số (đa thức, các kiểu phân hoạch vành đa thức, đa thức sinh, ma trận ,…). - Các thuật toán mã hóa khóa bí mật, khóa công khai - Lý thuyết hàm băm, cấp số nhân cylic trên vành đa thức - Các ứng dụng của hàm băm. 6. Phương pháp nghiên cứu - Phương pháp giải tích - Phương pháp mô phỏng - Phương pháp thực nghiệm 7. Ý nghĩa khoa học và thực tiễn của đề tài Kết quả nghiên cứu của luận án có thể góp phần vào việc xây dựng và phát triển các hàm băm, đặc biệt là các hàm băm mở rộng. Luận án đã đưa ra được nhiều phương pháp xây dựng hàm băm khác nhau. Hiện nay hàm băm có nhiều loại nhưng vẫn chưa thực sự phong phú, vẫn cần xây dựng thêm các hàm băm mới để đáp ứng được các ứng dụng đa dạng trong thực tế. 8. Bố cục của luận án Luận án gồm: Phần mở đầu, 4 chương nội dung, Phần kết luận, Phần phụ lục (trong đó có Chương trình phần mềm mô phỏng kết quả nghiên cứu). Chương I tập trung giới thiệu về phương pháp xây dựng các hệ
-4- mật cơ bản (khóa bí mật, khóa công khai), về hàm băm và các cấp số nhân cyclic. Chương II trình bày một số kết quả mới của nghiên cứu sinh về hàm băm, bao gồm: Hàm băm dựa trên hệ mật theo sơ đồ Lai-Massey; Xây dựng một hệ mật mã lai ghép sử dụng hệ mật Pohlig-Hellman kết hợp với sơ đồ Feistel và đề xuất khả năng sử dụng hệ mật này vào hàm băm; Xây dựng hàm băm dựa trên sơ đồ MDC-2, với điểm mới là dùng các hệ mật sử dụng cấp số nhân cyclic trên vành xn + 1, với n = 2k, các khóa dùng trong mật mã khối cũng được tạo từ các cấp số nhân cyclic trên vành đa thức. Chương III, trên cơ sở kết quả khảo sát ở chương II, NCS đề xuất xây dựng một lớp hàm băm mở rộng mới: - Hăm băm MDC-3 với độ dài mã băm 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). - Hàm băm MDC-4 với độ dài mã băm 512 bít (sơ đồ gồm 4 nhánh, mỗi nhánh 128 bít). - Hàm băm MDC-512 bít (sơ đồ gồm 2 nhánh, mỗi nhánh 256 bít) Phần kết luận nêu những đóng góp của luận án và hướng phát triển tiếp theo.
-5- CHƯƠNG 1. TỔNG QUAN VỀ MẬT MÃ VÀ HÀM BĂM 1.1. PHƯƠNG PHÁP XÂY DỰNG CÁC HỆ MẬT CƠ BẢN 1.1.1. Phương pháp xây dựng các hệ mật khóa bí mật 1.1.1.1. Mã hoán vị 1.1.1.2. Mã thay thế Gồm mã dịch vòng và mã thay thế 1.1.1.3. Các lưu đồ thông dụng Gồm lưu đồ Feistel và lưu đồ Lai-Massey, các lưu đồ này được sử dụng để xây dựng các hàm băm mới trong chương II và chương III. 1.1.1.4. Chuẩn mã dữ liệu (DES) a) Mô tả DES DES là thuật toán mã hoá một xâu bit x của bản rõ độ dài 64 bít bằng một khoá 56 bit. Bản mã nhận được cũng là một xâu bit có độ dài 64 bít. b) Các chế độ hoạt động của DES Có 4 chế độ làm việc đã được phát triển cho DES: Chế độ quyển mã điện tử (ECB), chế độ phản hồi mã (CFB), chế độ liên kết khối mã (CBC) và chế độ phản hồi đầu ra (OFB). 1.1.2. Phương pháp xây dựng các hệ mật khóa công khai 1.1.2.1. Hệ mật RSA a) Tạo khóa Tóm lược: Mỗi đầu liên lạc cần tạo một khoá công khai và một khóa riêng tương ứng theo 05 bước. b) Mã hoá và giải mã Tóm lược: B mã hoá một thông báo m để gửi cho A bản mã c: c  me mod n ; A giải mã bằng cách tính: m  cd mod n
-6- 1.1.2.2. Hệ mật ELGAMAL 1.1.2.3. Hệ mật McEliece Hệ mật McEliece dựa trên bài toán giải mã cho các mã tuyến tính (cũng là một bài toán nhị phân đầy đủ). Bài toán nhị phân được áp dụng là bài toán giải mã cho một mã sửa sai (nhị phân) tuyến tính nói chung. Tuy nhiên, đối với nhiều lớp mã đặc biệt đều tồn tại các thuật toán giải mã với thời gian đa thức. Một trong những lớp mã này là mã Goppa, chúng được dùng làm cơ sở cho hệ mật McEliece. 1.2. HÀM BĂM 1.2.1. Mô tả hàm băm Hàm băm là một hàm có ít nhất hai tính chất sau: Tính chất nén và tính chất dễ dàng tính toán. Ngoài hai tính chất trên hàm băm còn có một số tính chất khác: Khó tìm nghịch ảnh; khó tìm nghịch ảnh thứ hai; kháng va chạm. Ngoài ra, một đặc tính quan trọng cần có của hàm băm là tính khuếch tán. Tính khuếch tán này sẽ là tối ưu nếu nó đạt xấp xỉ một nửa chiều dài mã băm. 1.2.2. Phân loại hàm băm Hàm băm Không có khóa Có khóa Các ứng Các ứng MDC MAC dụng khác dụng khác OWHF CRHF Hình 1.7. Phân loại hàm băm
-7- 1.3. CẤP SỐ NHÂN CYCLIC 1.3.1. Nhóm nhân của vành đa thức Nếu: g ( x); f ( x)  G thì g ( x)* f ( x)  d ( x) G Có tất cả 2n 2 các nhóm nhân cyclic cấp n và nhóm nhân cyclic đơn vị I cũng thuộc vào lớp các nhóm nhân này. 1.3.2. Các cấp số nhân cyclic cấp n A(a,q)  {a( x), a( x)q( x), a( x)q 2 ( x),..., a( x)q m1( x)} 1.3.3. Phân hoạch vành đa thức Phân hoạch vành đa thức thường được chia thành các loại: Phân hoạch chuẩn, phân hoạch cực đại, phân hoạch cực tiểu, .... KẾT LUẬN CHƯƠNG I Chương này giới thiệu các kiến thức cơ bản có liên quan đến đề tài luận án, gồm các phương pháp xây dựng hệ mật khóa bí mật, hệ mật khóa công khai: Mã hoán vị, mã thay thế, các lưu đồ thuật toán Lai-Massey, Feistel, chuẩn mã dữ liệu DES; Thuật toán RSA, thuật toán Elgama và McEliece, ... Chương này cũng tập trung vào việc giới thiệu, mô tả hàm băm, các loại hàm băm thông dụng. Các kiến thức cơ bản về nhóm nhân cyclic và các cấp số nhân cyclic, các thuật toán dùng để xây dựng lớp hàm băm mới ở các chương sau cũng được để cập ở đây, là cơ sở nền tảng lý thuyết để nghiên cứu sinh sử dụng xây dựng các hàm băm mở rộng mới.
-8- CHƯƠNG 2. XÂY DỰNG CÁC HÀM BĂM MỚI 2.1. HÀM BĂM DỰA TRÊN HỆ MẬT THEO SƠ ĐỒ LAI-MASSEY 2.1.1. Hệ mật sử dụng cấp số nhân cyclic theo LAI-MASSEY NCS đưa ra một hệ mật mã khối xây dựng theo sơ đồ Lai-Massey, tuy nhiên các hàm mã hóa và các khóa được xây dựng từ các cấp số nhân cyclic trên vành đa thức. Trên cơ sở đó áp dụng hệ mật mã mới này vào một sơ đồ hàm băm đơn 64 bit, và tính toán tính khuếch tán của hàm băm này. Lưu đồ thuật toán của hệ mật là Lai-Massey, các khối mã hóa f sử dụng các CGP trên vành đa thức 2[x] / xn 1 với n  25  32 (k  5) Cấu trúc CGP tạo khối mã hóa f có dạng: A  a( x).xi ; i  0,31 Mạch điện mã hoá là một phép cộng theo các hệ số của đa thức a( x) với n bước dịch vòng. Thuật toán giải mã cũng thực hiện tương tự với các hệ số của đa thức nghịch đảo b( x) . (31) ................... (4) (3) (2) (1) (0) Vào Ra Hình 0.1. Mạch điện mã hóa f với a( x)  1 x  x2 Các khóa Ki cũng được tạo từ các CGP nhưng chúng được xây dựng trên các vành đa thức có hai lớp kề cyclic. Chọn vành đa thức có hai lớp kề cyclic x29 1 , khi đó 16 khóa Ki cho các vòng mã hóa là 16 phần tử đầu tiên trong một CGP được xây dựng như sau: Ki  Ka Koi mod x29 1; (i  0,15) (2.4) (Để thuận tiện cho mạch điện mã hóa ta chọn K0  x )
-9- Trong sơ đồ mã hóa, NCS có đưa ra một điểm mới so với sơ đồ Lai-Massey truyền thống, đó là nửa phải ở bước thứ i sẽ được cộng thêm với khóa Ki trước khi cộng với đầu ra của hàm f. Tiến hành tính toán độ khuếch tán của bộ mã khi thay đổi khóa K với cùng một bản rõ đầu vào. Thực hiện việc tính toán bằng chương trình mô phỏng (viết bằng MATLAB), tính được khoảng cách Hamming trung bình giữa các bản mã tính được như trong biểu thức: 1 29 d H (tb)   d H (C1 , Ci )  31,5 (2.7) 28 i 2 2.1.2. Xây dựng hàm băm trên cơ sở hệ mật Với ưu điểm mạch điện mã hóa khá đơn giản, ta có thể xây dựng một hàm băm mới từ hệ mật đề xuất ở trên. xi Hi-1 g E Hi Hình 2.3. Sơ đồ hàm băm Bảng 2.2 là kết quả tính toán phân bố của một số mã băm khi thay đổi lần lượt từng bit từ bit 1 đến bit 64 của bản tin rõ so với ban đầu. Bảng 2.2. Khoảng cách Hamming dH(C1,Ci) của hàm băm khi thay đổi 1 bit bản rõ đầu vào TT Bản tin rõ Mi Bản mã Ci dH(C1,Ci) 1 0123456789ABCDEF B588E9ED8C 722E5C 0 2 1123456789ABCDEF 123F4C166B0601C7 42 3 2123456789ABCDEF ADCDA2C8ECC0FC59 24
-10- 4 4123456789ABCDEF 796EF2 C1 BD 130 CC0 28 … … … … 30 0123456689ABCDEF E2 F E1 13 4 34 F91 55 4 34 31 0123456589ABCDEF 1 CE4 9 C5 1 C13 D E 94 1 36 32 0123456389ABCDEF 71 8 A6 4 A 3 B0 F3 FBF2 28 … … … … 63 0123456789ABCDED 1CE49C 51C 13DE941 36 64 0123456789ABCDEB 718A64A3B 0F3FBF2 28 65 0123456789ABCDE7 D D F49CD 63 3A 89DA7 42 Khoảng cách Hamming trung bình giữa các bản mã tính được như sau: 1 65 64  d H (tb)  d H (C1 , Ci )  30,75 (2.8) i 2 Tương tự tiến hành tính toán phân bố của hàm băm khi thay đổi khóa khởi tạo và giữ nguyên bản tin rõ đầu vào, ta được khoảng cách Hamming trung bình giữa các bản mã tính được như trong biểu thức (2.9): 1 29 d H (tb )   d H (C1 , Ci )  31,5 28 i  2 (2.9) Tóm lại: Việc sử dụng cấu trúc cấp số nhân cyclic trên vành đa thức x2  1 làm hàm mã hóa cho hệ mật sử dụng cho hàm băm và sử k dụng các CGP trên vành có hai lớp kề để tạo khóa cho các vòng mã hóa của hệ mật theo sơ đồ Lai-Massey như đề cập ở trên có một số ưu điểm sau: - Sơ đồ mã hóa đơn giản thuận tiện khi sử dụng cho hàm băm - Số lượng khóa tìm được rất nhiều (Nk = 229-1). - Độ khuếch tán của hệ mật khi thay đổi khóa, độ khuếch tán của hàm băm khi thay đổi dữ liệu, hoặc thay đổi khóa đều cho kết quả khá tốt (đạt xấp xỉ một nửa độ dài mã băm).
-11- 2.2. HÀM BĂM DỰA TRÊN HỆ MẬT MÃ LAI GHÉP Với mục đích kết hợp ưu điểm của các hệ mật và sơ đồ mã hóa đã có, NCS đề xuất một phương pháp xây dựng hệ mật mã lai ghép, 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 (có cải tiến). 2.2.1. Bài toán Logarit rời rạc và hệ mật POHLIG-HELLMAN Bài toán logarit rời rạc là bài toán khó, hệ mật Pohlig-Hellman là một hệ mật sử dụng bài toán logarit rời rạc. Phép mã hóa thực hiện theo phương trình đồng dư c  me mod p , phép giải mã được thực hiện theo m  ce mod p . 2.2.2. Đề xuất một phương pháp xây dựng hệ mật mã lai ghép Lược đồ mã hóa của hệ mật thực hiện theo sơ đồ Feistel cân bằng. Hàm mã hóa f sử dụng thuật toán mã hóa của hệ mật Pohlig- Hellman, thực hiện theo một trong hai cách sau: ci  f (mi , ei )  miei mod p (2.15) ci  f (mi , ei )  eimi mod p (2.16) e1 (32bit) e2 (32bit) e3 (32bit) e4 (32bit) Khóa bí mật K (128 bits) Hình 2.6. Tách các khóa con cho các vòng mã hóa Tiến hành mô phỏng tính khuếch tán của hệ mật khi thay đổi dữ liệu bản rõ M và thay đổi khóa bí mật K. Khoảng cách Hamming trung bình của 64 lần thay đổi bản rõ (lần lượt từ bit 1 đến 64) được tính theo công thức sau: 1  64 d H (tb)  d (C , C ) (2.20) 64 j 1 H 0 j Với trường hợp 1 tính được: dH(tb) = 31,84 bít (2.21)
-12- Và trường hợp 2 là: dH(tb) = 31,98 bít (2.22) Khoảng cách Hamming trung bình của các bản mã so với bản mã ban đầu khi thay đổi lần lượt từng bit của khóa K từ bit 1 đến bit 128 được tính theo công thức sau: 1  128 d H (tb)  d (C , C ) (2.23) 128 j 1 H 0 j Với trường hợp 1 tính được: dH(tb) = 28,25 bít (2.24) Và trường hợp 2 là: dH(tb) = 28,23 bít (2.25) Như vậy: Độ khuếch tán của hệ mật khi thay đổi dữ liệu đầu vào và khóa cũng đều đạt xấp xỉ một nửa chiều dài mã băm. 2.2.3. Khả năng xây dựng hàm băm từ hệ mật Với hệ mật như đề xuất ở mục 2.3.2, ta có thể áp dụng vào việc xây dựng các hàm băm không khóa với một số ưu điểm nhất định sau: - Hệ mật sử dụng sơ đồ Feistel cân bằng nên có độ khuếch tán tốt khi thay đổi dữ liệu bản rõ cũng như thay đổi khóa. - Hệ mật có độ an toàn khá tốt vì áp dụng bài toán một chiều logarit rời rạc vào làm hàm mã hóa, ngoài ra độ dài khóa là 128 bit cũng đảm bảo trước tấn công vét cạn. 2.3. HÀM BĂM SỬ DỤNG CÁC CẤP SỐ NHÂN CYCLIC 2.3.1. Mô tả hàm băm MDC-2 sử dụng lưu đồ FEISTEL NCS tập trung xây dựng một hàm băm kép dạng MDC-2 với điểm mới là sử dụng các cấp số nhân cyclic làm hàm mã hóa (trên vành đa thức 2[ x]/ xn 1với n 25 32 ) và tạo khóa (trên vành đa thức có hai lớp kề để đảm bảo số lượng khóa tạo ra là lớn nhất). Mật mã E được xây dựng theo 16 vòng mã hóa theo mô hình mạng hoán vị thay thế Feistel. 2.3.2. Xây dựng hàm băm và kết quả mô phỏng Mô phỏng tính toán tương tự như các hàm băm trước. Tiến hành thay đổi lần lượt từng bit từ bit 1 đến bit 128 của bản tin đầu vào M1
-13- rồi đưa vào hàm băm và tính khoảng cách Hamming dH (MD1, MDi ) 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à: 1 128 128  d H (tb)  d H (MD1, MDi )  64,12 (2.27) i 1 Tiếp tục 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. Bản tin đầu vào gồm 10 khối 128 bit được tạo ngẫu nhiên. Chúng ta tính được khoảng cách Hamming trung bình: 1 52 d H (tb)   d H (MD0 , MDi )  64, 40 (2.28) 52 i 1 KẾT LUẬN CHƯƠNG II Trong chương này, NCS đề 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 32 bít (Khi độ dài mã băm được tạo ra là 64 bít). - Với hệ mật mã 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. - 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 cũng có được độ khuếch tán tốt (xấp xỉ 64 bít). Tóm lại qua khảo sát bằng lý thuyết và mô phỏng, các hệ mật và hàm băm tạo ra ở trên có nhiều ưu điểm: Số khóa nhiều; mạch điện phần cứng đơn giản, dễ 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 ở khoảng cách Hamming tính được ở các trường hợp đều xấp xỉ một nửa chiều dài mã băm.
-14- CHƯƠNG 3. XÂY DỰNG MỘT LỚP CÁC HÀM BĂM MỞ RỘNG MỚI 3.1. XÂY DỰNG HÀM BĂM MỞ RỘNG MỚI MDC-3 NCS đề 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. xi g E g E g E H1i-1 H2i-1 H3i-1 A B A B A B A D A D A D Out 1 H1i Out 2 H2i Out 3 H3i Hi Hình 3.1. Sơ đồ hàm băm MDC-3 đề xuất Khối E mã hóa cho chuỗi bit có độ dài 128, được xây dựng theo dạng mô hình Feistel với một số đổi mới, cải tiến. 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[ x]/ xn 1 với n 26 64 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: Ki  Ka K0i mod x61 1;(i  1...16) (3.1)
-15- 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 M 0 , tính khoảng cách Hamming dH (MD0 , MDi ) 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: 1  384 d H (tb)  d (MD0 , MDi )  192, 26 384 i 1 H 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. Tiến hành thay đổi lần lượt từng bit từ bit 1 đến bit 60 của khóa K1 , 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: 1  60 d H (tb)  d (MD0 , MDi )  193, 43 60 1 H i 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. 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). 3.2. HÀM BĂM DỰA TRÊN HỆ MẬT MÃ KHỐI KẾT HỢP SƠ ĐỒ LAI- MASSEY VỚI SƠ ĐỒ FEISTEL 3.2.1. Hệ mật mã khối kết hợp sơ đồ LAI-MASSEY và FEISTEL Với mục đích kết hợp ưu điểm của hai sơ đồ này, NCS đề 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. Các hàm mã hóa f trong sơ đồ sử dụng các CGP trên vành đa thức 2 [x]/ xn 1 với n  2s , với hệ mật đề xuất, chọn n  26  64 và như thế f
-16- sẽ hoạt động với các khối 64 bit và là các CGP có dạng sau: A  a( x).xi ; i  0,63 (3.8)     Sơ đồ mạch mã hóa với CGP có số hạng đầu là đa thức a( x)  1 x  x7  x35  x60 và công bội x như trong hình 3.5. Dịch 64 nhịp 64 bít (63) ... (60) ....... (35) ... (7) ... (1) (0) Vào 64 bít Ra Hình 3.5. Mạch mã hóa f với a(x) 1 x  x7  x35  x60 Các khóa con ki 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. Chọn vành đa thức có hai lớp kề cyclic x61 1, khi đó 16 khóa cho các vòng mã là 16 phần tử đầu tiên trong một CGP được xây dựng: ki  Ka K0i mod x61 1;(i  0,1,...,15) (3.12) Tiến hành khảo sát tính khuếch tán của hệ mật đề xuất khi thay đổi dữ liệu đầu vào và thay đổi khóa (bằng chương trình mô phỏng). Khoảng cách Hamming trung bình giữa các bản mã của 128 lần thay đổi bit dữ liệu tính được như biểu thức (3.12): 1 128 d H (tb )   d H (C1 , Ci )  64,5bit 128 i 1 (3.12) Độ khuếch tán trung bình giữa các bản mã khi thay đổi khóa: 1 30 d H (tb )   d H (C0 , Ci )  62,53bit 30 i 1 (3.13) 3.2.2. Xây dựng hàm băm trên cơ sở hệ mật kết hợp 3.2.2.1. Sơ đồ hàm băm Ở đây, nghiên cứu sinh đề xuất một sơ đồ hàm băm không khóa dạng MDC-4 với mã băm 512 bit như mô tả trong hình 3.6.
-17- xi (512 bít) xi 1 xi 2 xi 3 xi 4 (128 bít) (128 bít) (128 bít) (128 bít) g E g E g E g E H i21 H i31 H i41 H i11 A1 B1 A2 B2 A3 B3 A4 B4 A1 B2 A2 B3 A3 B4 A4 B1 Hi 1 Hi 2 Hi 3 Hi 4 (128 bít) (128 bít) (128 bít) (128 bít) Hi (512 bít) Hình 0.2. Sơ đồ hàm băm MDC-4 (512 bit) 3.2.2.2. Đánh giá tính khuếch tán của hàm băm Tương tự ta cũng tiến hành tính toán tính khuếch tán của hàm băm khi thay đổi dữ liệu và thay đổi khóa. Dữ liệu băm là 5120 bit bao gồm 10 khối 512 bit và được tạo ngẫu nhiên. Tiến hành tính toán độ khuếch tán của một nghìn lần băm khi thay đổi dữ liệu băm, mỗi lần băm chỉ thay ngẫu nhiên 1 bit trong 5120 bit dữ liệu băm ban đầu. Tất cả các lần băm đều dùng chung khóa ban đầu Ka. Sau mỗi lần băm ta tính khoảng cách Hamming giữa mã băm so với mã băm ban đầu và từ đó tính được khoảng cách Hamming trung bình của một nghìn lần băm theo biểu thức (3.15) dưới đây: 1 1000 1000  d H (tb)  d H (C0 , Ci )  255,84bit (3.15) i 1
-18- Tương tự, tính toán độ khuếch tán trong 60 lần băm khi thay đổi khóa băm khởi tạo Ka, mỗi lần băm thay đổi ngẫu nhiên 1 bit trong số 60 bit khóa ban đầu (bit 61 vẫn để đảm bảo khóa có trọng số lẻ). Tất cả các lần băm đều có cùng dữ liệu băm, ta cũng tính được độ khuếch tán trung bình của 60 lần băm theo biểu thức (3.16) sau đây: 1 60 60  d H (tb)  d H (C0 , Ci )  256,57 bit (3.16) i 1 Như vậy: Độ khuếch tán của hàm băm khi thay đổi dữ liệu, thay đổi khóa đều cho kết quả tốt (xấp xỉ 254 bit so với mã băm 512 bit). 3.3. XÂY DỰNG HÀM BĂM MỞ RỘNG MỚI MDC 512 BÍT 3.3.1. Mô tả hệ mật mã khối 256 bít Sơ đồ mã hóa của hệ mật mã khối dựa trên mạng Feistel bốn nhánh không cân bằng (mỗi nhánh có độ dài 64 bít). Hàm mã hóa f có bốn đầu vào, ba đầu vào dữ liệu ( bi , ci và di ) và một đầu vào khóa ki . Độ dài của tất cả bốn đầu vào và đầu ra đều là 64 bit. Việc mã hóa được thực hiện bởi các CGP trên vành đa thức 2 [ x]/ xn 1 với n  26  64 . Cấu trúc của CGP sử dụng trong hàm f có dạng: Ai  ki ( x).g j ( x) mod x64  1; j  1, 2,...,64 (3.19) Dịch 64 nhịp Khóa con ki (64 bit) (63) (62) (2) (1) (0) (64 bits) bi p63 p62 p2 p1 p0 ci MAJ di Ra mi = p0 + p1x + p2x2 + …+p62x62 + p63x63 (64 bit) Hình 3.9. Mạch mã hóa hàm f 3.3.2. Đánh giá độ khuếch tán của hệ mật Tiến hành tính toán độ khuếch tán của hệ mật khi thay đổi mỗi bit dữ liệu bản rõ, đa thức sinh ka và đa thức đầu k0 để tạo khóa của hệ