Tài liệu Kỹ thuật thủy vân và mật mã học trong xác thực, bảo vệ bản quyền dữ liệu đa phương tiện

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI Đỗ Văn Tuấn KỸ THUẬT THỦY VÂN VÀ MẬT MÃ HỌC TRONG XÁC THỰC, BẢO VỆ BẢN QUYỀN DỮ LIỆU ĐA PHƯƠNG TIỆN Chuyên ngành: Cơ sở toán học cho tin học Mã số: 62460110 TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội – 2015 Công trình đượ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: 1) GS.TSKH. Lê Hùng Sơn 2) PGS.TS. Phạm Văn Ất Phản biện 1: PGS.TS. Đỗ Năng Toàn Phản biện 2: PGS.TS. Nguyễn Bá Tường Phản biện 3: TS. Nguyễn Văn Tảo Luận án sẽ được bảo vệ trước Hội đồng chấm 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 …….. giờ, ngày …….. tháng …….. năm …….…… Có thể tìm hiểu luận án tại thư viện: 1. Thư viện Tạ Quang Bửu - Trường ĐHBK Hà Nội 2. Thư viện Quốc gia Việt Nam DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA LUẬN ÁN 1. Đỗ Văn Tuấn, Trần Đăng Hiên, Phạm Văn Ất (2012) Một sơ đồ cải tiến hệ mật mã khóa công khai Rabin. Kỷ yếu Hội thảo quốc gia lần thứ XIV Cần Thơ, 07-08/10/2011, Một số vấn đề chọn lọc của Công nghệ thông tin và Truyền thông, tháng 6/2012, tr. 279-290. 2. Do Van Tuan, Tran Dang Hien, Pham Van At (2012) A Novel Data Hiding Scheme for Binary Images. International Journal of Computer Science and Information Security, August 2012, pp. 1-5. 3. Đỗ Văn Tuấn, Phạm Văn Ất (2012) Một thuật toán giấu tin trong ảnh có bảng màu. Chuyên san Các công trình nghiên cứu, phát triển và ứng dụng Công nghệ Thông tin và Truyền thông, Tạp chí Công nghệ Thông tin và Truyền thông, tháng 12/2012, tr. 14-21. 4. Đỗ Văn Tuấn, Trần Đăng Hiên, Cao Thi Luyên, Phạm Văn Ất (2013) Một thuật toán thủy vân bền vững khóa công khai cho ảnh màu dựa trên sự hoán vị ngẫu nhiên trong các tập con. Chuyên san Các công trình nghiên cứu, phát triển và ứng dụng Công nghệ Thông tin và Truyền thông, Tạp chí Công nghệ Thông tin và Truyền thông, tháng 6/2013, tr. 67-76. 5. Đỗ Văn Tuấn, Nguyễn Kim Sao, Nguyễn Thanh Toàn, Phạm Văn Ất (2014) Một sơ đồ nhúng tin thuận nghịch mới trên ảnh JPEG. Chuyên san Các công trình nghiên cứu, phát triển và ứng dụng Công nghệ Thông tin và Truyền thông, Tạp chí Công nghệ Thông tin và Truyền thông, tháng 12/2014, tr. 41-52. 6. Đỗ Văn Tuấn, Trần Đăng Hiên, Phạm Đức Long, Phạm Văn Ất (2015) Một lược đồ thủy vân thuận nghịch mới sử dụng mở rộng hiệu đối với các véc-tơ điểm ảnh. Chuyên san Công nghệ thông tin và Truyền thông, Tạp chí Khoa học và Kỹ thuật, Học viện Kỹ thuật Quân sự, tháng 4/2015, tr. 17-31. 1 MỞ ĐẦU Trong những năm đầu của thế kỷ 21, với sự phát triển của mạng Internet đã giúp cho quá trình phân phối các sản phẩm đa phương tiện giữa những nhà cung cấp với người dùng trở nên dễ dàng, nhanh chóng. Bên cạnh đó, vấn nạn xuyên tạc thông tin, vi phạm bản quyền trên những sản phẩm đa phương tiện cũng ngày một gia tăng. Do vậy, nhu cầu bảo mật, xác thực tính toàn vẹn, bảo vệ quyền tác giả đối với sản phẩm đa phương tiện trên môi trường trao đổi công khai ngày càng cấp thiết và đòi hỏi sự an toàn cao hơn. Bên cạnh phương pháp mật mã, gần đây trong lĩnh vực an toàn thông tin xuất hiện một hướng nghiên cứu mới đó là giấu tin. Giấu tin có thể được chia thành hai nhóm là giấu tin mật và thủy vân. Đối với giấu tin mật, dữ liệu nhúng là những thông điệp mật cần trao đổi giữa người gửi và người nhận. Việc nhúng tin mật vào những dữ liệu được truyền tải phổ biến trên Internet nhằm ngụy trang cho sự tồn tại của tin mật trước các đối thủ. Trái với giấu tin mật, dữ liệu nhúng trong các lược đồ thủy vân dùng để bảo vệ dữ liệu chứa tin. Việc nhúng thêm thông tin vào các sản phẩm đa phương tiện có thể làm giảm chất lượng sản phẩm nhưng nó là dấu vết để phát hiện sự thay đổi trái phép, hoặc chứng minh quyền sở hữu các sản phẩm chứa dấu thủy vân. Chính vì vậy, tác giả chọn đề tài “Kỹ thuật thủy vân và mật mã học trong xác thực, bảo vệ bản quyền dữ liệu đa phương tiện” để thực hiện luận án Tiến sĩ của mình. Mục đích chính của luận án là đề xuất một số lược đồ giấu tin, thủy vân ứng dụng trong xác thực tính toàn vẹn và bảo vệ quyền tác giả đối với các sản phẩm đa phương tiện nói chung và sản phẩm ảnh số nói riêng. Các kết quả nghiên cứu được trình bày trong 4 chương của luận án, ngoài phần mở đầu và kết luận. CHƯƠNG 1. MỘT SỐ KIẾN THỨC CƠ SỞ 1.1 Khái niệm về giấu tin 1.1.1 Định nghĩa giấu tin Giấu tin là phương pháp nhúng một đối tượng dữ liệu số 𝐴 (dữ liệu nhúng) vào sản phẩm đa phương tiện 𝐵 (dữ liệu môi trường) để nhận được sản phẩm đa phương tiện 𝐶 (dữ liệu chứa tin) chứa 𝐴. Giấu tin được phân loại như sau: 2 Giấu tin (Information hiding) Giấu tin mật (Steganography) Thủy vân số (Digital watermarking) Hình 1.1. Phân loại phương pháp giấu tin. 1.1.2 Mô hình giấu tin Một lược đồ giấu tin gồm hai quá trình nhúng tin và trích tin. Khóa Dữ liệu môi trường (Dữ liệu gốc) Nhúng tin Dữ liệu chứa tin Dữ liệu nhúng Hình 1.2. Mô hình nhúng tin. Khóa Dữ liệu gốc Dữ liệu chứa tin Trích tin Dữ liệu trích Hình 1.3. Mô hình trích tin. 1.1.3 Các tính chất của một lược đồ giấu tin Một lược đồ giấu tin có các tính chất như: - Khả năng nhúng tin - Tính che giấu - Tính bảo mật 1.1.4 Một số hướng tiếp cận của phương pháp giấu tin Giấu tin trên dữ liệu đa phương tiện có ba hướng tiếp cận chính là: miền quan sát (miền không gian, miền thời gian), miền biến đổi 3 và miền dữ liệu nén. Việc lựa chọn hướng tiếp cận phụ thuộc vào mục đích ứng dụng của lược đồ giấu tin. 1.2 Một số khái niệm về thủy vân trên dữ liệu đa phương tiện 1.2.1 Dữ liệu đa phương tiện Dữ liệu đa phương tiện là những dạng dữ liệu như: văn bản, ảnh số, âm thanh và video. Khi nói đến dữ liệu đa phương tiện, người ta thường quan tâm đến các tệp ảnh, âm thanh và video. Một phương pháp giấu tin nói chung và thủy vân nói riêng nếu thực hiện tốt trên ảnh số thì hoàn toàn có thể phát triển, ứng dụng trên dữ liệu âm thanh và video. 1.2.2 Phân loại phương pháp thủy vân Các lược đồ thủy vân có thể được chia thành hai nhóm như: Thủy vân (Watermarking) Thủy vân bền vững (Robust watermarking) Thủy vân dễ vỡ (Fragile watermarking) Hình 1.4. Phân loại phương pháp thủy vân. 1.2.2.1 Thủy vân bền vững Thủy vân bền vững (robust watermarking) yêu cầu dấu thủy vân phải ít bị biến đổi (bền vững) trước sự tấn công trên sản phẩm chứa dấu thủy vân, hoặc trong trường hợp loại bỏ được dấu thủy vân thì sản phẩm sau khi bị tấn công cũng không còn giá trị sử dụng. Do vậy, các lược đồ thủy vân bền vững thường được ứng dụng trong bài toán bảo vệ bản quyền. 1.2.2.2 Thủy vân dễ vỡ Thủy vân dễ vỡ (fragile watermarking) yêu cầu dấu thủy vân phải nhạy cảm (dễ bị biến đổi) trước sự tấn công trên dữ liệu thủy vân. Do vậy, thủy vân dễ vỡ được dùng để xác thực tính toàn vẹn của các sản phầm đa phương tiện trên môi trường trao đổi không an toàn. 1.3 Một số phép biến đổi dữ liệu Hai phép biến đổi thông dụng trong xử lý dữ liệu đa phương tiện là cosine rời rạc và wavelet rơi rạc. Ngoài việc dùng để nén dữ liệu, hai phép biến đổi này còn hay được sử dụng trong các bài toán như: 4 trích chọn đặc trưng, phát hiện ảnh giả mạo và thủy vân số. Nhằm nâng cao tốc độ thực hiện, hai phép biến đổi này thường được tiếp cận theo phương pháp ma trận. 1.4 Một số khái niệm trong mật mã 1.4.1 Số nguyên tố và thuật toán kiểm tra số nguyên tố Định nghĩa 1.1. Số nguyên tố là số lớn hơn 1, không chia hết cho số nguyên dương nào ngoài 1 và chính nó. Số nguyên lớn hơn 1 không phải là số nguyên tố được gọi là hợp số. Định lý 1.1. (Fermat nhỏ). Nếu 𝑝 là số nguyên tố và 𝑎 là số không chia hết cho p thì: 𝑎𝑝−1 ≡ 1 (𝑚𝑜𝑑 𝑝) Định nghĩa 1.2. Một số giả nguyên tố cơ sở 𝑎 là một hợp số nguyên n thoả mãn công thức 𝑎𝑛−1 ≡ 1 (𝑚𝑜𝑑 𝑛). Thuật toán kiểm tra số giả nguyên tố: boolean pseudoprime(n,b) { if (b^(n-1) %n ==1) return true; else return false; } Thuật toán kiểm tra số nguyên tố theo Định lý Fermat nhỏ: boolean fermat(n,k) { for (i from 1 to k) { b= random(2,n-1); if(pseudoprime(n,b) != true)return false; } return true; } 1.4.2 Ký hiệu Legendre Với p là số nguyên tố lẻ và 𝑎 nguyên, ký hiệu Legendre được định nghĩa như sau: 0, nếu 𝑝|𝑎 𝑎 𝐿 ( ) = { 1, nếu a là thặng dư bậc 2 của p 𝑝 −1, nếu a không là thặng dư bậc 2 của p Ở đây ký hiệu 𝑝|𝑎 có nghĩa 𝑝 là ước của 𝑎 (𝑎 chia hết cho 𝑝). 5 1.4.3 Ký hiệu Jacobi Giả sử 𝑛 = 𝑝 × 𝑞, trong đó 𝑝, 𝑞 là 2 số nguyên tố lẻ và số nguyên 𝑎, ký hiệu Jacobi được định nghĩa: 𝑎 𝑎 𝑎 𝐽( ) = 𝐿( )×𝐿( ) 𝑛 𝑝 𝑞 1.4.4 Định lý đồng dư Trung Hoa Giả sử 𝑛1 , 𝑛2 , … , 𝑛𝑘 là các số nguyên dương và nguyên tố cùng nhau đôi một. Khi đó, hệ phương trình đồng dư: 𝑥 ≡ 𝑎1 (𝑚𝑜𝑑 𝑛1 ) 𝑥 ≡ 𝑎2 (𝑚𝑜𝑑 𝑛2 ) { …………………. 𝑥 ≡ 𝑎𝑘 (𝑚𝑜𝑑 𝑛𝑘 ) có nghiệm duy nhất theo modulo 𝑛 = 𝑛1 × 𝑛2 × … × 𝑛𝑘 . Nghiệm duy nhất này được xác định theo công thức: 𝑘 𝑥 = ∑ 𝑎𝑖 × 𝑁𝑖 × 𝑀𝑖 𝑚𝑜𝑑 𝑛 Trong đó, 𝑁𝑖 = 𝑖=1 𝑛 𝑛𝑖 và 𝑀𝑖 = 𝑁𝑖−1 mod 𝑛𝑖 (nghĩa là 𝑀𝑖 × 𝑁𝑖 ≡ 1 (𝑚𝑜𝑑 𝑛𝑖 )), với 𝑖 = 1, … , 𝑘. 1.4.5 Hệ mật mã Rabin Với hai số nguyên tố 𝑝 và 𝑞 có dạng 3 (mod 4), sơ đồ Rabin lập bản mã 𝐶 cho bản rõ 𝑀 thuộc {0, 𝑛 − 1} (với 𝑛 = 𝑝 × 𝑞) như sau: 𝐶 = 𝑀2 𝑚𝑜𝑑 𝑛 Để xác định bản rõ 𝑀 từ bản mã 𝐶 ta cần giải phương trình đồng dư: 𝑋 2 ≡ 𝐶 (𝑚𝑜𝑑 𝑛) Phương trình đồng dư trên có 4 nghiệm theo modulo 𝑛 ứng với bốn hệ phương trình: { { 𝑥1 ≡ 𝐶 𝑝+1 4 𝑥1 ≡ 𝐶 (𝑚𝑜𝑑 𝑝) 𝑞+1 4 𝑝+1 4 𝑥3 ≡ −𝐶 { (𝑚𝑜𝑑 𝑞) (𝑚𝑜𝑑 𝑝) { 𝑞+1 4 𝑥2 ≡ 𝐶 𝑝+1 4 𝑞+1 4 𝑝+1 4 𝑥2 ≡ −𝐶 𝑥4 ≡ −𝐶 𝑞+1 4 (𝑚𝑜𝑑 𝑝 ) (𝑚𝑜𝑑 𝑞) (𝑚𝑜𝑑 𝑝) (𝑚𝑜𝑑 𝑞) 𝑥3 ≡ 𝐶 𝑥4 ≡ −𝐶 (𝑚𝑜𝑑 𝑞) Như vậy, từ một bản mã, lược đồ Rabin không thể xác định được bản rõ duy nhất. Điều này sẽ được khắc phục trong sơ đồ đề xuất ở Chương 2. 6 1.5 Một số phép toán trên ma trận nguyên - Ký hiệu 𝐼 𝑚×𝑛 là tập các ma trận nguyên không âm cấp 𝑚 × 𝑛 (m hàng và 𝑛 cột). - Với 𝐹 ∈ 𝐼 𝑚×𝑛 , nếu nói phần tử (𝑖, 𝑗) có nghĩa là phần tử trên hàng 𝑖 và cột 𝑗 (chỉ quan tâm đến vị trí), và nếu nói phần tử 𝐹𝑖,𝑗 nghĩa là phần tử trên hàng 𝑖, cột 𝑗 và có giá trị bằng 𝐹𝑖,𝑗 (quan tâm đến cả vị trí và giá trị). Hai giá trị 𝐹𝑖,𝑗 , 𝐹𝑢,𝑣 khác tính chẵn lẻ được ký hiệu là 𝐹𝑖,𝑗 # 𝐹𝑢,𝑣 . Định nghĩa 1.3. Phép nhân đồng vị ⊗ hai ma trận 𝐴 ∈ 𝐼 𝑚×𝑛 , 𝐵 ∈ 𝐼 𝑚×𝑛 ký hiệu là 𝐶 = 𝐴 ⊗ 𝐵 và được xác định theo công thức: 𝐶𝑖,𝑗 = 𝐴𝑖,𝑗 × 𝐵𝑖,𝑗 với 𝑖 = 1,2, … , 𝑚 và 𝑗 = 1,2, … , 𝑛 Định nghĩa 1.4. Phép toán SUM trên ma trận 𝐴 ∈ 𝐼 𝑚×𝑛 là một số nguyên, ký hiệu SUM(A) và tính theo công thức: 𝑚 𝑛 𝑆𝑈𝑀(𝐴) = ∑ ∑ 𝐴𝑖,𝑗 𝑖=1 𝑗=1 Định nghĩa 1.5. Phép toán 𝑀𝑂𝐷 trên ma trận nguyên 𝐹 ∈ 𝐼 𝑚×𝑛 là ma trận nhị phân cấp 𝑚 × 𝑛 ký hiệu: 𝐶 = 𝑀𝑂𝐷(𝐹) và được tính theo công thức: 𝐶𝑖,𝑗 = 𝐹𝑖,𝑗 mod 2 với 𝑖 = 1, … , 𝑚 và 𝑗 = 1, … , 𝑛 Định nghĩa 1.6. Trên ma trận 𝐹 ∈ 𝐼 𝑚×𝑛 , phần tử (𝑢, 𝑣) được gọi là liền kề với phần tử (𝑖, 𝑗) ký hiệu: (𝑖, 𝑗)(𝑢, 𝑣) nếu 𝑀𝑎𝑥{|𝑢 − 𝑖|, |𝑣 − 𝑗|} = 1 Định nghĩa 1.7. Ma trận nhị phân 𝐾 ∈ 𝐼 𝑚×𝑛 được gọi là ma trận liên thông nếu với mỗi cặp hai phần tử bất kỳ không kề nhau (𝑖, 𝑗) và (𝑢, 𝑣) có giá trị 𝐾𝑖,𝑗 = 𝐾𝑢,𝑣 = 1 luôn tồn tại dãy các phần tử (𝑝𝑡 , 𝑞𝑡 ) với 𝑡 = 1, … , 𝑘 sao cho: 𝐾𝑝𝑡 ,𝑞𝑡 = 1 với 𝑡 = 1, … , 𝑘 và (𝑖, 𝑗)(𝑝1 , 𝑞1 ) (𝑝2 , 𝑞2 ) ... (𝑝𝑘 , 𝑞𝑘 )  (𝑢, 𝑣) Định nghĩa 1.8. Phép ⨁ hai số nguyên không âm là phép toán xor trên từng cặp bít tương ứng của chúng. Định nghĩa 1.9. Với 𝐹 là ma trận nguyên không âm cấp 𝑚 × 𝑛, ký hiệu 𝑠 = 𝑋𝑆𝑈𝑀(𝐹) hay ∑⨁ 𝑖,𝑗 𝐹𝑖,𝑗 được hiểu là phép ⨁ trên tất cả các phần tử của 𝐹. 7 1.6 Kết luận chương 1 Chương này đã trình bày một số khái niệm, phân loại các phương pháp giấu tin và thủy vân. Ngoài ra, nội dung của chương này còn đề cập đến một số khái niệm trong mật mã học và các phép biến đổi dữ liệu đa phương tiện cũng như định nghĩa một số phép toán làm việc trên ma trận nguyên. CHƯƠNG 2. GIẤU TIN VÀ HỆ MẬT MÃ RABIN CẢI TIẾN 2.1 Bảo mật dữ liệu bằng sự kết hợp giữa giấu tin và mật mã Để tăng cường sự an toàn cho hệ thống, trong ứng dụng thường kết hợp phương pháp mật mã với kỹ thuật giấu tin theo các hướng: 1) Sử dụng các hệ mật mã để mã hóa tin mật và giấu bản mã vào dữ liệu đa phương tiện. 2) Sử dụng hệ mật mã khóa công khai để trao đổi khóa bí mật của các lược đồ giấu tin. 3) Kết hợp mật mã với giấu tin để xây dựng các lược đồ thủy vân dễ vỡ khóa công khai. 4) Kết hợp mật mã, giấu tin và thủy vân thuận nghịch để xây dựng mô hình bảo mật và xác thực dữ liệu trên đường truyền. 2.2 Một số kết quả gần đây về các sơ đồ Rabin cải tiến Để khắc phục hạn chế của thuật toán giải mã trong sơ đồ Rabin đã có một số sơ đồ cải tiến như: Shimada, Chen – Tsu và Harn. Trong các sơ đồ Shimada và Chen-Tsu yêu cầu hai số nguyến tố 𝑝, 𝑞 có dạng 𝑝 ≡ 7 (mod 8) và 𝑞 ≡ 3 (mod 8), điều này dẫn đến phạm vi ứng dụng bị thu hẹp. Ngoài ra, hai sơ đồ này có hạn chế chung là phải tính toán khá nhiều. Sơ đồ của Harn vẫn sử dụng các số nguyên tố 𝑝, 𝑞 dạng 3 (mod 4) nhưng đòi hỏi một khối lượng tính toán còn lớn hơn so với Shimada và Chen-Tsu. 2.3 Đề xuất một sơ đồ Rabin mới Phần này đề xuất sơ đồ Rabin có khả năng xác định duy nhất bản rõ từ một bản mã, và cần khối lượng tính toán ít hơn hẳn so với hai sơ đồ Shimada và Chen-Tsu. Ngoài ra, sơ đồ mới vẫn sử dụng hai số nguyên tố 𝑝, 𝑞 có dạng 3 (mod 4) nên phạm vi ứng dụng cũng được cải thiện hơn so với hai phương pháp cải tiến nói trên. 2.3.1 Phương trình Rabin 𝑋 2 ≡ 𝜃 (𝑚𝑜𝑑 𝑁 ) (2.1) 8 Trong đó, 𝜃 và 𝑁 đã biết, 𝑋 là nghiệm cần tìm. Ngoài ra 𝜃 và 𝑁 có hai tính chất sau: - 𝑁 = 𝑝 × 𝑞 và 𝑝, 𝑞 là hai số nguyên tố có dạng 3 (mod 4). - 𝜃 là thặng dư bình phương của 𝑁 và 0 ≤ 𝜃 < 𝑁 Phương trình (2.1) có tối đa bốn nghiệm phân biệt 𝑥1 , 𝑥2 , 𝑥2 , 𝑥4 và khi biết hai số nguyên tố 𝑝, 𝑞 thì các nghiệm này có thể được xác định như sau: 𝑥1 = 𝑅𝑜𝑜𝑡(𝑥𝑝 , 𝑥𝑞 ), 𝑥2 = 𝑅𝑜𝑜𝑡(𝑥𝑝 , 𝑞 − 𝑥𝑞 ), 𝑥3 = 𝑅𝑜𝑜𝑡(𝑝 − 𝑥𝑝 , 𝑥𝑞 ) và 𝑥4 = 𝑅𝑜𝑜𝑡(𝑝 − 𝑥𝑝 , 𝑞 − 𝑥𝑞 Trong đó: - 𝑥𝑝 = 𝜃 (𝑝+1)/4 𝑚𝑜𝑑 𝑝 và 𝑥𝑞 = 𝜃 (𝑞+1)/4 𝑚𝑜𝑑 𝑞 - Ký hiệu Root(u,v) là nghiệm của hệ phương trình đồng dư: 𝑥 ≡ 𝑢 (𝑚𝑜𝑑 𝑝) { 𝑥 ≡ 𝑣 (𝑚𝑜𝑑 𝑞) Nghiệm của hệ này được tính theo Định lý đồng dư Trung Hoa. Định lý 2.1. (1) Nếu 𝑝|𝜃 thì: 𝑥 𝑥 𝑥 𝑥 x1 = x3 , x2 = x4 , x2 = N – x1 , 𝐽 ( 1 ) = 𝐽 ( 2 ) = 0 𝑁 𝑁 (2) Nếu q|θ thì: x1 = x2 , x3 = x4 , x3 = N – x1 , 𝐽 ( 1 ) = 𝐽 ( 3 ) = 0 𝑁 𝑁 (3) Nếu 𝑝⏋θ và q⏋θ thì: 𝑥 𝑥 𝑁 𝑥2 𝑁 𝑥3 - 𝐽 ( 1 ) = 𝐽 ( 4 ) = 1, và 𝑥4 = 𝑁 − 𝑥1 - 𝐽 ( ) = 𝐽 ( ) = −1, và 𝑥3 = 𝑁 − 𝑥2 𝑁 𝑁 Luận án ký hiệu 𝑝⏋θ (𝑞⏋θ ) có nghĩa 𝜃 không chia hết cho 𝑝 (𝑞). Hệ quả 2.1. Giả sử 𝑀 là nghiệm cần tìm của phương trình (2.1), thì 𝑀 có thể được xác định như sau: 𝑀 (1) Nếu 𝐽 ( ) = 0 hoặc 1, thì M = x1 hoặc M = N − x1 𝑁 𝑀 (2) Nếu 𝐽 ( ) = −1, thì M = x2 hoặc M = N − x2 𝑁 Nhận xét 2.1. 𝑀 𝑁−1 Khi biết 𝐽 ( ) và biết 𝑀 thuộc nửa trên [0, ] hoặc nửa dưới 𝑁+1 𝑁 2 [ , 𝑁 − 1] của đoạn [0, 𝑁 − 1], thì từ Hệ quả 2.1 có thể xác định 2 duy nhất giá trị 𝑀 thông qua 𝑥1 hoặc 𝑥2 . Ý tưởng này sẽ được sử dụng trong sơ đồ đề xuất. 9 2.3.2 Thuật toán mã hóa Với bản rõ 𝑀 thuộc {0, 1, . . . , 𝑁 − 1} (với 𝑁 = 𝑝 × 𝑞), bản mã 𝐶 được xác định theo các bước: Bước 1: Xác định tham số α: 𝑀 𝑁−1 0, nếu J ( ) = 0 hoặc 1 và 𝑀 ∈ [0, ] 𝑁 2 𝑀 𝑁+1 1, nếu J ( ) = 0 hoặc 1 và 𝑀 ∈ [ , 𝑁 − 1] 𝑁 2 𝛼= 𝑀 𝑁−1 2, nếu J ( ) = −1 và 𝑀 ∈ [0, ] 𝑁 2 𝑀 𝑁+1 3, nếu J ( ) = −1 và 𝑀 ∈ [ , 𝑁 − 1] { 𝑁 2 Bước 2: Xác định bản mã 𝐶 theo công thức: 𝐶 = 4 × (𝑀2 𝑚𝑜𝑑 𝑁) + 𝛼 2.3.3 Thuật toán giải mã Khi biết bản mã 𝐶, việc xác định bản rõ 𝑀 gồm các bước : Bước 1: Tính - β = C mod 4 - θ = C div 4 Bước 2: Xét phương trình đồng dư: 𝑋 2 ≡ 𝜃 (𝑚𝑜𝑑 𝑁) Nếu 𝛽 = 0 hoặc 𝛽 = 1 thì tính nghiệm 𝑥1 , còn nếu 𝛽 = 2 hoặc 𝛽 = 3 thì tính nghiệm 𝑥2 của phương trình trên theo các công thức trong mục 2.3.1. Bước 3: Bản rõ 𝑀 được xác định theo 𝛽 và 𝑥1 hoặc 𝑥2 như sau: T/h1: Nếu β = 0, thì: 𝑁−1 𝑥1 , nếu x1 ∈ [0, ] 𝑀={ 2 𝑁 − 𝑥1 , nếu trái lại T/h2: β = 1, thì: 𝑁+1 𝑥1 , nếu x1 ∈ [ , 𝑁 − 1] 2 𝑀={ 𝑁 − 𝑥1 , nếu trái lại T/h3: β = 2, thì: 𝑁−1 𝑥 , nếu x2 ∈ [0, ] 𝑀={ 2 2 𝑁 − 𝑥2 , nếu trái lại 10 T/h4: β = 3, thì: 𝑀={ 𝑥2 , nếu x1 ∈ [ 𝑁 − 𝑥2 , nếu trái lại 𝑁+1 2 , 𝑁 − 1] 2.4 Giấu tin trên ảnh nhị phân Giấu tin trên ảnh nhị phân có vai trò quan trọng trong lĩnh vực giấu tin nói chung và thủy vân nói riêng. Theo tài liệu nghiên cứu, hai lược đồ giấu tin TCP và CTL thuộc nhóm những phương pháp tốt nhất hiện nay. Theo đó, với mỗi khối 𝐹 gồm 𝑚 × 𝑛 điểm ảnh cả hai lược đồ này đều có thể nhúng được tối đa 𝑟 = ⌊𝑙𝑜𝑔2 (𝑚 × 𝑛 + 1)⌋ bít. Để nhúng được 𝑟 bít, lược đồ TCP cần biến đổi nhiều nhất 2 phần trên 𝐹, trong khi lược đồ CTL chỉ thay đổi nhiều nhất 1 phần tử. Tuy nhiên, nội dung của lược đồ CTL khá phức tạp và các tác giả có sự nhầm lẫn nghiêm trọng trong việc xác định vị trí phần tử cần biến đổi dẫn đến thuật toán không thể khôi phục chính xác nội dung thông tin đã nhúng. 2.5 Đề xuất một lược đồ giấu tin mới trên ảnh nhị phân 2.5.1 Thuật toán nhúng dãy bít trên một khối điểm ảnh Để nhúng dãy r bít 𝑏 = 𝑏1 𝑏2 … 𝑏𝑟 vào khối 𝑚 × 𝑛 điểm ảnh 𝐹, thuật toán sử dụng hai khóa bí mật 𝑃 và 𝑞. Trong đó, 𝑃 là ma trận nguyên cấp 𝑚 × 𝑛 và 𝑞 là số nguyên thỏa mãn các điều kiện: - {1,2, … , 2𝑟 − 1} ⊆ {𝑃𝑖,𝑗 |𝑖 = 1 … 𝑚, 𝑗 = 1 … 𝑛} và 𝑃𝑖,𝑗 ∈ {0,1, … , 2𝑟 − 1} - 𝑞 ∈ {0,1, … , 2𝑟 − 1} với 𝑟 ≤ ⌊𝑙𝑜𝑔2 (𝑚 × 𝑛 + 1)⌋. Thuật toán biến đổi nhiều nhất một phần tử trên 𝐹 để nhận được ma trận 𝐺 luôn thỏa mãn điều: 𝑋𝑆𝑈𝑀(𝐺 ⊗ 𝑃) ⊕ 𝑞 = 𝑏 Nội dung thuật toán gồm các bước: Bước 1: - Tính 𝑠 = 𝑋𝑆𝑈𝑀(𝐹⨂𝑃)⨁𝑞 - Nếu s = b, thì đặt 𝐺 = 𝐹 và kết thúc thuật toán. - Nếu s ≠ b, chuyển sang Bước 2. Bước 2: - Tính 𝑑 = 𝑠 ⨁ 𝑏 - Chọn một phần tử (𝑢, 𝑣) sao cho 𝑃𝑢,𝑣 = 𝑑 - Đảo phần tử 𝐹𝑢,𝑣 : 𝐹𝑢,𝑣 = 1 − 𝐹𝑢,𝑣 11 - Đặt 𝐺 = 𝐹 và kết thúc thuật toán. 2.5.2 Thuật toán trích dãy bít trên một khối điểm ảnh Để trích dãy bít 𝑏 = 𝑏1 𝑏2 … 𝑏𝑟 từ khối điểm ảnh 𝐺, thuật toán sử dụng hai khóa bí mật P, q đã dùng trong thuật toán nhúng tin và tính theo công thức: 𝑏 = 𝑋𝑆𝑈𝑀(𝐺 ⊗ 𝑃) ⊕ 𝑞 2.6 Đề xuất một lược đồ giấu tin mới trên ảnh chỉ số màu Cũng giống như ảnh nhị phân, giấu tin trên ảnh ít màu (ảnh chỉ số màu) gặp phải những khó khăn nhất định. Do có nhiều vùng ảnh đồng màu và thường có sự khác biệt lớn về màu sắc giữa hai miền liền kề. Để tiết kiệm bộ nhớ, ảnh ít màu thường được tổ chức lưu trữ ở dạng bảng màu và có tối đa 256 màu khác nhau. Khi đó, giá trị của dữ liệu ảnh là các chỉ số tham chiếu đến bảng màu. Để cải thiện chất lượng ảnh, luận án sử dụng cách tiếp cận giấu tin trên biên (giáp ranh giữa hai vùng đồng màu). Nội dung lược đồ như sau: 2.6.1 Thuật toán nhúng tin Thuật toán chia ảnh 𝐼 thành các khối không chờm nhau cùng kích thước 𝑚 × 𝑛 và nhúng nhiều nhất một bít trên mỗi khối. Dưới đây trình bày thuật toán nhúng tin trên khối 𝐹. Thuật toán sử dụng ma trận khóa nhị phân liên thông 𝐾 cấp 𝑚 × 𝑛 với 𝑆𝑈𝑀(𝐾) ≥ 3. Khi thực hiện thành công sẽ cho ma trận 𝐺 thỏa mãn các điều kiện: - 1 ≤ 𝑆𝑈𝑀(𝑀𝑂𝐷(𝐺)𝐾) ≤ 𝑆𝑈𝑀(𝐾)– 1 - 𝑆𝑈𝑀 (𝑀𝑂𝐷(𝐺)𝐾)𝑚𝑜𝑑 2 = 𝑏 - 𝐹 và 𝐺 khác nhau tối đa một phần tử Bước 1: Đặt s = 𝑆𝑈𝑀(𝑀𝑂𝐷(𝐹) ⊗ 𝐾) Bước 2: Kiểm tra điều kiện nhúng tin, xét hai trường hợp: Nếu 𝑠 = 0 hoặc 𝑠 = 𝑆𝑈𝑀(𝐾), không nhúng tin và kết thúc. Nếu 1 ≤ 𝑠 ≤ 𝑆𝑈𝑀(𝐾) − 1, chuyển sang Bước 3 Bước 3: Xét hai khả năng: Nếu 𝑠 𝑚𝑜𝑑 2 = 𝑏, đặt 𝐺 = 𝐹 và kết thúc thuật toán. Nếu 𝑠 𝑚𝑜𝑑 2 ≠ 𝑏, chuyển sang Bước 4 Bước 4: Xây dựng tập ∏ theo công thức: {(𝑖, 𝑗)| 𝐾𝑖,𝑗 = 1, 𝐹𝑖,𝑗 chẵn, ∃(u, v): (𝑢, 𝑣) ⇔ (𝑖, 𝑗)và 𝐹𝑢,𝑣 #𝐹𝑖,𝑗 }, nếu 𝑠 = 1 ∏ = {{(𝑖, 𝑗)|𝐾𝑖,𝑗 = 1, 𝐹𝑖,𝑗 lẻ, ∃(u, v): (u, v) ⇔ (i, j) và 𝐹𝑢,𝑣 #𝐹𝑖,𝑗 }, nếu 𝑠 = 𝑆𝑈𝑀(𝐾) − 1 {(𝑖, 𝑗)|𝐾𝑖,𝑗 = 1, ∃(u, v): (u, v) ⇔ (i, j) và 𝐹𝑢,𝑣 #𝐹𝑖,𝑗 }, nếu 2 ≤ 𝑠 ≤ 𝑆𝑈𝑀(𝐾) − 2 12 Bước 5: Biến đổi một phần tử của 𝐹 để nhận được 𝐺 như sau: - Chọn một phần tử (𝑖, 𝑗) ∈ Π - Chọn một phần tử (𝑢, 𝑣) sao cho: (u,v)  (i,j) và 𝐹𝑢,𝑣 # 𝐹𝑖,𝑗 - Thay 𝐹𝑖,𝑗 bằng 𝐹𝑢,𝑣 . Đặt 𝐺 = 𝐹, kết thúc thuật toán. 2.6.2 Thuật toán trích tin Để trích bít 𝑏 từ ma trận 𝐺 thuật toán sử dụng ma trận nhị phân khóa 𝐾 dùng trong thuật toán nhúng tin. Bước 1: Tính 𝑠 ′ = 𝑆𝑈𝑀(𝑀𝑂𝐷(𝐺)𝐾) Bước 2: Trích bít 𝑏 Nếu 𝑠 ′ = 0 hoặc 𝑠 ′ = 𝑆𝑈𝑀(𝐾), kết luận 𝐺 không chứa tin. Nếu trái lại, tính 𝑏 = 𝑠 ′ 𝑚𝑜𝑑 2. 2.7 Kết luận chương 2 Dựa trên ý tưởng cải tiến của hai sơ đồ Chen-Tsu và Shimada, chương này đã đề xuất sơ đồ Rabin mới khắc phục được hạn chế của sơ đồ Rabin. Thay vì việc sử dụng hai số nguyên tố p, q có dạng 7 (mod 8) và 3 (mod 8) như các sơ đồ Shimada và Chen-Tsu, sơ đồ đề xuất vẫn sử dụng hai số nguyên tố dạng 3 (mod 4). Do đó, sơ đồ mới có phạm vi ứng dụng rộng hơn so với hai cải tiến trên. Các phân tích lý thuyết và kết quả thực nghiệm cho thấy, tốc độ giải mã của sơ đồ mới nhanh hơn khoảng 2 lần so với sơ đồ Chen-Tsu và 4 lần so với Shimada. Sơ đồ Rabin mới đã được công bố trong công trình [1]. Ngoài kết quả trên, chương này còn đề xuất hai lược đồ giấu tin mới trên ảnh nhị phân và ảnh chỉ số màu. Các kết quả phân tích và thực nghiệm cho thấy, hai lược đồ mới có khả năng nhúng tin lớn hơn và tính bảo mật cao hơn các lược đồ liên quan. Hai lược đồ giấu tin mới đã được công bố trong các công trình [2,3]. Các kết quả đề xuất trong chương này được sử dụng để xây dựng mô hình bảo mật và xác thực dữ liệu trên đường truyền ở Chương 3. CHƯƠNG 3. THỦY VÂN THUẬN NGHỊCH 3.1 Sơ lược về thủy vân thuận nghịch Thủy vân thuận nghịch là các lược đồ giấu tin có khả năng khôi phục dữ liệu gốc từ dữ liệu chứa dấu thủy vân. Theo tài liệu nghiên cứu, trong nhiều ứng dụng của y tế, quân sự và nghệ thuật, việc khôi phục lại ảnh gốc từ ảnh thủy vân là một trong những yêu cầu bắt buộc. Hai tính chất quan trọng nhất của thủy vân thuận nghịch là khả năng nhúng tin và chất lượng ảnh. 13 Trong thủy vân thuận nghịch thường dùng một số phương pháp như: nén bảo toàn dữ liệu; dịch chuyển histogram; các phép biến đổi nguyên thuận nghịch và sử dụng đặc trưng của ảnh nén JPEG. 3.2 Một số kết quả gần đây về thủy vân thuận nghịch trên ảnh JPEG Việc sử dụng đặc trưng ảnh nén JPEG để nhúng tin được bắt đầu nghiên cứu bởi Iwata và các đồng sự bằng cách sử dụng các khối DCT nhận được sau khi đã lượng tử hóa (khối DCT lượng tử). Mỗi khối này có kích thước 8 × 8 và thường chứa nhiều hệ số (phần tử) 0 ở góc dưới bên phải. Iwata sử dụng 9 đường chéo của khối (cùng chiều với đường chéo chính) và nhúng 1 bít trên mỗi đường chéo bằng cách biến đổi sao cho tổng số các hệ số 0 liên tiếp tính từ dưới lên của mỗi đường chéo có cùng tính chẵn lẻ với bít cần nhúng. Tuy nhiên lược đồ này chưa có tính chất thuận nghịch. Chang và đồng sự cũng sử dụng 9 đường chéo như trong Iwata nhưng nhúng trên mỗi đường chéo tối đa một bít tại hai phần tử bằng 0 cuối cùng (nếu có) trong dãy các phần tử 0 liên tiếp tính từ dưới lên. Ngoài ra, phần tử khác 0 cuối cùng có thể được biến đổi theo một qui tắc nhất định để đánh dấu vị trí nhúng tin. Do vây, lược đồ Chang vừa trích được các bít đã nhúng và vừa có khả năng khôi phục được ảnh gốc. Tuy nhiên khả năng nhúng tin của lược đồ này còn hạn chế như nhận xét của chính tác giả. Để nâng cao khả năng nhúng tin, Lin và cộng sự đề xuất lược đồ nhúng tin hai lớp bằng cách kết hợp lược đồ Chang với phương pháp mở rộng hiệu của Tian. Kết quả thực nghiệm của Lin cho thấy, khả năng nhúng tin của lược đồ này được cải thiện hơn so với lược đồ Chang, nhưng chất lượng ảnh giảm đáng kể. 3.3 Đề xuất một lược đồ thủy vân thuận nghịch mới trên ảnh JPEG Dựa trên ý tưởng của lược đồ Chang, phần này đề xuất lược đồ thủy vân thuận nghịch mới trên ảnh JPEG. Thay cho việc sử dụng 9 đường chéo như Chang, lược đồ đề xuất chỉ sử dụng 5 đường chéo gần với đường chéo chính và nhúng tối đa 2 bít trên mỗi đường chéo. Các phân tích lý thuyết và kết quả thực nghiệm cho thấy, lược đồ đề xuất có khả năng nhúng tin cao hơn và chất lượng ảnh tốt hơn so với hai lược đồ Chang, lược đồ Lin. 14 3.3.1 Thuật toán nhúng dấu thủy vân Trên mỗi dãy 𝐷𝑖 = (𝑑1 , 𝑑2 , … , 𝑑𝑘𝑖 ) với 1 ≤ 𝑖 ≤ 5, gọi 𝑞𝑖 là vị trí đầu tiên mà 𝑑𝑞𝑖 khác 0 tính từ 𝑑1 . Trường hợp mọi hệ số của 𝐷𝑖 đều bằng 0 thì chọn 𝑞𝑖 = 𝑘𝑖 + 1. Với 𝑞𝑖 ≥ 2, thuật toán nhúng một hoặc hai bít dấu thủy vân (𝑤1 𝑤2 ) vào dãy 𝐷𝑖 để nhận được 𝐷𝑖′ . Bước 1: Xử lý nhập nhằng: Nếu 1 ≤ 𝑞𝑖 ≤ 𝑘𝑖 thì: 𝑑𝑞 + 1, nếu 𝑑𝑞𝑖 > 0 𝑑𝑞′ 𝑖 = { 𝑖 𝑑𝑞𝑖 , nếu 𝑑𝑞𝑖 < 0 Bước 2: Nhúng tin, xét các trường hợp: T/h1: Nếu 𝑞𝑖 = 1 thì không nhúng tin trên dãy 𝐷𝑖 . T/h2: Nếu 𝑞𝑖 = 2 thì nhúng bít 𝑤1 theo công thức: 𝑑1′ = 𝑤1 T/h3: Nếu 𝑞𝑖 > 2 thì nhúng hai bít 𝑤1 𝑤2 theo công thức: 𝑑𝑞′ 𝑖 −1 = 𝑤1 và 𝑑q′ 𝑖 −2 = 𝑤2 3.3.2 Thuật toán trích dấu thủy vân và khôi phục ảnh gốc Thuật toán xét các dãy 𝐷𝑖′ = (𝑑1′ , 𝑑2′ , … , 𝑑𝑘′ 𝑖 ) với 1 ≤ 𝑖 ≤ 5. Gọi 𝑠𝑖 là vị trí đầu tiên mà 𝑑𝑠′ 𝑖 ≥ 2 hoặc 𝑑𝑠′ 𝑖 < 0 tính từ 𝑑1′ . Trường hợp mọi hệ số của 𝐷𝑖′ đều có giá trị 0 thì chọn 𝑠𝑖 = 𝑘𝑖 + 1. Nội dung thuật toán trích dấu thủy vân và khôi phục dãy 𝐷𝑖 = (𝑑1 , 𝑑2 , … , 𝑑𝑘𝑖 ): Bước 1: Trích dãy bít dấu thủy vân, xét các trường hợp: T/h 1: Nếu 𝑠𝑖 < 2 thì 𝐷𝑖′ không chứa tin. T/h 2: Nếu 𝑠𝑖 = 2 thì bít tin nhúng 𝑤1 = 𝑑1′ . T/h 3: Nếu 𝑠𝑖 > 2 thì hai bít tin nhúng 𝑤1 𝑤2 theo công thức: 𝑤1 = 𝑑𝑠′ 𝑖 −1 và 𝑤2 = 𝑑𝑠′ 𝑖 −2 Bước 2: Khôi phục dãy 𝐷𝑖 = (𝑑1 , 𝑑2 , … , 𝑑𝑘𝑖 ) từ 𝐷𝑖′ theo công thức: 0, nếu ℎ < 𝑠𝑖 ′ 𝑑ℎ = {𝑑ℎ − 1, nếu ℎ = 𝑠𝑖 và 𝑑ℎ′ > 0 𝑑ℎ′ , các trường hợp còn lại với ℎ = 1 … 𝑘𝑖 . 3.4 Một số kết quả gần đây về thủy vân thuận nghịch dựa trên phép biến đổi mở rộng hiệu đối với véc tơ điểm ảnh Phép biến đổi mở rộng hiệu (DE) của Tian là một trong những phép biến đổi khá hiệu quả. Phương pháp này chia ảnh gốc thành các 15 cặp giá trị điểm ảnh. Với mỗi cặp (𝑥, 𝑦), tính hiệu ℎ = 𝑥 − 𝑦 và nhúng bít 𝑏 vào ℎ theo công thức: ℎ′ = 2ℎ + 𝑏. Một nhận xét chung là, nếu hiệu ℎ có giá trị càng nhỏ (theo giá trị tuyệt đối) thì chất lượng ảnh càng cao. Để gia tăng khả năng nhúng tin và nâng cao chất lượng ảnh thủy vân, một số tác giả sử dụng phép biến đổi DE trên véc tơ điểm ảnh như: Alattar (2004) Mohammad (2006), Lee (2008) và Khodaei (2010). Sự khác nhau của các phương pháp này chủ yếu là cách chọn một phần tử trên véc tơ điểm ảnh làm phần tử cơ sở để tạo ra nhiều hiệu nhỏ nhằm nâng cao khả năng nhúng và chất lượng ảnh Alattar chia ảnh gốc thành các véc tơ 𝑛 điểm ảnh. Mỗi véc tơ 𝑈 = (𝑢0 , … , 𝑢𝑛−1 ) có thể nhúng được 𝑛 − 1 bít bằng phương pháp mở rộng trên các hiệu ℎ𝑖 = 𝑢𝑖 – 𝑢0 , với 𝑖 = 1, … , 𝑛 − 1. Để tạo ra các hiệu nhỏ hơn, Mohammad và cộng sự đã cải tiến lược đồ Alattar bằng cách chọn phần tử trung vị thay cho 𝑢0 để tạo 𝑛 − 1 hiệu ℎ𝑖 . Theo kết quả thực nghiệm của Mohammad, khả năng nhúng tin và chất lượng ảnh thủy vân của lược đồ này có phần cao hơn lược đồ Alattar. Tuy nhiên, cả hai lược đồ này đều có chung hạn chế là tốc độ thực hiện chậm và chỉ phù hợp với véc tơ có ít phần tử. Lee và các cộng sự đề xuất phương pháp chọn phần tử cơ sở giữa giá trị min và max của véc tơ. Phương pháp này tạo ra được nhiều hiệu nhỏ nhưng lược đồ này không sử dụng được các hiệu bằng 0 (các hiệu nhỏ nhất). Dựa trên lược đồ Lee, Khodaei và cộng sự chọn phần tử trung vị làm phần tử cơ sở và dùng công thức của Lee để nhúng dấu thủy vân. Hai lược đồ này thực hiện nhanh nhưng đều có một sự nhầm lẫn dẫn đến không khôi phục lại ảnh gốc khi giá trị điểm ảnh chứa dấu thủy vân vượt ra ngoài phạm vi cho phép. 3.5 Đề xuất một lược đồ thủy vân thuận nghịch mới sử dụng phép biến đổi mở rộng hiệu trên véc tơ điểm ảnh Lược đồ đề xuất cũng sử dụng cách chọn phần tử cơ sở như Lee, nhưng cách chọn phần tử cở sở của lược đồ đề xuất cho phép dùng cả các hiệu bằng 0. Do vậy, lược đồ đề xuất vừa cải thiện được khả năng nhúng tin lại vừa nâng cao được chất lượng ảnh thủy vân. Các kết quả thực nghiệm cho thấy, khả năng nhúng và chất lượng ảnh của lược đồ đề xuất cao hơn 5 lược đồ nói trên. 16 3.5.1 Thuật toán nhúng tin và khôi phục véc tơ điểm ảnh bằng phương pháp mở rộng hiệu 3.5.1.1 Thuật toán nhúng tin Thuật toán nhúng 𝑛 − 1 bít dữ liệu vào 𝑛 điểm ảnh của véc tơ 𝑈 = (𝑢0 , … , 𝑢𝑛−1 ) để nhận được 𝑈 ′ gồm các bước: Bước 1: Sắp xếp các phần tử của 𝑈 theo thứ tự tăng để nhận được 𝑉. Bước 2: Xác định phần tử cơ sở: 𝑛 Đặt 𝑎 = 𝑉 (⌊ ⌋) 2 Phần tử 𝑈(𝑘) đầu tiên của véc tơ 𝑈 có giá trị bằng 𝑎 được chọn làm phần tử cơ sở. Bước 3: Nhúng bít 𝑏𝑗 vào phần tử 𝑢𝑗 theo công thức: ℎ𝑗 = |𝑢𝑗 − 𝑎|, với 𝑗 = 0, … , 𝑛 − 1 và 𝑗 ≠ 𝑘 𝑎 + (2ℎ𝑗 + 𝑏𝑗 ), nếu 𝑢𝑗 ≥ 𝑎 và 𝑗 ≠ 𝑘 ′ 𝑢𝑗 = {𝑎 − (2ℎ𝑗 + 𝑏𝑗 ), (3.1) nếu 𝑢𝑗 < 𝑎 và 𝑗 ≠ 𝑘 - 𝑎, nếu 𝑗 = 𝑘 Khái niệm véc tơ khả mở Véc tơ 𝑈 được gọi là véc tơ khả mở nếu sau khi nhúng dãy bít 𝑏𝑗 (với 𝑏𝑗 ∈ {0,1}) theo công thức (3.1) mà các phần tử 𝑢𝑗′ vẫn thỏa mãn điệu kiện: 0 ≤ 𝑢𝑗′ ≤ 255, với 𝑗 = 0, … , 𝑛 − 1. 3.5.1.2 Thuật toán khôi phục Nếu 𝑈 khả mở thì có thể khôi phục các bít 𝑏𝑗 và 𝑈 từ 𝑈 ′ như sau: Bước 1: Sắp xếp 𝑈 ′ theo thứ tự tăng để nhận được véc tơ 𝑉 ′ Bước 2: Xác định phần tử cơ sở: Tìm 𝑗 lớn nhất sao cho: 1 ≤ 𝑗 ≤ ⌊𝑛⁄2⌋ và 𝑉 ′ (𝑗 − 1) ≤ 𝑉 ′ (𝑗) − 2 và đặt 𝑎 = 𝑉(𝑗). Nếu không tồn tại 𝑗 thỏa mãn điều kiện trên thì đặt 𝑎 = 𝑉 ′ (0). Chọn phần tử 𝑈 ′ (𝑘) đầu tiên của 𝑈 ′ có giá trị bằng 𝑎. Bước 3: Trích bít 𝑏𝑗 và khôi phục 𝑢𝑗 từ phần tử 𝑢𝑗′ theo các công thức: ℎ𝑗′ = |𝑢𝑗′ − 𝑎|, 𝑏𝑗 = ℎ𝑗′ mod 2, nếu 𝑗 ≠ 𝑘 (3.2) ′ ℎ𝑗 𝑎 + ⌊ ⌋ , nếu u𝑗′ ≥ 𝑎 và 𝑗 ≠ 𝑘 2 𝑢𝑗 = (3.3) ℎ𝑗′ 𝑎 − ⌊ ⌋ , nếu u𝑗′ < 𝑎 và 𝑗 ≠ 𝑘 2 nếu 𝑗 = 𝑘 { 𝑎, 17 3.5.1.3 Tính đúng đắn của thuật toán Từ công thức (3.1), có thể dễ dàng suy ra chỉ số 𝑘 xác định theo Bước 2 của thuật toán khôi phục 3.5.1.2 trùng với chỉ số 𝑘 trong thuật toán nhúng tin 3.5.1.1. Hay nói cách khác, 𝑈 ′ (𝑘) = 𝑈(𝑘) = 𝑎 là phần tử cơ sở. Điều đó khẳng định tính đúng đắn của thuật toán đề xuất. 3.5.2 Thuật toán nhúng tin và khôi phục bằng phương pháp chèn bít thấp Đối với các véc tơ không khả mở, lược đồ sử dụng khái niệm khả biến và thuật toán nhúng tin bằng cách chèn bít thấp như sau: 3.5.2.1 Thuật toán nhúng tin Sắp xếp véc tơ 𝑈 = (𝑢0 , … , 𝑢𝑛−1 ) theo thứ tự tăng để nhận được 𝑛 𝑉. Chọn giá trị cơ sở 𝑎 = 𝑉 (⌊ ⌋) và đặt ℎ𝑗 = |𝑢𝑗 − 𝑎|. Bít 𝑏𝑗 ∈ 2 {0,1} được nhúng vào bít thấp của ℎ𝑗 theo công thức: ℎ𝑗 𝑎 + (2 ⌊ ⌋ + 𝑏𝑗 ) , nếu 𝑢𝑗 ≥ 𝑎 + 2 2 ′ ℎ𝑗 𝑢𝑗 = (3.4) 𝑎 − (2 ⌊ ⌋ + 𝑏𝑗 ) , nếu 𝑢𝑗 ≤ 𝑎 − 2 2 nếu 𝑎 − 1 ≤ 𝑢𝑗 ≤ 𝑎 + 1 { 𝑢𝑗 , Khái niệm véc tơ khả biến Véc tơ 𝑈 được gọi là véc tơ khả biến nếu sau khi nhúng dãy bít 𝑏𝑗 (với 𝑏𝑗 ∈ {0,1}) theo công thức (3.4) mà các phần tử 𝑢𝑗′ vẫn thỏa mãn điệu kiện: 0 ≤ 𝑢𝑗′ ≤ 255, với 𝑗 = 0, … , 𝑛 − 1. 3.5.2.2 Thuật toán khôi phục Nếu 𝑈 khả biến thì từ 𝑈 ′ có thể tính được các bít 𝑏𝑗 nhưng không khôi phục được 𝑈. Do vậy, thuật toán 3.5.2.1 không khả nghịch. Để khôi phục được 𝑈 từ 𝑈 ′ , trong thuật toán 3.5.2.1 cần phải lưu trữ bít thấp của ℎ𝑗 (ký hiệu 𝐿𝑆𝐵(ℎ𝑗 )) trước khi thực hiện công thức (3.4). Thuật toán khôi phục 𝑏𝑗 và 𝑢𝑗 như sau: Bước 1: Sắp xếp 𝑈 ′ theo thứ tự tăng để nhận được véc tơ 𝑉 ′ Bước 2: Xác định giá trị cơ sở 𝑎: 𝑛 𝑎 = 𝑉 ′ (⌊ ⌋) 2 18