Các loại mật mã trong truyền số liệu

Mã Huffman

Mã Huffman lợi dụng xác suất xảy ra của các ký tự khác nhau mà gán các từ mã ngắn cho các ký tự có xác suất xảy ra lớn và ngược lại. Thí dụ, thay vì dùng 7 bit để mã tất cả các ký tự như mã ASCII, người ta chỉ gán 2 bit cho chữ E và 10 bit cho chữ Z, bởi lẻ, trong tiếng Anh xác suất xuất hiện chữ E rất lớn so với xác suất xuất hiện chữ Z. Mã này còn có tên Mã phụ thuộc tần số (frequency dependent code)

Với phương pháp này số bit trung bình dùng cho mỗi ký tự sẽ giảm. Nhưng do các mã dài ngắn khác nhau, để máy thu phân biệt được, người ta phải chọn các từ mã ngắn sao cho không trùng với các bit đầu của các từ mã dài hơn. Gọi là tính tiền tô (prefix property).

Giải thuật Huffman: Dưới đây là các bước tạo mã Huffman

- Tương ứng với mỗi dữ kiện liên kết một cây nhị phân chứa duy nhất một nút. Ở mỗi cây ghi tần số xuất hiện mà ta gọi là trọng lượng của cây.

- Tìm hai cây nhẹ nhất. Nếu có nhiều hơn hai, ta chọn ngẫu nhiên hai cây trong số các cây có trọng lượng nhẹ nhất, ghép chúng lại thành một cây đơn với nút gốc mới. Tổng trọng lượng hai cây này là trọng lượng của cây mới.

- Lặp lại các bước cho tới lúc chỉ còn một cây duy nhất.

Các cây ban đầu trở thành các lá của cây nhị phân cuối cùng này. Ta biết rằng đối với cây nhị phân thì chỉ có một đường duy nhất từ gốc cho tới lá. Với mỗi lá, đường từ gốc đến nó chính là mã Huffman tương ứng. Mã này xác định bằng cách ghi trị 0 cho nhánh bên trái và 1 cho nhánh bên phải (hoặc ngược lại).

Thí dụ 1: Thiết lập mã Huffman cho các ký tự A, B, C, D, E với tần số xuất hiện lần lượt là 0,25; 0,15; 0,10; 0,20; 0,30.

(H 3.3a) là cây với 5 nút đơn ban đầu và trọng lượng tương ứng.

(H 3.3b) ghép 2 cây B và C thành một cây mới với trọng lượng là tổng trọng lượng cây B và C (0,25)

Bước tiếp theo ta có thể ghép cây mới hình thành với cây D hay cây A với D. (H 3.3c) ghép cây mới với D để được một cây trọng lượng là 0,45.

(H 3.3d) ghép cây E và A

Cuối cùng, ghép hai cây mới tạo để được một cây duy nhất, Ghi trị 0 và 1 vào các nhánh (H 3.3e).

***SORRY, THIS MEDIA TYPE IS NOT SUPPORTED.***

(H 3.3)

Ta được bảng mã sau:

Ký tự	Mã
ABCDE	011001011100

Chiều dài trung bình của từ mã có thể tính như sau:

0,25*2 + 0,15*3 + 0,10*3 + 0,20*2 + 0,30*2 = 2,25 bít/ký tự

Do có sự chọn ngẫu nhiên khi các dữ kiện có cùng trọng lượng nên kết quả có thể cho các bảng mã khác nhau. Tuy nhiên, kết quả cuối cùng của các bộ mã khác nhau phải cho cùng chiều dài trung bình của từ mã.

Thí dụ 2: Mã hoá giá trị nhiệt độ trong khoảng từ 20° C đến 30° C với xác suất cho trong (H 3.4). Thay vì thực hiện các cây nhị phân như trên, ta có thể dựa vào xác suất của các giá trị nhiệt độ mà lập một đồ họa để thực hiện việc mã hóa sao cho các giá trị có xác suất lớn sẽ dùng từ mã ngắn nhất có thể có.

Các sự kiện (là các giá trị nhiệt độ) được liệt kê theo xác suất giảm dần (H 3.4a)

Ta bắt đầu bằng cách gán hai bít 0 và 1 cho 2 sự kiện có khả năng xảy ra ít nhất, sau đó hai sự kiện này được tổ hợp thành một sự kiện có xác suất bằng tổng hai xác suất của hai sự kiện đó, các sự kiện được sắp xếp theo thứ tự giảm dần và thủ tục lặp lại từ dưới lên và từ trái sang phải cho đến khi hai sự kiện cuối cùng được kết hợp. Từ mã của các sự kiện được viết bằng cách dò theo các đường của sơ đồ theo chiều ngược lại, từ phải qua trái. Cuối cùng ta có bảng mã (H 3.4b)

Từ mã trung bình: 0,21*2 + 0,17*3 + 0,15*3 + 0,12*3 + 0,1*3 + 0,06*4 + 0,05*4 + 0,04*5 + 0,03*6 + 0,02*6 =3,18 bít/sự kiện

Số bit dùng mã hóa đã giảm khoảng 20%.

Một ưu thế của phương pháp Huffman là có thể lập trình để thực hiện việc mã hóa.

Trở lại Thí dụ 1, bây giờ giả sử chuỗi ký tự được phát đi là A B E C A D B C, tương ứng với chuỗi bit 01100001010111100101, máy thu khi nhận được chuỗi dữ liệu sẽ thực hiện việc giải mã như thế nào ?

Nhờ vào tính tiền tố của các mã, máy thu sẽ lần lượt đọc các bit cho tới khi gặp một chuỗi con các bit tương ứng với một mã sẽ dừng lại, giải mã ký tự này, sau đó tiếp tục đọc chuỗi dữ liệu kế tiếp để tìm ra ký tự thứ hai. . .

(a) (b)

(H 3.4)

Mã Run length

Mã Huffman tuy có làm giảm số bit truyền đi nhưng nó đòi hỏi dữ liệu phải được tập hợp thành từng nhóm hay ký tự để xác định tần số lặp lại của các nhóm hay ký tự này. Việc này đôi khi rất khó thực hiện đối với một số loại dữ liệu thí dụ như dữ liệu từ một bản fax, tín hiệu mã hình ảnh . . .

Lấy thí dụ trường hợp bản fax, dữ liệu được phát đi không phải là các ký tự mà là các bit tương ứng với điểm sáng tối trên tờ giấy, như vậy phải có một kỹ thuật phù hợp để nén chuỗi dữ liệu này, đó chính là mã Run length.

Mã Run length được tạo ra bằng cách quan sát chuỗi bit 0 (hoặc 1) liên tiếp và thay thế chiều dài chuỗi bit này bởi một số nhị phân. Ở máy thu khi nhận được các số

nhị phân sẽ thay các số này bởi các bit 0 (hoặc 1) đồng thời chèn các bit khác loại vào.

Thí dụ ta phải tạo mã Run length cho chuỗi dữ liệu sau bằng cách dùng số 4 bit thay cho số bit 0 liên tiếp:

Dòng dữ liệu 0 . . . 0 1 0 . . . 0 1 1 0 . . . 0 1 0 . . . 0 1 1 0 . . . 0 91 bit

Số bit 0 liên tiếp 14 9 20 30 11

Run length (nhị phân) 1110 1001 0000 1111 0101 1111 1111 0000 0000 1011 40 bit

Run length (thập phân) 14 9 0 15 5 15 15 0 0 11

Nhận xét cách tạo mã :

- 1 bit 1 giữa các chuỗi bit 0 sẽ không được mã, máy thu tự động chèn bit 1 này vào khi phục hồi dữ liệu.

- Nếu có 2 bit 1 liên tiếp, ta xem như có 1 chuỗi gồm không bit 0 giữa 2 bit 1 này và phải được thay thế bởi số 0000.

- Nếu số số 0 nhiều hơn 15 ta phải dùng 2 số nhị phân thay cho chuỗi này (20=15+5; 30=15+15). Ở máy thu khi gặp chuỗi bốn bit 1 nó phải hiểu là phải lấy tổng số này với các số phía sau, nếu số sau cùng cũng gồm 4 bit 1, máy thu phải được báo bằng chuỗi 4 bit 0 theo sau (trường hợp sau số 30)

- Nếu chuỗi dữ liệu bắt đầu bằng bit 1 thì máy phát sẽ gửi đi 4 bit 0 đầu tiên.

- Ở cuối bản tin máy phát sẽ gửi tín hiệu báo chấm dứt bản tin và nhờ đó máy thu biết cách xử lý cho trường hợp bản tin kết thúc bởi chuỗi bit 0 hay bit 1.

Kỹ thuật nén này chỉ có hiệu quả khi chuỗi dữ liệu chứa rất nhiều một loại bit.

Ngoài ra, kỹ thuật nén Run length cũng được dùng mã hóa các chuỗi ký tự giống nhau bằng cách thay mỗi chuỗi ký tự liên tiếp bằng con số chỉ độ dài đứng trước ký tự đó.

Thí dụ, với chuỗi

HHHHHFFFFFFFFYYYYYYYYYYYYYGGGGGGGGGG

Sẽ có mã là: 5H8F13Y10G

Mã vi phân (Differential encoding)

Còn gọi là mã tương đối (Relative encoding)

Trong nhiều trường hợp, các dữ liệu liên tiếp nhau thay đổi rất ít . Thí dụ trường hợp mã tín hiệu hình ảnh trong kỹ thuật video, do phải xử lý 30 bán ảnh (khung) trong một giây để tạo ảnh động, nên chi tiết của các ảnh không khác nhau bao nhiêu, thay vì phải nén tín hiệu từng khung người ta nghĩ tới việc xác định sự khác nhau của các khung liên tiếp, mã thông tin này và gửi đi.

Nguyên tắc của mã vi phân như sau: khung thứ nhất được phát đi đồng thời lưu ở bộ đệm của máy phát và thu. Máy phát sẽ so sánh khung thứ hai với khung thứ nhất này, mã sự khác biệt và phát đi dưới dạng một khung. Máy thu khi nhận khung thứ hai, nhờ các mã chỉ sự khác biệt mà so sánh với khung thứ nhất (đã lưu trước đó) để tái tạo khung thứ hai, đồng thời nó lưu khung thứ hai này trong bộ đệm và quá trình tiếp tục với các khung mới.

(H 3.5) là một thí dụ minh họa.

5 7 6 2 8 6 6 3 5 66 5 7 5 5 6 3 2 4 78 4 6 8 5 6 4 8 8 55 1 2 9 8 6 5 5 6 65 5 2 9 9 6 8 9 5 1Khung thứ nhất	5 7 6 2 8 6 6 3 5 66 5 7 6 5 6 3 2 3 78 4 6 8 5 6 4 8 8 55 1 3 9 8 6 5 5 7 65 5 2 9 9 6 8 9 5 1Khung thứ nhì	5 7 6 2 8 6 6 3 5 66 5 8 5 5 6 3 3 3 78 4 6 8 5 6 4 8 8 55 1 3 9 7 6 5 5 8 65 5 2 9 9 6 8 9 5 1Khung thứ ba
	0 0 0 0 0 0 0 0 0 00 0 0 1 0 0 0 0 -1 00 0 0 0 0 0 0 0 0 00 0 1 0 0 0 0 0 1 00 0 0 0 0 0 0 0 0 0Khung phát đi là sai biệt giữa khung thứ nhì và khung thứ nhất	0 0 0 0 0 0 0 0 0 00 0 1 0 0 0 0 1 0 00 0 0 0 0 0 0 0 0 00 0 0 0 -1 0 0 0 1 00 0 0 0 0 0 0 0 0 0Khung phát đi là sai biệt giữa khung thứ ba và khung thứ nhì

(H 3.5)

Dữ liệu gồm các số nguyên được biểu diễn trong một khung 2 chiều, chúng không mang một ý nghĩa cụ thể nào, mục đích của thí dụ là để hiểu cách tạo mã. Khung thứ nhất chứa một tập hợp các số nguyên và khung thứ hai chứa một tập hợp các số nguyên khác khung thứ nhất một ít.

Trong hình, các khung nằm dưới khung thứ hai và thứ ba là khung chứa các mã vi phân, số 0 chỉ không có sự khác biệt dữ liệu của 2 khung, số 1 chỉ dữ liệu khung sau lớn hơn khung trước 1 đơn vị và số -1 chỉ ngược lại. Dĩ nhiên có thể sử dụng các số khác hơn là 1 và -1.

Thí dụ cho ta thấy sự xuất hiện một chuỗi dài các bit 0 và có thể được nén nhờ phương pháp Run length.

Mã Caesar (Caesar cipher)

Còn gọi là mã mẫu tự đơn (mono-alphabetic cipher)

Đây là loại mật mã có sớm nhất và đơn giản nhất. Người ta sẽ thay các ký tự của bản tin bằng các ký tự khác theo một qui luật nào đó, thí dụ bằng cách cộng một số nguyên vào mã ASCII của các ký tự ta sẽ có một bản tin mật. Thí dụ cộng 1 vào mã ASCII ta sẽ có ký tự B thay cho A, C thay cho B . . . . Và nơi nhận sẽ giải mã bằng cách trừ 1 cho các mã nhận được trước khi tra bảng mã ASCII.

Vì giải thuật tạo mã quá đơn giản nên bản tin có thể được giải mã một cách dễ dàng mà không cần biết trước khóa. Thí dụ, trong tiếng Anh, các ký tự E, T, O và N là các ký tự thường xuất hiện nhiều lần trong các văn bản nên khi gặp bản mã người ta có thể thay các ký tự lặp lại nhiều lần bằng các ký tự này. Sau vài thử nghiệm có thể thấy được qui luật và suy ra bản tin.

Để minh họa, giả sử một người nhận được bản tin sau:

{;RSDRSFF,PMRUYP,UNSMLSVVPIMY$234567890

Trước nhất người ta liệt kê các ký tự thường xảy ra : (7 lần), S (4 lần), R, P và M (3 lần), như vậy người ta có thể thay thử các ký tự S, R, P, M bởi E, T, O, A và N (in đậm):

{;EADEAFF,ONEUYO,UNANLAVVOINY$234567890

Tiếp tục, người ta có thể nghĩ là trong một văn bản luôn có các khoảng trống, như vậy thử thay các dấu bằng các khoảng trống, bản tin thành

{;EADEAFF ,ONEU YO ,U NANL AVVOINY $234567890

Nhận xét tiếp các từ chứa ít ký tự như AFF và YO, trong tiếng Anh, từ 3 ký tự mà hai ký tự sau giống nhau khiến ta nghĩ đến từ ADD và từ 2 ký tự kết thúc bằng O khiến ta nghĩ tới từ TO. Thay vào ta lại được bản tin:

{;EADEADD ,ONEU TO ,U NANL AVVOINY $234567890

Cho tới đây, dường như ta đã đi được một đoạn đường khá dài để sắp tới đích, thêm vài lần thử người ta có thể tìm ra bản tin.

PLEASE ADD MONEY TO MY BANK ACCOUNT #123456789

Một phương pháp khác để tạo mã mẫu tự đơn có tên là Polybius square. Mẫu tự I và J được kết hợp lại và được xử lý như một từ đơn, để tổng số mẫu tự là 25. 25 mẫu tự lại được chia thành dãy 5x5. Mỗi mẫu tự sẽ được mã bởi một cặp số tương ứng với hàng và cột trong bảng mã

	1	2	3	4	5
12345	AFLQV	BGMRW	CHNSX	DIJOTY	EKPUZ

Thí dụ bản văn N O W I S T H E T I M E

33 43 25 42 34 44 32 51 44 42 23 51

Mã đa mẫu tự (Poly-alphabetic cipher)

Để tránh việc lặp lại các ký tự trong bản mật mã, người ta dùng loại mã đa mẫu tự, tương tự mã Caesar, mỗi ký tự cũng được thay bởi một ký tự khác, nhưng các ký tự giống nhau không phải được thay bằng một ký tự duy nhất, mà sẽ được thay bằng các ký tự khác nhau tùy theo vị trí của nó.

Một thí dụ của mã đa mẫu tự là mã Vigenère

Dùng một mãng 2 chiều của các ký tự, trong đó mỗi hàng chứa các mẫu tự theo Alphabet nhưng thứ tự trong từng hàng khác nhau:

Thí dụ

Cột 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Hàng 0 A B CD E FGH I J K L M N O P Q R S T U V W X Y Z

Hàng 1 B C DE FGH I J K L M N O P Q R S T U V W X Y Z A

Hàng 2 C DE F GH I J K L M N O P Q R S T U V W X Y Z A B

Hàng 3 D E FG H I J K L M N O P Q R S T U V W X Y Z A B C

. . . . . . .

. . . . . . .

Hàng 24 Y Z AB C D E FGH I J K L M N O P Q R S T U V W X

Hàng 25 Z AB C D E FGH I J K L M N O P Q R S T U V W X Y

Cột 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1920 21 22 23 24 25

Để thay thế một ký tự, gọi i là vị trí tương đối của nó trong bản tin (bắt đầu là vị trí 0) và j là vị trí tương đối của nó trong thứ tự Alphabet. Gọi V là mãng, ký tự sẽ được thay bằng một ký tự trong V[ i mod 26,j ].

Thí dụ dùng mãng ở trên để thay các chữ THE trong bản tin ở các vị trí 25, 54 và 104. Ta lập bảng thay thế như sau:

Ký tự cần thay	Vị trí i	i mod 26	Vị trí j	Ký tự phải thay
THETHETHE	252627545556104105106	2501234012	197419741974	S (h25, kt19)H (h0, kt7)FVKITIG

Như vậy các ký tự THE ở các vị trí khác nhau trong bản tin đã lần lượt được thay bởi SHF, VKI và TIG.

Mặc dù đã giải quyết được sự lặp lại, nhưng xét kỹ chúng ta vẫn thấy rằng có một qui luật mà người ta vẫn có thể nhận ra đó là khoảng cách của các ký tự của cùng một mã là như nhau do tính tuần hoàn của mãng mẫu tự mà chúng ta sử dụng và do bài toán mod 26 (khoảng cách trong mã ASCII của S & H, V & K và T & I đều là 11).

Để khắc phục điều này người ta có thể tăng số hàng của mãng ký tự lên, nhưng như vậy đưa đến kết quả là khóa có thể quá dài (thậm chí dài hơn bản tin), khó khăn cho việc phát và lưu trữ một cách an toàn.

Mã chuyển vị (Transposition cipher)

Người ta sẽ sắp xếp lại thứ tự các ký tự của bản văn bằng cách lưu chúng trong một mãng 2 chiều m cột, m ký tự đầu tiên sẽ cho vào hàng thứ nhất, m ký tự kế tiếp cho vào hàng thứ hai, và cứ thế tiếp tục cho hết bản tin, sau đó hoán đổi vị trí các cột theo thứ tự mới, giả sử p₁, p₂ . . . p_m. Sự hoán đổi có thể thực hiện một cách ngẫu nhiên hoặc theo một qui luật định trước. Bản tin sẽ được truyền đi theo thứ tự từ p₁, p₂ . . . đến p_m

Thí dụ bản tin cần phát:

MISS PIGGY KERMIT ANIMAL AND FOZZIE BEAR

Giả sử dùng mãng 5 cột 1 2 3 4 5, Bản tin được đưa vào mãng như sau:

Số cột

1	2	3	4	5
MPIIAO	IIKTMNZB	SGEADZE	SGRALIA	YMNFER

Sắp xếp lại các cột theo thứ tự 2, 4, 3, 1, 5, ta được bản tin:

IIKTMNZBSGRAL IASGE ADZEMP IIAO (2 khoảng trống) YMN FER

Rõ ràng là bản tin đã mã hóa không còn một dáng dấp nào của bản tin ban đầu. Nhưng phương pháp vẫn còn khuyết điểm là sự lặp lại của các ký tự. Nếu kẻ gian xác định được mật mã đã dùng là loại chuyển vị thì khả năng giải được mã không khó lắm (nhất là có phương tiện tin học trong tay).

Mã DES (Data Encryption Standard)

Mã DES được phát triển bởi IBM vào những năm đầu thập niên 70, đã được chính phủ cho phép xem như chuẩn trong việc tạo mật mã dùng trong thương mại và những tin tức không coi là bí mật và người ta đã chế tạo các chip VLSI để thực hiện viêc tạo mã nhanh hơn.

DES chia bản tin ra thành từng khối 64 bit và dùng khóa 56 bit để thực hiện quá trình tạo mã rất phức tạp bao gồm các kỹ thuật như chuyển vị, thay thế, toán tử EX-OR và vài xử lý khác để tạo nên một bản mã 64 bit.

Tiến trình thực hiên gồm:

- Bước 1: Chuyển vị 64 bit dữ liệu và 56 bit khóa

- Bước 2 gồm 16 lần thực hiện sự mã hóa tương tự nhau nhưng với các khóa khác nhau, dữ liệu ra của lần thực hiện trước sẽ là dữ liệu vào của lần thực hiện sau.

- Bước 3: Trộn 32 bit đầu và 32 bit cuối

- Bước 4: Thực hiện lần chuyển vị cuối cùng.

(H 3. 6) mô tả các bước tạo mã của DES

***SORRY, THIS MEDIA TYPE IS NOT SUPPORTED.***

(H 3.6)

(H 3.7) minh họa một trong 16 lần thực hiện mã hóa

Trong (H 3.7) , các ký hiệu C₆₄ chỉ 64 bit đã được mã hóa, L₃₂ chỉ 32 bit đầu của C₆₄, R₃₂ là 32 bit cuối, K₅₆ là khóa 56 bit. Ngoài ra các ký hiệu như X₄₈ chỉ chuỗi dữ liệu 48 bit có được từ một tác vụ trung gian trước đó. Lưu ý là để đơn giản, chúng ta chỉ dùng cùng 1 ký hiệu cho các chuỗi dữ liệu ra của cùng 1 tác vụ, nhưng các chuỗi này là khác nhau (Thí dụ, cùng dùng ký hiệu X₆ cho các chuỗi dữ liệu ra từ mạch chia nhóm, nhưng các chuỗi ra từ các mạch khác nhau thì khác nhau).

Như (H 3.7) mô tả, đầu tiên, người ta chia 64 bit ra làm đôi, 32 bit đầu ký hiệu L₃₂ và 32 bit còn lại là R₃₂. Tiếp theo chuỗi R₃₂ được mở rộng thành 48 bit (R₄₈) bằng cách chuyển vị và nhân đôi một số bit (Ta ký hiệu R₄₈ để nhấn mạnh rằng chuỗi này được dẫn xuất từ R₃₂). Đồng thời khóa 56 bit cũng được phân làm đôi và thực hiện việc quay vòng cho mỗi nhóm (số lần quay tùy theo giải thuật ở từng bước mã hóa khác nhau), sau đó thực hiện chuyển vị, chuỗi bit ra ký hiệu là K₅₆. Bước tiếp theo là thực hiện hàm EX-OR cho R₄₈ và K₅₆, kết quả là chuỗi X₄₈, chuỗi này lại được phân thành 8 nhóm 6 bit (X₆) rồi thực hiện việc thay thế để giảm xuống thành các nhóm 4 bít (X₄) sau đó tổ hợp 8 nhóm này để thành chuỗi X₃₂. X₃₂ lại được EX-OR với L₃₂, kết quả là X₃₂. Cuối cùng chuỗi X₃₂ tổ hợp với chuỗi bit R₃₂ để cho mã 64 bit (C₆₄).

(H 3.7)

Tóm lại, giải thuật để có được một bản tin mật rất là phức tạp, nhưng như thế vẫn chưa chắc đã bảo mật tuyệt đối được bản tin. Ngoài ra, việc qui ước với nhau cách tạo các khóa hoặc cách thông tin cho nhau về các khóa cũng phải được thực hiện sao cho bí mật phải được bảo đảm. Vấn đề bảo mật còn rất nhiều điều phải nghiên cứu.