Đồ án Tìm hiều các kỹ thuật giấu tin trong ảnh

có dạng nhị phân, bản đồ số..., mỗi kỹ thuật giấu tin trong công tác bảo mật thông tin gồm : Chuyển thông tin sang dạng bit. Thuật toán giấu tin. Bộ giải mã thông tin. Chuyển từ dạng bit thành thông tin ban đầu. Kết hợp các kỹ thuật giấu tin trong các loại ảnh màu ta có thể nâng cao độ an toàn cho việc truyền tin. Sơ đồ kết hợp khi đó sẽ như sau: - Chuyển văn bản R thành file R’ có dạng bit. - A giấu R’ trong ảnh màu F để thu được ảnh màu F’. - A gửi ảnh màu F’ cho B. - Nhận được F’, B lọc tin để thu được file dạng bit R’. - Chuyển file dạng bit R’ thành văn bản R. Thuật toán giấu tin được dùng để giấu thông tin vào một phương tiện mang bằng cách sử dụng một khóa bí mật được dùng chung bởi người mã hóa và người giải mã. Việc giải mã thông tin chỉ có thể thực hiện được khi có khóa. Bộ giải mã thực hiện quá trình giải mã trên phương tiện thông tin mang đã chứa dữ liệu và trả lại thông điệp ẩn trong nó (hình 2.3). Thông tin giấu Thuật toán nhúng Phương tiện mang Truyền qua mạng Bộ giải mã Thông tin giấu Khóa K Khóa K Hình 2.1 - Lược đồ chung cho kỹ thuật giấu thông tin 2.3.1 Giấu thông tin trong ảnh số Giấu tin trong ảnh số là một phần của khái niệm giấu thông tin với việc sử dụng ảnh số làm phương tiện mang tin. Giấu thông tin trong ảnh số có nhiều ứng dụng trong thực tế như trong việc giấu các thông tin cần bảo mật và chuyển giao dữ liệu một cách an toàn. Ảnh nguồn mà ta đem nhúng thông tin vào được gọi là ảnh môi trường hay ảnh gốc, thuật ngữ ảnh môi trường để thay cho ảnh nguồn. Ảnh thu được sau khi đã giấu thông tin gọi là ảnh kết quả. Ảnh kết quả càng it nhiễu càng khó gây ra nghi ngờ về sự tồn tại thông tin trong ảnh. Thông thường ta không nên chọn những bức ảnh nhiều người biết làm ảnh môi trường mà nên chọn những bức ảnh lạ như ảnh cá nhân, ảnh phong cảnh,… Mỗi kỹ thuật giấu tin trong ảnh có những đặc điểm nhất định cần quan tâm như: mối liên hệ giữa dữ liệu nhúng với phương tiện mang tin, ai là người sẽ giải mã thông tin, có bao nhiêu người nhận, khóa là dùng chung hay là bí mật, tốc độ nhúng cao hay thấp, việc giải mã có là vấn đề quan trọng không ? Có nhiều cách để phân loại các kỹ thuật giấu thông tin trong ảnh số, dựa trên lĩnh vực áp dụng của kỹ thuật người ta chia kỹ thuật giấu thông tin trong ảnh thành hai loại: watermarking và image hiding. Watermarking còn được gọi là thủy vân, là kỹ thuật nhúng một biểu tượng vào trong ảnh môi trường để xác định quyền sở hữu ảnh môi trường. Kích thước của biểu tượng thường nhỏ. Kỹ thuật này cho phép đảm bảo nguyên vẹn biểu tượng khi ảnh môi trường bị biến đổi bởi các phép thao tác như lọc, nén mất dữ liệu, hay các biến đổi hình học,… Image hiding là kỹ thuật dùng một ảnh môi trường để lưu trữ và chuyển giao các dữ liệu quan trọng với kích thước tương đối lớn một cách an toàn. Mục đích của image hiding là làm cho dữ liệu trở nên không quan sát được đối với thị giác của con người. Hiện nay giấu thông tin trong ảnh là kỹ thuật còn tương đối mới và đang có xu hướng phát triển rất nhanh. 2.3.2 Giấu tin trong ảnh màu Giấu thông tin trong ảnh kỹ thuật số là một công nghệ tương đối mới và có khả năng giải quyết được nhiều vấn đề quan trọng. Lĩnh vực này tuy mới được nghiên cứu gần đây nhưng đang phát triển rất nhanh và cho những kết quả khả quan. Một vài thuật toán đã được thực hiện trên một số kiểu ảnh cụ thể. Maxemchuk đã đưa ra một phương pháp giấu thông tin trong các file ảnh văn bản lợi dụng khoảng trống giữa các dòng và giữa các ký tự. Tuy nhiên cách thực hiện này bị hạn chế đối với các loại ảnh đen trắng khác và số lượng thông tin được giấu trong ảnh là rất hạn chế. Koch và Zhao cũng đã đưa ra thuật toán giấu thông tin trong ảnh đen trắng sử dụng những khối bit ảnh có tỷ lệ bit đen và bit trắng là nhỏ hơn hoặc lớn hơn 1, mặc dù thuật toán này nhắm vào việc giấu sao cho khó bị phát hiện nhưng thực tế đã chứng minh nó không đủ an toàn. Nhưng kỹ thuật này lại mở ra một ý tưởng mới là giấu thông tin vào trong mỗi phần nhỏ của ảnh gọi là khối ảnh và đã được áp dụng cho hầu hết các thuật toán giấu thông tin trong ảnh. Đối với ảnh màu nói chung, việc phát triển các kỹ thuật giấu tin có nhiều thuận lợi hơn vì ảnh màu được sử dụng rất nhiều và cung cấp lượng dữ liệu lớn hơn cho việc giấu thông tin do mỗi điểm ảnh được biểu diễn bằng nhiều bit. Hơn nữa, với ảnh màu thì việc thay đổi một giá trị nhỏ ở một điểm ảnh thì chất lượng ảnh dường như không đổi và do đó khả năng bị phát hiện là rất thấp dưới thị giác của con người. Dưới đây là một số phương pháp được áp dụng rộng rãi cho việc giấu thông tin trong ảnh màu. 2.3.2.1 Thay thế least significant bit (LSB) LSB là khái niệm chỉ bit ít đặc trưng nhất trong các bit biểu diễn một điểm ảnh. Thay thế LSB là một trong những kỹ thuật giấu thông tin được dùng phổ biến nhất. Việc thay thế hai hay nhiều hơn nữa các bit LSB của mỗi điểm ảnh làm tăng dung lượng nhưng làm giảm độ an toàn của thông tin được giấu. Vì vậy cần quan tâm tới độ an toàn của mỗi kỹ thuật giấu tin dựa trên sự thay thế LSB. 2.3.2.2 Sử dụng bảng màu Thay vì tách các bit LSB của các điểm ảnh ta tách các bit LSB của bảng màu và thực hiện quá trình giấu tin trên các bit vừa thu được. Quá trình này cũng tương tự như khi ta giấu tin trong ảnh 24 bit màu với kích thước ảnh là 256 điểm ảnh (ảnh 8 bits màu), do đó lượng thông tin giấu được sẽ rất ít, bị giới hạn bởi kích thước bảng màu. Chẳng hạn đối với ảnh 8 bits màu, chọn kích thước khối là 10 x 10, r = 4, lấy từ mỗi ô màu ra 3 bits ta sẽ chỉ giấu được một lượng thông tin cực đại là 28 bits bằng thuật toán trên. Ưu điểm của sử dụng bảng màu là dễ thiết kế một kỹ thuật an toàn đối với một số nguồn ảnh nhất định. Hạn chế của nó là dung lượng giấu phụ thuộc và bị giới hạn bởi kích thước bảng màu, dễ gây ra nghi ngờ bởi sự giống nhau của ba ô màu liên tiếp trong bảng màu. Hơn nữa, bảng màu có thể bị sắp xếp lại hoặc điều chỉnh lại bởi phần mềm xử lý ảnh trong quá trình hiển thị hay lưu lại ảnh dẫn đến thông tin đã được giấu có thể sẽ bị mất đi không khôi phục lại được. 2.4 Kết luận chương Qua tìm hiểu ở chương 2 ta biết được về cấu trúc định dạng file ảnh BMP, từ đó tùy thuộc vào mỗi loại định dạng file ảnh BMP khác nhau, có nén hay không nén, có sử dụng bảng màu hay không sử dụng bảng màu để lựa chọn kỹ thuật giấu tin trong file ảnh BMP cho thích hợp. CHƯƠNG 3 - CÁC KỸ THUẬT GIẤU THÔNG TIN TRONG ẢNH MÀU 3.1 Giới thiệu chương Sau khi tìm hiểu về mật mã và cấu trúc của ảnh bitmap BMP thì ở chương 3 này, chúng ta sẽ tìm hiều về các thuật toán giấu tin trong ảnh, và các kỹ thuật giấu tin cho các kiểu ảnh BMP khác nhau, ảnh nhỏ hơn hoặc bằng 8 bits màu, ảnh hi-color, ảnh true-color, .... Cấu trúc chương gồm: + 3.1 Giới thiệu chương + 3.2 Các kỹ thuật giấu thông tin trong ảnh thứ cấp. + 3.2.1 Đặt bài toán. + 3.2.2 Các khái niệm cơ bản. + 3.2.3 Các kỹ thuật giấu tin trong ảnh thứ cấp. + 3.3 Các kỹ thuật giấu tin trong các loại ảnh màu. + 3.3.1 Ảnh nhỏ hơn hoặc bằng 8 bits màu. + 3.3.2 Ảnh hi-color (16 bits màu). + 3.3.3 Ảnh true-color (24 bits màu). + 3.4 Kỹ thuật giảm nhiễu trên ảnh kết quả + 3.5 Kết luận chương 3.2 Các kỹ thuật giấu thông tin trong ảnh thứ cấp 3.2.1 Đặt bài toán Trong mục này đề cập tới các kỹ thuật đơn giản và đáng tin cậy để giấu những thông tin quan trọng vào một ảnh thứ cấp (ảnh đen trắng) bằng cách sử dụng kỹ thuật mã hóa dùng khóa đối xứng với các trường hợp cụ thể như sau: - Sử dụng khóa bí mật K có chiều dài cố định. - Sử dụng khóa bí mật K với chiều dài thay đổi. - Sử dụng khóa bí mật K là một ma trận ảnh. - Sử dụng khóa bí mật K là ma trận khóa kích thước m x n (ma trận nhị phân dùng chung bởi người gửi và người nhận ) và ma trận trọng số cấp r, kích thước m x n cũng được dùng bởi người gửi và người nhận. Bài toán: Giả sử ta có thông tin quan trọng B cần gửi qua mạng. Người ta dùng một ảnh môi trường F đủ lớn để giấu thông tin B, sau đó gửi đi bức ảnh đã chứa thông tin B mà không sợ bị nghi ngờ về sự tồn tại của thông tin trong đó. Sử dụng một kỹ thuật giấu tin trong ảnh (chọn khóa bí mật K là ma trận và có thể kết hợp với ma trận trọng số) ta biến đổi ảnh F thành ảnh F’ có mang lượng thông tin trên mà không làm cho F’ sai khác nhiều so với F. Để thu được thông tin B đã giấu, chỉ cần có ảnh kết quả và các khóa mà không cần tới ảnh môi trường. Ký hiệu: F : ảnh môi trường được dùng để mang dữ liệu B, được chia thành từng khối Fi kích thước m x n. K : dùng chung bởi người gửi và người nhận (nếu K là ma trận khóa thì có kích thước m x n, là ma trận chỉ gồm 0 và 1). W : ma trận trọng số cấp r, kích thước m x n cũng được dùng chung bởi người gửi và người nhận. r : số lượng bit được giấu trong mỗi khối ảnh kích thước m x n của F, r phải thỏa mãn bất đẳng thức 2r -1 ≤ m x n. B: k x r bit dữ liệu cần giấu, được tách thành k chuỗi r bit. 3.2.2 Các khái niệm cơ bản 3.2.2.1 Ảnh thứ cấp và ma trận nhị phân Trước hết ta quan tâm tới đối tượng chính là các ảnh thứ cấp hay ảnh 1 bit màu. Đó là những bức ảnh mà mỗi điểm ảnh chỉ là những điểm đen hoặc trắng, được quy định bằng 1 bit, nếu bit mang giá trị 0 thì điểm ảnh là điểm đen, nếu bit mang giá trị 1 thì điểm ảnh là điểm trắng. Do đó để biểu diễn một ảnh đen trắng ta có thể dùng một ma trận nhị phân, là ma trận mà mỗi phần tử chỉ nhận một trong hai giá trị 0 hoặc 1. 3.2.2.2 Khóa bí mật Khóa bí mật K có thể: - Có độ dài không thay đổi. - Có độ dài biến thiên. - Khóa bí mật là một ma trận ảnh. - Khóa bí mật là một ma trận nhị phân có cùng kích thước với kích thước khối ảnh được dùng chung bởi người giấu tin và người giải mã thông tin. 3.2.2.3 Ma trận trọng số cấp r Ma trận trọng số cũng là một ma trận số có cùng kích thước với khóa và được sử dụng bởi người giấu tin và người giải mã thông tin. Tuy nhiên ma trận trọng số cần phải được thỏa mãn một số yêu cầu xác định. Một ma trận W kích thước m x n được gọi là ma trận trọng số cấp r nếu mỗi phần tử của tập hợp {1,2,…,2r -1} xuất hiện trong W ít nhất một lần và các phần tử của W chỉ nhận giá trị trong tập hợp {1,2,…,2r -1} với m, n, r là các số tự nhiên thỏa mãn 2r -1 ≤ m x n. Ngoài ra để thực hiện việc giấu tin trong ảnh màu người ta thêm vào sau ma trận hai tham số: tham số chứa số bit cần giấu trong ảnh Fi và kích thước của file văn bản cần giấu. 3.2.2.4 Phép đảo bit Phép đảo bit là một phép biến đổi trên các bit nhị phân. Đảo bit tương đương với phép biến đổi thay nó bởi phần bù của nó, tức là nếu ban đầu nó nhận giá trị 0 thì sau khi đảo nó sẽ nhận giá trị 1 và ngược lại, nếu ban đầu nó có giá trị 1 thì đảo nó sẽ mang giá trị 0. 3.2.2.5 Các phép toán trên ma trận Trước hết, ta coi một ảnh bitmap như một ma trận các số nguyên, vì vậy thuật ngữ bitmap và ma trận đôi khi được dùng với nghĩa tương đương. Giả sử có ma trận B, ký hiệu: - B[i,j] là phần tử nằm ở hàng thứ i cột thứ j của ma trận B. - SUM(B) là tổng tất cả các phần tử của ma trận B. Cho hai ma trận A và B có cùng kích thước, ta định nghĩa hai phép toán trên ma trận: - Phép hoặc loại trừ Å trên 2 ma trận: Å là phép toán trên hai ma trận nhị phân xác định như sau: A Å B = C A[i,j] Å B[i,j] = C[i,j] Ví dụ 1: a b a Å b 0 0 0 0 1 1 1 0 1 1 1 0 - Phép nhân Ä trên hai ma trận: Ký hiệu A Ä B là phép toán xác định như sau: A Ä B = C A[i,j] Ä B[i,j] = C[i,j] Ví dụ 2: Giả sử có F1, K, W như sau: 0 1 0 F1 = 1 1 1 1 0 0 0 0 0 K = 0 1 0 0 1 0 2 1 3 W = 2 1 3 2 1 3 Khi đó phép hoặc loại trừ giữa hai ma trận này cho ta kết quả: 0 1 0 F1 Å K = 1 0 1 1 1 0 Tiếp theo thực hiện phép nhân Ä với W: 0 1 0 F1 Å K Ä W = 2 0 3 2 1 0 và SUM((F1 Å K) Ä W) = 1 + 2 + 3 + 2 + 1 = 9 3.2.3 Các kỹ thuật giấu tin trong ảnh thứ cấp 3.2.3.1 Sử dụng khóa bí mật K có độ dài cố định a. Thuật toán Mã hóa Giả sử chúng ta cần giấu bit b vào trong ảnh thứ cấp F. Cắt một đoạn gồm có k điểm ảnh và giấu b vào trong ảnh. Trong đó k là khóa d = F/k = số đoạn Bước 1: Đọc liên tiếp k điểm ảnh. Gọi là f Ký hiệu Sum(f): là tổng số bit 1 có trong k. Đặt b = t mod 2 Bước 2: So sánh t và b: Nếu t và b cùng tính chẵn lẽ: thì không làm gì cả. Nếu t và b khác tính chẵn lẽ: thì ta tìm cách sửa đúng 1 bit trong f. Khi đó f ® f’: sao cho f’ và b là cùng tính chẵn lẻ. Bước 3: Việc sửa bit được tiến hành như sau: - Nếu có nhiều điểm đen và có điểm trắng thì sửa điểm trắng thành điểm đen. - Nếu có nhiều điểm trắng và có điểm điểm đen thì sửa điểm đen thành điểm trắng. - Nếu có điểm đen và điểm trắng xấp xỉ bằng nhau thì chọn ngẫu nhiên 1 bit để sửa. - Nếu bit không quan trọng, bit nằm ở đầu những đoạn cùng màu thì việc sửa tập trung vào bit không quan trọng của những đoạn cùng màu lớn nhất. Giải mã Chỉ cần có ảnh F’ và khóa k Bước 1: Đọc k điểm ảnh liên tiếp. Gọi là f Bước 2: Tính Sum(f) : - Nếu Sum(f) chẵn Þ bit b = 0; - Nếu Sum(f) lẻ Þ bit b = 1 ; Ví dụ 3: Các bit cần giấu là: 10110, ảnh F và khóa K như hình 3.1 Ảnh F 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 0 Khóa K = 5 Ảnh F’ 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 Hình 3.1- Mô tả bài toán và kết quả theo ví dụ 3 Mã hóa - Đọc liên tiếp 5 điểm ảnh và giấu bi vào trong ảnh. Gọi là fi. Cụ thể: - S1 = Sum(f1) = 4. Vì (4 mod 2) = 0 ≠ b1 = 1 và f1 = 01111 nên ta chọn bit f1(1,1) để sửa. - S2 = Sum(f2) = 4. Vì (4 mod 2) = 0 = b2 nên ta không thay đổi f2. - S3 = Sum(f3) = 5. Vì (5 mod 2) = 1 = b3 nên ta không thay đổi f3. - S4 = Sum(f4) = 3. Vì (3 mod 2) = 1 = b4 nên ta không thay đổi f4. - S5 = Sum(f5) = 3. Vì (3 mod 2) = 1 ≠ b5 = 0 và f5 = 01110 nên ta chọn bit f5(1,1) hoặc chọn f5(1,5) để sửa. Giải mã Chỉ cần có ảnh F’ và khóa K = 5. Đọc liên tiếp 5 điểm ảnh . Gọi là f’i - S1 = Sum(f’1) = 5 Þ b1 = 1 (Vì S1 lẻ) - S2 = Sum(f’2) = 4 Þ b2 = 0 (Vì S2 chẵn) - S3 = Sum(f’3) = 5 Þ b3 = 1 - S4 = Sum(f’4) = 3 Þ b4 = 1 - S5 = Sum(f’5) = 4 Þ b5 = 0 Vậy chuỗi được giải mã là: 10110 Đặc điểm của thuật toán Giải mã nhanh. Nhưng vì khóa có chiều dài cố định nên dễ bị phát hiện. Có thể cải tiến thuật toán bằng cách nén trước khi mã hóa hoặc sử dụng một trong các kỹ thuật mã hóa ở chương 1 trước khi mã hóa. b. Tính đúng của thuật toán Tính đúng của thuật toán được chứng minh bằng cách dựa trên chính văn bản của thuật toán đã trình bày. 3.2.3.2 Sử dụng khóa K với chiều dài thay đổi a. Thuật toán Mã hóa Giả sử chúng ta cần giấu bit b vào trong ảnh F. Cắt 1 đoạn gồm có ki (i = 1,2,...., n ) điểm ảnh và giấu b vào trong ảnh. Trong đó k là khóa, là số tự nhiên ngẫu nhiên. k = (k1,k2,k3,.....,kn) d = (n x m)/sum(k1,k2,...,kn) = số đoạn Giải thuật dựa vào tính chẵn lẻ: Bước 1: Đọc liên tiếp ki điểm ảnh. Gọi là fi Ký hiệu Sum(fi): là tổng số bit 1 có trong ki. Đặt b = t mod 2 Bước 2: So sánh t và b: Nếu t và b cùng tính chẵn lẻ: thì không làm gì cả. Nếu t và b khác tính chẵn lẻ: thì ta tìm cách sửa đúng 1 bit trong f. Khi đó f ® f’: sao cho f’ và b là cùng tính chẵn lẻ. Bước 3: Việc sửa bit được tiến hành như sau: Ta chọn chính sách: - Nếu có nhiều điểm đen và có điểm trắng thì sửa điểm trắng thành điểm đen. - Nếu có nhiều điểm trắng và có điểm đen thì sửa điểm đen thành điểm trắng. - Nếu số điểm đen và điểm trắng xấp xỉ bằng nhau thì chọn ngẫu nhiên 1 bit để sửa. - Nếu bit không quan trọng, bit nằm ở đầu những đoạn cùng màu thì việc sửa tập trung vào bit không quan trọng của những đoạn cùng màu lớn nhất. Giải mã Chỉ cần có ảnh F’ và khóa k1. Bước 1: Đọc ki điểm ảnh liên tiếp. Gọi là fi Bước 2: Tính Sum(fi): Nếu Sum(fi): chẵn ® bit bi = 0 Nếu Sum(fi): lẻ ® bit bi = 1 Ví dụ 4: các bit cần giấu là 10100, ảnh F và khóa K như hình 3.2 Ảnh F 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 0 Khóa K=(5,4,5,6,3) Ảnh F’ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 0 Hình 3.2 - Mô tả bài toán theo ví dụ 4 Mã hóa - Giấu bit b1: đọc liên tiếp 5 điểm ảnh và giấu b1 vào trong ảnh. Gọi là f1. S1 = Sum(f1)=4 . Vì (4 mod 2)=0 ≠ b1=1 và f1=01111 nên ta chọn bit F(1,1) để sửa. - Giấu bit b2: đọc liên tiếp 4 điểm ảnh và giấu b2 vào trong ảnh. Gọi là f2. S2 = Sum(f2)=4. Vì (4 mod 2)=0 = b2 nên ta không thay đổi f2. - Giấu bit b3: đọc liên tiếp 5 điểm ảnh và giấu b3 vào trong ảnh. Gọi là f3. S3 = Sum(f3)=4. Vì (4 mod 2)=0≠b3=1 và f3=01111 nên ta chọn bit F(2,5) để sửa. - Giấu bit b4: đọc liên tiếp 6 điểm ảnh và giấu b4 vào trong ảnh. Gọi là f4. S4 = Sum(f4) = 4. Vì (4 mod 2)=0=b4 nên không thay đổi f4. - Giấu bit b5: đọc liên tiếp 3 điểm ảnh và giấu b5 vào trong ảnh. Gọi là f5. S5 = Sum(f5) = 2. Vì (2 mod 2)=0 = b5 nên không thay đổi f5. Giải mã Chỉ cần có ảnh F’ và khóa k = (5,4,5,6,3). - Đọc liên tiếp 5 điểm ảnh. Gọi là f’1. S1 = Sum(f’1) = 5 Þ b1 = 1 (vì S1 lẻ). - Đọc liên tiếp 4 điểm ảnh. Gọi là f’2. S2 = Sum(f’2) = 4 Þ b2 = 0 (vì S2 chẵn). - Đọc liên tiếp 5 điểm ảnh. Gọi là f’3. S3 = Sum(f’3) = 5 Þ b3 = 1. - Đọc liên tiếp 6 điểm ảnh. Gọi là f’4. S4 = Sum(f’4) = 4 Þ b4 = 0. - Đọc liên tiếp 3 điểm ảnh. Gọi là f’5. S5 = Sum(f’5) = 2 Þ b5 = 0. Vậy chuỗi được giải mã là: 10100 Đặc điểm của thuật toán Khi chọn các bit thay đổi trong từng đoạn phù hợp thì bức ảnh sau khi giấu dữ liệu sẽ ít thay đổi hơn so với bức ảnh ban đầu. Ưu điểm của thuật toán - Một số bit dữ liệu được ẩn trong bức ảnh có thể không làm thay đổi hình ảnh ban đầu của bức ảnh. Do đó độ an toàn sẽ cao hơn. - Vì khóa k thay đổi nên việc tìm cách giải mã của đối phương sẽ gặp nhiều khó khăn. Khóa k chỉ được trao đổi giữa người gửi và người nhận. b. Tính đúng của thuật toán Tính đúng đắn của thuật toán được chứng minh bằng cách dựa trên chính văn bản của thuật toán đã trình bày gồm các bước như trên. 3.2.3.3 Sử dụng khóa bí mật k là một ma trận ảnh (do M.Y.Wu and J.H.Lee đề xuất: gọi tắt là thuật toán WL) a.Thuật toán WL Ta xem một bức ảnh chính là một ma trận nhị phân F, khóa K là một ma trận ảnh kích thước m x n và một số bit cần giấu. Để đơn giản ta xem kích thước của ảnh F là bội số của m x n. Việc giấu bằng cách thay đổi một số bit của F. Mã hóa Bước 1: chia F thành những khối, mỗi khối có kích thước m x n. Tính S = Sum(Fi Λ K) , Sk = Sum(K). [6] Bước 2: với mỗi khối Fi, kiểm tra điều kiện 0< S < Sk thì cho phép giấu tin vào Fi. Nếu không thỏa mãn điều kiện thì giữ nguyên Fi, không thay đổi bit nào. Bước 3: xem bit muốn giấu vào khối Fi là b, sau đó thực hiện các bước sau để thay đổi Fi: Nếu (S mod 2 = b ) thì giữ nguyên Fi. [6] Nếu S =1 thì chọn ngẫu nhiên 1 bit Fi[j,k] = 0 mà K[j,k] =1 thì đổi Fi[j,k] về 1. [6] Nếu S = Sk – 1 thì chọn ngẫu nhiên 1 bit Fi[j,k] =1 mà K[j,k] = 0 thì đổi Fi[j,k] về 0. [6] Nếu 1 < S < Sk thì chọn ngẫu nhiên 1 bit Fi[j,k] mà K[j,k] = 1 rồi đảo Fi[j,k]. Giải mã Giả sử Fi được biến đổi thành F’i thì ta có bất biến sau: 0< Sum(F’i Λ K) < Sum(K) Þ sum(F’i Λ K) = b mod 2. [6] Bước 1: chia F thành những khối, mỗi khối có kích thước m x n Tính S = Sum(F’i Λ K), Sk = Sum(K) Bước 2: với mỗi khối F’i, kiểm tra điều kiện 0<S<Sk thì cho giải mã từ F’i. Nếu không thỏa mãn điều kiện thì giữ nguyên Fi, không bit nào giấu trong Fi. Bước 3: xem bit giấu vào khối F’i là b. Khi người thu xác định được (0 < Sum(F’i Λ K) < Sum(K)) thì có thể tìm ra được bit đã giấu b: b = Sum(F’i Λ K) mod 2 [6] F1 F2 0 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 0 1 0 0 1 1 0 1 1 1 0 1 1 1 0 1 1 0 0 0 F3 F4 F3 F4 Khóa K 1 0 1 0 1 0 1 0 1 F’1 F’2 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 1 0 0 1 1 0 1 1 1 0 0 1 1 0 1 1 0 0 0 F’3 F’4 Hình 3.3 - Mô tả bài toán theo ví dụ 5 Ví dụ 5: chuỗi các bit cần giấu là: 101, ảnh F và khóa K được cho ở hình 3.3. F là một khối ảnh có kích thước 6x6 và K là một ảnh có kích thước 3x3. Mã hóa Trước tiên ta chia F thành 4 khối F1, F2, F3, F4. + Giấu bit đầu tiên: vì S = Sum(F1 Λ K) = 5 nên khối F1 không giấu dữ liệu, F1 được giữ nguyên. Vì S = Sum(F2 Λ K) = 2<Sk, một bit dữ liệu sẽ được giấu vào trong F. Vì bit đầu tiên cần giấu là bit 1 nên chọn ngẫu nhiên một bit trong F2 mà F2[j,k] = K[j,k] = 1 thì đảo F2[j,k] về 0 để đảm bảo thỏa mãn biểu thức trên (chọn F2[1,3] = 1). + Giấu bit thứ hai: vì S = Sum(F3 Λ K) = 4<Sk, một bit dữ liệu sẽ được giấu vào trong F. Vì bit thứ hai cần giấu là bit 0 và S mod 2 = 0 = b nên giữ nguyên F3. + Giấu bit thứ ba: vì S = Sum(F4 Λ K) = 4<Sk, một bit dữ liệu sẽ được giấu vào trong F. Vì bit thứ ba cần giấu là bit 1 và S = Sk – 1 nên chọn F4[j,k] = 1, K[j,k] = 0 rồi đổi F4[j,k] về 0 để đảm bảo thỏa mãn biểu thức trên (chọn F4[2,1] = 0). Giải mã: chỉ cần ảnh kết quả F’ và ma trận ảnh K. F’1 F’2 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 1 0 0 1 1 0 1 1 1 0 0 1 1 0 1 1 0 0 1 F’3 F’4 Khóa K 1 0 1 0 1 0 1 0 1 Hình 3.4 - Mô hình ảnh F’ và khóa K Trước tiên ta chia F’ thành 4 khối F’1, F’2, F’3, F’4. Giải mã bit thứ nhất: Vì S = Sum(F’1 Λ K) = Sum(K) = 5 nên khối F’1 không có giấu dữ liệu. Vì S = Sum(F’2 Λ K) = 3<Sk nên có một bit dữ liệu được giấu ở trong F’2 và S mod 2 =1, suy ra bit đầu tiên có giá trị là 1. Giải mã bit thư hai: Vì S = Sum(F’3 Λ K) = 4<Sk nên có một bit dữ liệu được giấu trong F’3 và S mod 2 = 0, suy ra bit thứ hai có giá trị 0. Giải mã bit thứ ba: Vì S = Sum(F’4 Λ K) = 3<Sk nên có một bit dữ liệu được giấu trong F’4 và S mod 2 = 1, suy ra bit thứ ba có giá trị 1. Vậy chuỗi được giải mã là 101. Đặc điểm của thuật toán Giải mã nhanh. Độ phức tạp được nâng cao hơn so với hai thuật toán trên. Cho phép giấu nhiều nhất 1 bit dữ liệu vào trong một khối. Nếu khối càng lớn thì tỉ lệ giấu tin càng ít. b. Tính đúng của thuật toán Người ta chứng minh tính đúng đắn của thuật toán bằng cách dựa trên chính văn bản của thuật toán được nêu qua các bước mã hóa và giải mã. 3.2.3.4 Sử dụng khóa K là ma trận khóa kích thước m x n (ma trận nhị phân) dùng chung bởi người gửi và người nhận kết hợp với ma trận trọng số cấp r, kích thước m x n cũng được dùng chung bởi người gửi và người nhận (do Yu-Yuan Chen, Hsiang-KangPan and Yu-Chee Tseng đề xuất: gọi tắt là CPT) a.Thuật toán CPT Với khối ảnh Fi, khóa K, ma trận trọng số W ta cần giấu r bit thông tin b1b2...br vào Fi bằng cách đảo nhiều nhất 2 bit của Fi. Mục đích của ta là biến đổi Fi thành F’i sao cho nó thỏa mãn yêu cầu sau: Sum((F’i Å K) Ä W) ≡ b1b2...br (mod 2r). [6] Mã hóa Quá trình biến đổi gồm bốn bước sau: Bước 1: tính ma trận T = Fi Å K. Bước 2: tính Sum = Sum((Fi Å K) Ä W). Bước 3: với ma trận T và với mọi w = 1,2,....,2r-1 ta xác định tập hợp Sw như sau: Sw = {(j,k)|( W[j,k] = w Λ T[j,k] = 0) Ú ( W[j,k] = 2r-w Λ T[j,k] = 1)} [6] Dễ nhận thấy Sw là tập hợp các tọa độ (j,k) của ma trận Fi[j,k] sao cho khi đảo bit Fi[j,k] thì Sum ở bước 2 tăng lên w. Thực vậy ta có: + Trường hợp 1: nếu W[j,k] = w và T[j,k] = 0 Khi đó đảo bit Fi[j,k] sẽ làm cho T[j,k] = 1, do đó Sum tăng lên w + Trường hợp 2: nếu W[j,k] = 2r – w và T[j,k] = 1 Khi đó đảo bit Fi[j,k] sẽ làm cho T[j,k] = 0, do đó Sum sẽ giảm đi 2r – w, tức là tăng lên w theo mod 2r. Quy ước rằng với mọi w’ ≡ w (mod 2r) trong đó w = 1,2,....,2r – 1, ta có Sw’ = Sw . Bước 4: ký hiệu: d = (b1b2....br) – Sum((Fi Å K) Ä W) (mod 2r). [6] Ta cần thực hiện việc đảo bit trên Fi để được F’i sao cho tổng Sum tính được ở bước 2 khi thay Fi bởi F’i sẽ tăng lên d. * Nếu d = 0: không thay đổi Fi . * Nếu d ≠ 0: 1. Chọn h bất kỳ thuộc tập {0,1,2,...,2r - 1}sao cho Shd ≠ Æ và S-(h - 1)d ≠Æ 2. Chọn (j,k) bất kỳ thuộc Shd và đảo bit Fi[j,k] (nếu là 0 thì đổi thành 1 và ngược lại, 1 đổi thành 0). 3. Chọn (j,k) bất kỳ thuộc S-(h - 1)d và đảo bit Fi[j,k]. Rõ ràng là để tăng Sum lên d, ta có thể chọn hai tập khác rỗng Shd và S-(h - 1)d. Thật vậy, hai tập hợp này chứa các vị trị bit trong khối Fi mà ta có thể đảo để tăng Sum lên hd và –(h - 1)d một cách tương ứng, kết quả cuối cùng là Sum sẽ tăng lên là hd + (-(h - 1)d) = d. Tương tự như các tập Sw khác ta cũng có thể coi tập S0 là tập chứa các vị trí mà khi đảo những bit có vị trí này trên Fi thì sẽ tăng Sum lên 0. Kết quả này cũng đạt được nếu ta không đảo bất kỳ bit nào trên Fi. Vì vậy ta có thể coi S0 là tập trống và khi nói đảo 1 bit có vị trí thuộc tập S0 có nghĩa là không cần làm gì cả. Giải mã Khi nhận được bức ảnh kết quả, người nhận chỉ cần tách các bit ít đặc trưng nhất của từng điểm ảnh và chia thành từng khối F’i kích thước m x n. Quá trình biến đổi gồm ba bước sau: Bước 1: tính ma trận T = F’i Å K Bước 2: tính tổng Sum = Sum((Fi Å K) Ä W) Bước 3: sử dụng ma trận khóa và ma trận trọng số để tính giá trị của r bit thông tin được giấu trong mỗi khối ảnh bằng công thức sau: (b1b2....br) = Sum((Fi Å K) Ä W) (mod 2r) Ví dụ 6: cho F gồm (F1 F2 F3 F4), K, W như sau: F1 F2 0 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 0 1 0 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 0 1 F3 F4 Kh