Một giải pháp nâng cao hiệu quả giải mã của các hệ mật đa trị và nhập nhằng MAS

Bài viết trình bày việc thiết lập những kết quả mới cho phép phát triển một thuật toán giải mã hiệu quả cho các hệ mật MAS. Nhờ đó, thời gian giải mã dữ liệu trong các hệ mật này được giảm xuống mức tối thiểu.
Nội dung trích xuất từ tài liệu:
Một giải pháp nâng cao hiệu quả giải mã của các hệ mật đa trị và nhập nhằng MAS Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR), Nha Trang, ngày 8-9/10/2020 DOI: 10.15625/vap.2020.00176 MỘT GIẢI PHÁP NÂNG CAO HIỆU QUẢ GIẢI MÃ CỦA CÁC HỆ MẬT ĐA TRỊ VÀ NHẬP NHẰNG MAS Long Thị Lệ, Nguyễn Đình Hân Viện Toán ứng dụng và Tin học, Trường Đại học Bách khoa Hà Nội le.lt@sis.hust.edu.vn, han.nguyendinh@hust.edu.vn TÓM TẮT: Hệ mật đa trị và nhập nhằng MAS (multi-valued and ambiguous cryptosystem) được thiết kế nhằm bảo vệ an toàn dữ liệu của các mạng cảm biến đám mây. Vì vậy, MAS thích hợp và có thể hoạt động hiệu quả trên các máy chủ dữ liệu đám mây, các thiết bị di động cũng như các thiết bị cảm biến nhỏ. Tuy nhiên, do đặc tính đa trị của MAS, giải mã dữ liệu thường cần nhiều thời gian hơn so với mã hóa dữ liệu. Trong bài báo này, chúng tôi thiết lập những kết quả mới cho phép phát triển một thuật toán giải mã hiệu quả cho các hệ mật MAS. Nhờ đó, thời gian giải mã dữ liệu trong các hệ mật này được giảm xuống mức tối thiểu. Từ khóa: Bảo mật, mật mã, hệ mật đa trị và nhập nhằng, MAS, đồ thị. I. GIỚI THIỆU Mục tiêu cơ bản của mật mã học là tạo ra các hệ mật cho phép truyền tin bí mật trong môi trường không an toàn. Do không có hệ mật nào tồn tại được lâu dài trước sự tấn công nên nhu cầu phát triển những hệ mật mới phục vụ các lĩnh vực của đời sống mang tính thời sự cấp thiết, là hướng đi phù hợp với xu hướng phát triển và nhu cầu của xã hội. Năm 2014, nhóm tác giả Nguyễn Đình Hân, Longzhe Han, Đào Minh Tuấn, Hoh Peter In và Minho Jo [1] đã đề xuất một phương pháp mới cho phép xây dựng các hệ mật đa trị và nhập nhằng (Multi-valued and ambiguous cryptosystem - MAS). Đặc tính đa trị của phép mã hóa cùng với thuộc tính nhập nhằng của ngôn ngữ biểu diễn (không là mã như trong các hệ mật thông thường) đã giúp các hệ mật MAS nâng cao đáng kể hiệu quả bảo vệ an toàn dữ liệu. Tuy nhiên, đặc tính đa trị cũng gây ra một trở ngại cho quá trình giải mã. Cụ thể là, giải mã cần phân biệt và lựa chọn đúng bản rõ trong số nhiều bản rõ nhận được từ một bản mã. Vì vậy, quá trình giải mã dữ liệu thường cần nhiều thời gian hơn so với quá trình mã hóa dữ liệu. Trong bài báo này, chúng tôi đề xuất một giải pháp nâng cao hiệu quả giải mã của các hệ mật MAS. Từ đó, giúp giảm thiểu thời gian giải mã dữ liệu trong các hệ mật này. Để cải thiện hiệu quả giải mã, chúng tôi sử dụng một đồ thị đầy đủ đặc biệt để biểu diễn ngôn ngữ của hệ mật MAS. Khi thực hiện giải mã, các bản rõ của cùng một bản mã sẽ được biểu diễn tương ứng với các đường đi trên đồ thị. Chúng tôi chứng minh một kết quả mới khẳng định bản rõ tương ứng với đường đi ngắn nhất trên đồ thị là kết quả của phép giải mã. Tính hiệu quả của thuật toán tìm đường đi ngắn nhất trên đồ thị đã được biết đến rộng rãi. Vì vậy, giải pháp của chúng tôi có thể làm giảm đáng kể thời gian giải mã dữ liệu. Trước khi trình bày chi tiết giải pháp, sau đây chúng tôi nhắc lại một số định nghĩa liên quan về đồng cấu đa trị, quy tắc mã hóa đa trị; điều kiện cần và đủ để một đồng cấu đa trị trở thành một quy tắc mã hóa đa trị hoặc một quy tắc mã hóa đa trị hạn chế; các kĩ thuật giúp tăng tính bảo mật với thuộc tính nhập nhằng của ngôn ngữ. Hệ mật đa trị và nhập nhằng cùng với thủ tục mã hóa, giải mã sẽ được trình bày ở Phần 2. Đóng góp chính của bài báo gồm phương pháp và các kết quả mới sẽ được trình bày cụ thể trong Phần 3. Trước hết, ta nhắc lại một số khái niệm cơ sở liên quan đến ngôn ngữ hình thức (chi tiết tham khảo [1]). Cho A là bảng chữ cái. Như thường lệ, A* là vị nhóm tự do của các từ trên A. Từ rỗng được kí hiệu là và A+ = A*-{ }. Độ dài của từ w = a1a2 … an với ai A là |w| = n, | | = 0. A≤n = w A*: |w| ≤ n}. Một phân tích của từ w A* trên X A* là w = u1u2 … un, trong đó ui X , i = 1, 2, …, n và n ≥ 1. Mỗi tập con của A* được gọi là một ngôn ngữ. Một ngôn ngữ X A* được gọi là mã nếu mỗi từ w A* có nhiều nhất một phân tích trên X. Kí hiệu X* là vị nhóm con tự do được sinh bởi X và X* = X+ { }. Kiến thức chung về các hệ mật được tham khảo từ [2]. Chi tiết các vấn đề liên quan đến ngôn ngữ không nhập nhằng được tham khảo từ [3]. Định nghĩa 1.1. Một hệ mật là bộ năm thành phần ( ) thỏa mãn các điều kiện sau: 1. là tập hữu hạn các từ/văn bản gốc (từ rõ/từ hiện/bản rõ). 2. là tập hữu hạn các từ/văn bản mã (bản mã). 3. là tập hữu hạn các khóa. 4. Với mỗi , có một phép mã hóa và một phép giải mã tương ứng . Mỗi và là các ánh xạ sao cho ( ( )) với mọi . Định nghĩa 1.2. Xét ngôn ngữ X A+ và số tự nhiên k . Khi đó: Long Thị Lệ, Nguyễn Đình Hân 255 (i) Tập được gọi là -không nhập nhằng nếu thỏa mãn điều kiện sau: với mọi k m 1 và với mọi x1, x2, …, xk, y1, y2, …, ym X nếu x1x2 … xk = y1 y2 … ym thì k = m và xi = yi với i = 1, 2, …, k. Ngược lại, X không thỏa mãn điều kiện trên thì X được gọi là k-nhập nhằng. (ii) Nếu tồn tại số k lớn nhất sao cho X là k-không nhập nhằng, thì k được gọi là độ không nhập nhằng của X. Ngược lại, X được gọi là có độ không nhập nhằng ∞. II. HỆ MẬT ĐA TRỊ VÀ NHẬP NHẰNG A. Tiếp cận và phương pháp thiết lập Trong phần này, ta sẽ nhắc lại các khái niệm, phương pháp để thiết kế một hệ mật có tính chất đa trị và nhập nhằng. Ta cần những khái niệm về phé ...