Tài liệu NGHIÊN CỨU HỆ MẬT MÃ KHỐI DỰA TRÊN HỖN LOẠN RỜI RẠC

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI TẠ THỊ KIM HUỆ NGHIÊN CỨU HỆ MẬT MÃ KHỐI DỰA TRÊN HỖN LOẠN RỜI RẠC Chuyên ngành: Kỹ thuật viễn thông Mã số: 62520208 TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT VIỄN THÔNG HÀ NỘI - 2017 Công trình này được hoàn thành tại Trường Đại học Bách khoa Hà Nội Người hướng dẫn khoa học: PGS.TS.Hoàng Mạnh Thắng Phản biện 1: GS.TS. Nguyễn Bình Phản biện 2: PGS.TS. Bạch Nhật Hồng Phản biện 3: PGS.TS. Phạm Ngọc Thắng Luận án được bảo vệ trước Hội đồng đánh giá luận án tiến sĩ cấp trường họp tại Trường Đại học Bách khoa Hà Nội vào hồi 9 giờ, ngày 15 tháng 03 năm 2017 Có thể tìm hiểu luận án tại: 1. Thư viện Tạ Quang Bửu, Trường ĐHBK Hà Nội 2. Thư viện Quốc gia Việt Nam MỞ ĐẦU 1. Mật mã và kỹ thuật hỗn loạn trong bảo mật thông tin Bảo mật là một kỹ thuật thiết yếu trong hệ thống thông tin. Xu hướng phát triển công nghệ thông tin là người dùng có thể chia sẻ và sử dụng chung tài nguyên mạng từ những vị trí địa lý khác nhau trong các thời điểm khác nhau, dẫn đến sự phân tán tài nguyên và hậu quả là tăng nguy cơ mất mát dữ liệu và các thông tin có giá trị. Càng mở rộng các kết nối thì xuất hiện càng nhiều lỗ hổng bảo mật, tài nguyên càng dễ bị tấn công và xâm phạm. Mật mã là một trong những biện pháp an toàn và đáng tin cậy để bảo mật dữ liệu hiệu quả. Do đó, ứng dụng kỹ thuật mật mã là xu hướng tất yếu trong truyền tin bảo mật. Do vậy những thay đổi trong cách đánh giá độ an toàn của mật mã hiện đại đã mở ra nhiều hướng nghiên cứu mới của mật mã như: Bảo mật trong điện toán đám mây; Mở rộng mô hình mã hóa cho nhóm đối tượng và cho việc giải mã từng phần; An toàn trước các tấn công vật lý; An toàn trước sự tấn công của máy tính lượng tử và Bảo mật trong mạng lưới IoTs. Các hàm hỗn loạn rời rạc được chứng minh là kế thừa được các tính chất của các hàm hỗn loạn liên tục như tính chất nhạy cảm với điều kiện đầu, nhạy cảm với sự thay đổi giá trị của các tham số và không thể dự báo dài hạn. Ưu điểm của mật mã hỗn loạn được xem như mô hình phát triển mật mã hiện đại [25, 31]. Về nguyên lý, các phương pháp bảo mật ứng dụng hỗn loạn là lợi dụng sự phức tạp của các đặc tính động học của hệ thống hỗn loạn cũng như đặc trưng của hệ thống hỗn loạn để che giấu thông tin dựa trên các giải thuật thực hiện khác nhau. Do đó, mật mã hỗn loạn là một hướng nghiên cứu mới, an toàn và đáng tin cậy để bảo mật dữ liệu 1 hiệu quả. Mật mã hạng nhẹ và mật mã hỗn loạn có thể thay thế mật mã chuẩn là hai hướng nghiên cứu được quan tâm trong những năm gần đây. Ưu nhược điểm của mật mã hỗn loạn đã được nghiên cứu chi tiết. Dựa trên những tính chất này, luận án đề xuất dùng hàm hỗn loạn cho mật mã hạng nhẹ để cải thiện các nhược điểm về bảo mật của mật mã hạng nhẹ. Bài toán thiết kế mật mã hạng nhẹ sử dụng hàm hỗn loạn rời rạc như là một hướng đi mới để cải thiện thời gian thực thi và khả năng bảo mật cho mật mã hạng nhẹ. Các thuật toán mật mã được đề xuất trong [30], [16] và thuật toán ẩn tin (steganography) [21] dễ dàng bị phân tích khi chu kỳ của hàm hỗn loạn rời rạc quá ngắn [7]. Các tác giả trong [8] đã giải thích sự phụ thuộc của chu kỳ vào các tham số điều khiển. Tác giả trong [8] bình luận rằng chu kỳ của hàm hỗn loạn càng dài thì càng tốt về mặt bảo mật khi áp dụng hàm hỗn loạn đó vào hệ mật mã. Do đó, chu kỳ của hệ hỗn loạn rời rạc cũng là một trong nhưng tham số quan trọng trong bài toán thiết kế mật mã hỗn loạn nói chung. 2. Những vấn đề còn tồn tại Tính chất phức tạp của hệ hỗn loạn tạo ra tính ưu việt trong bảo mật thông tin như là khả năng chịu đựng các tấn công phân tích mã, tăng tốc độ xử lý, tăng độ phức tạp thuật toán. Điều này đã được khẳng định trong các nghiên cứu của Kocarev [24], Masuda [31] và Fridrich [16]. Tìm ra các bài toán thiết kế hệ mật mã dựa trên hỗn loạn phù hợp với xu hướng phát triển của mật mã hiện đại. Mật mã hạng nhẹ hướng tới việc tìm ra điểm cân bằng của ba yếu tố: Giảm tài nguyên thực thi, giảm thời gian xử lý, tăng mức độ bảo mật [14]. Do đó, hướng phát triển của mật mã hạng nhẹ được quan tâm nhiều hiện nay là cải tiến các hệ mã thông qua việc đề xuất các hàm mã hóa mới [32]. Phân bố chu kỳ của hàm Cat hai chiều (Arnold’s Cat map) đã được phân tích bởi Chen và các cộng sự trong [7, 8, 9], tuy nhiên phương pháp này chỉ áp dụng cho hàm Cat hai chiều và cho các trường hợp giá trị tham số hoàn toàn xác định. Khi áp dụng cho hàm Cat đa chiều phương pháp 2 này trở nên phức tạp rắc rối, và việc đánh giá chu kỳ của hàm Cat mở rộng vẫn là một vấn đề mở cần tìm hiểu. 3. Mục tiêu, đối tượng và phạm vi nghiên cứu Bài toán thiết kế thuật toán hệ mật mã sử dụng các ánh xạ hỗn loạn đã được nghiên cứu rất nhiều trong thời gian gần đây. Có thể khẳng định rằng đây là một hướng nghiên cứu mới trong việc tạo ra những bộ mã mật có thể tương đương những bộ mã truyền thống về khả năng bảo mật, dễ dàng thực hiện trên phần cứng, giảm thời gian xử lý, giảm chi phí thiết kế. Luận án nghiên cứu một số hướng phát triển của mật mã hiện đại từ đó dẫn dắt các ra vấn đề trong mật mã hỗn loạn. Dựa trên những vấn đề đã phân tích, luận án đề xuất thuật toán tạo mật mã khối hỗn loạn theo cấu trúc mạng hoán vị thay thế (SPN). Khả năng bảo mật của hệ thống cũng được đánh giá qua các hệ số đặc trưng cho các tấn công bảo mật. Luận án đề xuất hai hàm hỗn loạn rời rạc là Skew Tent và Standard cho mô hình thiết kế hệ mật mã hỗn loạn hạng nhẹ. Luận án đề xuất phương pháp mở rộng hàm Arnold Cat rời rạc dựa trên biến đổi giả Hadamard nhanh gọi là hàm Cat-Hadamard. Kết quả đạt được là hàm Cat-Hadamard kế thừa hoàn toàn các đặc tính hỗn loạn của hàm Cat hai chiều, do đó có thể thay thế hàm Cat bởi Cat-Hadamard trong các ứng dụng mật mã. 4. Phương pháp nghiên cứu Luận án nghiên cứu gồm lý thuyết, mô phỏng và thực nghiệm. Phân tích lý thuyết cho các ý tưởng đề xuất để giải quyết vấn đề thông qua công cụ là toán học với các chứng minh rõ ràng. Các phân tích đánh giá về mặt lý thuyết được kiểm chứng qua mô phỏng trên máy tính bằng Matlab hoặc ngôn ngữ C/C++. Một phần trong các nghiên cứu được thực hiện trên phần cứng và phần mềm cho thấy khả năng ứng dụng thực tế của ý tưởng đề xuất. 5. Ý nghĩa khoa học và những đóng góp của luận án 3 Luận án nghiên cứu tính chất của các hàm hỗn loạn khi được biểu diễn trong miền hữu hạn chính xác. Ảnh hưởng của các tham số đến tính chất đầu ra và chu kỳ của hàm hỗn loạn một chiều, hai chiều hoặc nhiều chiều. Từ đó đề xuất thuật toán mật mã khối theo cấu trúc mạng lưới hoán vị thay thế với các cấu trúc lớp thay thế S-box và lớp hoán vị dựa trên hỗn loạn. Mở rộng hàm CAT rời rạc trong miền số nguyên hữu hạn và trong trường Galois, so sánh với các phương pháp hiện có thông qua việc tính toán Kolmogorov-Sinai (KS) entropy, hoặc phân bố xác suất Chi- bình phương với giả thiết phân bố của chuỗi giả ngẫu nhiên được tạo ra là một phân bố đều. Đánh giá các trạng thái trung gian được tạo ra theo các bước lặp hàm Cat map mở rộng, lựa chọn tham số thay đổi. Chứng minh các tính chất của hàm CAT mở rộng có sự kế thừa từ hàm CAT hai chiều, thông qua biến đổi Hadamard nhanh, số chiều của CAT được tăng lên nhanh chóng trở thành một hàm đa biến đầu vào. Hai ứng dụng hàm Cat mở rộng là thiết kế bộ tạo đa ma trận MDS cho hệ mật mã khối và bộ tạo chuỗi số giả ngẫu nhiên. 6. Cấu trúc nội dung của luận án Chương 1, luận án trình bày các nguyên tắc thiết kế hệ mật mã hỗn loạn và các vấn đề còn tồn tại trong hệ mật mã hỗn loạn, từ đó đề xuất một mô hình thiết kế hệ mật mã khối hỗn loạn dựa trên cấu trúc lưới hoán vị thay thế cho ứng dụng mã hóa ảnh. Chương 2, luận án đề xuất hai biến thể cho thuật toán mật mã khối hạng nhẹ theo cấu trúc mạng hoán vị thay thế (SPN) dựa trên hỗn loạn. Các thiết kế hướng tới tiêu chí tăng độ bảo mật nhưng vẫn thỏa mãn yêu cầu cài đặt, tài nguyên sử dụng và thời gian xử lý phù hợp với yêu cầu của thuật toán mật mã hạng nhẹ. Chương 3 đề xuất một dạng thức mở rộng hàm Cat dựa trên biến đổi giả Hadamard nhanh, được gọi là hàm Cat-Hadamard. Đề xuất hai ứng dụng hàm Cat mở rộng là thiết kế bộ tạo đa ma trận MDS cho hệ mật mã khối và bộ tạo chuỗi số giả ngẫu nhiên. 4 Chương 1 MẬT MÃ HỖN LOẠN 1.1. Nguyên lý thiết kế mật mã hỗn loạn Hỗn loạn được nghiên cứu trong bảo mật về cơ bản chia làm hai nhánh nghiên cứu chính, là bảo mật cho luồng bit ngay trong quá trình truyền tin và bảo mật cho cả một đơn vị dữ liệu, thường được tính theo khối bit/byte dữ liệu [24]. Nghiên cứu về hệ mật mã hỗn loạn trong [25], [24] và [43], các tác giả đã đề xuất 10 nguyên tắc thiết kế hệ mã mật dựa trên hỗn loạn là: 1. Định nghĩa đầy đủ và nghiêm ngặt các nguyên lý thiết kế. 2. Định nghĩa đầy đủ và nghiêm ngặt về khóa và không gian khóa. 3. Lựa chọn các hàm hỗn loạn (ánh xạ hỗn loạn) có độ nhạy cao để điều khiển các tham số không phù hợp. 4. Lựa chọn hàm hỗn loạn không nên làm lộ toàn bộ đặc tính động lực học của hệ thống: Điều này có thể làm cho kẻ tấn công dự đoán thông tin về các tham số điều khiển hoặc điều kiện khởi tạo. 5. Phân tích hiệu năng của các quỹ đạo hỗn loạn như nguồn Entropy. 6. Nên sử dụng các hàm (ánh xạ) hỗn loạn có hàm mật độ phân bố đều và sự đo lường tập bất biến không phụ thuộc vào các tham số điều khiển. 5 Kj Input data Encryptor Key generator Control _ Block Buffer Output data Decryptor Kr-j-1 control Hình 1.1: Sơ đồ khối thiết kế phần cứng 7. Không gian bản mã phải được xác định theo cách mà sự khôi phục lại đặc tính động học của các hàm hỗn loạn là không khả thi. 8. Thời gian mã hóa/giải mã không phụ thuộc vào giá trị của khóa bí mật của một hệ mật mã hỗn loạn. 9. Hệ mật mã hỗn loạn có khả năng chống lại các kiểu tấn công cổ điển [39, 43]. 10. Chống được các tấn công tương ứng với các ứng dụng cụ thể. 1.2. Đề xuất hệ mật mã khối hỗn loạn rời rạc dựa trên cấu trúc mạng hoán vị - thay thế Luận án đề xuất sơ đồ khối phần cứng cho hệ mật mã khối hỗn loạn, thiết kế này đề xuất việc tích hợp cả phần giải mã và phần tạo mã trên cùng một khối. Do đó, phần cứng có thể thực hiện chức năng của một bộ mã hoặc một bộ giải mã đồng thời, phù hợp với các mô hình lưu trữ hoặc truyền thông tin trong thời gian thực như Hình 1.1. Bản rõ là ảnh số RGB, kích thước cho mỗi lớp mầu là là H × W trong đó H là kích thước ảnh theo chiều dọc cũng là số lượng điểm ảnh đếm được theo chiều dọc và W là kích thước ảnh theo chiều ngang cũng là số lượng điểm ảnh đếm được theo chiều ngang, được biểu diễn dưới dạng chuỗi các byte liên tiếp một chiều. 6 Bộ tạo khóa Bộ tạo khóa Kj={Ksj; Kpj} Kr-j-1={Ksr-j-1; Kpr-j-1} Bản rõ Bản rõ rs Khối thay thế byte Hàm SkewTent Ksr-j-1 Ksj Khối thay thế byte Hàm SkewTent ngược rs r r rp Khối hoán vị bit Hàm Standard Bản mã Kpr-j-1 Kpj Kênh truyền Khối hoán vị bit ngược Hàm Standard rp Bản mã Hình 1.2: Thuật toán mã hóa ảnh RGB Thuật toán lập mã Hình 1.2 mô tả thuật toán lập mã với khóa bí mật Kj được tạo ra từ bộ tạo khóa. Kj đóng vai trò là tham số điều khiển và tạo ra hai khóa con cho khối thay thế và hoán vị là Ksj và Kpj , ta có Kj = {Ksj ; Kpj }. Ảnh RGB-8bit có 3 lớp mầu và mỗi điểm ảnh được mã hóa bằng 8-bit, ảnh đầu vào được biến đổi thành một chuỗi một chiều gồm các byte là P = [p1 p2 ...pm ...], trong đó pm ∈ {0, 1, ..., 255}. Chuỗi P được phần chia thành các khối có kích thước cố định là Tblock = 2 byte. Khối thứ b là B(b) sẽ chứa byte thứ i và byte thứ (i + 1)th của chuỗi P . Ta có, B(b) = [pi pi+1 ] là một khối gồm hai byte pi và pi+1 . Mỗi byte trong khối B(b) được thay thế giá trị bằng việc áp dụng hàm Skew Tent rời rạc [15, 31]. Ksj là tập các tham số điều khiển tại vòng thứ j, ta có Ksj = [ksj1 ; ...; ksji ; ...; ksjrs ]. Trong đó, ksji là tham số điều khiển tại vòng thứ i của quá trình thay thế và tại vòng thứ j của toàn bộ thuật toán. Sau đó, mỗi khối B(b) thu được sau tiến trình thay thế được sắp xếp lại trong ma trận bit hai chiều để thực hiện quá trình hoán vị, với kích thước ma trận hai chiều là M × M . Trong quá trình hoán vị, vị trí các bit trong ma trận hai chiều được hoán đổi bằng hàm Standard [26]. Quá trình thay thế giá trị byte được lặp lại rs lần, sau đó đầu ra của khối thay thế sẽ là đầu vào của khối hoán vị. Quá trình hoán vị vị trí các bit trong ma trận hai chiều được lặp lại rp lần, và cả hai quá trình này được lặp thêm r 7 LFSR1 Qk1(n) X1(0) f(X1(n-1)) Bộ tạo các giá trị khởi tạo ngẫu nhiên Xi(0) LFSR2 Qk2(n) X2(0) f(X2(n-1)) LFSR3 Qk3(n) X3(0) X1(n) X2(n) X3(n) Tạo ra các tham số điều khiển Ksj Kpj f(X3(n-1)) Hình 1.3: Bộ tạo khóa hỗn loạn lần cho toàn bộ thuật toán. Thuật toán giải mã Thuật toán giải mã là các tiến trình thực thi ngược lại so với thuật toán mã hóa. Tham số của quá trình thay thế ngược hay còn được gọi là giải thay thế là ksji sẽ được đồng bộ với các giá trị tương ứng ở thuật toán mã hóa. Toàn bộ các đầu ra của thuật toán giải mã sẽ thu được sau r vòng lặp. Về mặt thực thi tham số Kr−j−1 cho lần lặp thứ (r − j − 1) ở quá trình giải mã có giá trị tương đương với tham số Kj tại vòng lặp thứ j của quá trình mã hóa. Khối điều khiển trong sơ đồ Hình 1.1 sẽ đồng bộ hai tập khóa tương ứng Kj and Kr−j−1 cho cả bộ mã hóa và giải mã, ta có Kj = {Ksj ; Kpj } và Kr−j−1 = {Ksr−j−1 ; Kpr−j−1 }. Bộ tạo khóa hỗn loạn Kiến trúc bộ tạo khóa hỗn loạn trong thiết kế này dựa trên mô hình được trình bày trong [15]. Bộ tạo khóa gồm hàm Logistic được kết nôi song song như Hình 1.3. Trong đó, X1 (0) , X2 (0) và X3 (0) nằm trong khoảng từ 1 đến 2N − 1. 8 (a) Hình ảnh của bản rõ 1 và bản mã 1 (b) Hình ảnh của bản rõ 2 và bản mã 2 Hình 1.4: Hình ảnh của bản rõ và bản mã tương ứng với thuật toán đề xuất Phân tích bảo mật Đánh giá mức độ bảo mật của hệ mật mã khối hỗn loạn đề xuất, luận án lựa chọn các thông số NPCR và UACI [45]. Để xác định độ nhạy cảm của hệ mật mã đề xuất với khóa mật, xét hệ số CDR [27], hệ số này chỉ rõ sự thay đổi nhỏ của khóa bí mật, sẽ làm thay đổi rất lớn giá trị đầu ra của bản mã. Điều này rất có ý nghĩa trong việc chống tấn công vét cạn và tấn công thống kê, giả sử kẻ thù có năng lực tính toán siêu việt có thể tiến hành được bất cứ phép tìm kiếm vét cạn không gian khóa hữu hạn, khi chỉ số CDR tiến đến 100% thì thời gian cần cho thực hiện tấn công vét cạn là gần như vô hạn. Bảng 1.1, lưu các giá trị của các hệ số CDR, NPCR, UACI, các tác giả trong [45] chỉ ra rằng nếu các giá trị NPCR >99.56%, UACI >33.22%, thì hệ mật mã không bị phân tích bởi các loại tấn công bảo mật như tấn công vét cạn, tấn công vi sai và tấn công chỉ biết bản mã [45]. Các giá trị cho thấy khả năng chống tấn công của hệ mã đề xuất hoàn toàn tương đương với các bộ mã kinh điển AES. 9 Bảng 1.1: So sánh các hệ số NPCR, UACI và CDR của bản mã thu được từ thuật toán đề xuất và AES Ảnh 1 Thuật toán NPCR UACI CDR Mật mã khối hỗn loạn [C1] 99.63% 33.39% 94.65% AES - Chế độ CBC [41] 99.60% 33.41% 96.66% Thuật toán Ảnh 2 NPCR UACI CDR Mật mã khối hỗn loạn [C1] 99.72% 33.56% 95.12% AES - Chế độ CBC [41] 99.85% 33.31% 98.54% Bảng 1.2: So sánh tài nguyên phần cứng thực thi trên kit phát triển Altera FPGA DE2 Thuật toán Mật mã khối Tổng số Tổng số Pin Thời gian cổng Logic thanh ghi 12% 4% 8% 181.174 ms 7% 4% 82% 196.608 ms 36% 28% 82% 4 ms mã hóa hỗn loạn [C1] AES - Chế độ ECB [41] nối tiếp AES - Chế độ ECB [41] song song Tài nguyên thực thi Các mô tả thiết kế phần cứng của thuật toán được trình bày trong các bài báo đã công bố [C1] và [C3]. Kết quả thực nghiệm chỉ ra rằng thuật toán mật mã khối hỗn loạn theo cấu trúc SPN phù hợp với các tiêu chí thiết kế và giải quyết các vấn đề đã phân tích ở trên. Tài nguyên của hệ mật mã khi thực thi trên kit phát triển Altera FPGA DE2 là rất nhỏ ≤ 15% so với tài nguyên của toàn hệ thống. 10 Chương 2 ĐỀ XUẤT HỆ MẬT KHỐI HẠNG NHẸ DỰA VÀO CÁC ĐẶC TÍNH HỖN LOẠN CỦA HÀM SKEW TENT VÀ STANDARD RỜI RẠC 2.1. Thiết kế lớp S-box 4×4 móc xích dựa trên tính chất hàm Skew Tent rời rạc Hàm Skew Tent ( xn = xn−1 /r nếu xn−1 ∈ [0, r] , (1 − xn−1 ) / (1 − r) nếu xn−1 ∈ (r, 1] (2.1) với 0 < r ≤ 1. Đồ thị hàm Skew Tent được mô tả trong Hình 2.1. Hàm Skew Tent rời rạc [30] là FA : [0, M ] → [0, M ] với tham số 0 < A < M là tham số điều khiển, được định nghĩa như sau. ( xn−1 /A nếu 0 ≤ xn−1 ≤ A FA (xn−1 ) = . (2.2) (M − xn−1 ) / (M − A) nếu A < xn−1 ≤ M Hàm Skew tent lượng tử hóa được mô tả như sau: (
X ceil M ×K nếu1 ≤ X ≤ K 1  . FK (X) = M −X f loor M × M −K + 1 nếu K < X ≤ M (2.3) 1 là một ánh xạ song ánh, M là số nguyên dương Dễ dàng nhận thấy, FK và M ≥ 2. Trong mật mã học, ánh xạ đảo ngược có vai trò quan trọng 11 SKEW TENT MAP 1 0.8 x(n) 0.6 0.4 0.2 0 0 1000 2000 3000 n 4000 5000 6000 (a) Đồ thị biên độ (b) Đồ thị pha Hình 2.1: Đồ thị biên độ và pha của hàm Skew Tent trong thuật toán giải mã. Gọi được tính như sau:    X1 , −1 FK (Y ) = X2 ,   X1 , −1 −1 là hàm ngược của hàm Skew Tent, FK FK nếu m(Y ) = Y và XK1 > nếu m(Y ) = Y và XK1 ≤ nếu m(Y ) = Y + 1 M −X2 M −K M −X2 M −K , (2.4) trong đó     X1 = M −1 KY ; X2 = (M −1 K − 1)Y + M     m (Y ) = Y + M −1 KY − M −1 KY + 1. (2.5) (2.6) Trong trường hợp tổng quát, để thiết kế S-box u × v bit, có nghĩa là với u bit đầu vào sẽ tạo ra v bit đầu ra. Do vậy các giá trị đầu vào của S-box sẽ là các số dương X nằm trong khoảng X = [0, 1, 2, ..., 2u − 1] và đầu ra nằm trong khoảng (0, 1, 2, ..., 2v − 1), như vậy không gian giá trị đầu ra của hàm Skew Tent khi thiết kế S-box là Y = [0, 1, 2, ..., M − 1] và M = 2v − 1. Khi đó, S-box được tạo ra sau khi lặp hàm Skew Tent rời rạc k lần theo phương trình (2.8). 12 X0 X1 S-box 4x4 hỗn loạn S-box 4x4 hỗn loạn Y0 Y1 X15 Lớp S – boxes C0=IV … … S-box 4x4 hỗn loạn Y15 Hình 2.2: Lược đồ lớp S-box hỗn loạn móc xích k SK (X) = FK (X + 1) − 1, (2.7) hàm chuyển đổi S-box ngược trong thuật toán giải mã có dạng sau −k −1 (X + 1) − 1. (X) = FK SK (2.8) k : Gu → G v . với FK 2 2 Lớp S-box hỗn loạn móc xích được mô tả Hình 2.2, chế độ móc xích (Chaining block mode) là mô hình bảo mật chống tấn công lựa chọn bản rõ [41]. Trong lược đồ lớp S-box hỗn loạn móc xích, định nghĩa khối đầu vào là 64 bit X = x63 x62 ...xb ...x1 x0 , với xb ∈ {0, 1} là các bit độc lập nhau, chia thành 16 khối con Xi mỗi khối 4 bit Xi = x4×i+3 ||x4×i+2 ||x4×i+1 ||x4×i với i = {0, 1, 2...15}. Các khối Xi là đầu vào của lớp S-box 4 × 4-bit nối móc xích với nhau, các S-box được tạo ra trong Phần 2.1.2 phụ thuộc vào tham số điều khiển K và số vòng lặp rp. Đầu vào mỗi S-box thu được khi cộng đảo bit (XOR) khối Xi và đầu ra của S-box trước đó Yi−1 trong chuỗi móc xích. Tại S-box đầu tiên khối X0 cộng với véc-tơ khởi tạo (Initialization vector-IV) là C0 như phương trình (2.9- 2.10), do đó sẽ làm tăng độ ảnh hưởng lẫn nhau của các S-box trong chuỗi. Y0 = SK (K, [X0 ⊕ IV ]). (2.9) Ym = SK (K, [Xm ⊕ Ym−1 ]); m = 1, 3...15, (2.10) trong đó, SK là các S-box phụ thuộc tham số K. Khả năng chống tấn công phân tích thống kê tuyến tính hoặc vi phân phụ thuộc vào số lượng S-box hoạt động ở đầu ra. Một S-box được gọi là S-box hoạt động nếu và chỉ nếu S-box đó khác không. Ta có định lý sau 13 x 0 x1 x 2 x 3 x4 x5 x6 x7 S1 S2 x60x61x62x63 …………………. Lớp xáo trộn …………………. S16 Lớp trộn byte (MixBytes) Lớp khuếch tán ………………………… Lớp hoán vị bit (PerBits) …………………………… y60y61y62y63 y 0 y1 y 2 y 3 Hình 2.3: Lớp khuếch tán hỗn loạn Gọi M số bit của một khối đầu vào, xét Sj : G42 → G42 và Sj+1 : G42 → G42 là hai S-box hoạt động, trong đó Sj là S-box thứ j t h trong chuỗi móc xích. Gọi Xj , Xj+1 ∈ G42 là hai khối con đầu vào 4 bit. Do đó đầu ra Yj = Sj (Xj ⊕ Yj−1 ) và Yj+1 = Sj+1 (Xj+1 ⊕ Yj ) có thể viết lại như sau Yj+1 = Sj+1 (Xj+1 ⊕ Sj (Xj ⊕ Yj−1 )). Có thể thấy rằng, M bit đầu vào chia thành M 4 khối con Xj mỗi khối 4 bit, các S-box móc xích với nhau nên mỗi khối con đầu ra được tạo ra sẽ chứa ít nhất 1 S-box hoạt động, và M tương ứng với M 4 đầu ra sẽ có ít nhất 4 S-box hoạt động. 2.2. Thiết kế lớp khuếch tán dựa trên hỗn loạn Lớp khuếch tán hỗn loạn được mô tả như Hình 2.3. Bao gồm hai lớp con (lớp phụ) là Lớp trộn các byte (MixBytes), lớp thứ hai là lớp hoán vị phi tuyến (PerBits) theo các bit. Đối với thiết kế mật mã hạng nhẹ hiện đại [4, 17, 18, 23, 35, 42], độ dài một khối bản rõ là 2m bit, lớp thay thế có 2m−2 S-box kích thước 4 × 4 − bit, số byte được tính tương ứng là tByte = 2m−3 . Ví dụ, một khối bản rõ kích thước là 2m = 64 bit, thì tByte = 2m−3 = 8 byte. Đầu ra của lớp S-box được sắp xếp lại thành các byte để đưa vào lớp MixBytes. Gọi Si và Si+1 là hai S-box lân cận, và X = Si Si+1 là byte được ghép bởi hai lân cận nhau, do đó Si là 4 bit trọng số cao và Si+1 là 4 bit trọng số thấp của X. Hàm Standard có đặc tính hỗn loạn tốt hơn các hàm hỗn loạn hai chiều 14 khác khi sử dụng các đại lượng đo tính trộn, entropy hoặc phân bố thông kê Chi-bình phương, ngoài ra quỹ đạo hỗn loạn của hàm Standard cũng được phân tích chi tiết trong [1] thể hiện rằng hàm Standard hoàn toàn phù hợp với thiết kế hệ mã mật hỗn loạn, ví dụ trong [26] tác giả đề xuất sử dụng hàm Standard để thiết kế hệ mật mã khối, hàm Standard cũng được sử dụng nhiều trong các thuật toán mã hóa ảnh như trong [27, 33, 44]. Trong phần này, luận án sử dụng hàm Standard cho ứng dụng tạo ra lớp hoán vị bit (Perbits) cho khối khuếch tán. Hàm Standard rời rạc được biểu diễn như sau ( xi+1 = mod  (xi + yi , N )    , (2.11) yi+1 = mod yi + K × sin xi+1N×2π , N với (xi , yi ) ∈ [0, N ]. Giả sử khối đầu vào lớp hoán vị có kích thước 22×m bit nối tiếp, sắp xếp các bit vào ma trận bit hai chiều kích thước N = 2m . Gọi bit i có vị trí thứ i trong chuỗi bản rõ ban đầu i ∈ {0, 1, ..., 22×m } và (xi , yi ) là tọa độ của bit i trong ma trận bit hai chiều, (xi+1 , yi+1 ) là tọa độ bit i + 1 và i + 1 là vị trí của bit i sau khi được hoán vị thông qua hàm Standard. Khi đó, i = xi × N + yi và i + 1 = xi+1 × N + yi+1 . Tọa độ (xi+1 , yi+1 ) được tính như phương trình (2.12) " # " # xi+1 x i = F rp , (2.12) yi yi+1 Để đánh giá hiệu quả của lớp khuếch tán đề xuất, luận án dựa trên chiến thuật vết rộng theo [11, 12, 13] từ đó tìm ra phân phối vết về mặt lý thuyết trong mỗi véc-tơ đầu vào và đầu ra tương ứng. Xét véc-tơ hSXi là một tập các trạng thái đầu vào chứa Ms S-box với hSXi = h0, 0, ..., Sm , ..., 0i, và chỉ có một S-box hoạt động là Sm 6= 0 do đó ||S|| = 1. Thực hiện lớp khuếch tán qua năm bước lặp, số nhánh của véc-tơ trạng thái đầu ra hSY i được tính trong Bảng 2.1. Kết quả thu được trong Bảng 2.1 cho thấy số nhánh của lớp khuếch tán đề xuất thu được sau 3 bước lặp lớn hơn so với các thuật toán mật mã khối hạng nhẹ cấu trúc SPN. Chiến thuật vết rộng của họ mật mã khối giống AES (AES-like) [12] tuân theo nguyên tắc sau, các mẫu hoạt động trong một vòng được xác đinh bởi các S-box khác không trong các trạng thái khác nhau tại đầu vào 15 Bảng 2.1: So sánh số lượng S-box hoạt động Số vòng Số nhánh LED/ PHOTON/ KLEIN Lớp khuếch tán hỗn loạn. 1 5 3 2 6 6 3 8 13 4 9 16 5 9 16 mỗi vòng. Chúng ta có thể so sánh một cách ngắn ngọn lớp khuếch tán của LED và lớp khuếch tán đề xuất theo mẫu hoạt động như Hình 2.4. Các bước SubByte và AddRoundKey sẽ bỏ qua vì cả hai không đóng vai trò lan truyền mẫu hoạt động. Mẫu hoạt động tại mỗi vòng lặp và véc-tơ hSi và có ít nhất một S-box hoạt động, các S-box khác không được quy ước là các ô mầu xám (grey box). Các mẫu hoạt động Các mẫu hoạt động Dịch hàng Trộn Byte Trộn cột (a) Lớp khuếch tán của LED Hoán vị bit (b) Lớp khuếch tán hỗn loạn đề xuất Hình 2.4: So sánh sự lan truyền của các mẫu hoạt động trong một vòng lặp của lớp khuếch tán hỗn loạn và của LED/PHOTON/KLEIN/mCrypton 16 Chương 3 MỞ RỘNG HÀM ARNOLD CAT VÀ CÁC ỨNG DỤNG 3.1. Mở rộng hàm Arnol Cat hai chiều dựa trên biến đổi giả Hadamard nhanh Hàm Cat được giới thiệu bởi Arnold [34] là hàm kiểu tuyến tính phân đoạn theo từng chiều. Dạng thức toán học của hàm Cat rời rạc được định nghĩa như phương trình (3.1), khi đó Cat được coi như là một ánh xạ F : S 2 → S 2 , và S = [0, N − 1] là miền số hữu hạn khi N là một số dương. Hàm Cat hai chiều rời rạc được định nghĩa như sau # " # ! " x1 (n) x1 (n − 1) = mod A (a, b)2×2 × ,N , (3.1) x2 (n) x2 (n − 1) " # 1a khi đó, A (a, b)2×2 = được gọi là ma trận hai chiều và n b a×b+1 là số bước lặp hàm và N được gọi là toán hạng của phép chia Modulo với N > 1. Biến đổi giả Hadamard nhanh (FPHT) [40] được định nghĩa bởi quan hệ sau " # " # 2 × Hk−1 Hk−1 21 Hk = = ⊗ Hk−1 , (3.2) Hk−1 Hk−1 11 trong đó, k ≥ 1, H0 = 1, Hk là ma trận kích thước 2k × 2k và ⊗ được quy ước là phép nhân Kronecker [19]. Trong trường hợp đặc biệt a = b = 1, 17 hàm Arnold Cat trong phương trình (3.1) được coi là biến đổi FPHT với H1 = AT (1, 1)2×2 . Xem xét mở rộng của hàm Cat hai chiều từ phương trình (3.1) thành ma trận 2k -chiều sử dụng FPHT. Ma trận đầu tiên của biến đổi FPHT trong phương trình (3.2) được lựa chọn như sau H1 = AT (a, b)2×2 . Do đó hàm đề xuất được gọi là Cat-Hadamard 2k - chiều được định nghĩa dưới đây       x1 (n) x1 (n − 1)  x (n)    x (n − 1)    2    2   (3.3)   = mod Hk ×   , N  ...    ...   x2k (n) x2k (n − 1) trong " đó, Hk được tạo#ra bởi phương trình (3.2), với k ≥ 2, H0 = 1, và a×b+1 b . Luôn quy ước m = 2k trong suốt nội dung dưới H1 = a 1 đây. Hàm Cat-Hadamard được định nghĩa trong phương trình (3.3) là một ánh xạ một-một " hay # còn gọi là một song ánh. 21 Gọi C = , và phương trình (3.2) được viết lại theo dạng đệ quy 11 như sau Hk = (C ⊗ Hk−1 ) = C ⊗ (C ⊗ ...(C ⊗H1 )) {z } | (3.4) (k−1) times = C ⊗(k−1) ⊗ H1 , với H1 = AT (a, b)2×2 . Phương trình (3.3) được viết lại theo dạng đệ quy sau n bước lặp như sau       x1 (n) x1 (0)    x (n)   x (0)    2   2     = mod Hk × (Hk × (...(Hk ×  )...)), N  {z }  ...  |   ...  n times x2k (n)       = mod Hkn ×    x1 (0) x2 (0) ... x2k (0) 18 x2k (0)       , N  .   (3.5)