TỔNG QUAN VẤN ĐỀ NGHIÊN CỨU
Các khái niệm cơ bản
Thông tin
Thông tin là một khái niệm trừu tượng, phi vật chất và rất khó được định nghĩa chính xác. Hai định nghĩa về thông tin:
Thông tin là sự cảm hiểu của con người về thế giới xung quanh thông qua sự tiếp xúc với nó.
Thông tin là một hệ thống những tin báo và mệnh lệnh giúp loại trừ sự không chắc chắn (uncertainty) trong trạng thái của nơi nhận tin. Nói ngắn gọn, thông tin là cái mà loại trừ sự không chắc chắn.
Định nghĩa đầu chưa nói lên được bản chất của thông tin. Định nghĩa thứ hai nói rõ hơn về bản chất của thông tin và được dùng để định lượng thông tin trong kỹ thuật.
Thông tin là một hiện tượng vật lý, nó thường tồn tại và được truyền đi dưới một dạng vật chất nào đó. Những dạng vật chất dùng để mang thông tin được gọi là tín hiệu. Lý thuyết tín hiệu nghiên cứu các dạng tín hiệu và cách truyền thông tin đi xa với chi phí thấp, một ngành mà có quan hệ gần gũi với lý thuyết thông tin. Thông tin là một quá trình ngẫu nhiên. Tín hiệu mang tin tức cũng là tín hiệu ngẫu nhiên và mô hình toán học của nó là các quá trình ngẫu nhiên thực hay phức. Và lý thuyết thông tin là lý thuyết ngẫu nhiên của tin tức, có nghĩa là nó xét đến tính bất ngờ của tin tức đối với nơi nhận tin.
Mô hình của các quá trình truyền tin
Khái niệm thông tin thường đi kèm với một hệ thống truyền tin.
Hình 1. 1 Mô hình của các quá trình truyền tin
Sự truyền tin (transmission): Là sự dịch chuyển thông tin từ điểm này đến điểm khác trong một môi trường xác định.
Nguồn tin (information source):
Là một tập hợp các tin mà hệ thống truyền tin dùng để lập các bảng tin hay thông báo (message) để truyền tin.
Bảng tin chính là dãy tin được bên phát truyền đi.
Thông tin có thể thuộc nhiều loại như
Một dãy kí tự như trong điện tín (telegraph) của các hệ thống gởi điện tín (teletype system);
một hàm theo chỉ một biến thời gian f(t) như trong radio và điện thoại;
một hàm của thời gian và các biến khác như trong tivi trắng đen – ở đây thông tin có thể được nghĩ như là một hàm f(x, y, t) của toạ độ hai chiều và thời gian biểu diễn cường độ ánh sáng tại điểm (x, y) trên màn hình và thời gian t;
một vài hàm của một vài biến như trong trường hợp tivi màu – ở đây thông tin bao gồm ba hàm f(x, y, t), g(x, y, t), h(x, y, t) biểu diễn cường độ ánh sáng của các ba thành phần màu cơ bản (xanh lá cây, đỏ, xanh dương)
Thông tin trước khi được truyền đi, tuỳ theo yêu cầu có thể được mã hoá để nén, chống nhiễu, bảo mật…
Kênh tin (channel):
Là nơi hình thành và truyền (hoặc lưu trữ) tín hiệu mang tin đồng thời ở đấy xảy ra các tạp nhiễu (noise) phá hủy tin tức.
Trong lý thuyết thông tin kênh là một khái niệm trừu tượng đại biểu cho hỗn hợp tín hiệu và tạp nhiễu.
Môi trường truyền tin thường rất đa dạng:
Môi trường không khí, tin được truyền dưới dạng âm thanh và tiếng nói, ngoài ra cũng có thể bằng lửa hay bằng ánh sáng;
Môi trường tầng điện ly trong khí quyển nơi mà thường xuyên xảy ra sự truyền tin giữa các vệ tinh nhân tạo với các trạm rada ở dưới mặt đất;
Đường truyền điện thoại nơi xảy ra sự truyền tín hiệu mang tin là dòng điện hay đường truyền cáp quang qua biển trong đó tín hiệu mang tin là sóng ánh sáng v.v…
Nhiễu (noise):
Cho dù môi trường nào cũng có nhiễu. Nhiễu rất phong phú và đa dạng và thường đi kèm với môi trường truyền tin tương ứng.
Chẳng hạn nếu truyền dưới dạng sóng điện từ mà có đi qua các vùng của trái đất có từ trường mạnh thì tín hiệu mang tin thường bị ảnh hưởng ít nhiều bởi từ trường này. Nên có thể coi từ trường này là một loại nhiễu.
Nếu truyền dưới dạng âm thanh trong không khí thì tiếng ồn xung quanh có thể coi là một loại nhiễu.
Nhiễu có nhiều loại chẳng hạn nhiễu cộng, nhiễu nhân.
Nhiễu cộng là loại nhiễu mà tín hiệu mang tin bị tín hiệu nhiễu “cộng” thêm vào.
Nhiễu nhân là loại nhiễu mà tín hiệu mang tin bị tín hiệu nhiễu “nhân” lên.
Nơi nhận tin (sink):
Là nơi tiếp nhận thông tin từ kênh truyền và cố gắng khôi phục lại thành thông tin ban đầu như bên phát đã phát đi.
Tin đến được nơi nhận thường không giống như tin ban đầu vì có sự tác động của nhiễu. Vì vậy nơi nhận phải thực hiện việc phát hiện sai và sửa sai.
Nơi nhận còn có thể phải thực hiện việc giải nén hay giải mã thông tin đã được mã hoá bảo mật nếu như bên phát đã thực hiện việc nén hay bảo mật thông tin trước khi truyền
Các loại hệ thống truyền tin
Các nguồn tin thường thấy trong tự nhiên được gọi là các nguồn tin nguyên thuỷ. Đây là các nguồn tin chưa qua bất kỳ một phép biến đổi nhân tạo nào.
Các tín hiệu âm thanh, hình ảnh được phát ra từ các nguồn tin nguyên thuỷ này thường là các hàm liên tục theo thời gian và theo mức, nghĩa là có thể biểu diễn một thông tin nào đó dưới dạng một hàm s(t) tồn tại trong một quãng thời gian T và lấy các trị bất kỳ trong một phạm vi (smin, smax) nào đó.
Hình 1. 2 Các loại hệ thống truyền tin
Các nguồn như vậy được gọi là các nguồn liên tục (continuous source), các tin được gọi là tin liên tục (continuous information) và kênh tin được gọi là kênh liên tục (continuous channel).
Tuy nhiên vẫn có những nguồn nguyên thuỷ là rời rạc
Bảng chữ cái của một ngôn ngữ.
Các tin trong hệ thống điện tín, các lệnh điều khiển trong một hệ thống điều khiển, …
Trong trường hợp này các nguồn được gọi là nguồn rời rạc (discrete source), các tin được gọi là tin rời rạc (discrete information) và kênh tin được gọi là kênh rời rạc (discrete channel).
Sự phân biệt về bản chất của tính rời rạc và tính liên tục là số lượng tin của nguồn trong trường hợp rời rạc là hữu hạn còn trong trường hợp liên tục là không đếm được.
Rời rạc hóa
Các hệ thống liên tục có nhiều nhược điểm của như cồng kềnh, không hiệu quả, và chi phí cao.
Các hệ thống truyền tin rời rạc có nhiều ưu điểm hơn, khắc phục được những nhược điểm trên của các hệ thống liên tục và đặc biệt đang ngày càng được phát triển và hoàn thiện dần những sức mạnh và ưu điểm của nó.
Rời rạc hoá thường bao gồm hai loại: Rời rạc hoá theo trục thời gian, còn được gọi là lấy mẫu (sampling) và rời rạc hoá theo biên độ, còn được gọi là lượng tử hoá (quantize).
Lấy mẫu (Sampling):
Lấy mẫu một hàm là trích ra từ hàm ban đầu các mẫu được lấy tại những thời điểm xác định.
Vấn đề là làm thế nào để sự thay thế hàm ban đầu bằng các mẫu này là một sự thay thế tương đương, điều này đã được giải quyết bằng định lý lấy mẫu nổi tiếng của Shannon.
Định lý lấy mẫu của Shannon
Một hàm s(t) có phổ hữu hạn, không có thành phần tần số lớn hơn có thể được thay thế bằng các mẫu của nó được lấy tại những thời điểm cách nhau một khoảng hay nói cách khác tần số lấy mẫu
Hình 1. 3 Định lý lấy mẫu của Shannon
Lượng tử hoá (Quantize):
Biên độ của các tín hiệu thường là một miền liên tục (smin, smax). Lượng tử hoá là phân chia miền này thành một số mức nhất định, chẳng hạn là smin=s0, s1,…,sn=smax và qui các giá trị biên độ không trùng với các mức này về mức gần với nó nhất.
Việc lượng tử hoá sẽ biến đổi hàm s(t) ban đầu thành một hàm s’(t) có dạng hình bậc thang. Sự khác nhau giữa s(t) và s’(t) được gọi là sai số lượng tử. Sai số lượng tử càng nhỏ thì s’(t) biểu diễn càng chính xác s(t).
Nguồn rời rạc
Nguồn tin liên tục sau khi được lấy mẫu và lượng tử hoá sẽ trở thành nguồn rời rạc.
Chúng ta học chủ yếu các nguồn rời rạc.
Nguồn rời rạc
Một nguồn rời rạc là một bảng chữ cái A gồm m kí hiệu, A={a1, a2, …, am}, với những xác suất xuất hiện p(ai), i = 1,.., m.
Định nghĩa không diễn tả mối quan hệ giữa tin trước và sau trong một bản tin, nên đây được gọi là một nguồn rời rạc không nhớ (discrete memoryless source).
Bảng tin của một nguồn tin rời rạc không nhớ
Là một dãy (có thể vô hạn) các kí hiệu liên tiếp từ bảng chữ cái của nguồn tin, x = (… a–2a–1a0a1a2…)
Trong thực tế bảng tin có bắt đầu và kết thúc cho nên bảng tin là một dãy hữu hạn các kí hiệu, x* = (a1a2 …an)
Hệ thống mã hóa (cryptosystem)
Hệ thống mã hóa (cryptosystem) là một bộ năm (P, C, K, E, D) thỏa mãn các điều kiện sau:
Tập nguồn P là tập hữu hạn tất cả các mẩu tin nguồn cần mã hóa có thể có
Tập đích C là tập hữu hạn tất cả các mẩu tin có thể có sau khi mã hóa
Tập khóa K là tập hữu hạn các khóa có thể được sử dụng
E và D lần lượt là tập luật mã hóa và giải mã. Với mỗi khóa , tồn tại luật mã hóa và luật giải mã tương ứng. Luật mã hóa và luật giải mã là hai ánh xạ thỏa mãn
Tính chất 4 là tính chất chính và quan trọng của một hệ thống mã hóa. Tính chất này bảo đảm một mẩu tin được mã hóa bằng luật mã hóa có thể được giải mã chính xác bằng luật .
Hệ thống mã hóa quy ước (mã hóa đối xứng)
Trong hệ thống mã hóa quy ước, quá trình mã hóa và giải mã một thông điệp sử dụng cùng một mã khóa gọi là khóa bí mật (secret key) hay khóa đối xứng (symmetric key). Do đó, vấn đề bảo mật thông tin đã mã hóa hoàn toàn phụ thuộc vào việc giữ bí mật nội dung của mã khóa đã được sử dụng.
Với tốc độ và khả năng xử lý ngày càng được nâng cao của các bộ vi xử lý hiện nay, phương pháp mã hóa chuẩn (Data Encryption Standard – DES) đã trở nên không an toàn trong bảo mật thông tin. Do đó, Viện Tiêu chuẩn và Công nghệ Quốc gia Hoa Kỳ (National Institute of Standards and Technology – NIST) đã quyết định chọn một chuẩn mã hóa mới với độ an toàn cao nhằm phục vụ nhu cầu bảo mật thông tin liên lạc của chính phủ Hoa Kỳ cũng như trong các ứng dụng dân sự. Thuật toán Rijndael do Vincent Rijmen và Joan Daeman đã được chính thức chọn trở thành chuẩn mã hóa nâng cao (Advanced Encryption Standard – AES) từ 02 tháng 10 năm 2000.
Hệ thống mã hóa khóa công cộng (mã hóa bất đối xứng)
Nếu như vấn đề khó khăn đặt ra đối với các phương pháp mã hóa quy ước chính là bài toán trao đổi mã khóa thì ngược lại, các phương pháp mã hóa khóa công cộng giúp cho việc trao đổi mã khóa trở nên dễ dàng hơn. Nội dung của khóa công cộng (public key) không cần phải giữ bí mật như đối với khóa bí mật trong các phương pháp mã hóa quy ước. Sử dụng khóa công cộng, chúng ta có thể thiết lập một quy trình an toàn để truy đổi khóa bí mật được sử dụng trong hệ thống mã hóa quy ước.
Trong những năm gần đây, các phương pháp mã hóa khóa công cộng, đặc biệt là phương pháp RSA, được sử dụng ngày càng nhiều trong các ứng dụng mã hóa trên thế giới và có thể xem như đây là phương pháp chuẩn được sử dụng phổ biến nhất trên Internet, ứng dụng trong việc bảo mật thông tin liên lạc cũng như trong lĩnh vực thương mại điện tử.
Kết hợp mã hóa quy ước và mã hóa khóa công cộng
Các phương pháp mã hóa quy ước có ưu điểm xử lý rất nhanh và khả năng bảo mật cao so với các phương pháp mã hóa khóa công cộng nhưng lại gặp phải vấn đề khó khăn trong việc trao đổi mã khóa. Ngược lại, các phương pháp mã hóa khóa công cộng tuy xử lý thông tin chậm hơn nhưng lại cho phép người sử dụng trao đổi mã khóa dễ dàng hơn. Do đó, trong các ứng dụng thực tế, chúng ta cần phối hợp được ưu điểm của mỗi phương pháp mã hóa để xây dựng hệ thống mã hóa và bảo mật thông tin hiệu quả và an toàn.
MỘT SỐ THUẬT TOÁN
Hệ thống mã hóa quy ước.
Hệ thống mã hóa quy ước là hệ thống mã hóa trong đó quy trình mã hóa và giải mã đều sử dụng chung một khoá – khóa bí mật. Việc bảo mật thông tin phụ thuộc vào việc bảo mật khóa.
Trong hệ thống mã hóa quy ước, thông điệp nguồn được mã hóa với mã khóa k được thống nhất trước giữa người gửi A và người nhận B. Người A sẽ sử dụng mã khóa k để mã hóa thông điệp x thành thông điệp y và gửi y cho người B; người B sẽ sử dụng mã khóa k để giải mã thông điệp y này. Vấn đề an toàn bảo mật thông tin được mã hóa phụ thuộc vào việc giữ bí mật nội dung mã khóa k. Nếu người C biết được mã khóa k thì C có thể “mở khóa” thông điệp đã được mã hóa mà người A gửi cho người B.
Hình 2. 1 Hệ thống mã hóa quy ước
Phương pháp mã hóa dịch chuyển
Phương pháp mã hóa dịch chuyển là một trong những phương pháp lâu đời nhất được sử dụng để mã hóa. Thông điệp được mã hóa bằng cách dịch chuyển xoay vòng từng ký tự đi k vị trí trong bảng chữ cái.
Trong trường hợp đặc biệt k = 3, phương pháp mã hóa bằng dịch chuyển được gọi là phương pháp mã hóa Caesar.
Hình 2. 2 Mã hóa dịch chuyển
Mã hóa dịch chuyển là một phương pháp mã hóa đơn giản, thao tác xử lý mã hóa và giải mã được thực hiện nhanh chóng. Tuy nhiên, trên thực tế, phương pháp này có thể dễ dàng bị phá vỡ bằng cách thử mọi khả năng khóa . Điều này hoàn toàn có thể thực hiện được do không gian khóa K chỉ có n phần tử để chọn lựa.
Ví dụ: Để mã hóa một thông điệp được biểu diễn bằng các chữ cái từ A đến Z (26 chữ cái), ta sử dụng P = C = K = Z26. Khi đó, thông điệp được mã hóa sẽ không an toàn và có thể dễ dàng bị giải mã bằng cách thử lần lượt 26 giá trị khóa k Î K. Tính trung bình, thông điệp đã được mã hóa có thể bị giải mã sau khoảng n /2 lần thử khóa k Î K.
Phương pháp mã hóa thay thế
Phương pháp mã hóa thay thế (Substitution Cipher) là một trong những phương pháp mã hóa nổi tiếng và đã được sử dụng từ hàng trăm năm nay. Phương pháp này thực hiện việc mã hóa thông điệp bằng cách hoán vị các phần tử trong bảng chữ cái hay tổng quát hơn là hoán vị các phần tử trong tập nguồn P.
Hình 2. 3 Mã hóa thay thế
Đây là một phương pháp đơn giản, thao tác mã hóa và giải mã được thực hiện nhanh chóng. Phương pháp này khắc phục điểm hạn chế của phương pháp mã hóa bằng dịch chuyển là có không gian khóa K nhỏ nên dễ dàng bị giải mã bằng cách thử nghiệm lần lượt n giá trị khóa k Î K. Trong phương pháp mã hóa thay thế có không gian khóa K rất lớn với n! phần tử nên không thể bị giải mã bằng cách “vét cạn” mọi trường hợp khóa k. Tuy nhiên, trên thực tế thông điệp được mã hóa bằng phương pháp này vẫn có thể bị giải mã nếu như có thể thiết lập được bảng tần số xuất hiện của các ký tự trong thông điệp hay nắm được một số từ, ngữ trong thông điệp nguồn ban đầu!
Phương pháp Affine
Nếu như phương pháp mã hóa bằng dịch chuyển là một trường hợp đặc biệt của phương pháp mã hóa bằng thay thế, trong đó chỉ sử dụng n giá trị khóa k trong số n! phần tử, thì phương pháp Affine lại là một trường hợp đặc biệt khác của mã hóa bằng thay thế.
Để có thể giải mã chính xác thông tin đã được mã hóa bằng hàm thì ek phải là một song ánh. Như vậy, với mỗi giá trị phải có nghiệm duy nhất .
Phương trình tương đương với . Vậy, ta chỉ cần khảo sát phương trình .
Định lý: Phương trình có nghiệm duy nhất với mỗi giá trị khi và chỉ khi a và n nguyên tố cùng nhau.
Vậy, điều kiện a và n nguyên tố cùng nhau bảo đảm thông tin được mã hóa bằng hàm ek có thể được giải mã và giải mã một cách chính xác.
Gọi là số lượng phần tử thuộc và nguyên tố cùng nhau với n.
Phương pháp Vigenere
Trong phương pháp mã hóa bằng thay thế cũng như các trường hợp đặc biệt của phương pháp này (mã hóa bằng dịch chuyển, mã hóa Affine,…), ứng với một khóa k được chọn, mỗi phần tử x P ∈ được ánh xạ vào duy nhất một phần tử y ∈ C. Nói cách khác, ứng với mỗi khóa k ∈ K, một song ánh được thiết lập từ P vào C.
Khác với hướng tiếp cận này, phương pháp Vigenere sử dụng một từ khóa có độ dài m. Có thể xem như phương pháp mã hóa Vigenere Cipher bao gồm m phép mã hóa bằng dịch chuyển được áp dụng luân phiên nhau theo chu kỳ.
Không gian khóa K của phương pháp Vigenere Cipher có số phần tử là nm, lớn
hơn hẳn phương pháp số lượng phần tử của không gian khóa K trong phương
pháp mã hóa bằng dịch chuyển. Do đó, việc tìm ra mã khóa k để giải mã thông
điệp đã được mã hóa sẽ khó khăn hơn đối với phương pháp mã hóa bằng dịch
chuyển.
Hình 2. 5 Phương pháp Vigenere
Phương pháp Hill
Phương pháp Hill được Lester S. Hill công bố năm 1929: Cho số nguyên dương
m, Jđịnh nghĩa P=C=(Zn)m. Mỗi phần tử x ∈ P là một bộ m thành phần, mỗi
thành phần thuộc Zn. Ý tưởng chính của phương pháp này là sử dụng m tổ hợp
tuyến tính của m thành phần trong mỗi phần tử x ∈ P để phát sinh ra m thành
phần tạo thành phần tử y ∈ C.
Mã tuyến tính Hamming
Các mã tuyến tính được xây dựng dựa trên các kết quả của Đại số tuyến tính. Sinh viên cần nắm vững các khái niệm về không gian vector, không gian con, sự độc lập tuyến tính, các vector trực giao, các cấu trúc đại số, đặc biệt là cấu trúc trường…đã được giới thiệu ở hầu hết các giáo trình Toán cao cấp (Giải tích và Đại số tuyến tính).
Các khái niệm về mã tuyến tính được trình bày trên trường Galois, là một trường F có số phần tử hữu hạn. Ta ký hiệu trường này là Fq (hay GF(q)) nếu | F | = q.
Ta nhắc lại một số khái niệm về trường Galois:
Với q là số nguyên tố, trường Galois GF(q) là tập ký hiệu F = {0, 1, 2, …, q – 1}, trên đó có hai phép toán cộng Å và nhân Ä modulo q
Đặc biệt khi F là bảng mã nhị phân {0 ,1} với phép toán cộng bit và nhân bit (theomodulo 2) đã biết thì trường Galois GF(2), thường ký hiệu ngắn gọn là F2: Trường F2 là tập F = {0, 1}, trên đó có hai phép toán ‘cộng bit’ và ‘nhân bit’
Để cho thuận tiện, nếu không gây nhầm lẫn, trong các phần sau có thể sử dụng ký hiệu ‘+’ và ‘.’ thông thường thay cho các ký hiệu Å bit và Ä bit, và được hiểu tùy theo ngữ cảnh. Trong giáo trình này, ta chỉ xét các mã nhị phân, vì vậy hầu hết các khái niệm và kết quả chỉ trình bày cho các mã nhị phân trên trường F2. Các khái niệm và kết quả cho các trường GF(q) được mở rộng một cách tương tự.
Mã tuyến tính là một lớp mã được dùng rất phổ biến trong việc chống nhiễu (phát hiện sai và sửa sai). Mã tuyến tính C có mục đích mã hóa các khối tin k bit thành các từ mã n bit trước khi truyền đi, nói cách khác, trong n bit của từ mã truyền đi có k bit chứa thông tin, còn n – k bit là thêm vào (mã hóa) đề chống nhiễu.
Tập tất cả các từ mã độ dài n trên trường GF(q) làm thành một không gian vector n chiều, ký hiệu là , khi đó mỗi vector của không gian này là một từ mã q- phân độ dài n.
Mã tuyến tính Hamming là mã có ma trận H có tính chất giá trị của cột hi bằng i (i = 1, 2, …)
Bổ đề:
Các mã tuyến tính Hamming đều có khoảng cách Hamming d =3. Vì vậy có thể phát hiện sai 2 bits và sửa sai 1 bit.
Xét mã tuyến tính Hamming C(7, 4) có các bit thông tin nằm ở các vị trí 3, 5, 6, 7. Hãy xác định ma trận sinh G của bộ mã.
TÀI LIỆU THAM KHẢO
| [1] | TS. Nguyễn Đức Toàn, Slide bài giảng Lý thuyết thông tin, 2022. |
| [2] | PGS. TS. Nguyễn Văn Định, Bài giảng Cơ sở mã hóa thông tin, Hà Nội, 2015. |
| [3] | Dương Anh Đức và Trần Minh Triết, Mã hóa và ứng dụng, Nhà xuất bản Đại học Cần Thơ, 2003. |
