1. Cây hậu tố tổng quát và bài toán LCS

Cây hậu tố là một cấu trúc dữ liệu đặc biệt rất có ích đối với một số bài toán tổ hợp liên quan đến các xâu [1]. Khái niệm này do Weiner đưa ra vào năm 1973 nhưng ông lại không sử dụng tên này mà gọi là cây vị trí (position tree) [1,2]. Cây hậu tố có rất nhiều ứng dụng, trong đó các bài toán về xâu con là một trong những ứng dụng cổ điển. Một số định nghĩa và ký hiệu trong bài báo như sau: Cho S là một xâu với độ dài m. S[i, j] được gọi là xâu con của S từ vị trí i đến vị trí j.

Định nghĩa: Cây hậu tố T của xâu S gồm m kí tự là một cây có hướng, có gốc chứa đúng m là được đánh số từ 1 tới m. Mỗi một nút bên trong cây, khác với nút gốc, có ít nhất hai con và mỗi cạnh được gán nhãn bởi một xâu con không rỗng của S. Không có hai cạnh nào đi ra từ một nút mà có nhãn của cạnh bắt đầu bằng cùng một kí tự. Đặc điểm quan trọng của cây hậu tố đó là, với bất kì lá i nào, nhãn của cạnh trên đường từ gốc tới lá i chính là hậu tố của S bắt đầu từ vị trí i, tức là S[i..m]. [1]

Nhãn đường của nút v (L(v)) là xâu con được gán nhãn cho cạnh bắt đầu từ gốc và kết thúc tại nút đó, hay chính là nhãn của đường từ gốc của cây tới nút đó. [2]

Độ sâu của một nút: Với mỗi nút v của một cây hậu tố, độ sâu của nút v là độ dài của L(v) (tức là số kí tự trên đường). [2]

Hình 1 minh họa một cây hậu tố đối với xâu S = xtpxtd [4]

Hình 1. Cây hậu tố đối với xâu S = xtpxtd. 

Rõ ràng với định nghĩa về cây hậu tố thì đôi khi không đảm bảo luôn tồn tại một cây hậu tố đối với các xâu bất kì. Vì một hậu tố của S lại chính là tiền tố của một hậu tố khác. Khi đó đường đi của hậu tố này sẽ không kết thúc tại một lá, như vậy không phù hợp với định nghĩa đã đưa ra vì số lá sẽ ít hơn số kí tự của xâu. Để tránh điều này trước khi xây dựng cây hậu tố cho một xâu, người ta thường thêm vào cuối xâu một kí hiệu mà không hề xuất hiện trong xâu đó và gọi là kí hiệu kết thúc, giả sử đó là $. Ví dụ, cây hậu tố đối với xâu S = xtpxt, thì dễ thấy hậu tố xt là tiền tố của hậu tố xtpxt nên đường đi của hậu tố xt không kết thúc tại một lá và khi đó số lá không phải là 5, mà chỉ là 3 như hình 2 dưới đây.

Hình 2. Cây hậu tố đối với xâu S = xtpxt. 

Có một số thuật toán xây dựng cây hậu tố với thời gian thực hiện là tuyến tính được đưa ra như thuật toán của Weiner năm 1973, thuật toán của McCreight và gần đây nhất là thuật toán của Ukkonen. Trong đó thuật toán của Ukkonen được xem là có nhiều ưu điểm nhất vì nó mang lại sự hiệu quả về không gian để xây dựng cây hậu tố, mặt khác nó giải thích đơn giản hơn các thuật toán còn lại. [2]

Từ cây hậu tố, đưa ra khái niệm cây hậu tố tổng quát, đó là một cây hậu tố biểu diễn tất cả các hậu tố của một tập các xâu [4]. Để xây dựng cây hậu tố tổng quát cho một tập các xâu {S1, S2, …, Sn} thì trước tiên phải thêm các kí hiệu $ vào cuối mỗi xâu Si (i = 1..n) rồi xây dựng cây hậu tố tổng quát đối với xâu S = S1$1… Sn$n. Khi đó, mỗi lá không còn kí hiệu bởi một số tự nhiên nữa mà sẽ là một cặp số (i, j), trong đó i chỉ hậu tố thuộc xâu Si, j chỉ vị trí bắt đầu của hậu tố trong xâu Si. Hình 3 minh họa cây hậu tố tổng quát của 2 xâu S1 = xabxa và S2 = babxba.

Hình 3. Cây hậu tố tổng quát của 2 xâu S1 = xabxa và S2 = babxba.

Bài toán LCS của 2 xâu S1 và S2 với cây hậu tố tổng quát được thực hiện như sau:

• Bước 1: Xây dựng cây hậu tố tổng quát đối với S1 và S2 
• Bước 2: Đánh dấu mỗi nút bên trong v của cây bằng số 1 (hoặc 2) nếu cây con dưới v chứa một lá đối với một hậu tố của S1 (hoặc S2)
• Bước 3: Duyệt cây tìm các nút được đánh số cả 1 và 2 và chọn nút u nào mà có độ sâu lớn nhất và khi đó L(u) chính là xâu con dài nhất

Trở lại với ví dụ trên, xâu con dài nhất của hai xâu S1 = xabxa và S2 = babxba chính là L(W4) = abx như minh họa trong hình 4 dưới đây.

Hình 4. Cách thực hiện bài toán LCS đối với hai xâu S1 = xabxa và S2 = babxba

2. Áp dụng bài toán LCS dựa trên cây hậu tố tổng quát vào ẩn mã

Ẩn mã là việc giấu thông tin trong một phương tiện chứa hay còn gọi là vật phủ theo cách nếu không phải người nhận thực sự thì không thể biết được sự tồn tại của thông tin đã được giấu. Do vậy khi thực hiện ẩn mã, người gửi thường sẽ phải sửa vật phủ và thông tin trao đổi là các thông báo giữa người gửi và người nhận. Đôi khi để tăng độ an toàn, người gửi có thể kết hợp với một phương pháp mật mã nào đó nhằm mã hóa thông báo trước rồi mới ẩn vào trong vật phủ. Như vậy kẻ tấn công dù có phát hiện và trích xuất ra được thông báo từ vật có ẩn tin đi nữa thì chưa chắc đã biết được nội dung thực sự đang được trao đổi. Tuy nhiên, tất cả cách làm này vẫn làm thay đổi vật phủ, do đó có thể bị phát hiện bởi các phương pháp tấn công thống kê, phân tích cặp mẫu,… Điều đó cũng có nghĩa là kĩ thuật ẩn mã đó không an toàn. Vào năm 2011, Khalil Challita và Hikmat Farhat thuộc khoa Khoa học máy tính của trường đại học Notre Dam – Louaize, Lebanon đã đưa ra một phương pháp ẩn mã hoàn toàn mới cũng với ý tưởng kết hợp với mật mã [3]. Các tác giả đã sử dụng ảnh làm vật phủ và không hề thay đổi ảnh phủ như các cách ẩn mã trước đây mà khéo léo tìm ra những xâu bit con giống nhau giữa thông báo và ảnh phủ thông qua việc áp dụng bài toán LCS dựa trên cây hậu tố tổng quát. Đây là một ý tưởng hoàn toàn mới và sáng tạo. Phần tiếp theo của bài báo trình bày chi tiết về cách thức áp dụng bài toán LCS vào phương pháp ẩn mã mới này.

Hình 5 mô tả mô hình ẩn mã kết hợp với mật mã của Khalil Challita và Hikmat Farhat

Hình 5.

Giữa người gửi và người nhận đã thống nhất một tập ảnh phủ từ trước, trong mỗi lần trao đổi, họ sẽ bí mật lựa chọn một trong những ảnh phủ trong tập này. Bài toán LCS ở đây có đầu vào chính là thông báo cần trao đổi và ảnh phủ, còn đầu ra là một vector chứa vị trí các bit bắt đầu và kết thúc của các xâu con giống nhau giữa hai đầu vào này. Trước tiên, người gửi sẽ biểu diễn thông báo và ảnh phủ dưới dạng các xâu bit. Sau đó, người gửi thực hiện xây dựng cây hậu tố tổng quát đối với hai xâu bit vừa nhận được. Bài toán LCS sẽ được áp dụng để tìm ra những xâu bit con giống nhau giữa thông báo và ảnh phủ. Sự sáng tạo của các tác giả khi đề xuất phương pháp ẩn mã này chính là việc lưu lại vị trí bắt đầu và kết thúc của các xâu bit con giống nhau, thay vì lưu chính các bit đó và đây được xem là một sự mã hóa rất thông minh. Nhờ vậy kĩ thuật này không cần gửi đi vật phủ cũng như các bit của thông báo mà chỉ là một vector với những con số khá ngẫu nhiên, do vậy kẻ tấn công không thể nào có thể tìm ra được nội dung thông báo thực sự được trao đổi. Về phía người nhận đã có ảnh phủ nên chỉ đơn giản là tìm các bit trong đó tại các vị trí đã chỉ ra ở vector nhận được để suy ra thông báo cần biết. Dễ thấy rằng, ảnh phủ không hề bị thay đổi một chút nào mặc dù nó vẫn mang được thông tin cần trao đổi, nói cách khác phương pháp ẩn mã hoàn toàn khác biệt so với các cách làm trước đây, có sự ẩn mã nhưng thực chất lại chẳng hề thực hiện ẩn trong vật phủ. Ngoài ra, để an toàn hơn nữa, người gửi cũng có thể mã hóa vector trước khi truyền đi. Dưới đây là thuật toán thực hiện của phương pháp này, còn được gọi là thuật toán dựa trên cách phân tích cú pháp tĩnh (Static Parsing Steganography – SPS):

Trước tiên, thuật toán sẽ kiểm tra xem liệu toàn bộ xâu bit của thông báo có là một xâu bit con của ảnh phủ hay không, nếu đúng thì sẽ lưu các chỉ số bắt đầu và kết thúc của xâu bit con đó vào Vector. Ngược lại nếu không tìm thấy xâu bit con nào trùng khớp với thông báo, thì thuật toán tiếp tục đệ quy để tìm ra một xâu bit con giống nhau trong nửa trái và nửa phải của thông báo với ảnh phủ. Tiếp tục lặp quá trình này cho tới khi tìm ra được tất cả các bit của thông báo khớp với các bit của ảnh phủ. 

Ví dụ 1: Giả sử xâu bit của ảnh phủ là 1000110110011011 và thông báo là 00011011 thì vector đầu ra sẽ là 29 vì xâu bit của thông báo chính là một xâu con xuất hiện bắt đầu ở vị trí thứ 2 và kết thúc tại vị trí thứ 9 trong xâu bit của ảnh phủ.

Ví dụ 2: Xâu bit của ảnh phủ là 1000110110011011 và thông báo là 01101101. Trường hợp này không có một xâu con nào của ảnh phủ giống toàn bộ xâu bit của thông báo nên phải gọi đệ quy thêm 2 lần hàm SPS, đó là SPS(0110, 1000110110011011) trả về giá trị là 47 và SPS(1101, 1000110110011011) trả về giá trị là 58. Vậy vector đầu ra sẽ có giá trị là 4758.

3. Kết luận

Xây dựng cây hậu tố tổng quát là một bài toán rất nổi tiếng và có nhiều ứng dụng khác nhau, đặc biệt trong việc tìm xâu con dài nhất của hai hay nhiều xâu. Kĩ thuật kết hợp ẩn mã và mật mã do Khalil Challita và Hikmat Farhat đưa ra là rất sáng tạo trong việc áp dụng bài toán LCS dựa trên cây hậu tố tổng quát. Kết quả là không những đưa ra được một kĩ thuật ẩn mã mới, khác biệt hoàn toàn so với các kĩ thuật trước đây, mà còn rất hiệu quả trong quá trình cài đặt. Ảnh phủ không hề bị sửa chữa và thông báo thực sự cũng không cần gửi đi trong mỗi lần trao đổi. Tuy vậy, người nhận vẫn trích xuất được thông tin nhờ vector vị trí các bit giống nhau giữa thông báo và ảnh phủ. Như vậy rõ ràng kẻ tấn công khó có thể biết được nội dung mà hai bên đang trao đổi với nhau. Do đó, đây có thể được xem là một phương pháp ẩn mã rất an toàn và hoàn toàn có thể ứng dụng được trong thực tế.