Một thuận toán giấu tin và áp dụng giấu tin mật trong ảnh

T¹p chÝ Khoa häc & C«ng nghÖ - Sè 4(44) Tập 2/N¨m 2007<br /> <br /> MỘT THUẬT TOÁN GIẤU TIN<br /> VÀ ÁP DỤNG GIẤU TIN MẬT TRONG ẢNH<br /> Nguyễn Văn Tảo (Khoa Công nghệ thông tin - ĐH Thái Nguyên)<br /> <br /> 1. Tổng quan<br /> Trong môi trường phân phối điện tử rất phát triển như hiện nay, việc bảo vệ cho các<br /> thông tin quan trọng trong quá trình trao đổi trở nên cấp thiết. Theo phương pháp truyền thống,<br /> thông tin mật trước khi truyền đi sẽ được mã hoá, như vậy trong quá trình truyền, những người<br /> ngoài cuộc quan sát bản tin đã mã hoá sẽ biết được tầm quan trọng của bản tin được trao đổi,<br /> điều đó làm tăng sự tò mò muốn khám phá để tìm ra được nội dung thực của bản tin.<br /> Gần đây, một phương pháp mới được nhiều nhà khoa học quan tâm nghiên cứu đó là<br /> nhúng các thông tin mật vào các đối tượng dữ liệu khác (phương tiện chứa) như ảnh, video,<br /> audio, ... rồi sử dụng chính các phương tiện chứa đã bao gồm thông tin mật để trao đổi.<br /> Bài báo này đề xuất một thuật toán giấu tin mật cho phép giấu một lượng thông tin khá<br /> lớn mà phải thay đổi rất ít giá trị dữ liệu gốc. Từ thuật toán này, chúng tôi xây dựng lược đồ<br /> giấu tin trong ảnh áp dụng với một số dạng ảnh ứng dụng trong trao đổi thông tin mật.<br /> 2. Một số lược đồ giấu tin mật trong ảnh nhị phân<br /> 2.1. Giấu tin theo khối bit đơn giản (CB)<br /> Ý tưởng cơ bản của kỹ thuật này là chia một ảnh gốc thành các khối nhỏ và trong mỗi<br /> khối nhỏ sẽ giấu một bit thông tin. Quá trình giấu tin:<br /> Với một ảnh gốc kích thước M×N, chia phần thông tin ảnh thành các khối nhỏ có kích<br /> thước m×n, số các khối nhỏ sẽ là (M×N)/(m×n) khối. Vì ảnh là đen trắng nên mỗi khối là một<br /> ma trận hai chiều m dòng, n cột các phần tử có giá trị 0 hoặc 1.<br /> Chọn các khối chưa giấu tin để thực hiện giấu tin, các khối được chọn cho đến khi giấu<br /> hết các thông tin cần giấu hoặc khi đã chọn hết các khối.<br /> Với mỗi khối ảnh F kích thước m×n và bit đang cần giấu b, tiến hành biến đổi F thành F’<br /> để giấu bit b sao cho:<br /> SUM(F’) mod 2 = b<br /> <br /> (1)<br /> <br /> Như vậy, mỗi lần giấu một bit, có thể xảy ra hai trường hợp: SUM(F) mod 2 = b, khi đó<br /> ta giữ nguyên khối ảnh. Ngược lại chọn ngẫu nhiên một bit trong khối F và tiến hành đảo giá trị<br /> của bit này để được khối ảnh mới F’.<br /> Quá trình tách tin: Khi nhận được ảnh đã giấu tin, việc giải mã tin sẽ thực hiện theo các bước:<br /> Chia ảnh thành các khối có kích thước giống kích thước khối đã sử dụng khi thực hiện<br /> giấu, đây chính là khoá để giải mã.<br /> Với mỗi khối ảnh đã giấu tin F’ được chọn theo thứ tự như quá trình giấu tin, thực hiện<br /> tách lấy bit thông tin đã giấu theo công thức: b = SUM(F’) mod 2.<br /> Như vậy, sau khi xét hết các khối đã giấu, ta thu được một chuỗi bit, chuỗi này là thông<br /> tin nhị phân đã giấu cần phải lấy ra.<br /> 25<br /> <br /> T¹p chÝ Khoa häc & C«ng nghÖ - Sè 4(44) Tập 2/N¨m 2007<br /> <br /> Lược đồ giấu tin CB có thể giấu được 1 bit thông tin vào một khối kích thước m×n bit<br /> mà chỉ thay đổi tối đa 1 bit trong đó.<br /> 2.2. Lược đồ giấu tin của M.Y.Wu và J.H.Lee (WL)<br /> Kỹ thuật giấu tin theo khối bit CB thể hiện độ an toàn không cao với việc sử dụng duy<br /> nhất kích thước khối là khoá cho quá trình giấu tin, ảnh chứa thông tin giấu cũng dễ bị phát hiện<br /> do kỹ thuật có thể sẽ đảo bit trong các khối ảnh toàn màu đen hoặc toàn màu trắng dẫn tới sự bất<br /> thường ở vị trí bit đảo so với các điểm lân cận trong khối.<br /> Kỹ thuật giấu thông tin trong ảnh đen trắng do M.Y.Wu và J.H.Lee vẫn trên tư tưởng<br /> giấu một bit thông tin vào một khối ảnh gốc nhưng đã khắc phục được phần nào những tồn tại<br /> nêu trên bằng cách đưa thêm khoá K cho việc giấu tin và đưa thêm các điều kiện để đảo bit<br /> trong mỗi khối, theo điều kiện đó các khối ảnh gốc toàn màu đen hoặc toàn màu trắng sẽ không<br /> được sử dụng để giấu tin.<br /> Quá trình biến đổi khối ảnh F thành F’ để giấu 1 bit b được thực hiện sao cho:<br /> SUM(K^F’) mod 2 = b<br /> <br /> (2)<br /> <br /> Công thức (2) cũng được sử dụng cho quá trình tách lấy tin đã giấu.<br /> Lược đồ giấu tin WL có thể giấu được 1 bit thông tin vào một khối m×n bit và chỉ phải<br /> thay đổi tối đa 1 bit trong đó [2].<br /> 2.3. Lược đồ giấu tin của Chen-Pan-Tseng<br /> Trên cơ sở của thuật toán của Wu-Lee như đã trình bày trong mục 2.2, các tác giả Yu<br /> Yuan Chen, Hsiang Kuang Pan và Yu Chee Tseng đã phát triển một kỹ thuật giấu tin mới. Kỹ<br /> thuật này sử dụng một ma trận khoá K và một ma trận trọng số W trong quá trình giấu và tách<br /> thông tin.<br /> Quá trình biến đổi khối ảnh F thành F’ kích thước m×n để giấu r bit thông tin b1b2..br<br /> được thực hiện sao cho:<br /> <br /> SUM((F’⊕ K) ⊗ W) ≡ b1b2...br (mod 2r).<br /> <br /> (3)<br /> <br /> Công thức (3) được sử dụng để tách chuỗi bit đã giấu b1b2...br từ khối ảnh F’.<br /> Lược đồ CPT cho phép giấu r bit thông tin vào một khối ảnh nhị phân kích thước m×n<br /> (với 2r < m×n) bằng cách chỉ thay đổi nhiều nhất 2 bit trong khối ảnh gốc [3].<br /> Năm 2005, nhóm tác giả thuộc Viện Công nghệ thông tin đã nghiên cứu và đưa ra một<br /> cải tiến làm rút ngắn thời gian thực hiện quá trình giấu tin với kỹ thuật này [1].<br /> 3. Đề xuất thuật toán giấu tin mật<br /> 3.1. Ý tưởng<br /> Các thuật toán giấu tin mật ở trên có một điểm chung là tùy theo bit thông tin đang<br /> cần giấu và giá trị các điểm trong khối ảnh gốc đang xét, tiến hành biến đổi khối ảnh gốc<br /> để đạt đến một bất biến nào đó làm tiêu chuNn cho quá trình lọc tìm lại thông tin giấu.<br /> Trong phần này, chúng tôi đề xuất kỹ thuật giấu tin dựa trên ý tưởng nhúng dãy k bit<br /> b=(b1, b2 , ..., bk) vào dãy n bit x=(x1, x2, ..., xn ), với n = 2k -1 và chỉ thay đổi tối đa 1 bit<br /> trong dãy x.<br /> 26<br /> <br /> T¹p chÝ Khoa häc & C«ng nghÖ - Sè 4(44) Tập 2/N¨m 2007<br /> <br /> Ví dụ: Cần nhúng dãy 2 bit b=(b1, b2) vào dãy 3 bit x=(x1, x2, x3), tuỳ quan hệ giữa các bit<br /> của b và x, thực hiện:<br /> Nếu<br /> Nếu<br /> Nếu<br /> Nếu<br /> <br /> b1 = x1 ⊕ x3, b2 = x2 ⊕ x3 thì giữ nguyên x<br /> b1 ≠ x1 ⊕ x3, b2 = x2 ⊕ x3 thì đảo bit x1<br /> b1 = x1 ⊕ x3, b2 ≠ x2 ⊕ x3 thì đảo bit x2<br /> b1 ≠ x1 ⊕ x3, b2 ≠ x2 ⊕ x3 thì đảo bit x3<br /> <br /> Như vậy, sau khi biến đổi x thành x’=( x1' , x2' , x3' ) theo quá trình trên ta luôn có:<br /> b1 = x1' ⊕ x3' và b2 = x2' ⊕ x3' đây chính là các công thức sử dụng cho quá trình tách lấy<br /> thông tin đã giấu.<br /> 3.2. Giấu chuỗi k bit b vào chuỗi n bit x (thuật toán giấu tin HT)<br /> <br /> Định nghĩa: Phép cộng không nhớ các số nhị phân, ký hiệu ⊕ được định nghĩa như sau:<br /> 1 ⊕ 1 = 0; 1 ⊕ 0 = 1; 0 ⊕ 1 = 1; 0 ⊕ 0 = 0<br /> Từ định nghĩa ta có tính chất: b ⊕ b = 0 với mọi số nhị phân b.<br /> Quá trình giấu tin<br /> Tiến hành nhúng chuỗi k bit b=(b1, b2, ..., bk) vào chuỗi n bit x=(x1, x2, ..., xn) để được<br /> chuỗi x’ theo các bước:<br /> n<br /> <br />  Tính f ( x) = ⊕ xi .db(i) , trong đó db(i) là biểu diễn nhị phân của i.<br /> i=1<br /> <br />  Tính: s = b ⊕ f(x)<br />  Nếu s = 0 thì lấy x’=x, ngược lại đảo bit ở vị trí s trong x để được x’ theo công thức:<br /> x’=(x1, x2, ..., 1-xs,..., xn)<br /> Quá trình tách tin<br /> Quá trình lọc tìm lại b từ chuỗi x’ được thực hiện theo công thức: b=f(x’)<br /> Tính đúng đắn của thuật toán<br /> Quá trình giấu và tách tin như trên đảm bảo chỉ thay đổi tối đa 1 bit trong chuỗi n bit gốc<br /> x và luôn tách được đúng dãy k bit b đã giấu. Thực vậy:<br /> Với s ≠ 0, từ công thức: s = b ⊕ f(x)
s ⊕ f(x) = b ⊕ f(x) ⊕ f(x)
b = s ⊕ f(x)<br />
b = s ⊕ (db(1).x1⊕ db(2).x2 ⊕.... ⊕db(s).xs ⊕... ⊕db(n).xn)<br /> Do s = db(s) và db(s) ⊕ db(s) = 0 nên được:<br /> b = db(1).x1⊕ db(2).x2 ⊕.... ⊕db(s).(1-xs)⊕... ⊕db(n).xn = f(x’)<br /> Với s = 0, do x’ = x nên có b = f(x) = f(x’)<br /> Như vậy, trong mọi trường hợp ta đều có việc nhúng chuỗi bit thông tin mật b vào chuỗi<br /> bit gốc x để được x’ luôn đảm một bất biến b=f(x’). Đây chính là yếu tố đảm bảo cho việc tìm lại<br /> được chính xác thông tin đã giấu.<br /> <br /> Ví dụ về quá trình giấu và tách tin:<br /> Xét với k=3, n=7, chuỗi bit gốc x=1001101, chuỗi bit cần giấu b=100<br /> 27<br /> <br /> T¹p chÝ Khoa häc & C«ng nghÖ - Sè 4(44) Tập 2/N¨m 2007<br /> <br /> * Quá trình giấu chuỗi b vào x để được x’ thực hiện như sau:<br /> n<br /> <br /> Tính f ( x) = ⊕ xi .db(i) =<br /> i=1<br /> <br /> =1.db(1) ⊕ 0.db(2) ⊕ 1.db(3) ⊕ 1.db(4) ⊕ 1.db(5) ⊕ 0.db(6) ⊕ 1.db(7)<br /> = 1 ⊕ 0 ⊕ 0 ⊕ 100 ⊕ 101 ⊕ 0 ⊕ 111 = 111<br /> Tính s = b ⊕ f(x) = 100 ⊕ 111 = 011 = 3<br /> Do s = 3 ≠ 0, đảo bit ở vị trí 3 trong x được x’ = 1011101<br /> * Quá trình giải tin từ x’ để tìm lại b được thực hiện như sau:<br /> = f(x’) = 1.db(1) ⊕ 0.db(2) ⊕ 1.db(3) ⊕ 1.db(4) ⊕ 1.db(5) ⊕ 0.db(6) ⊕ 1.db(7)=<br /> <br /> Tính b<br /> <br /> = 1 ⊕ 0 ⊕ 11 ⊕ 100 ⊕ 101 ⊕ 0 ⊕ 111=100<br /> 3.3. Đánh giá thuật toán giấu tin mới HT<br /> Các lược đồ giấu tin CB và WL cho phép nhúng 1 bit vào một khối ảnh gốc gồm m×n bit<br /> và phải thay đổi tối đa 1 bit của khối ảnh gốc; lược đồ giấu tin CPT cho phép nhúng r bit vào<br /> khối ảnh gốc gồm m×n bit với 2r < m×n và phải thay đổi nhiều nhất 2 bit trong khối ảnh gốc.<br /> Như vậy, để giấu được k bit thông tin, lược đồ CPT cần có ít nhất m×n = 2k+1 bit gốc;<br /> thuật toán chúng tôi đề xuất trong bài báo này cần 2k-1 bit gốc.<br /> Chúng tôi tiến hành đánh giá các thuật toán giấu tin theo một số yếu tố:<br /> - Khả năng giấu: AH = 100*k/n %<br /> - Tính Nn: HH = 100*I(k)/n %<br /> Trong đó: k là số bit có thể giấu, n là số bit gốc tối thiểu để giấu được k bit, I(k) là số bit tối<br /> đa có thể phải đảo khi giấu k bit vào n bit gốc. Giá trị AH càng lớn thể hiện dung lượng tin có<br /> thể giấu cao; HH càng nhỏ thể hiện sau khi giấu tin dữ liệu chứa ít bị thay đổi so với dữ liệu<br /> gốc. Kết quả so sánh các yếu tố giữa lược đồ mới với lược đồ CPT được thể hiện qua bảng 1.<br /> Bảng 1. So sánh một số yếu tố giữa lược đồ CPT và lược đồ mới HT<br /> k<br /> 1<br /> 2<br /> 3<br /> 4<br /> 5<br /> 6<br /> 7<br /> 8<br /> 9<br /> 10<br /> 11<br /> 12<br /> <br /> 28<br /> <br /> n<br /> CPT<br /> 2k+1<br /> 3<br /> 5<br /> 9<br /> 17<br /> 33<br /> 65<br /> 129<br /> 257<br /> 513<br /> 1025<br /> 2049<br /> 4097<br /> <br /> AH<br /> <br /> I(k)<br /> HT<br /> 2k-1<br /> 1<br /> 3<br /> 7<br /> 15<br /> 31<br /> 63<br /> 127<br /> 255<br /> 511<br /> 1023<br /> 2047<br /> 4095<br /> <br /> CPT<br /> 2<br /> 2<br /> 2<br /> 2<br /> 2<br /> 2<br /> 2<br /> 2<br /> 2<br /> 2<br /> 2<br /> 2<br /> 2<br /> <br /> HT<br /> 1<br /> 1<br /> 1<br /> 1<br /> 1<br /> 1<br /> 1<br /> 1<br /> 1<br /> 1<br /> 1<br /> 1<br /> 1<br /> <br /> CPT<br /> k/(2k+1)<br /> 33.33<br /> 40.00<br /> 33.33<br /> 23.53<br /> 15.15<br /> 9.23<br /> 5.43<br /> 3.11<br /> 1.75<br /> 0.98<br /> 0.54<br /> 0.29<br /> <br /> HH<br /> HT<br /> k/(2k-1)<br /> 100.00<br /> 66.67<br /> 42.86<br /> 26.67<br /> 16.13<br /> 9.52<br /> 5.51<br /> 3.14<br /> 1.76<br /> 0.98<br /> 0.54<br /> 0.29<br /> <br /> CPT<br /> 2/(2k+1)<br /> 66.67<br /> 40.00<br /> 22.22<br /> 11.76<br /> 6.06<br /> 3.08<br /> 1.55<br /> 0.78<br /> 0.39<br /> 0.20<br /> 0.10<br /> 0.05<br /> <br /> HT<br /> 1/(2k-1)<br /> 100.00<br /> 33.33<br /> 14.29<br /> 6.67<br /> 3.23<br /> 1.59<br /> 0.79<br /> 0.39<br /> 0.20<br /> 0.10<br /> 0.05<br /> 0.02<br /> <br /> T¹p chÝ Khoa häc & C«ng nghÖ - Sè 4(44) Tập 2/N¨m 2007<br /> <br /> 4. Áp dụng thuật toán HT để giấu tin trong ảnh<br /> Thuật toán giấu tin mật HT chúng tôi đề xuất trong mục 3 tiến hành giấu k bit vào chuỗi<br /> n=2k-1 bit gốc. Với bài toán giấu tin trong ảnh, thông tin cần giấu có thể được chuyển thành một<br /> chuỗi các bit, dữ liệu gốc là giá trị các điểm ảnh được chọn cho việc giấu tin. Tuỳ loại ảnh, ta có<br /> thể áp dụng thuật toán cho phù hợp. Ngoài ra, có thể kết hợp sử dụng hệ thống khoá cho quá<br /> trình giấu tin và lọc tìm lại tin giấu, kiểm soát chất lượng ảnh sau khi giấu tin.<br /> 4.1. Giấu tin trong ảnh nhị phân<br /> Bài toán: Có một ảnh chủ nhị phân F, kích thước M×N, một thông điệp bí mật đã chuyển<br /> sang dạng nhị phân H gồm s bit. Thực hiện giấu H vào F và tách tìm lại H từ ảnh đã giấu tin.<br /> Để thực hiện bài toán trên, khi sử dụng thuật toán HT cần chia H thành r đoạn có độ dài<br /> k bit; ảnh F cũng chia thành r đoạn có độ dài n≥2k-1 bit. Mỗi đoạn k bit của H sẽ được giấu vào<br /> một đoạn n bit của F. Như vậy, khả năng giấu tin trong mỗi đoạn sẽ là AH =<br /> được hết s bit của H vào M×N bit của F thì k phải là số thoả mãn<br /> <br /> k<br /> và để giấu<br /> 2 −1<br /> <br /> k<br /> s<br /> ≥<br /> 2 −1 M × N<br /> k<br /> <br /> k<br /> <br /> (4).<br /> <br /> Thuật toán giấu tin trong ảnh nhị phân HTB<br /> Quá trình giấu tin:<br /> Vào:<br /> <br /> Ảnh nhị phân F kích thước M×N; chuỗi bit cần giấu H có độ dài s.<br /> <br /> Ra:<br /> <br /> Ảnh đã giấu tin F' và giá trị k.<br /> <br /> Thực hiện:<br /> - Chọn k là số tự nhiên lớn nhất thoả (4)<br /> - Chia H lần lượt thành các đoạn có độ dài k bit, số đoạn sẽ là r =<br /> <br /> s<br /> . Ký hiệu các đoạn là<br /> k<br /> <br /> Hi (i=1..r)<br /> - Chuyển F thành chuỗi gồm M×N bit, rồi chia lần lượt thành các đoạn có độ dài 2k-1 bit,<br /> M ×N s<br /> khi đó số đoạn có được sẽ là k<br /> ≥ = r . Ký hiệu các đoạn là Fi (i=1..r). Như vậy, số đoạn<br /> 2 −1 k<br /> bit gốc đủ để giấu số đoạn thông điệp bí mật.<br /> - Lần lượt nhúng chuỗi k bit Hi vào chuỗi Fi (i=1..r) theo thuật toán HT để được chuỗi<br /> Fi đã chứa tin giấu.<br /> '<br /> <br /> - Chuyển chuỗi bit F1' F2' ... Fr' thành ảnh F' kích thước M×N.<br /> <br /> Quá trình tách tin:<br /> Vào:<br /> <br /> Ảnh nhị phân F' kích thước M×N; giá trị k.<br /> <br /> Ra:<br /> <br /> Chuỗi bit H tách ra từ ảnh F'.<br /> <br /> Thực hiện:<br /> - Chuyển F' thành chuỗi gồm M×N bit, rồi chia lần lượt thành các đoạn có độ dài 2k-1 bit<br /> 29<br /> <br />