Luận văn Nghiên cứu một số khả năng phát hiện tin giấu trong môi trường ảnh

đó ta hi vọng rằng giá trị của hàm f sẽ tăng (hoặc giảm) sau khi giấu tin LSB. Định nghĩa 2.3.2: Việc giấu tin LSB sử dụng các kiểu hàm lật (flip) bit Fm(x) với m = -1, 0, 1 và x là giá trị điểm ảnh. Cụ thể như sau: F1: 0 ↔ 1, 2 ↔ 3, …, 254 ↔ 255. F−1: −1 ↔ 0, 1 ↔ 2, 3 ↔ 4, …, 253 ↔ 254, 255 ↔ 256 hay F−1(x) = F(x+1) −1 với mọi x. F0(x) = x, với x P. Định nghĩa 2.3.3: Phép lật bit F1 và F-1 được áp dụng lên nhóm G(x1, x2, …, xn) với một mặt nạ M (M là một n-bộ với các thành phần nhận giá trị -1, 0 hoặc 1) được định nghĩa như sau: FM(G) = (FM(1)(x1), FM(2)(x2), …, FM(n)(xn)) trong đó M(i)  {-1, 0, 1} 70 Ví dụ: nếu các giá trị các điểm ảnh trong nhóm G là (39, 38, 40, 41) và mặt nạ M = (1, 0, 1, 0) thì FM(G) = (F1(39), F0(38), F1(40), F0(41)) = (38, 38, 41, 41). Định nghĩa 2.3.4: Cho một mặt nạ M, phép lật bit F, và hàm khoảng cách f, một nhóm G các điểm ảnh được phân lớp vào một trong ba lớp sau: G  R  f(FM(G)) > f(G). G  S  f(FM(G)) < f(G). G  U  f(FM(G)) = f(G). Trong đó R gọi là các nhóm chính quy (Regular), S là các nhóm đơn (Singular) và U là các nhóm không dùng được (Unusable). Khái niệm 2.3.5: Ta gọi RM là số tương đối các nhóm R với mặt nạ M không âm, M  {0, 1}. SM là số tương đối các nhóm S với mặt nạ M không âm, M  {0, 1}. R-M là số tương đối của các nhóm R với mặt nạ M không dương, M {-1, 0}. S-M là số tương đối của các nhóm S với mặt nạ M không dương, M {-1, 0}. Ta có RM xấp xỉ bằng R-M và SM xấp xỉ bằng S-M và được viết như sau: MM RR  và MM SS  Việc giấu tin LSB tập trung vào sự khác biệt giữa RM và SM. Nếu có 50% điểm ảnh bị lật (khi mỗi điểm ảnh bị giấu bit thông điệp) ta thu được MM SR  nhưng ảnh hưởng của việc giấu tin LSB đến R-M và S-M lại ngược lại. Dưới đây sẽ trình bày các bước cụ thể của kỹ thuật RS trong đó có sử dụng đến các khái niệm và định nghĩa vừa trình bày ở trên. 71 2.4.2 Thuật toán RS (Regular – Singular) Ý tưởng Kỹ thuật RS phân hoạch ảnh cần kiểm tra thành các nhóm điểm ảnh cố định. Mỗi nhóm đó lại được phân lớp vào các nhóm R hay S phụ thuộc vào sự khác biệt giữa các điểm ảnh trong nhóm bị tăng hoặc giảm sau phép lật bit LSB với mặt nạ M. Sau đó tính xác suất của việc giấu tin căn cứ vào số nhóm R, S đó. Input Ảnh I cần kiểm tra. n: số phần tử của một nhóm Mn: mặt nạ là một vecto có các phần tử nhận giá trị trong tập {-1, 0, 1} Output p: Xác suất giấu tin trong ảnh I Thuật toán Bước 1: Đọc vào ảnh I Bước 2: Đọc giá trị các điểm ảnh vào một ma trận AMxN. Bước 3: P = P  {xi} với xi  [0, 255]. Bước 4: Chia ảnh thành MxN/n nhóm khác nhau. Mỗi nhóm n điểm ảnh. Với mỗi nhóm G = (x1, x2, …, xn) ta thực hiện các bước sau: Bước 5: Tính hàm f(G)    1 1 1 )( n i ii xxGf Bước 6: Cho mặt nạ M = {M(i)}i = 1,…, n với M(i)  {-1, 0, 1}. Tính FM(G) = (FM(1)(x1), FM(2)(x2), …, FM(n)(xn)) Bước 7: Phân lớp nhóm G Nếu f(FM(G)) > f(G) thì R = R  G; Nếu f(FM(G)) < f(G) thì S = S  G; Nếu f(FM(G)) = f(G) thì U = U  G; 72 Bước 8: Tính RM = số các nhóm R tương ứng với mặt nạ M, M(i)  {0, 1} SM = số các nhóm S tương ứng với mặt nạ M, M(i)  {0, 1} R-M = số các nhóm R tương ứng với mặt nạ M, M(i)  {-1, 0} S-M = số các nhóm S tương ứng với mặt nạ M, M(i)  {-1, 0} Bước 9: Nếu |RM| =|SM| thì p = 1 Ngược lại thực hiện các bước 9 đến bước 12 Bước 10: Tính các hệ số d0 = RM(p/2) - SM(p/2); d1 = RM(1- p/2) - SM(1- p/2); d-0 = R-M(p/2) – S-M(p/2); d-1 = R-M(1- p/2) – S-M(1- p/2); Bước 11: Tính xp là nghiệm của phương trình     032 000110201   ddxddddxdd pp Bước 12: Tính ước lượng độ dài thông điệp p p = xp /(xp – ½); Phân tích thuật toán RS Ban đầu phân hoạch MxN điểm ảnh thành (MxN/n) nhóm mỗi nhóm n điểm ảnh độc lập liền kề nhau. Thông thường chọn n = 4 (là các khối 2x2). Với P là tập tất cả các giá trị điểm ảnh. Với mỗi nhóm G chứa n giá trị điểm ảnh trên P. G = (x1, x2, …, xn). Ta sẽ phân lớp các nhóm G vào ba lớp R, S, U. Trước tiên, ta xác định hàm f(G) là tổng khoảng cách về sự khác biệt giữa các phần tử kề nhau trong G theo định nghĩa 3.3.1. Tiếp theo với mỗi điểm ảnh xi (1  i  n) của nhóm G, ta xác định hàm lật bit FM(i)(xi). Giá trị của hàm này phụ thuộc vào giá trị của M(i) tương ứng trong mặt nạ M. Nếu M(i) = 0 thì FM(i)(xi) = xi điều này nghĩa là không có sự thay đổi bit tại xi. Nếu M(i) = 1 và xi ≥ 0 thì FM(i)(xi) sẽ nhận giá trị xi +1 nếu xi là số chẵn, ngược lại sẽ nhận giá trị là xi-1 nếu xi là số lẻ. Nếu M(i) = 1 và xi ≥ -1, thì FM(i)(xi) sẽ nhận giá trị là xi+1 nếu xi là lẻ, ngược lại hàm sẽ nhận giá trị là xi-1 nếu xi là số chẵn. Với mỗi FM(i)(xi) với 1  i  n có ta thu được FM(G) = (FM(1)(x1), FM(2)(x2), …, FM(n)(xn)). 73 Ở bước tiếp theo, với mặt nạ M = {M(i)}i = 1,…, n với M(i)  {-1, 0, 1}, hàm f(G) và FM(G) đã thu được ở bước trước, ta phân lớp nhóm G thành các lớp R, S, U theo định nghĩa 3.3.2. Nếu nhóm G không có sự thay đổi giá trị của các phần tử kề nhau sau phép lật bit theo mặt nạ M (tương ứng M = {0}) thì G  U. Nếu sự khác biệt giữa các phần tử kề nhau sau phép lật bit trên nhóm G theo mặt nạ M là lớn hơn sự khác biệt giữa các phần tử kề nhau trong nhóm G ban đầu thì G  R, ngược lại G  S. Sau khi phân lớp các nhóm G, nếu sử dụng mặt nạ M với các phần tử có giá trị không âm (thuộc {0,1}) để lật bit, đếm số nhóm G  R, gọi là RM, tương tự SM là số nhóm G  S; nếu sử dụng mặt nạ M với các phần tử có giá trị không dương {-1,0} để lật bit, đếm số nhóm G  R, gọi là R-M, tương tự S-M là số nhóm G  S. Nếu có một ảnh chứa tin ẩn (stego) với chiều dài thông điệp ẩn đã giấu là p (phần trăm các điểm ảnh) chưa được biết. Khởi tạo, độ đo của số các phần tử trong các nhóm R và S tương ứng là RM(p/2), R-M(p/2), SM(p/2), S-M(p/2). Giả sử thông điệp là một vecto bit ngẫu nhiên, trung bình chỉ một nửa các điểm ảnh sẽ bị lật bít thông qua việc giấu tin, nếu ta lật bít LSB của tất cả các điểm ảnh thì số các phần tử của nhóm R và S là RM(1 - p/2), SM(1- p/2), R-M(1-p/2), S-M(1- p/2). Hình 2.4 dưới đây mô tả một đồ thị RS với trục x là giá trị phần trăm các điểm ảnh đã bị lật bit LSB, trục y là số tương đối các nhóm R và S với các mặt nạ M, -M. Trong đó M = [0, 1, 1, 0]. Hình 2.4. Đồ thị RS của một ảnh kiểm tra. 74 Người ta đã tiến hành thực nghiệm và các kết quả thực nghiệm đã chỉ ra rằng các đường R-M và S-M gần như một đường thẳng trong khi các đường RM và SM xấp xỉ đường cong của một đa thức bậc hai (parabol). Cũng bằng thực nghiệm, ước lượng hai giá trị của RM(1/2) và SM(1/2) từ các mẫu thống kê ta thu được RM(1/2) = SM(1/2). Để không mất thời gian làm thực nghiệm và để việc ước lượng chiều dài thông điệp được đơn giản hơn ta chấp nhận hai giả thiết sau đây. Các giả thiết này đã được người ta tiến hành thực nghiệm để kiểm chứng [26]. (i). Giao điểm của các đường RM và R-M có cùng tọa độ x với giao điểm của SM, S-M. (ii). RM(1/2) = SM(1/2). Trên đồ thị RS, số các nhóm R và S ở p/2 và 1-p/2 tạo thành các đường thẳng (hình 2.4), các điểm còn lại và hai giả thiết (i) và (ii) ở trên cung cấp các ràng buộc đầy đủ để xác định duy nhất các parabol và giao điểm của chúng. Sau khi thay đổi tỷ lệ trên trục x để p/2 thành 0 và 100-p/2 thành 1 bằng phép thế tuyến tính xp = (x-p/2)(1- p), tọa độ x của các giao điểm là nghiệm của phương trình sau:     032 000110201   ddxddddxdd pp Trong đó các hệ số đã được chỉ ra trong bước 10 của thuật toán. Cuối cùng ta tính ước lượng độ dài thông điệp p như công thức ở bước 12. * Độ chính xác của độ dài thông điệp đã được ước lượng Có ba yếu tố chính ảnh hưởng đến độ chính xác của độ dài thông điệp đã được ước lượng đó là: độ lệch ban đầu, mức độ nhiễu hoặc chất lượng của ảnh mang tin và vị trí của các bit thông điệp trên ảnh [26]. Thứ nhất, độ lệch ban đầu: Kỹ thuật RS có thể cho độ dài thông điệp khác 0 nhờ số chẵn các biến ngẫu nhiên trên ảnh gốc. Độ lệch ban đầu khác không có thể là một số dương hoặc âm và nó đặt ra một giới hạn cho độ chính xác có được của phương pháp RS. Người ta đã tiến hành kiểm tra với một cơ sở dữ liệu gồm 331 ảnh đa cấp xám JPEG và thu được một phân phối Gauss có độ lệch chuẩn 0.5%. Số ảnh nhỏ hơn thì phải có số các biến cao hơn trong độ lệch ban đầu vì số lượng các nhóm R và S là nhỏ hơn. Các ảnh trung gian và các ảnh nhiễu có các biến lớn hơn trong các độ lệch ban đầu. Ngược lại, độ lệch lại rất thấp đối với các ảnh JPEG, các ảnh không được nén thu được qua các camera số, qua máy quét và các các ảnh đã qua bộ lọc xử lý ảnh. Các ảnh mầu cũng cho các biến lớn hơn trong độ lệch so với các ảnh đa cấp xám. 75 Thứ hai, mức độ nhiễu: Với các ảnh có nhiều nhiễu, sự khác biệt giữa số các điểm ảnh R và S trên ảnh “cover” là nhỏ. Do vậy, các đường trên đồ thị RS giao nhau ở một góc nhỏ và độ chính xác của kỹ thuật RS giảm. Đối với ảnh chất lượng thấp, ảnh đã qua nén và các ảnh nhỏ cũng như vậy. Thứ ba, vị trí các bít thông điệp trên ảnh: Kỹ thuật RS chính xác hơn nếu các bit thông điệp được phân bố một cách rời rạc ngẫu nhiên trên ảnh. 76 2.5 KỸ THUẬT PHÂN TÍCH CẶP MẪU SPA 2.5.1 Các khái niệm Kỹ thuật phân tích cặp mẫu SPA (Sample Pair Analysis) do Sorina Dumitrescu et. al. đưa ra nhằm phát hiện các giấu tin mật LSB thông qua việc phân tích cặp mẫu. Khi tỷ lệ giấu tin lớn hơn 3% thì phương pháp này có thể ước lượng độ dài đã giấu với độ chính xác tương đối cao [23, 27, 28]. Kỹ thuật SPA dựa trên lý thuyết về xích hữu hạn trạng thái. Các trạng thái của xích hữu hạn trạng thái được chọn từ tập hỗn hợp (multisets) các cặp mẫu được gọi là tập hỗn hợp dấu vết (trace multisets). Trước khi giấu tin, các phần tử trong cặp có quan hệ với nhau theo một độ đo nào đó. Nhưng sau khi giấu tin LSB một cách ngẫu nhiên thì các tập này sẽ thay đổi và nó dẫn đến những thay đổi các quan hệ thống kê. Giả sử rằng ta có các mẫu liên tiếp nhau s1, s2, …, sN (các chỉ số thể hiện vị trí của một mẫu trên ảnh). Một cặp mẫu là một bộ hai (si, sj) 1 i, j  N. Đặt P là tập tất cả các cặp mẫu được lấy ra từ một ảnh. P có thể coi như là một tập hỗn hợp (multiset) của các bộ hai (u, v), trong đó u và v là các giá trị của hai mẫu. Nếu không có gì ngoại lệ thì bộ hai (u, v) hoặc các phần tử của P luôn tham chiếu đến các giá trị của các mẫu khác nhau được lấy ra từ ảnh. Định nghĩa Dn = {(u,v)  P | |u-v| = n} là một tập con (submultiset) của P chứa cặp mẫu có dạng (u, u+n) hoặc (u+n, u) trong đó n là một số nguyên cố định 0  n  2b -1, b là số bit nhị phân biểu diễn mỗi giá trị mẫu. Hay nói cách khác, các cặp mẫu trong Dn sai khác nhau một lượng bằng n. Từ việc giấu tin chỉ ảnh hưởng tới các bít LSB nên ta sử dụng nhiều nhất là (b-1) bit tín hiệu trong việc chọn lựa các tập hỗn hợp đóng này. Với mỗi số nguyên m, 0  m  2b-1 -1 ta định nghĩa tập Cm là tập con (submultiset) của P có chứa các cặp mẫu mà giá trị của nó chỉ sai khác nhau m trong (b-1) bit đầu tiên. Cm = {(u, v)  P \ 2 vu  = m} với 0  m  2b-1 -1. Ta xét mối quan hệ giữa Dn và Cm. Thứ nhất, ta có Cm chứa D2m. Thật vậy, nếu (u, v) là một cặp trong D2m (|u-v| = 2m) thì cả u và v là cùng chẵn hoặc cùng lẻ. Bằng việc dịch phải một bit và lấy sai phân trị tuyệt đối ta thu được giá trị |u-v|/2 và do đó cặp (u, v)  Cm. 77 Thứ hai, D2m+1 = Cm  Cm+1 hay các cặp mẫu của tập D2m+1 là giao của hai tập Cm và Cm+1. Thật vậy, nếu cặp (u,v)  D2m+1 thì (u,v) có thể có các dạng sau (2k-2m-1, 2k), (2k, 2k-2m-1), (2k-2m, 2k+1) hoặc (2k+1, 2k-2m) với mọi k. Cặp (2k-2m-1, 2k), (2k, 2k-2m-1) thuộc tập Cm+1 vì bằng phép dịch phải một bit các giá trị 2k và 2k-2m-1 theo thứ tự sẽ là thu được giá trị k và k-(m+1) và như vậy chúng sẽ vẫn sai khác nhau m+1. Hai cặp (2k-2m, 2k+1) và (2k+1, 2k-2m) thuộc Cm vì bằng phép dịch phải một bit thì giá trị của 2k+1 và 2k-2m theo thứ tự thu được giá trị là k và k-m, như vậy chúng vẫn sai khác nhau là m. Ta phân hoạch D2m+1 thành hai tập con X2m+1 và Y2m+1, trong đó X2m+1 = D2m+1  Cm+1 Y2m+1 = D2m+1  Cm với 0  m  2b-1 -2 và 12bX . 1212   bb DY . Cả hai tập X2m+1 và Y2m+1 đều là những tập con (submultiset) của P. Tập X2m+1 chứa các cặp (u,v) có dạng (2k-2m-1, 2k) hoặc (2k, 2k-2m-1). Tập Y2m+1 chứa các các cặp (u,v) có dạng (2k-2m, 2k+1) hoặc (2k+1, 2k-2m). Những cặp mà trong đó thành phần chẵn lớn hơn sẽ nằm trong tập X2m+1 còn những cặp mà trong đó thành phần lẻ lớn hơn sẽ nằm trong tập Y2m+1 và tất cả những cặp này đều sai khác nhau 2m+1. Với các ảnh có tín hiệu chuẩn, xác suất để một cặp mẫu ở trong tập D2m+1 có các thành phần chẵn lớn hơn hoặc nhỏ hơn là như nhau. Điều đó có nghĩa là với số nguyên m bất kỳ, 0  m  2b-1-2 ta có E(|X2m+1|) = E(|Y2m+1|) (1) Để phân tích ảnh hưởng của việc giấu tin LSB trên các cặp mẫu ta xem xét bốn trường hợp có thể của việc “lật” bit LSB theo mẫu, gọi mẫu   {00, 01, 10, 11} với 1 biểu thị cho một (hoặc nhiều) mẫu trong một cặp có bị đảo bit, 0 biểu thị cho một (hoặc nhiều) mẫu vẫn giữ nguyên (không bị đảo bít). Với mỗi m, 0  m  2b-1-1, tập Cm được phân hoạch thành X2m-1, D2m, Y2m+1. Rõ ràng Cm là đóng đối với phép giấu nhưng các tập con thành phần X2m-1, D2m, Y2m+1 thì không. Lấy một cặp mẫu (u, v) tùy ý của X2m-1 thì (u, v) có thể có dạng (2k-2m+1, 2k) hoặc (2k, 2k-2m+1). Bằng việc chuyển đổi cặp mẫu (u, v) qua mẫu  =10, ta thu được mẫu (u’, v’) = (2k-2m, 2k) hoặc (u’, v’)=(2k+1, 2k-2m+1). Tương tự như vậy, nếu (u, v) được thay đổi thông qua mẫu 01 thì (u’, v’) = (2k-2m+1, 2k+1) hoặc (u’v’) = (2k, 2k-2m). Rõ ràng X2m và Y2m tạo thành một phân hoạch của D2m. 78 Như vậy, Cm với 0  m  2b-1-1 có thể được phân hoạch thành bốn tập con X2m-1, X2m, Y2m và Y2m+1 được gọi là các tập con hỗn hợp dấu vết (trace submultisets) của Cm. Hơn nữa Cm là đóng nhưng bốn tập con của nó thì không đóng đối với các thao tác giấu tin LSB. Điều này giống như một máy trạng thái hữu hạn được mô tả trên hình 2.5. Trên hình 2.5 các trạng thái (các nút tròn) chính là các tập con (trace submultise) của Cm. Các cung được gắn nhãn  là mẫu chuyển đổi nối từ trạng thái A sang trạng thái B thể hiện rằng bất kỳ cặp mẫu nào trong A sẽ trở thành một cặp mẫu trong B nếu áp dụng mẫu chuyển đổi . Hình 2.5. Xích hữu hạn trạng thái với các trạng thái là các tập con của Cm (m>0). Tập C0 là đóng đối với phép giấu tin LSB và có thể được phân hoạch thành hai tập Y1 và D0. Hình 2.5 mô tả một máy trạng thái cho C0. Hình 2.6. Xích hữu hạn trạng thái cho tập C0. Ý nghĩa của các xích hữu hạn trạng thái trong hình 2.5 và 2.6 là: có thể đo (một cách thống kê) số các tập con trước và sau khi giấu tin bằng cách sử dụng các xác suất của các mẫu thay đổi trong mỗi tập (multiset). Hơn nữa, nếu việc giấu tin LSB được làm một cách ngẫu nhiên trong ảnh thì các xác suất là các độ dài của thông điệp ẩn. 79 Với mỗi mẫu chuyển đổi   {00, 10, 01, 11} và với bất kỳ tập con (submutiset) A  P, ta định nghĩa xác suất (, A) là xác suất các cặp mẫu của A bị thay đổi theo mẫu . Đặt p là chiều dài thông điệp bị giấu trong các bit bị chia bởi tổng số các mẫu trong các ảnh. Thế thì hệ số các mẫu đã thay đổi bằng giấu tin LSB là p/2. Giả sử rằng, các bit thông điệp của giấu tin mật LSB được phân bố ngẫu nhiên trong ảnh, ta có (i). (00,P) = (1-p/2)2 (ii). (01,P) = (10,P) = p/2(1-p/2) (iii). (11,P) = (p/2)2 Đặt A và B là hai tập con của P sao cho A  B. Ta nói rằng tập A là không chệch đối với tập B nếu (,A) = (,B) ứng với mỗi mẫu biến đổi   {00, 10, 01, 11}. Khi B = P ta nói rằng A là không chệch. Nếu tất cả bốn tập con của Cm là không chệch thì ta nói rằng Cm là không chệch. 2.5.2 Phát hiện giấu tin mật LSB nhờ kỹ thuật SPA Input Ảnh I cần kiểm tra Output p: Xác suất giấu tin trong ảnh I Thuật toán Bước 1: Đọc vào ảnh I Bước 2: Đọc giá trị các điểm ảnh vào một ma trận A. Bước 3: Chia ma trận A thành dãy S gồm N mẫu liên tiếp nhau s1, s2, …, sN. Mỗi mẫu si là một giá trị điểm ảnh. Bước 4: Xác định P = {(si, sj) } với 1 i, j  N Bước 5: b = độ dài xâu nhị phân biểu diễn mỗi mẫu. Bước 6 : Với số nguyên n cố định, 0  n  2b-1 Mỗi (u, v)  P nếu |u-v|= n thì Dn = Dn  {(u,v)}; Bước 7: Với số nguyên m, 0 m  2b-1-1 Mỗi (u, v)  P nếu |u-v|/2= m thì Cm = Cm  {(u,v)}; 80 Bước 8: Xác định các tập sau  12b X  ; 1212   bb DY ; với 0  m  2b-1 -2 X2m+1 = D2m+1  Cm+1; Y2m+1 = D2m+1  Cm ; Bước 9: Đặt  = {00, 01, 10, 11} Bước 10: Nếu  = 00 hoặc  = 10 thì tập '2' 12 mm XX  chứa các cặp mẫu của tập mm XX 212  bị thay đổi thông qua các mẫu 00 hoặc 10. Nếu  = 01 hoặc  = 11 thì tập ' 12'2  mm YY chứa các cặp mẫu của tập 122  mm YY bị thay đổi thông qua các mẫu 01 hoặc 11. Bước 11: Tính p Nếu E{|X2m+1|} = E{|Y2m+1|} thì Xác định p là nghiệm nhỏ hơn của các phương trình sau Nếu m = 0:     ;0 2 222 4 2 ' 1 ' 1 ' 1 ' 1 ' 2 ' 0 2 10     XY pXYDDpCC Nếu m ≥ 1     0 2 22 4 ' 12 ' 12 ' 12 ' 12 ' 22 ' 2 2 1       mm mmmmmm XY pXYDDpCC 81 2.5.3 Phân tích kỹ thuật SPA Sau khi đọc vào ảnh I và lấy dữ liệu trên ảnh I vào ma trận A, ta thống kế các giá trị điểm ảnh có trên ảnh. Chia ma trận A thành N mẫu liên tiếp nhau (mỗi mẫu là một giá trị điểm ảnh) và được biểu diễn bằng xâu nhị phân độ dài b. Từ các mẫu đã có, ta xác định tập P là tập các cặp mẫu có thể có. Với n là một số nguyên cố định 0  n  2b-1 ta xây dựng tập tất cả các cặp trong P mà có khoảng cách giữa chúng bằng n. Gọi tập đó là Dn. Với mỗi số nguyên m, 0  m  2b-1 -1 ta xây dựng tập Cm là tập tất cả các cặp (u, v)  P mà |u-v|/2 = m Hiển nhiên, tập con Dn (với 0  n  2b -1) của P dùng để mô tả sự thay đổi được tạo ra từ việc giấu tin vào bit it quan trọng nhất ở giữa hai giá trị mẫu khác nhau. Còn tập con Cm (0  m  2b-1 -1) của P lại là một bất biến dưới phép giấu tin LSB. Tiếp theo ta phân hoạch tập D2m+1 thành hai tập con X2m+1 và Y2m+1 như sau X2m+1 = D2m+1  Cm+1 Y2m+1 = D2m+1  Cm với 0  m  2b-1 -2 và 12bX . 1212   bb DY . Trong đó, tập X2m+1 chứa các cặp (u,v) có dạng (2k-2m-1, 2k) hoặc (2k, 2k-2m- 1). Tập Y2m+1 chứa các các cặp (u,v) có dạng (2k-2m, 2k+1) hoặc (2k+1, 2k-2m). Hay nói cách khác, những cặp mà trong đó thành phần chẵn lớn hơn sẽ nằm trong tập X2m+1 còn những cặp mà trong đó thành phần lẻ lớn hơn sẽ nằm trong tập Y2m+1 và tất cả những cặp này đều sai khác nhau 2m+1. Với các ảnh có tín hiệu chuẩn, xác suất để một cặp mẫu ở trong tập D2m+1 có các thành phần chẵn lớn hơn hoặc nhỏ hơn là như nhau. Điều đó có nghĩa là với số nguyên m bất kỳ, 0  m  2b-1-2 ta có E (|X2m+1|) = E (|Y2m+1|) (2.5.1) Theo như phân tích trong mục 2.5.1 và các máy trạng thái mô tả trong hình 2.5 và 2.6 ta có với m = 0 tập C0 được phân hoạch thành Do và Y1, với 1  m  2b-1-2 thì Cm được phân hoạch thành bốn tập con X2m-1, X2m, Y2m và Y2m+1. Tiếp theo ta sử dụng mẫu   {00, 01, 10, 11} với 1 biểu thị cho một (hoặc nhiều) mẫu trong một cặp có bị đảo bit, 0 biểu thị cho một (hoặc nhiều) mẫu vẫn giữ nguyên (không bị đảo bít) để xem xét sự ảnh hưởng của việc lật bit LSB trên các mẫu. Các trường hợp khác nhau của mẫu  như sau: Nếu  = 00 hoặc  = 10 thì ta gọi tập ' 2 ' 12 mm XX  là tập chứa các cặp mẫu của tập mm XX 212  bị thay đổi thông qua các 82 mẫu 00 hoặc 10. Nếu  = 01 hoặc  = 11 thì tập ta gọi ' 12 ' 2  mm YY chứa các cặp mẫu của tập 122  mm YY bị thay đổi thông qua các mẫu 01 hoặc 11. Gọi p là chiều dài thông điệp bị giấu trong các bit bị chia bởi tổng số các mẫu trong các ảnh. Với 1 m  2b-1-1, ta có các phương trình sau: |||)|2|( 2 || 4 )1(|| ' 12 ' 12 ' 2 2 2 12   mmmmm XXD pCppX (2.5.2) |||)|2|( 2 || 4 )1(|| ' 12 ' 12 ' 2 2 2 12   mmmmm YYD pCppY (2.5.3) Với m = 0 ta có |||)|22( 22 |)1(| '1 ' 1 ' 0 2 0 2 1 YYD ppCpY  (2.5.4) Chứng minh phương trình (2.5.2) (2.5.3) (2.5.4) Ta có tập '2' 12 mm XX  chứa các cặp mẫu của tập mm XX 212  bị thay đổi thông qua các mẫu 00 hoặc 10. Tập ' 12 ' 2  mm YY chứa các cặp mẫu của tập 122  mm YY bị thay đổi thông qua các mẫu 01 hoặc 11. Xác suất mà cặp mẫu tùy ý của tập mm XX 212  bị thay đổi qua các mẫu 00 và 10 là bằng (1-p/2)2 + p/2(1-p/2) = 1- p/2. Xác suất mà cặp mẫu tùy ý của tập mm YY 212  bị thay đổi qua các mẫu 01 và 11 là bằng p/2(1-p/2) – (p/2)2 = p/2. Ta có số lượng của các phần tử trong tập '2' 12 mm XX  bằng |||| '2' 12 mm XX  và được tính như sau 2/|)||(|)2/1|)(||(||||| 122212 ' 2 ' 12 pYYpXXXX mmmmmm   (2.5.5) Tương tự ta có số lượng các phần tử của tập ' 12 ' 2  mm YY như sau 2/|)||(|)2/1|)(||(||||| 212122 ' 12 ' 2 pXXpYYYY mmmmmm   (2.5.6) Trừ (2.5.5) cho (2.5.6) ta có )1|)(||||||(||||||||| 221212 ' 2 ' 2 ' 12 ' 12 pYXYXYXYX mmmmmmmm   (2.5.7) Tập X2m-1  Y2m hoán đổi các cặp mẫu chỉ với tập X2m  Y2m+1 và các cặp bị hoán đổi chỉ bằng các mẫu 10 hoặc 11, trên thực tế cặp mẫu tùy ý của mỗi tập thành phần ở trên có xác suất là p/2. Ta có 83 )1|)(||||||(||||||||| 221212 ' 2 ' 2 ' 12 ' 12 pXYYXXYYX mmmmmmmm   (2.5.8) Cộng (2.5.7) và (2.5.8) ta được )1|)(||(||||| 1212 ' 12 ' 12 pYXYX mmmm   (2.5.9) Bước tiếp theo là suy dẫn ra số phần tử của tập ' 12 ' 12   mm YX sử dụng máy trạng thái hữu hạn trong hình 2.2. Chú ý: 1212   mm YX hoán đổi các cặp chỉ với tập D2m. (D2m = X2m Y2m). )2/1(||])2/()2/1|).[(||(||||| 2 22 1212 ' 12 ' 12 ppDppYXYX mmmmm   (2.5.10) Từ |D2m| = |Cm| - |X2m-1|-|Y2m+1| dẫn đến )2/1(||)1|).(||(||||| 21212 ' 12 ' 12 ppCpYXYX mmmmm   (2.5.11) Nhân cả hai vế của (2.5.9) với (1-p) rồi cộng với với (2.5.11) ta thu được phương trình )2/1(||)1(||2||)2(|| 212 ' 12 ' 12 ppCpXpYpX mmmm   (2.5.12) Nhưng với Cm là đóng với thao tác giấu, từ đó |||||||| '2 ' 12 ' 12 mmmm DYXC   (2.5.13) Cuối cùng từ (2.5.12) và (2.5.13) ta thu được phương trình (2.5.2). Tương tự bằng việc nhân hai vế của (2.5.9) với (1-p) rồi cộng với với (2.5.11) sau đó cũng sử dụng công thức (2.5.13) ta thu được phương trình (2.5.3). Việc chứng minh phương trình (2.5.4) cũng tương tự. Từ công thức (2.5.2) đến (2.5.4) với điều kiện E{|X2m+1|} = E{|Y2m+1|}, 0 m  2b-1-2. Cuối cùng ta thu được các phương trình bình phương mạnh để ước lượng giá trị của p như sau     1,0 2 22 4 ' 12 ' 12 ' 12 ' 12 ' 22 ' 2 2 1       mXY pXYDDpCC mm mmmmmm (2.5.14) và     0,0 2 222 4 2 ' 1 ' 1 ' 1 ' 1 ' 2 ' 0 2 10     mXY pXYDDpCC (2.5.15) Phương trình (2.5.14) và (2.5.15) là phương trình bậc hai theo p. Nghiệm nhỏ hơn của phương trình (2.5.14) (hoặc 2.5.15) là giá trị được ước lượng của p, với điều kiện 84 |Cm |> |Cm+1| và |D2m | ≥ |D2m+2| (hoặc 2|C0| > |C1| và 2|D0| ≥ |D2|) (2.5.16) Thật vậy, ta có các bất đẳng thức 2|C0| > |C1| > |C2| > … >|Cm| > |Cm+1| > … (2.5.17) 2|D0| > |D2| > |D4| > … > |D2m| > |D2m+2| > … (2.5.18) Đặt U và V là hai tập các biến ngẫu nhiên rời rạc tương ứng với các giá trị thứ nhất và thứ hai của các cặp mẫu trong P, ta có hàm hội tụ xác suất có điều kiện (pmf – probability mass fuction) P(u,v). Xem xét sự khác biệt giữa U và V ta có một biến ngẫu nhiên mới là Z = U – V. Gọi hàm hội tụ xác suất của Z là PZ(z). Hàm PZ(z) chiếu từ hàm hội tụ xác suất có điều kiện P(u,v) vào (1,1). Nếu cặp mẫu của P được lấy ra ngẫu nhiên thì rõ ràng PZ(z) bằng 0 từ đó E(U) = E(V). Như vậy, dựa trên giả thiết (1) và nếu có 2|D0| > |D1| > |D2| > … > |Di| > |Di+1| > … (2.5.19) kết hợp với (2.5.17) và (2.5.18) ta có (2.5.16). Để chứng minh giá trị thực của p nhỏ hơn hoặc bằng hai nghiệm thực của phương trình (2.5.14) thì p phải thỏa bất đẳng thức sau:   1 22 ' 12 ' 12 ' 22 ' 2     mm mmmm CC XYDD p (2.5.20) Chú ý, vế phải của bất đẳng thức trên biểu diễn chung cho hai nghiệm của phương trình (2.5.15). Bất đẳng thức (2.5.20) là tương đương với bất đẳng thức sau   1 1 ' 12 ' 32 ' 12 ' 12     mm mmmmmm CC XYXYCC p (2.5.21) Bằng việc dùng công thức (2.5.9) và điều kiện |Cm| > |Cm=+1| thì bất phương trình (2.5.21) sẽ trở thành (p-1)(|Cm| - |Cm+1|)  (1-p) (|Y2m+1| - |X2m-1| + |Y2m+3| - |X2m+1|) (2.5.22) Áp dụng giả thiết (1) thì bất phương trình trên giản lược thành 0  (1-p) (|D2m| - |D2m+2|) (2.5.23) 2.5.4 Ước lượng độ chính xác của chiều dài thông điệp dấu theo SPA Cho một tập P các cặp mẫu, các kỹ thuật phân tích tin ẩn LSB đã đưa ra là thỏa mãn với điều giả định (1). Với p là độ dài thông điệp ẩn trong phương trình (2.5.14) 85 hoặc (2.5.15), gọi độ chính xác của chiều dài thông điệp ẩn đã ước lượng là pˆ thì nó phụ thuộc vào độ khác biệt m. m = |X2m+1| - |Y2m+1| (2.5.24) Công thức (2.5.24) dùng để tính toán ước lượng pˆ theo phương trình (2.5.14) hoặc (2.5.15) với một giá trị m sao cho |m | là nhỏ nhất có thể. Với ước lượng vững của chiều dài thông điệp ẩn có thể thu được từ tổ hợp các tập (trace multiset) trong giới hạn m mà |m | là nhỏ. Với 1  i  m  j  2b-1-1, và với 0 m  2b-1-1, máy trạng thái hữu hạn của Cm trong hình 3.2 có thể được tổ hợp và được khai triển từ  j im m C  bằng việc thay thế các tập con X2m-1, X2m, Y2m, Y2m+1 với lần lượt các tập  j im m X  12 ,  j im m X  2 , j im m Y  2 ,  j im m Y  12 . Ta nói rằng tập  j im m C  là không chệch nếu bốn tập hợp  j im m X  12 ,  j im m X  2 , j im m Y  2 ,  j im m Y  12 không chệch. Với m giá trị khác nhau ta có điều kiện                   j im m j im m YEXE 1212 (2.5.25) Đây là điều kiện “lỏng lẻo” hơn là giả thiết (1) đối với từng giá trị m riêng biệt. Mặt khác, với m cố định thì   j im m  là nhỏ hơn |m| một cách đáng kể. Điều này chính là hệ số quyết định của độ chính xác của việc phân tích tin ẩn. Điều kiện (2.5.25) chỉ ra rằng với một cặp mẫu (u,v)  P , |u-v| = 2t+1, i  t  j, giá trị chẵn của u và v có xác suất lớn hơn (hoặc nhỏ hơn) giá trị lẻ của u và v. Dựa trên cấu trúc của máy trạng thái hữu hạn, quan hệ thống kê trong (2.5.25), các tập  j im m C  và  1 1   j im m C là không chệch nếu phép giấu tin mật LSB được thực hiện thông qua việc giấu ngẫu nhiên ta có thể suy ra các phương trình bình phương mạnh vững hơn để ước lượng p như sau                   j im j im mmmmjiji iXYXYDD pCCp 1,02 24 ' 12 ' 12 ' !2 ' !2 ' 22 ' 21 2 (2.5.26) 86 Tương tự, dựa trên (2.5.25), tập C0,  j im m C  và  1 1   j im m C là không chệch với 0 = i  j  2b-1-2 nếu việc giấu tin LSB là ngẫu nhiên ta cũng có       022 2 2 4 0 ' 12 ' 12 0 ' 12 ' 12 ' 22 ' 010 2             j m mm j m mmjj XYXYDD pCCp (2.5.27) Giải cả hai phương trình bình phương mạnh với ẩn p, phụ thuộc vào giá trị chỉ số i ban đầu, thì nghiệm nhỏ hơn là p được ước lượng. Tiếp theo ta xác định một giới hạn về lỗi ước lượng của phương trình (2.5.26) và (2.5.27). Giới hạn lỗi này là m = |X2m+1| - |Y2m+1| với 0  m  2b-1-2 (2.5.28) 222 2      ji j im m ij DD e  với 1  i  j  2b-1-2. (2.5.29) Và 220 0 0 2      j j m m j DD e  với 0= i  j  2b-1-2. (2.5.30) Ta có thể giới hạn ước lượng lỗi như sau  p e e jipp ij ij    1 1 2 ),(ˆ với 0  i  j  2b-1-2 (2.5.31) Trong đó ),(ˆ jip là giá trị của p đã ước lượng thu được từ việc giải phương trình (2.5.26) khi i ≥ 1 và giải phương trình (2.5.27) khi i =0 với điều kiện là eij <1 và việc giấu tin LSB được thực hiện một cách ngẫu nhiên. Để giảm lỗi ước lượng, thì ta làm |eij| nhỏ đi. Ngược lại thì ta tăng |D2i| - |D2j+2| và làm giảm   j im m  . Nói chung   j im m  giảm khi sự khác biệt giữa i và j tăng. Tuy nhiên khi cho một số i, khoảng cách j-i lớn hơn, sự khác biệt |D2i| - |D2j+2| lớn hơn thì ước lượng vững của p tới hạn hơn. Bởi vì |D2i| là một hàm tăng đơn điệu trên i. Do đó, ta đặt i = 0 và chọn giá trị j lớn trong phương trình (2.5.27) để thu được ước lượng vững của p. 87 Độ chính xác ước lượng cũng bị ảnh hưởng bởi cách chọn các cặp mẫu trong tập P. Cho i và j, |D2i| - |D2j+2| (trong đẳng thức (2.5.20)) là lớn hơn nếu các cặp mẫu trong P được lấy ra từ những vị trí gần hơn của một sóng tín hiệu. Do vậy, với một ước lượng vững hơn của p, các thành phần trong tập P nên là các cặp hai mẫu liền kề nhau về mặt không gian. Trong phân tích ở trên ta thu được bất đẳng thức (2.5.31). Sau đây ta sẽ đi chứng minh bất đẳng thức này Trường hợp i ≥ 1: Với 1  i  j  2b-1-2, ta cố định vài giá trị i và j. Để đơn giản ta dùng kí hiệu pˆ thay cho kí hiệu pˆ (i,j). Ta có pˆ thỏa phương trình                   j im j im mmmmjiji iXYXYDD pCCp 1,02 2 ˆ 4 ˆ ' 12 ' 12 ' !2 ' !2 ' 22 ' 21 2 (2.5.32) Ta có          j im jimm j im mm XXXYXY ' 12 ' 12 ' 12 ' 12 ' 12 ' 12 Sử dụng (2.5.9) và (2.5.28) ta thu được            j im jimm j im mm XXXYpXY ' 12 ' 121212 ' 12 ' 12 1         12' 1212' 12 111     jjii j im m XpXXpXp  (2.5.33) Thay vào (2.5.32) ta được               0111ˆ1 2 ˆ 4 ˆ 12 ' 1212 ' 12 ' 22 ' 21 2             jjii j im m jiji XpXXpXpp DDpCCp  (2.5.34) 88 Viết lại (2.5.34) thành                  01ˆ1ˆ1 2 ˆ 1ˆ1ˆ1 2 ˆ 1ˆ1 4 ˆ 12 ' 12 ' 22 12 ' 12 ' 21 2                  jjj iii j im mji XppXpDp XppXpDpppCCp  (2.5.35) Ta đánh giá biểu thức sau với m≥1 tùy ý      12' 12'2 1ˆ1ˆ12 ˆ    mmm XppXpD p (2.5.36) Ta thay ' 12 ' 12 ' 2   mmmm YXCD và sắp xếp lại các số hạng trong (2.5.36) ta thu được           12' 12' 12' 12 12 ' 12 ' 2 1ˆ1 2 ˆ 2 ˆ 1ˆ1ˆ1 2 ˆ          mmmmm mmm XppXXYpCp XppXpDp (2.5.37) Cộng (2.5.9) và (2.5.11), sau đó chia cho 2 hệ số ta được               2 1 2 1 2 11 2 1 2 12121212 ' 12 ppCpYXpYXX mmmmmm (2.5.38) mmmm DCYX 21212   (2.5.39) Thay vào (2.5.37) giá trị của )1|)(||(||||| 1212 ' 12 ' 12 pYXYX mmmm   , giá trị ' 12 mX từ (2.5.38) và đẳng thức (2.5.39) ta thu được         mm mmm DpppCppp XppXpDp 2 12 ' 12 ' 2 ˆ1 2 1ˆ 22 1ˆ1ˆ1 2 ˆ           (2.5.40) Thay vào (2.5.40) m = i và m = j+1 sau đó thay vào (2.5.35), và thay đẳng thức sau    2222     jiij j im m DD e  ta thu được phương trình: 89              01 ˆ11ˆ 2 1 222 2 222 2 1     jiij ijjiji DDep ppeDDpppCC (2.5.41) Ta sẽ giải phương trình (2.5.41) như là một hàm bậc hai với biến là  pp ˆ . Đặt các hệ số 1(2 1  ji CCa ;    ijji eDDpb   11 222 ; |)||)(|()1( 222 2  jiij DDepc Phương trình có nghiệm khi b2+4ac ≥ 0. Gọi x0 là nghiệm nhỏ nhất của phương trình. Thì ta có bất đẳng thức sau b c x   2 0 . Thật vậy, ta có a acbbx 2 4|| 2 0      b c acbba acbb      2 42 4 2 22 Hay nói cách khác    ]11[ |)||)(|()1(2 222 222 2 0 ijji jiij eDDp DDep x      Giả sử rằng eij 0 thì  ij ij e ep x    1 )()1(2 0 , ta thay vào (2.5.41) được điều phải chứng minh. Người ta tiến hành thực nghiệm và ước lượng chiều dài thông điệp chính xác có thể thu được khi i=0, j =30 và ngưỡng dự đoán là 0.018 và trong trường hợp đó sai số trung bình là 0.023. Người ta cũng đưa ra một bảng kết quả như sau [27]. Tỷ lệ giấu tin 0% 3% 5% 10% 15% 20% Tỷ lệ sai số 0.1379 0.1103 0 0 0 0 90 Hầu hết các phương pháp tấn công đều tránh các thao tác giấu tin LSB ở những vị trí mà các cặp mẫu liền kề nhau có giá trị sai khác ít. Chẳng hạn, không có việc giấu tin ở các cặp mẫu liền lề và giá trị của chúng sai khác nhau nhỏ hơn 3 [28]. Mặt khác ta có thể coi C0 là chệch, vi phạm sự phát hiện chính xác. Chẳng hạn một tấn công chống lại SPA đó là, các bít thông điệp chỉ được giấu vào các vị trí mẫu thích hợp mà ở đó tất cả các cặp mẫu liền kề là Ct, t ≥ với  là một ngưỡng cố định trước. Mặt khác bất kỳ cặp mẫu (u, v), |u-v| ≥ 2 -1 sẽ thỏa |u’-v’| ≥ 2 -1, cặp (u’, v’) biểu diễn các giá trị của hai mẫu sau khi giấu tin LSB trong đó. Rõ ràng, việc giấu tin LSB này có điều kiện trên Ct với t ≥  và cả việc nhúng tin lẫn giải tin có thể dẫn đến cùng một Ct và để quyết định mẫu nào là có giấu tin. 91 2.6 KỸ THUẬT PHÂN TÍCH ĐỘ LỆCH CHUẨN Input: Tập ảnh bất kỳ (gồm cả ảnh đã giấu tin và ảnh chưa giấu tin). Output: H0 : là tập chứa các ảnh không giấu tin. H1 : là tập chứa các ảnh có giấu tin. Sao cho sai số bài toán là nhỏ nhất Thuật toán Ta coi dữ liệu ảnh là các mẫu. Có hai trường hợp xẩy ra: a/. Mẫu được lấy từ tập hợp tuỳ ý; b/. Mẫu được lấy từ một họ có phân bố xác suất đã biết. Ta giả thiết là các mẫu được lấy từ một họ có phân bố chuẩn. Giả sử X là đại lượng ngẫu nhiên, độc lập có phân bố chuẩn N(a, 2), với kỳ vọng a và phương sai 2, có tập trị số x1, x2, ..., xn, có hàm mật độ xác suất của X là:   2 2 ( ) 21p x , x 2 x a e        R Theo định nghĩa, hàm phân bố của X được xác định bằng:     2 2 ( ) 21F x P X x , 2 u ax e du x R          Ta có bổ đề sau: Bổ đề 1: Cho X1, X2 , ... , Xn là n đại lượng ngẫu nhiên, độc lập cùng phân bố chuẩn N(a,2). Khi đó đại lượng ngẫu nhiên X1+X2+...+Xn sẽ có phân bố chuẩn N(na, n2). Chứng minh: Theo tính chất của kỳ vọng toán học, kỳ vọng của một tổng bằng tổng các kỳ vọng của từng thành phần, do đó kỳ vọng E(X1+X2 +...+Xn)= E(X1) + ...+ E(Xn) = na. Do tính độc lập của chúng, phương sai là: D(X1+X2 +...+Xn)= D(X1) + ... + D(Xn) = n2. 92 Định lý: Cho X là đại lượng ngẫu nhiên có phân bố chuẩn N(a,2). Khi đó đại lượng ngẫu nhiên Y=(X-a)/ có phân bố chuẩn N(0,1). ([7],[8]). Thực tế a và 2 chưa biết, nên ta phải ước lượng a, 2. Bằng phương pháp hợp lý cực đại (maximum likelihood) [6, 7, 8], ta có các ước lượng hợp lý cực đại: 1 1 n i i a X x n     (2.6.1) 2 2 2 1 1 S ( ) n i i x x n      (2.6.2) Ta ký hiệu: Xmax = max {x1, x2, …, xn} và Xmin= min {x1, x2,…, xn } Khi đó các đại lượng ngẫu nhiên: max 1V S X X  , min2V X X S   , sẽ có phân bố chuẩn Nn(0, 1), không phụ thuộc vào a và 2, mà chỉ phụ thuộc vào n, [6, 7]. Ta đặt V=V1+V2, theo bổ đề 1, do đại lượng ngẫu nhiên V1, V2 có phân bố chuẩn Nn(0,1), nên V có phân bố chuẩn Nn(0, 2). Theo định lý giới hạn trung tâm, (3) 2 V có phân bố chuẩn Nn(0,1), đã được lập thành bảng XII trong [7, trang 247], với n = 1,2,3,... và độ tin cậy  = 0.1, 0.05,... Trong (3), đại lượng ngẫu nhiên V có phân bố chuẩn Nn(0,1), tức là có xác xuất oP {V ³ x } ( ) o n x p t dt    Trong đó pn(t) là hàm mật độ xác suất chuẩn Nn(0,1). Nếu cho trước n và giá trị xác suất sai lầm loại một  = 0, ta có thể xác định được x0 qua phương trình sau:      0 0 01)(1)( x x nn dttpdttp  Vì V=V1+V2, nên 2 V  x0  V1+V2  2 x0. 93 Do đó sau khi xác định được x0, ta có thể tìm được ngưỡng t0 = 2 x0. Theo phương pháp thống kê, ta có thể phát biểu lại bài toán 1 như sau: Hãy kiểm định giả thuyết H0: ”ảnh không giấu tin” (tức V  t0) và H1: ”ảnh có giấu tin” (tức V< t0) với xác suất sai lầm  = 0. Các yếu tố trên chính là vấn đề cơ bản để xây dựng bài toán phân loại sau: Biểu diễn dữ liệu của một ảnh C bất kỳ dưới dạng vector C26x10 với phần tử cịj là tần số của pixel i*10+j (0 ≤ i ≤ 25, 0 ≤ j ≤ 9). Tính X10 với các giá trị 25 j 0 x ij i c   trong đó (0 ≤ i ≤ 25, 0 ≤ j ≤ 9). Tính Xmax = max{x0 , x2 ,…, x9}, Xmin = min{x0 , x2 ,…, x9}. Ký hiệu    9 010 1 j jxX và S =    9 0 2)( 10 1 j j Xx Từ đó ta xác định được: V= V1 + V2 = S XX minmax  Với n=10 và độ tin cậy =0.1, ta nhận được x0 = 2.149. Do đó ngưỡng t0 = 2 x0 = 3.0349  3. Kết luận: Nếu V3, H0 đúng nghĩa là C là ảnh không giấu tin với độ tin cậy 90%. Ngược lại C là ảnh có giấu tin. 94 2.7 KỸ THUẬT THỐNG KÊ  – BÌNH PHƯƠNG MỘT BẬC TỰ DO Mệnh đề: Gọi m là số lần xuất hiện một biến cố A trong dãy n phép thử Becnouli với xác suất xuất hiện biến cố A là P(A) = p >0, q =1 - p. Khi đó, đại lượng ngẫu nhiên npq npmY  sẽ có xấp xỉ phân bố chuẩn N(0,1). Chứng minh: Ta biết nếu Y có phân bố chuẩn N(0,1), thì hàm đặc trưng tương ứng là f(t)= 2 2t e  , - < t < , và sự tương ứng đó là 1-1. Như vậy, ta chỉ cần chỉ ra hàm đặc trưng của đại lượng ngẫu nhiên npq npmY  là f(t)  2 2t e  Theo định nghĩa, đại lượng ngẫu nhiên m sẽ có hàm đặc trưng là: (t) = E(eitm) =    knkitk n k k n qpeC 0 nitknkit n k k n qpeqpeC )()( 0    , với i2 =1. Hàm đặc trưng của đại lượng ngẫu nhiên npq npmY  là: f(t) = E( )( npq npm it e  ) = npq itnp e  E( npq itm e )=exp{ npq itnp  )(q+p npa it e )n (2.7.1) Mặt khác eiz = 1+(iz) / 1 ! + ...+ (iz)k / k ! + o(zk) (2.7.2) Thay (2.7.2) vào (2.7.1), thì khi n  ta có: f(t) = n n to n t        )( 2 1 22  exp{- 2 2t } Đó là điều cần chứng minh mệnh đề. Bổ đề 2: Cho dãy số nhị phân ngẫu nhiên, độc lập S= {so, s1, ..., sn-1 } với n1. Ký hiệu n0, n1 lần lượt là tần số xuất hiện chữ số 0, 1 trong dãy S, (n0 + n1 = n). Đặt X2 = n nn 210 )(  (2.7.3) Khi đó, nếu S là ngẫu nhiên, độc lập thì X2 có phân bố χ - bình phương một bậc tự do. 95 Chứng minh: Ta đã biết, nếu đại lượng ngẫu nhiên Y có phân bố chuẩn N(0,1), thì đại lượng ngẫu nhiên Y2 sẽ có phân bố χ - bình phương một bậc tự do ([7]). Do đó để chứng minh (2.7.3), ta chỉ cần chứng minh rằng n nnX 10  có phân bố chuẩn N(0,1). Với 0 ≤ k ≤ n-1, ta đặt )0(χ k =1 nếu chữ số 0 xuất hiện tại vị trí k của dãy S; ta đặt )0(χ k =0 nếu ngược lại. Rõ ràng n0 = )0( 1 0    n k k . Ta có: Kỳ vọng của no là E(n0) = E(   1 0 )0( n k k ) = npE n k k    ))0(( 1 0  Phương sai của n0 là D(n0) = D         1 0 )0( n k k =     1n 0k k ))0((D = ]))0(E())0((E[ 1n 0k 2 k 2 k    =    1n 0k 2 )pp(     1n 0k )p1(p = npq Theo mệnh đề trên, npq npn 0 là đại lượng ngẫu nhiên có phân bố xấp xỉ chuẩn N(0,1) (2.7.4) Trường hợp đặc biệt khi S là dãy nhị phân ngẫu nhiên, độc lập cùng phân bố, nên p=q=1/2. Thay giá trị p, q vào biểu thức (2.7.4), ta có n nn n nn npq npn      000 2)2/(2 = n nn n nnn 10100 )(2  Như vậy n nn 10  có phân bố chuẩn N(0,1). Do đó n nn n nn 210 2 10 )(        có phân bố χ - bình phương một bậc tự do. 96 Áp dụng bổ đề 2: Áp dụng bổ đề 2 vào việc phát hiện ảnh có giấu tin, khi sử dụng kỹ thuật giấu tin trên LSB (cho trường hợp giấu tuần tự, giấu ngẫu nhiên). Sau khi tính tần số các pixel của một ảnh cần kiểm tra. Kết quả thống kê được ma trận C26x10 (bỏ qua hàng cuối cùng của C, vì hàng này có chứa các giá trị 0), ta được ma trận C25x10. Thực hiện tiếp một số bước sau: 1/. Tìm giá trị lớn nhất của C25x10, ký hiệu là Xmax = max{cij, i=0,1,2,...,24, j=0,1,...9}. Giả sử Xmax = 00 jic (tìm thấy Xmax tại vị trí (io, jo)). 2/. Tính ]0[n 0i =   4 0j j2,i0 c , ]1[n 0i =   4 0j 1j2,i0 c , ]1[n]0[nn 000 iii  . Theo bổ đề 2, 0 0 2])1[]0[( i ioi n nn  có phân bố  - bình phương một bậc tự do. 3/. Nếu ảnh có các tần số pixel )( ])1[]0[( 2 1 2 0 0   i ioi n nn , thì ta kết luận ảnh không chứa tin mật (cover ). Nếu )( ])1[]0[( 2 1 2 0 0   i ioi n nn , ta kết luận ảnh có chứa tin mật, với xác suất sai lầm là . 97 Chương 3. THỬ NGHIỆM Thông qua việc nghiên cứu một số thuật toán giấu tin và phát hiện tin giấu trong môi trường ảnh, trong chương này, luận văn trình bày mô hình thử nghiệm và kết quả thử nghiệm kỹ thuật phát hiện tin giấu PoV3. 3.1 MÔI TRƯỜNG CÀI ĐẶT - Hệ thống thử nghiệm được xây dựng trên ngôn ngữ lập trình Matlab 7.0 - Thực hiện trên Windows XP 3.2 MÔ HÌNH HỆ THỐNG Hệ thống gồm 2 phân hệ sau: - Phân hệ giấu tin: Thực hiện giấu 1 thông điệp vào các bit LSB của ảnh. Input: - Ảnh F - Thông điệp m Output: - Ảnh F’ chứa nội dung thông điệp m - Phân hệ phát hiện ảnh có giấu tin: kiểm tra, phát hiện khả năng có tồn tại tin giấu trong ảnh. Input: - Ảnh F Output: - Kết luận ảnh F có khả năng giấu tin hay không? - Vẽ đồ thị xác suất giấu tin 98 Hình 3.1. Mô hình hệ thống thử nghiệm 99 3.3 TẬP DỮ LIỆU ẢNH Hệ thống được tiến hành thử nghiệm trên 50 ảnh cấp xám, các ảnh này được chuyển dạng từ các ảnh sau: 100 101 3.4 KẾT QUẢ THỬ NGHIỆM KỸ THUẬT PoV3 Tiến hành thử nghiệm kỹ thuật PoV3 với tập dữ liệu ảnh. Các ảnh được giấu các lượng tin giấu khác nhau: 0%, 10%, 20%, ...,100% (của tổng số bit LSB trong ảnh). Các bit tin giấu được sinh ngẫu nhiên và giấu ngẫu nhiên vào miền LSB của ảnh. Các ảnh sau khi giấu tin được sử dụng để phát hiện ảnh giấu tin bằng phương pháp trên, chúng tôi nhận được kết quả như trong sau: Hình 3.2 Đồ thị xác suất giấu tin trước khi giấu tin 102 Hình 3.3 Đồ thị xác suất giấu tin sau khi giấu 10% Hình 3.4 Đồ thị xác suất giấu tin sau khi giấu 20% 103 Hình 3.5 Đồ thị xác suất giấu tin sau khi giấu 30% Hình 3.6 Đồ thị xác suất giấu tin sau khi giấu 40% 104 Hình 3.7 Đồ thị xác suất giấu tin sau khi giấu 50% Hình 3.8 Đồ thị xác suất giấu tin sau khi giấu 60% 105 Hình 3.9 Đồ thị xác suất giấu tin sau khi giấu 70% Hình 3.10 Đồ thị xác suất giấu tin sau khi giấu 80% 106 Hình 3.11 Đồ thị xác suất giấu tin sau khi giấu 90% Hình 3.12 Đồ thị xác suất giấu tin sau khi giấu 100% 107 KẾT LUẬN Thông qua việc nghiên cứu một số kỹ thuật giấu tin mật trên ảnh, luận văn phân tích đánh giá ưu nhược điểm của các kỹ thuật từ đó làm cơ sở cho việc thiết kế các hệ thống giấu tin mật trên ảnh phục vụ tối đa nhu cầu người sử dụng. Đồng thời, luận văn đã nghiên cứu, tìm hiểu và đánh giá một số kỹ thuật thủy vân trên ảnh, tập trung chủ yếu vào các kỹ thuật thủy vân bền vững. Kỹ thuật chọn và thay đổi hệ số trong miền tần số giữa của phép biến đổi DCT đã trình bày vừa giữ nguyên được tính bền vững của thủy vân, vừa giảm tối đa việc phải thay đổi cặp hệ số chọn dẫn đến sự khác biệt giữa ảnh sau khi nhúng thủy vân và ảnh gốc là nhỏ nhất có thể, đồng thời cũng làm độ an toàn cho thủy vân. Từ đó làm cơ sở để xây dựng thủy vân ẩn bền vững đáp ứng được các yếu cầu là bảo đảm chất lượng ảnh sau khi nhúng thủy vân và tính bền vững của thủy vân trước những tấn công lên ảnh chứa. Trọng tâm luận văn nghiên cứu khả năng có thể để phát hiện ảnh có giấu tin, đặc biệt là giấu tin mật. Cách tiếp cận chủ yếu của các kỹ thuật đã trình bày là dựa trên lý thuyết xác suất thống kê, xác định xác suất của việc giấu tin trong ảnh. Tuy nhiên bài toán khó hơn bài toán phát hiện sự tồn tại của thông điệp là bài toán trích chọn ra thông điệp bí mật thì chưa đề cập đến. Những kết quả chính đạt được của luận văn: 1. Nghiên cứu tài liệu, hệ thống lại các vấn đề sau - Một số kỹ thuật giấu tin trong ảnh - Một số khả năng phát hiện ảnh có giấu tin 2. Thử nghiệm kỹ thuật phát hiện ảnh có giấu tin PoV3 Hướng phát triển Luận văn trình bầy bài toán phát hiện tin giấu trong ảnh và một số kỹ thuật phát hiện tin giấu trong ảnh, tuy nhiên, bài toán khó hơn là trích chọn ra thông điệp giấu trong ảnh thì chưa đề cập tới. Hi vọng trong tương lai tôi có cơ hội tiếp tục phát triển đề tài theo hướng này. 108 TÀI LIỆU THAM KHẢO Tiếng Việt [1] Lương Mạnh Bá, Nguyễn Thanh Thủy (1999), Nhập môn xử lý ảnh số, Nhà xuất bản Khoa học và kỹ thuật. [2] Nguyễn Xuân Huy, Trần Quốc Dũng (2003), Giáo trình giấu tin và thủy vân ảnh, Hà Nội. [3] Nguyễn Xuân Huy, Bùi Thế Hồng, Trần Quốc Dũng (2004), “Kỹ thuật thủy vân số trong ứng dụng phát hiện xuyên tạc ảnh tĩnh”, Kỷ yếu hội nghị Quốc gia một số vấn đề chọn lọc của công nghệ thông tin lần thứ 7, Đà Nẵng. Nhà xuất bản Khoa học kỹ thuật. [4] Trịnh Nhật Tiến (2008), Giáo trình an toàn dữ liệu, T.110-132, Hà Nội. [5] Lý Hoàng Tú, Trần Đình Điệp (2003), “Lý thuyết xác suất thống kê”, Nhà xuất bản Giáo dục. [6] Phạm Thị Ngọc Yến, Ngô Hữu Tình, Lê Tấn Hùng, Nguyễn Thị Lan Hương (2007), Cơ sở MATLAB và ứng dụng, Nhà xuất bản Khoa học kỹ thuật. [7] Tống Đình Quỳ, Giáo trình xác suất thống kê, Nhà xuất bản giáo dục, 2002. Tiếng Anh [8] David Kahn, “The History of Steganography” (1996), Proc. Of First Int. Workshop on Information Hiding, Cambridge, UK, May 30-June 1996, Lecture notes in Computer Science, Vol.1174, Ross Anderson(Ed), p.1-7. [9] Fabien A. P. Petitcolas, et al (1999). “Information Hiding – A survey”, Proceedings of the IEEE, Vol. 87, No.7, p. 1062-1078. [10] Fabien A. P. Petitcolas (1999), “Introduction to Information Hiding”, in Information techniques for Steganography and Digital Watermarking, S.C. Katzenbeisser et al., Eds. Northwood, MA: Artec House, p. 1-11. [11] Fabien A. P. Petitcolas, Ross J.Anderson, Markus G.Kuhn, “Attacks on Copyright Marking Systems”, Second workshop on information hiding, vol. 1525 of Lecture notes in Computer Science, Portland, Oregon, USA 14-17, p. 218-238. 109 [12] Swason M. D., Kobayashi M., and Tewfik A. H (1998), “Mutimedia Data- embedding and Watermarking Technologies”, Proceedings of IEEE, Vol. 86, No. 6, 1064-1087 [13] Yu Yuan Chen, Hsiang Kuan Pan and Yu Chee Tseng (2000), “A secure Data Hiding Scheme for Two-Color Images”, IEEE Symp. On Computer and Communication. [14] M. Y. Wu, J. H. Lee (1998), “A novel data embedding method for two-color fascimile images”. In Proceedings of international symposium on multimedia information processing. Chung-Li, Taiwan, R.O.C. [15] Jonathan Watkins (2001), “Steganography - Messages Hidden in Bits”, Multimedia Systems Coursework, Department of Electronics and Computer Science, University of Southampton, SO17 1BJ, UK. [16] Matteo Fortini (2002), “Steganography and Digital Watermarking: a global view”. [17] Jessica Fridrich, Miroslav Goljan (2004), “On estimation of secret message length in LSB steganography in spatial domain”, Department of Electronics and Computer Engineering, SUNY Binghamton, Binghamton, NY 13902- 6000. [18] Andrew D. Ker (2004), “Quantitative Evaluation of Pair and RS Steganalysis”, Oxford University Computing Laboratary, Parks Road, Oxford OX1 3QD, England. [19] aJessica Fridrich, aMiroslav Goljan, bDavid Soukal (2005), “Searching for the Stego-Key”, aDepartment of Electronics and Computer Engineering, bDepartment of Computer Science SUNY Binghamton, Binghamton, NY 13902-6000, USA. [20] Jeffrey A. Bloom and Rafael Alonso (2003), “SmartSearch Steganography”, In Security and Watermarking of Multimedia Contents V, Edward J. Delp III, Ping Wah Wong, Editors, Proceedings of SPIE Vol. 5020. [21] Jessica Fridrich, Miroslav Goljan (2003), “Practical Steganalysis of Digital Images – State oí Art”, Department of Electronics and Computer Engineering, SUNY Binghamton, Binghamton, NY 13902-6000. 110 [22] R. Chandramouli (2002), “A Mathematical Approach to Steganalysis”, To appear in Proc. SPIE Security and Watermarking of Multimedia Contents IV, California. [23] Christy A. Stenley (2005), “Pairs of Values and the Chi-squared Attack”, Department of Mathematic, Iowa State University. [24] Shen Ge, Yang Gao, Ruili Wang (2007), “Least Signification Bit Steganography Detection with Machine Learning Techniques”, 2007 ACM SIGKDD Workshop on Domain Driven Datamining, San Jose, California, USA. [25] Abbas Alfaraj (2006), “On the Limits of Steganography”, MS.c. Information Security, UCL. [26] Westfeld and Pfitzmann (1999), “Attacks on steganographic systems”, In information Hiding Third International Workshop IH’99 Proceedings, Lecture Notes in Computer Science vol. 1768, pages 61-76. [27] J. Fridrich, M. Goljan, and R. Du (2001), “Detecting LSB Steganography in Color and Gray-Scale Images”, Magazine of IEEE Multimedia, Special Issue on Security, pp. 22–28. [28] Sorina Dumitrescu, Xiaolin Wu, and Zhe Wang (2003), “Detection of LSB Steganography via Sample Pair Analysis”, IEEE Transactions On Signal Processing, Vol. 51, No. 7. [29] Xiangyang Luo, Fenlin Liu (2007), “A LSB Steganography Approach Against Pixels Sample Pairs Steganalysis”, International Journal of Innovative Computing, Information and Control, Volume 3, Number 3, pp. 575—588. [30] Romana Machado, 1996 [31] Christy A. Stanley, Pairs of Values and the Chi-squared Attack, May 1, 2005 [32] A. Westfeld and A. Pfitzmann, Attacks on Steganographic Systems, Lecture Notes in Computer Science, vol.1768, Springer-Verlag, Berlin, 2000 [33] A. Westfeld, Detecting Low Embedding rates. In: Petitcolas et al. (eds.): Preproceedings 5th Information Hiding Workshop, Noordwijkerhout, Netherlands, Oct. 7−9, 2002.