Luận văn Giấu tin trong ảnh và ứng dụng trong an toàn bảo mật thông tin

tỷ lệ lớn nhất trong các chương trình ứng dụng, các phần mềm, hệ thống giấu tin trong đa phương tiện bởi lượng thông tin được trao đổi bằng ảnh là rất lớn và hơn nữa giấu thông tin trong ảnh cũng đóng vai trò hết sức quan trọng trong các hầu hết các ứng dụng bảo vệ an toàn thông tin như: nhận thực thông tin, xác định xuyên tạc thông tin, bảo vệ bản quyền tác giả, điều khiển truy cập, giấu thông tin mật...Chính vì thế mà vấn đề này đã nhận được sự quan tâm rất lớn của các cá nhân, tổ chức, trường đại học, và viện nghiên cứu trên thế giới. Thông tin sẽ được giấu cùng với dữ liệu ảnh nhưng chất lượng ảnh ít thay đổi và chẳng ai biết được đằng sau ảnh đó mang những thông tin có ý nghĩa. Và ngày nay, khi ảnh số đã được sử dụng rất phổ biến, thì giấu thông tin trong ảnh đã đem lại nhiều những ứng dụng quan trọng trên các lĩnh vực trong đời sống xã hội. Ví dụ như đối với các nước phát triển, chữ kí tay đã được số hoá và lưu trữ sử dụng như là hồ sơ cá nhân của các dịch vụ ngân hàng và tài chính. Nó được dùng để nhận thực trong các thẻ tín dụng của người tiêu dùng. Hay trong một số những ứng dụng về nhận diện như thẻ chứng minh, thẻ căn cước, hộ chiếu…người ta có thể giấu thông tin trên các ảnh thẻ để xác định thông tin thực. Ví dụ như hình vẽ bên là một thẻ chứng minh đã được giấu tin trong ảnh. Thông tin giấu là số thẻ trùng với số đã được in rõ ở trên thẻ. 16 Một thẻ thông minh đã được giấu tin sử dụng trong công tác nhận dạng Phần mềm WinWord của MicroSoft cũng cho phép người dùng lưu trữ chữ kí trong ảnh nhị phân rồi gắn vào vị trí nào đó trong file văn bản để đảm bảo tính an toàn của thông tin. Tài liệu sau đó được truyền trực tiếp qua máy fax hoặc lưu truyền trên mạng. Theo đó, việc nhận thực chữ kí, xác thực thông tin đã trở thành một vấn đề cực kì quan trọng khi mà việc ăn cắp thông tin hay xuyên tạc thông tin bởi các tin tặc đang trở thành một vấn nạn đối với bất kì quốc gia nào, tổ chức nào. Thêm vào đó, lại có rất nhiều loại thông tin quan trọng cần được bảo mật như những thông tin về an ninh, thông tin về bảo hiểm hay các thông tin về tài chính. Các thông tin này được số hoá và lưu trữ trong hệ thống máy tính hay trên mạng. Chúng rất dễ bị lấy cắp và bị thay đổi bởi các phần mềm chuyên dụng. Việc nhận thực cũng như phát hiện thông tin xuyên tạc đã trở nên vô cùng quan trọng, cấp thiết. Và một đặc điểm của giấu thông tin trong ảnh nữa đó là thông tin được giấu một cách vô hình. Nó như là cách truyền thông tin mật cho nhau mà người khác không thể biết được, bởi sau khi giấu thông tin thì chất lượng ảnh gần như không thay đổi đặc biệt đối với ảnh mầu hay ảnh xám. 17 Từ năm học 1995-1996, Bộ giáo dục và Đào tạo đã bắt đầu ứng dụng công nghệ thông tin vào công tác bảo mật đề thi tốt nghiệp trung học phổ thông thay cho việc niêm phong, đóng dấu đề thi để chuyển qua theo đường bưu điện. Trong mục này đề cập tới một kỹ thuật đơn giản đáng tin cậy để giấu những thông tin quan trọng nào một ảnh đen trắng (ảnh nhị phân) bằng cách sử dụng khoá bí mật và một ma trận trọng số. Phương pháp này được chứng minh là có độ an toàn cao, đảm bảo chất lượng ảnh gốc và có tỉ lệ giữa kích thước thông tin giấu được với kích thước ảnh môi trường tương đối so với các phương pháp khác và cho phép giấu được tới [log2(m*n+1)] bit dữ liệu vào trong mỗi khối ảnh kích thước m*n mà chỉ cần thay đổi nhiều nhất 2 bit trong khối ảnh đó. 2.2. Các đặc trưng của giấu thông tin trong ảnh Như đã nói ở trên nhúng thông tin trong ảnh có hai khái niệm khác nhau đó là thuỷ vân số ( digital watermarking ) và giấu thông tin mật trong ảnh (stegnography). Trong khi thuỷ phân số không yêu cầu thông tin giấu phải vô hình và chịu được các thao tác biến đổi trên ảnh thì giấu thông tin trong ảnh yêu cầu các thông tin giấu phải ẩn không bị phát hiện và lượng thông tin giấu càng lớn càng tốt (capacity of hidden message). Hai phương pháp này có những đặc điểm khác nhau, cách thực hiện khác nhau nhưng trong báo cáo này là giấu tin trong ảnh nên chỉ đề cập tới các đặc trưng chính của giấu thông tin trong ảnh.  Phương tiện chứa có dữ liệu tri giác tĩnh Dữ liệu gốc ở đây là dữ liệu của ảnh tĩnh, dù đã giấu thông tin vào trong ảnh hay chưa thì khi ta xem ảnh bằng thị giác dữ liệu ảnh được tri giác tĩnh nghĩa là ảnh không thay đổi theo thời gian khi tri giác, điều này khác với đa phương tiện audio hay video vì khi ta tri giác các dữ liệu phương tiện chứa gốc là hình ảnh hay âm thanh thì dữ liệu gốc sẽ thay đổi liên tục với tri giác của con người theo các đoạn hay các bài, các cảnh . . . Sự khác biệt này ảnh hưởng lớn đối với các kỹ thuật giấu tin trong audio 18 hay video. Đối với giấu thông tin trong ảnh phương pháp giấu và kỹ thuật giấu phụ thuộc vào đặc điểm thị giác của con người ví dụ như độ sáng tối, hay yếu tố khoảng cách to nhỏ. . .  Giấu tin trong ảnh tác động lên dữ liệu ảnh nhưng không thay đổi kích thước ảnh. Các phép toán thực hiện công việc giấu tin sẽ được thực hiện trên dữ liệu của trên ảnh. Dữ liệu ảnh bao gồm các phần header, bảng phân màu và dữ liệu ảnh. Khi giấu thông tin, các phương pháp đều biến đổi giá trị của các bit trong dữ liệu ảnh chứ không chứ không thêm vào hay bớt đi dữ liệu ảnh. Do vậy mà kích thước ảnh trước hay sau khi giấu thông tin là như nhau.  Đảm bảo yêu cầu chất lượng ảnh sau khi giấu thông tin. Đây là một yêu cầu quan trọng đối với giấu thông tin trong ảnh. Sau khi giấu thông tin bên trong, ảnh phải đảm bảo được yêu cầu không bị biến đổi để có thể bị phát hiện dễ dàng so với ảnh gốc. Yêu cầu này giường như quá đơn giản đối với ảnh màu và ảnh xám bởi mỗi pixel ảnh được biểu diễn bởi nhiều bit, nhiều giá trị và khi ta thay đổi một giá trị nhỏ nào đó chất lượng ảnh không thay đổi, thông tin giấu khó bị phát hiện, nhưng đối với ảnh đen trắng thì việc giấu thông tin phức tạp hơn nhiều, vì ảnh đen trắng mỗi pixel ảnh chỉ có hai giá trị đen hoặc trắng, và nếu ta biến đổi một bit từ đen thành trắng mà không khéo thì sẽ rất bị phát hiện. Do đó yêu cầu với các kỹ thuật giấu tin trong ảnh màu hay ảnh xám và giấu thông tin trong ảnh đen trắng là khác nhau. Trong khi đối với ảnh màu thì các thuật toán chú trọng vào việc làm sao cho giấu dược càng nhiều thông tin càng tốt thì các thuật toán áp dụng cho ảnh đen trắng lại tập trung vào làm thế nào để thông tin giấu khó bị phát hiện.  Thông tin trong ảnh sẽ bị biến đổi nếu có bất kỳ một biến đổi nào trên ảnh. 19 Vì phương pháp giấu ảnh dựa trên việc điều chỉnh các giá trị của các khối bit theo một quy tắc nào đó và khi giải mã sẽ theo các giá trị đó để tìm được thông tin giấu. Theo đó, nếu một phép biến đổi nào đó trên ảnh sẽ làm thay đổi giá trị của các bit thì sẽ làm thông tin sai lệch. Chính đặc điểm này mà giấu thông tin trong ảnh có tác dụng nhận thực và phát hiện xuyên tạc thông tin.  Không cần ảnh gốc khi giải mã ảnh Thông tin được giấu trong ảnh sẽ được mang cùng dữ liệu ảnh, khi giải mã chỉ cần ảnh đã mang thông tin mà không cần dùng đến ảnh gốc để so sánh đối chiếu. 2.3. Sự khác nhau giữa giấu tin trong ảnh đen trắng với ảnh màu Khởi nguồn của giấu thông tin trong ảnh là thông tin được giấu trong các ảnh màu hoặc ảnh xám, trong đó mỗi pixel ảnh mang nhiều giá trị, được biểu diễn bằng nhiều bit. Với ảnh đó thì việc thay đổi một giá trị nhỏ ở một pixel thì chất lượng ảnh gần như không thay đổi, và khả năng bị phát hiện rất thấp dưới con mắt người bình thường. Do đó hệ thống thị giác của con người cũng đóng một vai trò quan trọng trong việc bảo đảm tính không nhìn thấy thông tin được giấu trên ảnh. Với những ảnh mà mỗi điểm ảnh chỉ mang một giới hạn nhỏ các giá trị thì việc giấu thông tin trong ảnh đảm bảo tính vô hình của thông tin che giấu là một công việc khó khăn hơn nhiều. Đặc biệt với ảnh đen trắng, mỗi điểm ảnh chỉ mang một trong hai giá trị trắng hoặc đen. Vậy thì khi thay đổi giá trị một pixel từ đen thành trắng hoặc ngược lại thì rất dễ bị phát hiện. Một số thuật toán khác thì giấu chất lượng ảnh tốt hơn nhưng lượng thông tin giấu được bít và quá đơn giản không đảm bảo được độ an toàn thông tin. Bảng sau sẽ liệt kê những khác nhau cơ bản giữa giấu thông tin trong ảnh đen trắng và ảnh mầu. 20 Sự khác nhau giữa giấu thông tin trong ảnh đen trắng và ảnh màu Giấu thông tin trong ảnh đen trắng Giấu thông tin trong ảnh màu hoặc ảnh xám Thông tin giấu được ít Thông tin giấu nhiều hơn Tính ẩn thấp Tính ẩn cao Độ an toàn thông tin thấp do dễ bị phát hiện có thông tin chứa thông tin bên trong Độ an toàn cao Các thuật toán giấu ít, phức tạp Nhiều thuật toán và có nhiều hướng mở rộng phát triển. Như áp dụng giải thuật di truyền. Ảnh màu sau khi giấu tin rất khó phát hiện sự thay đổi 21 Ảnh đen trắng sau khi giấu cùng một lượng thông tin như ảnh màu nhưng chất lượng kém hơn . 2.4. Các thuật toán giấu tin trong ảnh 2.4.1 Giấu tin trong ảnh thứ cấp 2.4.1.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 (đen trắng ) bằng cách: - Sử dụng khoá bí mật K cố định. - Sử dụng khoá bí mật K cố định với chiều dài thay đổi. - Sử dụng khoá bí mật K cố định là một ma trận ảnh. - Sử dụng khoá K (ma trận khoá kích thước m*n (ma trận 0/1) dùng chung bởi người nhận và người gửi), và ma trận trọng số cấp r, kích thước m*n cũng được dùng chung bởi người gửi và người nhận. 22  Bài toán: Giả sử ta có đề thi 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 đề thi, sau đó gửi đi bức ảnh đã chứa thông tin đề thi mà không sợ bị nghi ngờ về sự tồn tại thông tin trong đó. Sử dụng một kỹ thuật giấu tin trong ảnh (chọn khoá bí mật K 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 tin trên mà không làm cho F’ sai khác nhiều so với F. Để thu được thông tin đề thi B đã giấu, chỉ cần có ảnh kết quả và các khoá mà không cần đến ả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*n. K: Dùng chung bởi người gửi và người nhận (nếu K là ma trận khoá thì có kích thước m*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*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*n của F, r phải thoả mãn bất đẳng thức: 2r-1≤ m*n. B: k*r bít dữ liệu cần giấu, được tách thành k chuỗi r bit . 2.4.1.2. Các khái niệm cơ bản Ảnh thứ cấp và ma trận nhị phân Trước hết ta quan tâm đến các đối tượng chính là các ảnh thứ cấp hay ảnh một bit màu. Đó là những bức ảnh mà mỗi điểm ảnh chỉ là đen hoặc trắng, được qui định bởi 1 bit. Nếu bit mang giá trị 0 thì điểm ảnh là điểm đen, nếu là 1 thì điểm ảnh là 23 điểm trắng. Do đó, để biểu diễn một điểm ả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 gía trị là 0 hoặc 1. Khoá bí mật Khoá bí mật K có thể: - Có độ dài không thay đổi. - Có độ dài biến thiên. - Khoá bí mật là một ma trận ảnh. - Khoá bí mật là một ma trận nhị phân có cùng 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. 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 khoá 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 thoả mãn số yêu cầu xác định. Một ma trận w kích thước m*n được gọi là ma trận 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 n, m, r là các số tự nhiên thoả mãn 2r-1≤ m*n. Từ những định nghĩa ta nhận thấy với mỗi m,n,r thoả mãn 2r-1≤ m*n sẽ có biểu thức: )12(12 )12)!*(12(* −−− −− rr mnrrmnc khả năng chọn w.  Ví dụ: - Với m=n=2, r=2 ta sẽ có 128 khả năng chọn w. 24 - Với m=n=4, r=4 ta sẽ có 2.326.692.130.963.200 khả năng lựa chọn w. Con số này đủ lớn để làm giảm nguy cơ thông tin bị giải mã bởi những kẻ phá hoại. 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 b tương đương với phép biến đổi thay b bởi 1-b, tức là nếu ban đầu b nhận giá trị 0 thì sau khi đảo thì nó nhận giá trị 1 và ngược lại, nếu ban đầu b có giá trị 1 thì sau khi đảo nó sẽ mang giá trị 0. Các phép toán trên ma trận Trước hết, ta coi một bitmap như là một ma trận 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 ma trận:  Định nghĩa 1: Phép hoặc loại trừ ⊕ : ⊕ : là phép toán trên hai ma trận nhị phân xác định như sau: A⊕B =C C[i,j]=A[i,j]⊕ B[i,j] Trong đó: 25 A B A⊕ B 0 0 0 0 1 1 1 0 1 1 1 0  Ví dụ 1: Giả sử có hai ma trận Fi và K sau: Fi = ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ 011 101 010 , K = ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ 110 011 110 Khi đó phép hoặc loại trừ giữa hai ma trận này cho ta kết quả: Fi ⊕ K  Định nghĩa 2: Phép nhân⊗ : Kí hiệu: A ⊗ B là phép toán xác định như sau A⊗B=C Trong đó: C[i,j] = A[i,j] * B[i,j]  Ví dụ 2: Giả sử có Fi , K, W như sau: Fi = ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ 011 001 011 K= ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ 110 011 110 W= ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ 321 321 321 26 Thực hiện phép toán Fi ⊕ K ta được: Fi ⊕ K= ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ 011 001 011 ⊕ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ 110 011 110 = ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ 101 010 101 Tiếp theo thực hiện phép ⊗ với w. ((Fi ⊕K) ⊗w) = ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ 101 010 101 ⊗ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ 321 321 321 = ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ 301 020 301 Và cuối cùng tính tổng SUM ((Fi⊕K)⊗w) =1+3+2+1+3=10. 2.4.2.Các kỹ thuật giấu tin trong ảnh thứ cấp 2.4.2.1. Sử dụng khoá bí mật K cố định Thuật toán  Mã hoá: Giả sử chúng ta cần giấu bit b vào trong ảnh. Cắt một đoạn gồm có k điểm ảnh và giấu b vào trong ảnh. Trong đó k là khoá(k lẻ). d= F/k = số đoạn . Giải thuật dựa vào tính chẵn lẻ:  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 b và t cùng tính chẵn lẻ: thì không làm gì. 27 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 ở 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à khoá 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. Suy ra : bít b = 0 Nếu Sum(f) : lẻ. Suy ra : bit b=1 28  Bước 3: Chuyển đổi bít thành kí tự  Đặc điểm của thuật toán: Giải mã nhanh. Nhưng vì khoá 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ã hoá. 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 đã trình bày. 2.4.2.2. Sử dụng khoá bí mật K cố định với chiều dài thay đổi Thuật toán Mã hóa: Giả sử chúng ta cần giấu bit b vào trong ảnh. Cắt một đ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,...,kn ) D= (n x m)sum/(k1,k2,...) x 1 = 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 mó 2.  Bước 2: So sánh t và b : Nếu t và b có cùng tính chẵn lẻ : thì không làm gì. 29 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 ở 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 ki.  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 Suy ra bit b = 0 Nếu Sum(fi) : Lẻ suy ra bit b = 1 Bước 3 : Chuyển đổi bit thành kí tự. 30 Đặc điểm của thuật toán Như vậy, khi chọn các bit thay đổi trong từng đoạn phù hợp thì bức ảnh sau khi giấu sẽ ít thay đổi so với bức ảnh ban đầu. Ưu điểm thuật toán là: - Một bit dữ liệu được ẩn trong bức ảnh có thể không làm thay đổi hình ảnh ban đầu bức ảnh. Do đó độ an toàn sẽ cao hơn. - Vì khóa 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 nhận và người gửi. 2.4.2.3. Thuật toán giấu tin của Wu - Lee (WL) Thuật toán Ta xem một bức ảnh chính nhi phân F, khoá 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ã hoá:  Bước 1: Chia F thành những khối Fi, mỗi khối có kích thước m x n. Tính S = Sum(Fi ⊗K), Sk = SUM(K)  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 Fi. Nếu không thoả mãn điều kiện thì không giấu vào Fi.  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 : TH1: Nếu (S mod 2=b) thì không thay đổi Fi. 31 TH2: Nếu ( S mod 2!=0) thì sẽ thay đổi một phần tử ( h, g) trên Fi từ 1 Æ 0 hoặc từ 0 Æ 1 tại K( h, g) ==1. Khi đó xét 3 khả năng sau: a ) Nếu S=1 tìm phần tử (h,g) thoả mãn K[h,g] = 1 và Fi [h,g] = 0 và thay Fi [ h,g] =1. b) Nếu S= Sk -1 tìm (h,g) thoả mãn K[h,g] =1 và Fi [h,g] =1 và gán Fi [h,g]= 0; c) Nếu 2 <=S < Sk – 1 thì chọn ngẫu nhiên (h,g) thoả mãn K[h,g] = 1 và đảo bit Fi [h,g] có nghĩa giá trị của Fi [h,g] sẽ từ 0 Æ1 hoặc 1Æ0. Ví dụ: Chuỗi bit cần giấu là 010 F1 F2 F1’ F2’ Khoá K F3 F4 F3’ F4’ F là một ma trận khối ảnh có kích thước 8 x 8 và K là một ma trận ảnh có kích thước là 4 x 4. Trước tiên ta chia F thành 4 khối F1, F2, F3, F4. Vì Sum(F1⊗ K) = 1 nên ta chọn K[2,2] =1 và F1[2,2] =0 và đổi F1[2,2]=1. Vì Sum (F2⊗K )= Sk – 1 nên ta chọn K[3,3] = 1 và F2[3,3] =1 và đổi F2[3,3] =0. 1 0 1 0 0 1 0 0 1 0 1 1 0 1 0 0 1 1 0 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 0 1 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 0 1 1 1 1 0 1 0 0 1 1 0 0 0 0 0 1 0 1 0 1 1 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 1 1 1 0 1 0 1 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 1 1 1 0 32 Vì Sum(F3⊗K )=4 nên ta chọn K[3,4]= 1 và đổi F3[3,4]=0. Giải mã: Phương pháp trên cho phép giấu nhiều nhất 1 dữ liệu trong một khối. Giả sử F(i) được biến đổi thành Fi’ thì ta có bất biến sau: I1: 0sum(Fi ⊗K)= b mod 2 Khi người thu xác định được 0 < sum(Fi ⊗K) <sum(K) thì họ sẽ tìm ra được bit đã giấu b: b= sum(Fi ‘⊗K) mod 2. Ví dụ : Chuỗi các bit cần giấu là: 010 F là một khối ảnh có kích thước 6 x 6 và K là một ảnh có kích thước 3 x 3. trước tiên ta chia F thành 4 khối F1, F2, F3, F4. Vì Sum(F1⊗ K) = Sum (K) =5. Do đó khối F1 không giấu dữ liệu. Vì Sum (F2⊗K )= Sum(K)=3, một bít dữ liệu sẽ được giấu vào trong F. F1 F2 1 1 0 1 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 1 1 1 0 1 1 0 1 0 F3 F4 1 1 0 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1 0 1 1 0 1 0 '1F '2F '3F '4FKhoá K 0 1 0 1 1 1 0 1 0 33 Vì bit đầu tiên cần giấu là bit 0, F2 đổi thành F2’ để đảm bảo thoả mãn biểu thức trên. Vì Sum (F3⊗K )= Sum(K)=3, một bít dữ liệu sẽ được giấu vào trong F. Vì bit tiếp theo cần giấu là bit 1, F3 được giữ nguyên. Tương tự F4 bị thay đổi để giấu bit 1. Phân tích thuật toán: - Thứ nhất: Vì phép toán AND được sử dụng để tính Fi⊗K, nên giá trị lớn nhất của SUM( Fi⊗K) không thể vượt quá SUM(K) và do đó tính chất của phép toán AND, nếu có một khối nào đó bị thay đổi thì vị trí thay đổi chỉ xảy ra ở phần tử có giá trị 1 trong khóa K, vì thế nếu một ảnh F hoàn toàn trắng nào đó được truyền đi thì kẻ thù khi bắt được thông tín sẽ dễ dàng tìm được vị trí 1 của khóa K, đó là lí do mà ta không dùng trường hợp SUM(Fi ⊗K)= 0. Đây là một kẽ hở của thuật toán đối với khóa. - Thứ 2: Với trường hợp SUM(Fi ⊗ K)= SUM(K) cũng tương tự nếu F hoàn toàn đen thì vị trí của bit thay đổi cũng là vị trí mà bít tương ứng ở khóa là 1. - Để tránh trường hợp trên thuật toán đã phải đưa ra phụ thuộc : 0< SUM(Fi ⊗K) <SUM(K). Nhưng cho dù thế đi chăng nữa thì vị trí tương ứng với bít ở vị trí đó trong khóa K có giá trị là 1, và bit không bao giờ bị thay đổi tương ứng sẽ là bit 0 ở vị trí đó trong khóa K. Và như thế việc lựa chọn khóa K như thế nào là một công việc hết sức quan trọng. - Thứ 3 : Nếu ảnh F được lựa chọn để giấu thông tin có quá nhiều điểm trắng hoặc có quá nhiều điểm đen thì tỉ lệ bit giấu được sẽ thấp hơn. 34 - Nói chung thuật toán nay vẫn chưa đạt những yêu cầu cần thiết về khả năng giấu, độ an toàn thông tin cũng như chất lượng ảnh. Tuy nhiên đó là áp dụng với ảnh đen trắng, nếu ta áp dụng kỹ thuật này cho ảnh màu thì cũng thu được kết quả khả quan. Đặ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. Tính đúng đắn 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. 2.4.2.4. Kỹ thuật giấu tin Chen-Pan-Tseng( CPT) Các đặc điểm Sử dụng khoá K là ma trận khoá kích thước m*n( ma trận 0/1) dùng chung bởi người gửi và người nhận và ma trận trọng số w cấp r, kích thước m*n cũng được dùng chung bởi người gửi và người nhận. Đặc điểm của ma trận trọng số cấp r: Ma trận trọng số câp r là một ma trận số nguyên có kích thước bằng kích thước của khối ảnh m*n và thỏa mãn các điều kiện sau: W là một ma trận số nguyên có các phần tử nằm trong khoảng giá trị (0 ….2r – 1). Với r là số cho trước thỏa mãn 2r < m*n. Mối phần tử có giá trị từ 1…2r- 1 xuất hiện ít nhất 1 lần. 35 Thuật toán Với khối ảnh như Fi, ma trận trọng số W, khoá K, ta cần giấu r bit thông tin b1b2b3. . .br vào Fi bằng cách đảo nhiều lần 2 bit của Fi. Mục đích của chúng ta là biến đổi Fi thành Fi’ sao cho nó thoả mãn yêu cầu sau: SUM(Fi’⊕K) ⊗ W ≡b1b2b3. . .br(mod 2).  Quá trình giấu tin: Quá trình biến đổi gồm 4 bước sau:  Bước 1: Tính ma trận T=Fi ⊕ K.  Bước 2: Tính tổng Sum= SUM( T ⊗ W).  Bước 3: Với ma trận T và với mọi w=1,2,3,. . .,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))}. Dễ nhận thấy Sw là tập hợp các toạ độ (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[i, k]= 2r- w và T[j, k]=1. Khi đó đảo bit Fi[j,k] sẽ làm T[j, k] =0 do đó Sum sẽ giảm đi 2r-w, tức tăng lên w theo mod 2r. Qui ước rằng với mọi w’≡w(mod 2r ) trong đó w=1,2,3,. . .,2r-1, ta có Sw’ = Sw.  Bước 4: 36 Kí hiệu d=(b1b2b3. . .br) - SUM(Fi⊕K)⊗ W(mod 2r). Ta cần thực hiện việc đảo bit trên Fi để được Fi sao cho tổng Sum tính được ở bước 2 khi thay Fi bởi Fi’ sẽ tăng lên d.  Nếu d=0, không cần thay đổi Fi  Nếu d ≠ 0. o Chọn h bất kỳ thuộc tập {0,1,2,. . .,2r-1} sao cho Shd≠∅ và S-(h-1)d≠∅. o 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 lai đổi 1 thành 0). o 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 2 tập khác trống Shd và S-(h-1)d. Thật vậy, hai tập này chứa các vị trí chứa các 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 hd+(-(h-1)d)=d. Tương tự như các tập Sw ta cũng có thể coi tập S0 là tập chứa các vị trí mà khi dảo các bit có vị trí này trên Fi thì ta 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 một bit có vị trí thuộc tập S0’ có nghĩa là không cần làm gì cả.  Ví dụ: Cho F, K, W như sau: Giả sử ta cần giấu 12 bit thông tin B=001010000001 vào F thành 4 khối kích thước 4*4 F1, F2, F3, F4 , mỗi khối ta sẽ giấu r=3 bit của B. 37 Thực hiện phép hoặc loại trừ Fi với K thu được Ti , nhân với W rồi tính tổng các phần tử ma trận kết quả: Với F1 ta có Sum((F1⊕K)⊗ W) ≡0 (mod 8), để giấu 3 bit đầu tiên của B là 001 vào F1 ta cần biến đổi F1 sao cho Sum tăng lên 1. Nhận thấy T1[2,4]=0 và W[2,4 ]=1 nên ta có thể đảo giá trị bit F1[2,4] để được F1. Với F2 ta có Sum((F2⊕K)⊗ W) ≡2(mod 8)) và 3 bit tiếp theo của B là 010 do đó không cần phải thực hiện biến đổi trên F2 . Để giấu 3 bit 000 vào F3 có Sum ((F3⊕K)⊗ W) ≡2(mod 8) ta cần biến đổi sao cho Sum tăng lên 6 bằng cách đảo bit F3[4,4]. Với F4 ta có Sum((F1⊕K)⊗ W) ≡4(mod 8) trong khi 3 bit cần giấu là 001 nên ta cần tăng Sum lên 5, việc này không thể thực hiện được bằng cách đảo một bit trong F4 mà phải cần tới hai bit. Ta chọn S10=S2={(2,2)} và S-5=S3={(1,3),(2,1),(3,2),(3,4)} và đảo hai bit F4[2,2] và F4[3,2] . Kết quả nhận được như hình vẽ trên. 1 0 0 1 1 0 1 0 1 1 0 0 1 0 1 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 0 1 1 0 0 1 0 1 0 1 KF ⊕2 KF ⊕1 KF ⊕3 KF ⊕4 0 1 0 1 0 1 1 0 1 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 0 1 0 0 1 1 1 0 1 0 1 1 0 1 0 1 1 1 1 0 1 0 0 1 1 1 ' 1F '2F ' 3F '4F 38  Giải mã: Khi nhận được bức ảnh kết quả, người nhận chỉ cần tách các bít ít đặc trưng nhất của từng điểm ảnh và chia thành từng khối Fi’ kích thước m*n. Quá trình biến đổi gồm 4 bước sau:  Bước 1: Tính ma trận T=Fi’ ⊕ K.  Bước 2: Tính tổng Sum= SUM( T ⊗ W).  Bước 3: Sử dụng ma trận khoá 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 (mod 2).  Bước 4: Chuyển đổi bit thành kí tự. 39 Tính đúng của thuật toán Để chứng minh tính đúng của thuật toán trên ta sử dụng các bổ đề sau:  Bổ đề 1: Với mọi w=1,2….,2r – 1 thoả mãn w ≠ 2r-1 ta có: (Sw = ∅ ) ⇒ ( ∅≠−wrS2 )  Chứng minh: Với w ≠ 2r-1 giả sử Sw=∅. 0 1 0 1 0 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 0 0 0 0 1 1 1 0 1 0 1 1 0 1 0 1 1 1 1 0 1 1 0 1 1 1 F1 F2 F3 F4 0 0 1 0 1 1 1 0 0 1 0 0 1 1 0 0 K= 6 7 1 2 2 3 4 5 5 6 7 1 1 2 3 4 W= F= 40 Từ định nghĩa của ma trận trọng số ta suy ra tồn tại ít nhất một phần tử W[j,k]=w, do đó ta phải có Fi[j,k]^K[j,k]=1 vì nếu không khi ta đảo Fj[j,k] sẽ được giá trị 1 dẫn đến tổng Sum((Fi⊕K)⊕W) sẽ tăng lên w và do đó Sw không rỗng (trái với giả thiết). Do đó Fi[j,k]^K[j,k]=1. Nếu ta đảo giá trị của Fi[j,k] thì Sum sẽ giảm đi w hay tăng lên 2r-w (mod 2r), suy ra tập khác rỗng.  Bổ đề được chứng minh.  Bổ đề 2: Tập hợp 12 −rS khác rỗng.  Chứng minh: Từ định nghĩa 1 ta suy ra tồn tại ít nhất một phần tử W[j,k] của ma trận W nhận giá trị 2r-1. Mặt khác ta có 2r-1≡-2r-1(mod 2r) nên nếu ta đảo giá trị của Fi[j,k] thì Sum sẽ tăng lên hoặc giảm đi 2r-1.  Bổ đề được chứng minh.  Bổ đề 3: Bước 4 luôn luôn thực hiện được và nhiều nhất hai bit của Fi bị đảo để giấu được r bit dữ liệu. Tức là luôn luôn tìm được h sao cho Shd và S-(h-1)d khác rỗng với mọi d nhận giá trị từ 0 tới 2r-1.  Chứng minh: Áp dụng định lý số học với mọi cặp số nguyên tố cùng nhau d1, d2, mọi x=1, 2,..d2-1 luôn tồn tại m, n sao cho nd1=nd2+x hay md1≡x(mod d2) ta suy ra tập hợp { d mod 2r, 2d mod 2r,…} chứa tất cả và chỉ chứa các bội nhỏ hơn 2r của ước số chung lớn 41 nhất của d và 2r nên tồn tại một số nguyên k sao cho kd≡2r-1(mod 2r) giả sử k là số nguyên nhỏ nhất thoả mãn điều này. Ta đi tìm h thoả mãn Shd≠∅ và S-(h-1)d≠∅. Với h=1, nếu S-d≠∅ (theo bổ đề 1). Với h=2, nếu S2d≠∅ thì h=2 là lời giải, nếu không thì S-d≠∅ theo bổ đề 1. Tiếp tục làm như vậy với h=3, 4,… k-1, nếu vẫn chưa tìm được h thoả mãn thì ta có thể khẳng định là h=k là lời giải vì khi đó 1SS 2kd −= r khác rỗng.  Vậy bổ đề được chứng minh. 2.4.3. Giấu tin trong ảnh màu và ảnh đa cấp xám Kết quả thực nghiệm cho thấy việc sử dụng ảnh đen trắng làm ảnh môi trường đem lại hiệu quả rất thấp vì việc biến đổi điểm ảnh từ đen sang trắng hay trắng sang đen rất dễ tạo ra các nhiễu trên ảnh và dễ bị phát hiện bởi hệ thống thị giác của con người. Hơn nữa ảnh đen trắng cung cấp lượng dữ liệu tương đối nhỏ để thực hiện các thao tác giấu tin. Ví dụ như một bức ảnh đen trắng kích thước 300*300 pixel chỉ cung cấp cho ta một lượng dữ liệu vào khoảng 90 kilobytes (kB) trong khi một bức ảnh 24 màu kích thước tương ứng có thể cho tới 2000 kB. Hạn chế này được khắc phục bằng cách sử dụng ảnh màu và ảnh đa cấp xám làm ảnh môi trường. Đối với việc chọn ảnh màu và ảnh đa cấp xám làm ảnh môi trường ta cần thực hiện thêm một bước xử lý nữa. Trước hết ta quan tâm tới khái niệm bit ít đặc trưng nhất (Least Significant Bit hay - LSB). LSB là bit có ảnh hưởng ít nhất tới việc quyết định màu sắc của mỗi điểm ảnh, vì vậy khi ta thay đổi bit ít đặc trưng nhất của một điểm ảnh thì màu sắc của điểm ảnh mới sẽ tương đối gần với điểm ảnh cũ. LSB của một điểm ảnh cũng tương tự như chữ số hàng đơn vị của một số tự nhiên, khi ta thay đổi giá trị của chữ số này thì chênh lệch giữa số cũ và số mới sẽ ít hơn khi ta thay đổi 42 giá trị của chữ số hàng chục hoặc hàng trăm. Việc xác định LSB của mỗi điểm ảnh trong một bức ảnh phụ thuộc vào định dạng của ảnh và số bit màu dành cho mỗi điểm của ảnh đó. Quá trình giấu tin vào ảnh màu và đa cấp xám cũng tương tự như với ảnh đen trắng nhưng trước hết ta chọn từ mỗi điểm ảnh ra từ ít đặc trưng nhất để tạo thành một ảnh nhị phân gọi là ảnh thứ cấp. Sử dụng ảnh thứ cấp này như là ảnh môi trường để giấu tin, sau khi biến đổi ảnh thứ cấp ta trả nó lại ảnh ban đầu để thu được ảnh kết quả. Ảnh màu và ảnh đa cấp xám cho hiệu quả cao hơn ảnh đen trắng vì việc thay đổi bit ít đặc trưng nhất trong những ảnh này dường như không làm thay đổi màu sắc của điểm ảnh trong việc thay đổi mỗi bit trong ảnh đen trắng làm cho điểm ảnh chuyển màu từ đen sang trắng hoặc ngược lại từ trắng sang đen do đó rất dễ bị phát hiện. Đối với ảnh 16 bit màu hoặc 24 bit màu việc xác định LSB tương đối đơn giản, tuy nhiên đối với ảnh nhỏ hơn hoặc bằng 8 bit màu (những ảnh có sử dụng bảng màu) thì rất phức tạp. Khó khăn này có thể khắc phục nếu ta sắp lại bảng màu cuả ảnh hoặc sử dụng những màu không dùng đến trong bảng màu của ảnh nhỏ hơn bằng 8 bit màu. 2.4.3.1. Ảnh đa cấp xám Đối với ảnh đa cấp xám, bảng màu của nó đã được sắp, tức là những cặp màu trong bảng màu có chỉ số chênh lệch càng ít thì càng giống nhau. Vì vậy đối với ảnh đa cấp xám bit LSB của mỗi điểm ảnh là bit cuối cùng của mỗi điểm ảnh. Quá trình tách bit LSB của ảnh đa cấp xám và thay đổi các bit này bằng thuật toán giấu tin trong ảnh đen trắng sẽ làm chỉ số màu của điểm ảnh màu bị thay đổi tăng hoặc giảm 1 đơn vị, do đó điểm ảnh mới sẽ có độ sáng tối của ô màu liền trước hoặc liền sau ô màu của điểm ảnh cũ. Bằng mắt thường rất khó có thể nhận thấy sự thay đổi về độ sáng tối này.Thực nghiệm cho thấy ngay cả khi ta đảo toàn bộ các bit cuối của điểm ảnh trong một ảnh 8 bit cấp xám cũng không gây ra sự khác nhau nhiều. Vì vậy 43 việc trong mỗi khối ảnh ta chỉ thay đổi nhiều nhất 2 điểm ảnh sẽ khiến khả năng phân biệt ảnh gốc và ảnh kết quả là rất khó khăn. 2.4.3.2. Ảnh nhỏ hơn hoặc bằng 8 bit màu: Những ảnh thuộc loại này gồm có ảnh 16 bit màu (4 bit màu) và ảnh 256 màu (8 bit màu ). Khác với ảnh đa cấp xám, ảnh màu với số bit màu nhỏ hơn hoặc bằng 8 không phải luôn luôn được sắp bảng màu. Những màu ở liền kề nhau trong bảng màu có thể rất khác nhau chẳng hạn như màu đen với màu trắng vẫn có thể được xếp cạnh nhau. Vì vậy việc xác định bit LSB của ảnh loại này rất khó. Nếu ta chỉ làm như đối với ảnh xám, tức là lấy bit cuối cùng của mỗi điểm ảnh để tạo thành ảnh thứ cấp thì mỗi thay đổi 0→1 hoặc 1→0 trên ảnh thứ cấp có thể làm cho màu của điểm ảnh cũ và mới tương ứng thay đổi rất nhiều dù chỉ số màu của chúng cũng chỉ tăng hoặc giảm mà thôi. Để khắc phục khó khăn này, ta có thể sắp lại bảng màu của ảnh môi trường sao cho 2 màu liên tiếp khác nhau ít nhất bằng cách so sánh thành phần màu của từng cặp điểm màu với nhau. Tuy nhiên màu của điểm ảnh là một vecto 3 thành phần không sắp thứ tự nên việc so sánh chỉ mang tính chất tương đối . Quá trình sắp lại bảng màu tiến hành như sau : B1: Chọn một màu bất kỳ trong bảng màu, giả sử là màu A(x,y,z) để đưa vào vị trí đầu tiên trong bảng màu trong đó x là thành phần Red, y là thành phần Green, z là thành phần Blue. B2: Duyệt tất cả các màu còn lại trong bảng màu, với mỗi màu B(m,n,p) chưa được sắp ta tính đại lượng s(A,B) = sqrt[(x-m)2 + (y-n)2 + (z-p)2 ] B3: Chọn màu B có s(A,B) nhỏ nhất để xếp cạnh màu A trong bảng màu, quay lại bước 2 để tiếp tục tìm màu chưa được sắp gần với B nhất. 44 B4: Quá trình kết thúc khi mọi màu của bảng màu đã được sắp. Sau khi sắp bảng màu ta lại thay đổi lại chỉ số của mỗi điểm màu trong ảnh màu của điểm không bị thay đổi. Chẳng hạn nếu sau khi sắp lại bảng màu, màu có chỉ số 15 trong bảng màu cũ mang chỉ số mới là 80 trong bảng màu mới thì mọi điểm ảnh có giá trị là 15 phải được đổi thành 80. So với ảnh 16 bit màu hoặc 24 bit màu, ảnh 8 bit màu cũng như ảnh 4 bit màu có vẻ khó giấu thông tin hơn vì việc thay đổi dù chỉ một bit trên một điểm ảnh cũng có thể dẫn đến sự thay đổi nhận thấy được về màu sắc cuả điểm ảnh, cho dù bảng màu của điểm ảnh đã được sắp. Tuy nhiên dựa vào đặc điểm không phải ảnh nào cũng sử dụng tất cả các màu trong bảng màu để hiện thị ảnh ta có thể sử dụng những màu không dùng đến kết hợp với việc sắp bảng màu để làm mịn ảnh kết quả. Để biết những màu nào được dùng, màu nào không dùng đến trong bảng màu ta duyệt toàn bộ các màu trong bảng và đánh dấu những màu có chỉ số xuất hiện trong dữ liệu ảnh. Giả sử trong bảng màu có một màu C không dùng đến với mỗi điểm màu A khi tìm thấy được màu B có sử dụng trong bảng màu để sắp cạnh A mà giá trị s(A,B) vẫn còn lớn hơn một ngưỡng nào đó ta sẽ chèn ô màu C vào ô màu A và B đồng thời đổi lại màu của ô C sao cho giống A và B nhất có thể. Trường hợp số màu được sử dụng nhỏ hơn hoặc bằng 86 màu (đối với ảnh 256 màu) hay nhỏ hơn hoặc bằng 6 (đối với ảnh 16 màu) thì việc sắp lại bảng màu cho ta kết quả giấu tin rất đẹp. Khi đó quá trình sắp lại bảng màu tiến hành theo các bước sau: B1: Duyệt bảng màu để xác định màu nào có được sử dụng, màu nào không được sử dụng. 45 B2: Sắp các màu có sử dụng vào các vị trí thứ 3*k của bảng màu với k=0,1,2,……(vị trí đầu tiên trong bảng màu là vị trí thứ 0). Chèn các ô màu không dùng đến vào các vị trí còn lại của bảng màu. B3: Với mỗi màu A(x,y,z) có sử dụng đến nằm ở vị trí 3*k của bảng màu mới, ta copy màu A vào ô màu nằm ở vị trí 3*k+1 và vào ô màu nằm ở vị trí 3*k-1. B4: Chỉnh lại chỉ số màu của mỗi điểm ảnh để thu được ảnh mới giống hệt ảnh cũ hiển thị. B5: Quá trình sắp lại bảng màu sẽ cho ta một ảnh mới không hề khác ảnh cũ khi hiển thị, tuy nhiên cần có sự khác nhau về mặt giá trị. Tiến hành giấu tin trên ảnh thứ cấp của ảnh vừa thu được bằng cách tách bit cuối cùng trong mỗi điểm ảnh. Việc đảo bit trên ảnh thứ cấp làm cho giá trị của điểm ảnh tăng hoặc giảm 1, tức là điểm ảnh mới sẽ mang màu của ô có chỉ số 3*k+1 hoặc 3*k-1 (giá trị cũ là 3*k), nhưng cả hai ô này đều có màu của ô 3*k nên điểm ảnh mới không hề có sự thay đổi về màu sắc so với điểm ảnh cũ. Như vậy ảnh có kết quả không có nhiễu, tức là ảnh sẽ giống hệt nhau. Một hướng khác đối với giấu tin trong ảnh nhỏ hơn 8 bit màu là ta giấu thông tin vào bảng màu. Tức là 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 bit 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 bit màu, chọn kích thước khối là 10*10, r=4, lấy từ mỗi ô màu ra bit ta sẽ chỉ giấu được một lượng thông tin cực đại là 28 bit bằng thuật toán trên. Tuy nhiên giải pháp này cũng có những hạn chế vì ảnh kết quả có bảng màu đặc biệt, dễ gây ra nghi ngờ bởi sự giống nhau của 3 ô 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 46 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.3.3. Ảnh hi - color (16 bit màu) Ảnh 16 bit màu thực tế chỉ có thể sử dụng 15 bit cho mỗi điểm ảnh trong đó 5 bit biểu diễn cường độ tương đối của màu đỏ, 5 bit biểu diễn cường độ tương đối của màu xanh lam, 5 bit biểu diễn cường độ tương đối của màu xanh lơ. Còn lại một bit không dùng đến là bit cao nhất của byte thứ hai trong mỗi cặp hai byte biểu diễn một điểm ảnh, đó chính là bit LSB của ảnh 16 bit màu. Việc thay đổi giá trị của những bit này sẽ không hề ảnh hưởng tới màu sắc của từng điểm ảnh trong ảnh môi trường. Do đó ta sẽ chọn những bit này để tạo thành ảnh thứ cấp và sau biến đổi thu được ảnh kết quả không hề có nhiễu. Nếu chỉ lấy những bit này để tạo thành ảnh thứ cấp thì lượng thông tin sẽ bị hạn chế. Chẳng hạn một ảnh 256 màu kích thước 200*200 pixel có số màu được sử dụng nhỏ hơn bằng 86 màu sẽ giấu được lượng thông tin bằng lượng thông tin mà một ảnh 16 bit màu cùng kích thước giấu được, trong khi kích thước tính bằng byte của ảnh 256 màu chỉ bằng một nửa của ảnh 16 bit màu. Hơn nữa cả hai ảnh môi trường này đề cho ảnh kết quả không có nhiễu. Để tăng lượng thông tin giấu được trong ảnh 16 bit màu ta có thể lấy nhiều hơn 1 bit từ mỗi điểm ảnh. Nếu đánh số 16 bit của mỗi cặp hai byte biểu diễn một điểm ảnh lần lượt từ bit thấp của byte thứ nhất là 1 tới bit cao nhất của byte này là 8, kế tiếp là bit thấp nhất của byte thứ hai được đánh số 9 cho tới bit cao nhất của byte này là 16, trước hết ta sẽ lấy bit thứ 16, sau đó có thể lấy các bit được đánh số 1,6 và 11 để tạo thành ảnh thứ cấp. Khi trả ảnh thứ cấp cho ảnh môi trường ta cũng theo đúng thứ tự này để trả bit đúng vị trí. 2.4.3.4. Ảnh true color (24 bit màu) Ảnh true color sử dụng 3 byte cho mỗi điểm ảnh, mỗi byte biểu diễn mộ thành phần trong cấu trúc RGB. Trong mỗi byte các bit thấp càng ít ảnh hưởng tới màu của 47 điểm ảnh. Vì vậy các bit cuối cùng của mỗi byte trong phần dữ liệu ảnh là các LSB của ảnh true color. Để tăng lượng thông tin giấu được vào ảnh môi trường, từ mỗi byte của ảnh true color ta sẽ lấy nhiều hơn 1 bit để tạo thành ảnh thứ cấp.Thông thường cũng chỉ nên lấy nhiều nhất là 4 bit cuối cùng của mỗi byte để ảnh không bị nhiễu đáng kể, khi đó lượng thông tin tối đa có thể giấu trong ảnh cũng tăng gấp 4 lần so với lượng thông tin tối đa giấu được trong ảnh đó nếu chỉ lấy 1 bit cuối cùng của từng byte. Nhờ vậy, lượng thông tin giấu được trong ảnh màu tương đối lớn. Chẳng hạn một bức ảnh Kodak Photo CD với độ phân giải 2048*3072 điểm ảnh 24 màu theo định dạng RGB có thể giấu được 180.000 byte dữ liệu nếu tách từ mỗi byte biểu diễn một thành phần màu của một điểm ảnh ra 2 bit. Bằng kết quả thực nghiệm ta thấy rằng việc thay toàn bộ các bit cuối của mỗi byte trong phần dữ liệu của ảnh true color cũng không gây ra sự khác biệt nhiều so với ảnh gốc. Điều này làm ta nghĩ tới việc thay toàn bộ các bit này bởi các bit dữ liệu của thông tin cần giấu và khi đó lượng thông tin giấu được là rất lớn, có thể đạt tới một phần tám kích thước ảnh môi trường. Tuy nhiên, phương pháp thay thế đơn giản này cho độ an toàn không bằng vì để có được thông tin đã giấu chỉ cần tách các bit cuối cùng của mỗi byte ảnh kết quả. Mặc dù vậy, hướng đi này có thể sẽ đem lại nhiều kết quả khả quan nếu khắc phục được yếu điểm về độ an toàn. Một trong những cách giải quyết là sử dụng thêm một khóa thay thế để biến đổi thông tin trước khi giấu và áp dụng giải thuật di truyền (Ran-zan Wang, Chi-Fang Lin, ja-Chen Lin Đại học quốc gia Chiao Tung, Đài loan) . 2.4.4. Kết quả thực nghiệm và đánh giá. Thuật toán giấu thông tin trong ảnh trình bày ở trên cho phép giấu nhiều nhất [log2(mmn+1)] bit dữ liệu vào trong một khối ảnh kích thước m*n, tức là với m*n bit 48 môi trường có thể giấu được [log2(mmn+1)] bit dữ liệu. Do đó với kích thước khối cố định thì tỷ lệ giấu dữ liệu lớn nhất có thể là: mn mnf )1(log2 += Nhận thấy đây là một hàm đơn điệu giảm theo m*n, vì vậy muốn có tỉ lệ giấu tin càng lớn thì m*n càng nhỏ. Tuy nhiên, ta cần lưu ý rằng độ an toàn của thông tin lại phụ thuộc tỉ lệ thuận vào kích thước mà ta dùng: kích thước khối càng lớn độ an toàn càng cao. Do đó tỉ lệ giấu tin sẽ tỉ lệ nghịch với độ an toàn nhưng lại giảm tỉ lệ giấu tin và ngược lại, kích thước khối nhỏ sẽ làm tăng tỉ lệ giấu tin nhưng lại làm giảm độ an toàn. Thông thường ta nên chọn kích thước khối sao cho [log2(mn+1)] = 8 hoặc bằng 4, tức là giấu được 8 hay 4 bit dữ liệu vào mỗi khối ảnh kích thước mn. Dưới đây là một số kết quả thu được đến khi tiến hành giấu tin vào các bức ảnh đen trắng, ảnh màu và ảnh đa cấp xám với kích thước khối bit giấu tin là 16*16, r=8: - Đối với một bức ảnh 8 bit màu kích thước 200*200, mỗi điểm ảnh lấy ra một bit để giấu thông tin vào cho ta giấu khoảng 240 byte. Chất lượng ảnh sau khi giấu có sự thay đổi nhỏ nhưng với thị giác của người thì không thể phân biệt được sự thay đổi đó. - Còn với ảnh 16 bit màu có kích thước 2008200, mỗi điểm ảnh là 2 byte nhưng ta chỉ lấy bit có trọng số cao nhất về phía bên trái của byte thứ 2 để giấu tin. Ảnh có dung lượng khoảng 240 byte giống như ảnh 8 bit màu. Nhưng chất lượng ảnh sau khi giấu không có sự thay đổi nào. - Ảnh 24 bit màu cũng có kích trên, mỗi điểm ảnh được chứa trong 3 byte. Mỗi byte tách ra k bit thì dung lượng ảnh sau khi giấu khoảng 3k*140 bit và chất lượng sau khi giấu có sự thay đổi rất nhỏ. 49 CHƯƠNG 3. THIẾT KẾ VÀ CÀI ĐẶT CHƯƠNG TRÌNH 3.1. Môi trường làm việc. Môi trường làm việc của chương trình là window XP 3.2. Ngôn ngữ thực hiện thuật toán. Việc chọn ngôn ngữ lập trình cho một bài toán cũng là một vấn đề rất quan trọng để giải quyết bài toán vì mỗi ngôn ngữ lập trình có những ưu điểm và nhược điểm nhất định . Chương trình của ta tuy sử dung đối tượng là các ảnh nhưng việc hiển thị ảnh không phải là vấn đề chính, các thao tác nói chung đều dựa trên các bit dữ liệu ảnh với số lượng tương đối lớn. Vì vậy vấn đề thời gian và bộ nhớ cần được lưu ý. Việc lựa chon ngôn ngữ lập trình C++ với trình biên dịch Microsoft Visual C++ làm việc trên môi trường windows là tương đối phù hợp với phạm vi của luận văn này. 3.3. Tổ chức và thực hiện chương trình Chương trình được thiết kế, cài đặt với mục đích thể hiện thuật toán giấu tin trong ảnh đen trắng, trên cơ sở đó phát triển thuật toán cho việc giấu tin trong ảnh màu và ảnh đa cấp xám. Input: - F là ma trận nhị phân cấp m*n được dùng làm môi trường giấu tin. - K là ma trận nhị phân cấp m*n được dùng ma trận khóa để nâng cao độ bảo mật. - W là ma trận trọng số cấp m*n được dùng để nâng cao khả năng giấu tin trong ảnh F. Các thành phần của w ( ký hiệu phần tử hàng i, cột j của ma trận [w]i,j cần thỏa mãn điều kiện: 50 {[w]i,j | i= 1 ,2…m, j=1,2…n} = { 1,2….,q-1} - b là một giá trị nguyên cần giấu vào F. Giá trị của b thỏa mãn điều kiện 0<=b<=q-1.( q là số nguyên thỏa mãn: 2<=q<=m*n). Các ma trận K và ma trận w được sử dụng như là khóa bí mật. Người gửi dùng để giấu tin còn người nhận dùng để lấy thông tin. OutPut : - Ma trận nhị phân F’ cấp m*n ( F’ là ma trận nhị phân sau khi giấu b vào F và F’ khác tối đa hai phần tử) 3.3.1. Qui trình thực hiện chính Phép tách ảnh thứ cấp từ ảnh môi trường Phép tách ảnh thứ cấp từ ảnh môi trường thực hiện việc tách các bit ít đặc trưng nhất của ảnh được chọn lưu vào một file dạng “*.tmp”. Với các bit ảnh 148 bit màu mỗi điểm ảnh chỉ tách ra một bit, với ảnh 16 bit màu, mỗi điểm ảnh cũng chỉ tách ra 1 bit là bit cao nhất của byte thứ 2 trong 2 byte biểu diễn một điểm ảnh. Với ảnh 24 bit màu số bit tách ra từ mỗi byte biểu diễn điểm ảnh được xác định bởi một số nguyên xác định. Giấu tin file văn bản vào ảnh thứ cấp Bằng thuật toán giấu tin trong khối bit của ảnh đen trắng. Phép trả ảnh thứ cấp vào ảnh môi trường. Trả lại các bit từ ảnh thứ cấp sau khi giấu tin vào mỗi điểm ảnh của ảnh môi trường theo đúng trật tự khi lấy ra. Phép giấu thông tin vào ảnh và lấy thông tin từ ảnh kết quả. -Phép tách ảnh thứ cấp từ ảnh môi trường. 51 -Giấu tin từ file văn bản vào ảnh thứ cấp. -Phép trả ảnh thứ cấp vào ảnh môi trường. -Phép tách ảnh thứ cấp từ ảnh sau khi giấu. -Lấy tin từ ảnh thứ cấp và giải mã ra thành file văn bản. 3.3.2. Các giao diện chính của chương trình và kết quả đạt được. Giao diện chính của chương trình: Select Source Image: nút lệnh để tìm đến ảnh môi trường. Select File Text : file thông tin cần giấu. Embed: Nút lệnh dùng để thực hiện giấu tin. Extract : Nút lệnh dùng để lây thông tin đã giấu. 52 Giao diện dùng để lấy thông tin đã giấu. Select Image: chọn đến ảnh kết quả (ảnh sau khi đã chứa thông tin giấu) Select File Key: nút lệnh dùng để chọn khóa giải mã. Extract: thực thi giải mã. 53 Ảnh khi chưa giấu tin. Sau khi giấu đoạn văn bản sau vào bức ảnh: “ chương trình giấu tin trong ảnh sử dụng thuật toán CPT bảo vệ luận văn tốt nghiệp “ 54 Thu được ảnh kết quả sau: Chúng ta thấy ảnh kết quả sau khi giấu tin không thể phát hiện được bằng thị giác của con người. 55 KẾT LUẬN Cùng với giấu thông tin trong audio và giấu thông tin trong video, kỹ thuật giấu thông tin trong ảnh là những hướng nghiên cứu chính của thuật toán giấu thông tin hiện nay và đã đạt được những kết quả khả quan. Mặc dù so với hai kỹ thuật trước, kỹ thuật giấu thông tin trong ảnh bị hạn chế về mặt kích thước của ảnh so với hai kỹ thuật trên. Nhưng ảnh số vẫn được các nhóm nghiên cứu lựa chọn cho việc giấu thông tin vì ảnh số cho phép thực hiện các thao tác tới từng điểm ảnh đơn lẻ. Ngoài ra hệ thống thị giác của con người có khả năng nhạy cảm thấp với những thay đổi nhỏ trong ảnh. Luận văn đã trình bày một số khái niệm liên quan tới việc che giấu thông tin nói chung, cụ thể hơn là giấu thông tin trong ảnh số và cũng trình bày một thuật toán giấu tin trong ảnh đen trắng, trên cơ sở đó phát triển thuật toán cho việc giấu tin trong ảnh màu và ảnh đa cấp xám. Với thuật toán giấu tin trong ảnh mầu thì tính vô hình của thông tin sau khi giấu được đảm bảo, thông qua việc chọn m, n đủ lớn những biến đổi không gây ra sự chú ý đáng kể nào. Ảnh sau khi giấu tin sẽ ít xuất hiện những điểm ảnh có màu sắc khác so với các điểm ảnh xung quanh và với thị giác của con người thì không thể phân biệt được sự khác nhau đó. Tính mạnh mẽ ở đây được hiểu là ảnh sau khi đã giấu thông tin bởi một hệ thống giấu tin nào đó có chịu được các biến đổi trên ảnh không hoặc có chịu được các cuộc tấn công có chủ đích. Đối với cách giấu thông tin ở đây, thì ảnh sau khi giấu sẽ không chịu được các biến đổi trên ảnh, các phép nén ảnh và các cuộc tấn công có chủ đích gì. Nếu thực hiện thì thông tin giấu sẽ bị mất đi tính chân thực ban đầu. Do đó phương pháp giấu tin này có tác dụng rất lớn trong phát hiện thông tin có bị xuyên tạc hay không. Còn độ an toàn của thuật toán đã chỉ rõ trong thuật toán giấu thông tin trong khối bit của ảnh đen trắng đã chứng minh với m, n,r đủ thuật toán trên đảm bảo độ an toàn rất cao. 56 Do kiến thức còn hạn chế và thời gian nghiên cứu ngắn nên tôi chỉ tập trung vào nghiên các kỹ thuật giấu tin trong ảnh BMP(bitmap) vì đây là loại ảnh được sử dụng rộng rãi nhất trong giấu tin mật. Trong luận văn này không tránh khỏi thiếu sót, vì vậy rất mong nhận được sự góp ý của các thầy, cô giáo và các bạn. Hà Nội, ngày13 tháng4 năm 2009 SINH VIÊN Nguyễn Thanh Cường 57 TÀI LIỆU THAM KHẢO 1. Luận án tiến sĩ toán học: Phát triển một số kỹ thuật giấu dữ liệu trong ảnh. Ứng dụng trong trao đổi thông tin. 2. Đồ án tốt nghiệp đại học: Thiết kế và cài đặt qui trình giấu tin trong ảnh màu - Phạm Văn Hoà. 3. Đồ án tốt nghiệp đại học: Xây dựng hệ thống bảo mật bằng kỹ thuật giấu tin - Trần Giang Nam. 4. M. Wu, J. Lee. A novel data embedding method for two – color Fastcimile image. In Proceeding of international symposium on multimedia information processing. Chung- Li, Taiwan, R.O.C, 1998. 5. D. Kohn. The Codebreakers: the story of Select Writing. Scribner, New Ỷok, 1996. 6. Yu-Yuan Chen, Hsing-kuang Pan, and Yu-Chee Tseng. A secure Data Hiding Scheme for Two- Color Images. Taiwan