Giáo trình Lý thuyết thông tin - Vũ Vinh Quang

iệu năm để phân tích 
một số cĩ 200 chữ số ra thừa số. 
ðộ an tồn của thuật tốn RSA dựa trên cơ sở những khĩ khăn của việc 
xác định các thừa số nguyên tố của một số lớn. 
5.4.3 Hệ mã Rabin 
ðây là hệ mật cĩ độ an tồn cao về mặt tính tốn chống lại được cách tấn 
cơng bản rõ 
126 
Thuật tốn 
Tạo khố: Mỗi thực thể tạo một khố cơng khai và một khố riêng tương ứng. 
Mỗi thực thể A cần thực hiện các cơng việc sau: 
1. Tạo hai số nguyên tố lớn p và q cĩ cỡ xấp xỉ nhau. 
2. Tính n=p×q. 
3. Khố cơng khai của A là n, khố riêng của A là (p,q). 
Mã hố: B mã hố văn bản m gửi cho A. 
1. Nhận được khố cơng khai xác thực của A là n. 
2. Biểu diễn đoạn văn bản là một số nguyên trong miền: {0, 1, . . , n-1} 
3. Tính c = m2 mod n. 
4. Gửi bản mã c cho A. 
Giải mã: Khơi phục bản rõ m từ c, cần phải dùng thuật tốn tìm căn bậc hai 
theo modulo n từ số nguyên tố p và q đã cho để tính ra 4 căn bậc hai m1, m2, 
m3 và m4 của c theo modulo n. Khi đĩ văn bản đã gửi là một trong các giá trị 
m1, m2, m3 hoặc m4. A bằng cách này hay cách khác quyết định đâu là m. 
Chú ý : Giả sử p và q đều được chọn sao cho ≡ 3 (mod 4) thì việc tính tốn 4 
căn bậc 2 của c theo modulo n được thực hiện đơn giản theo thuật tốn sau: 
+ Sử dụng thuật tốn Euclid mở rộng để tìm số nguyên a và b thoả mãn 
a×p + b×q = 1. Chú ý rằng a và b cĩ thể được tính chỉ 1 lần trong suốt 
quá trình tạo khố. 
+ Tính r = c(p + 1)/4 mod p. 
+ Tính s = c(q + 1)/4 mod q. 
+ Tính x = (aps + bqr) mod n. 
+ Tính y = (aps - bqr) mod n. 
+ Bốn căn bậc 2 của c theo modulo n lần lượt là x, -x mod n, y và -y 
mod n. 
127 
Ví dụ 
Tạo khố: Chọn số nguyên tố p = 277, q = 331, tính n = p×q = 91687. Khố 
cơng khai của A là n = 91687, khố riêng là (p = 277, q= 331). 
 Mã hố: Giả sử rằng 6 bit cuối cùng của văn bản gốc là quy định để tái tạo 
trước khi mã hố. Yêu cầu mã hố 10 bit văn bản m = 1001111001, B tái tạo 
lại 6 bit cuối cùng của m để thu được 16 bit văn bản m = 1001111001111001, 
biểu diễn ở dạng thập phân là m = 40569 sau đĩ B tính c = m2 mod n = 405692 
mod 91687 = 62111. 
Giải mã: ðể giải mã c, A dùng thuật tốn tính được 4 căn bậc hai của c mod n 
là m1 = 69654, m2 = 22033, m3 = 40569, m4 = 51118 biểu diễn ở dạng nhị 
phân là: 
m1 = 10001000000010110, m2 = 101011000010001 
m3 = 1001111001111001, m4 = 1100011110101110 
Ta thấy chỉ m3 cĩ phần mở rộng quy định, khi đĩ A tiến hành giải mã c 
(hay m3 ) để khơi phục văn bản gốc m = 1001111001. 
Tính bảo mật của hệ mã khố cơng khai Rabin 
Do việc phân tích n thành thừa số là rất khĩ nên lược đồ mã khố cơng 
khai Rabin là minh chứng bảo đảm chống lại sự tấn cơng của đối phương. Tuy 
nhiên, lược đồ mã khố cơng khai Rabin khơng chống lại được sự tấn cơng 
bản mã chọn trước. Mặt hạn chế của lược đồ mã khố cơng khai Rabin là 
người nhận phải lựa chọn chính xác bản rõ từ 4 khả năng. Sự nhập nhằng 
trong giải mã cĩ thể dễ dàng khắc phục trong thực tế bằng cách thêm phần mở 
rộng vào bản rõ trước khi mã hố. Khi đĩ, với xác suất cao, chính xác một 
trong bốn căn bậc 2: m1, m2, m3, m4 của bản mã c sẽ cĩ phần mở rộng này, và 
người nhận sẽ chọn đĩ là bản rõ mong đợi. Nếu khơng cĩ căn bậc 2 nào của c 
cĩ phần mở rộng này thì người nhận từ chối. Nếu phần mở rộng được sử dụng 
128 
như đã nĩi ở trên, lược đồ Rabin khơng dễ bị tấn cơng bằng bản mã chọn 
trước. 
5.4.4 Hệ mã Elgamal 
Hệ mã Elgamal xây dựng dựa trên bài tốn logarithm rời rạc là bài tốn 
được dùng nhiều trong thủ tục mật mã. 
Chúng ta sẽ bắt đầu bằng việc mơ tả bài tốn khi thiết lập trường hữu 
hạn Zp trong đĩ p là số nguyên tố. Nhớ lại rằng nhĩm nhân Z*P là nhĩm cyclic 
và phần tử sinh của Z*P được gọi là phần tử nguyên thuỷ. Bài tốn logarithm 
rời rạc trong Zp là đối tượng trong nhiều cơng trình nghiên cứu và được xem là 
bài tốn khĩ. Khơng cĩ một thuật tốn thời gian đa thức nào cho bài tốn 
logarithm rời rạc, để gây khĩ khăn cho các phương pháp tấn cơng đã biết, p 
phải cĩ ít nhất 150 chữ số và (p-1) phải cĩ ít nhất một thừa số nguyên tố lớn. 
Lợi thế của bài tốn logarithm rời rạc trong xây dựng hệ mã là khĩ tìm được 
các logarithm rời rạc, song bài tốn ngược lấy luỹ thừa lại cĩ thể tính tốn hiệu 
quả theo thuật tốn “bình phương và nhân”. Nĩi cách khác, luỹ thừa theo 
modulo p là hàm một chiều với các số nguyên tố p thích hợp. 
Thuật tốn 
Tạo khố: Mỗi thực thể tạo một khố cơng khai và một khố riêng tương ứng. 
1. Tạo một số nguyên tố p và phần tử sinh α ∈nhĩm nhân Z*P . 
2. Chọn một số nguyên a, 1 ≤ a ≤ p-2, và tính aα mod p. 
3. Khố cơng khai của A là (p, α , aα ); khố riêng là a. 
Mã hố: B mã hố văn bản m gửi cho A. 
1. Thu được khố cơng khai của A (p, α , aα ). 
2. Biểu diễn văn bản như một số nguyên m trong {0,1,...,p-1}. 
3. Chọn ngẫu nhiên một số nguyên k, 1 ≤ k ≤ p-2. 
129 
4. Tính kγ α= mod p và a km ( )δ α= × mod p. 
5. Gửi bản mã c = ( , )γ δ cho A. 
Giải mã: Khơi phục bản rõ m từ c bằng việc tính 1( )γ δ− × mod p. 
Ví dụ 
Tạo khố: Chọn số nguyên tố p=2357 và phần tử sinh α =2∈ Z*2357. A chọn 
khố riêng a = 1751 và tính aα mod p = 21751 mod 2357 = 1185. Khố cơng 
khai của A là (p = 2357, α = 2, aα = 1185). 
Mã hố: ðể mã hố một văn bản m=2035, B chọn ngẫu nhiên một số nguyên 
k = 1520 và tính γ =21520 mod 2357 = 1430, 
δ = 2035×11851520 mod 2357 = 697. B gửi γ =1430 và δ =697 cho A. 
Giải mã: ðể giải mã, A thực hiện tính: m = 872*697 mod 2357 = 2035. 
Chú ý: Một bất lợi của mã hố Elgamal là sự mở rộng của văn bản, bản mã cĩ 
thể dài gấp 2 lần so với bản rõ. Mã hố Elgamal là một trong những lược đồ 
mã hố sử dụng sự ngẫu nhiên trong tiến trình mã hố. Những nguyên tắc cơ 
bản đằng sau kỹ thuật mã hố ngẫu nhiên là sử dụng tính ngẫu nhiên để tăng 
thêm sự bảo mật bằng mật mã của tiến trình mã hố theo một trong các 
phương thức sau: 
1. Tăng dần khoảng trống trong bản rõ một cách phù hợp. 
2. Ngăn ngừa hoặc làm suy giảm sự cĩ hiệu lực của sự tấn cơng bản 
rõ chọn trước thơng qua ánh xạ một - nhiều từ bản rõ đến bản mã. 
Tính bảo mật của mã hố Elgamal 
Vấn đề bẻ khố lược đồ mã hố Elgamal, khơi phục m từ p, α , aα , γ , 
và δ tương đương với giải quyết vấn đề Diff-Hellman. Trên thực tế, lược đồ 
mã hố Elgamal được xem như sự thay đổi khố Diff-Hellman để quyết định 
khố akα , và việc mã hố văn bản bằng tính nhân với khố đĩ. Vì lý do này, 
130 
tính bảo mật của lược đồ mã hố Elgamal được gọi là cơ sở trong vấn đề 
logarithm rời rạc trong Z*P . 
5.4.5 Hệ mã MHK (Merkle -Hellman Knapsack) 
Sơ đồ mã khố cơng khai ba lơ dựa trên cơ sở của bài tốn tập con, quan 
điểm cơ bản là chọn một trường hợp của bài tốn tổng con mà dễ dàng tìm lời 
giải, sau đĩ che giấu nĩ như một trường hợp của bài tốn tổng con tổng quát 
khĩ cĩ hy vọng giải được. Khố được thiết lập ban đầu cĩ thể dùng như khố 
riêng, cịn khố được thiết lập sau khi biến đổi là khố cơng khai. Sơ đồ mã 
hố MHK che giấu lời giải bằng phép nhân theo modulo và phép hốn vị. 
 ðịnh nghĩa một dãy siêu tăng là một dãy các số nguyên dương (b1,b2, ..., 
bn) thoả mãn tính chất 
1
1
i
i j
j
b b
−
=
>∑ với mỗi i, 2 ≤ i ≤ n. 
Thuật tốn 
Tạo khố: Mỗi thực thể tạo một khố cơng khai và một khố riêng tương ứng. 
Một số nguyên n được cố định như một tham số hệ thống phổ biến. 
1. Chọn một dãy siêu tăng (b1,b2, ..., bn) và modulo M sao cho 
 M > b1 + b2 + ... + bn. 
2. Chọn số nguyên ngẫu nhiên W 1 ≤ W ≤ M-1 sao cho UCLN(W, M) = 1. 
3. Chọn một phép hốn vị ngẫu nhiên pi của n số nguyên {1,2,...,n}. 
4. Tính ai = Wbpi (i) mod M với i = 1, 2, ..., n. 
5. Khố cơng khai là (a1, a2, ..., an), khố riêng là (pi , M, W, (b1,b2, ..., 
bn)). 
Mã hố: B mã hố văn bản m gửi cho A. 
1. Thu được khố cơng khai (a1, a2, ..., an) của A. 
2. Biểu diễn văn bản m như một chuỗi nhị phân cĩ độ dài n, m=m1m2...mn. 
3. Tính số nguyên c = m1a1 + m2a2 + ... + mnan. 
131 
4. Gửi bản mã c cho A. 
Giải mã: ðể khơi phục bản rõ m từ c, cần thực hiện các cơng việc sau: 
1. Tính d = W-1c mod M. 
2. Sử dụng thuật tốn tìm lời giải bài tốn tổng dãy siêu tăng để tìm các 
số nguyên r1,r2,...,rn,ri∈{0,1}, sao cho d=r1b1+r2b2+ ... +rnbn. 
3. Các bit văn bản m là mi = rpi (i), i = 1, 2, ..., n. 
Ví dụ 
Tạo khố: Lấy n=6, chọn dãy siêu tăng (12, 17, 33, 74, 157, 316), M=737, 
W=635 và phép hốn vị pi của (1, 2, 3, 4, 5, 6) được định nghĩa bởi pi (1)=3, 
pi (2)=6, pi (3)=1, pi (4)=2, pi (5)=5, pi (6)=4. 
Khố cơng khai là (319, 196, 250, 477, 200, 559), Khố riêng là (pi , 
M, W, (12, 17, 33, 74, 157, 316)). 
Mã hố: Văn bản m = 101101, tính: c = 319 + 250 + 477 + 559 = 1605 
Giải mã: Tính d = W-1c mod M = 136, và tìm lời giải cho bài tốn tổng dãy 
siêu tăng: 136 = 12r1 + 17r2 + 33r3 +74r4 + 157r5 + 316r6, nhận được 136 = 12 
+ 17 + 33 + 74. Từ đĩ r1 = 1, r2 = 1, r3 = 1, r4 = 1, r5 = 0, r6 = 0. Sử dụng phép 
hốn vị pi được các bit văn bản m: m1 = r3 = 1, m2 = r6 = 0, m3 = r1 = 1, m4 = 
r2 = 1, m5 = r5 = 0, m6 = r4 = 1. 
Tính bảo mật của mã hố MHK 
Lược đồ mã hố MHK cĩ thể bị bẻ khố bởi thuật tốn thời gian đa thức. 
Trong cách thiết lập khố cơng khai, thuật tốn này tìm một cặp số nguyên U’, 
M’ sao cho U’/M’ là tỉ lệ với U/M (W và M là một phần khố riêng, và U=W-1 
mod M) và sao cho các số nguyên b’i = U’ai mod M, 1 ≤ i ≤ n từ dãy siêu 
tăng. Dãy này cĩ thể được một đối thủ sử dụng thay thế vào dãy (b1,b2, ..., bn) 
để giải mã văn bản. 
132 
TÀI LIỆU THAM KHẢO 
[1] ðặng Văn Chuyết, Nguyễn Tuấn Anh, “Cơ sở lý thuyết truyền tin” – Tập 1 
và 2, Nhà xuất bản Giáo dục, 1998. 
[2] Robert B.Ash, “Information theory “, Nhà xuất bản Dover, inc, 1990. 
[3] Masud Mansuripur, “Introduction to information theory “, Nhà xuất bản 
Prentice-Hall, Inc, 1987. 
[4] I. Cziszar and J. Korner. Information theory, “Coding Theorems for 
Discrete Memoryless Systems”. Academic Press, New York. 1997. 2nd 
edition. 
[5] D. Hammer, A. Romashenko, A. Shen, N. Vereshchagin, “Inequalities for 
Shannon entropies and Kolmogorov complexities”, Proceedings of CCC'97 
Conference, Ulm. Final version: Inequalities for Shannon entropy and Kol-
mogorov Complexity, Journal of Computer and System Sciences, v. 60, p. 
442{464 (2000). 
[6] A. Shen, “Algorithmic Information Theory and Kolmogorov Complexity”, 
Lecture notes of an introductory course. Uppsala University Technical Report 
2000-034. Available online at 
[7] Bar-Yam, Yaneer, “Dynamics of Complex Systems (Studies in 
Nonlinearity)”, Westview Press, Boulder, 1997. 
[8] Campbell, Jeremy, Grammatical Man, “Information, Entropy, Language, 
and Life, Simon and Schuster”, New York, 1982. 
[9] Cover, T. M., and Thomas J. A., “Elements of Information Theory”, John 
Wiley and Sons, New York, 1991. 
[10] Gatlin, L. L., “Information Theory and the Living System”, Columbia 
University Press, New York, 1972. 
133 
[11] Hamming, R. W., “Coding and information theory”, 2nd ed, Prentice-
Hall, Englewood Cliffs, 1986. 
[12] Landauer, R., “The physical nature of information”, Phys. Lett. A, 217 
188, 1996. 
134 
MỤC LỤC 
LỜI MỞ ðẦU 1 
CHƯƠNG 1. NHỮNG KHÁI NIỆM CƠ BẢN 3 
1.1 Giới thiệu về lý thuyết thơng tin ..............................................................3 
1.2 Hệ thống truyền tin ..................................................................................3 
1.2.1 Các quan điểm để phân loại các hệ thống truyền tin ........................4 
1.2.2 Sơ đồ truyền tin và một số khái niệm trong hệ thống truyền tin......4 
1.3 Nguồn tin nguyên thuỷ.............................................................................5 
1.3.1 Khái niệm chung..............................................................................5 
1.3.2 Bản chất của thơng tin theo quan điểm truyền tin ............................7 
1.4 Hệ thống kênh tin...................................................................................10 
1.4.1 Khái niệm........................................................................................10 
1.4.2 Phân loại mơi trường truyền tin ......................................................11 
1.4.3 Mơ tả sự truyền tin qua kênh: .........................................................11 
 1.5 Hệ thống nhận tin ..................................................................................13 
 1.6 Một số vấn đề cơ bản của hệ thống nhận tin..........................................13 
 1.6.1 Hiệu suất...........................................................................................13 
 1.6.2 ðộ chính xác.....................................................................................13 
 1.7 Rời rạc hĩa một nguồn tin liên tục.........................................................13 
 1.7.1 Quá trình lấy mẫu.............................................................................14 
 1.7.2 Quá trình lượng tử hĩa.....................................................................16 
1.8 ðiều chế và giải điều chế .......................................................................17 
1.8.2 Giải điều chế ...................................................................................18 
CHƯƠNG 2. TÍN HIỆU 19 
2.1 Một số khái niệm cơ bản........................................................................19 
2.1.1 Tín hiệu duy trì: ..............................................................................19 
2.1.2 Tín hiệu xung ..................................................................................19 
2.2 Phân tích phổ cho tín hiệu......................................................................20 
2.2.2 Tích phân Fourier và phổ liên tục ...................................................27 
2.2.3 Phổ các tín hiệu điều chế ................................................................28 
2.3 Nhiễu trắng.............................................................................................33 
CHƯƠNG 3. LƯỢNG TIN, ENTROPI NGUỒN RỜI RẠC 35 
3.1 ðộ đo thơng tin ......................................................................................35 
3.1.2 ðộ đo thơng tin. ..............................................................................35 
3.2 Lượng tin của nguồn rời rạc...................................................................37 
135 
3.2.1 Mối liên hệ của lượng tin và lý thuyết xác suất ..............................37 
3.2.3 Tính chất của lượng tin ...................................................................45 
3.2.4 Lượng tin trung bình .......................................................................46 
3.3 Entropi của nguồn rời rạc......................................................................47 
3.3.1 Khái niệm entropi ...........................................................................47 
3.3.2 Tính chất của entropi .....................................................................47 
3.3.3 Entropi đồng thời và Entropi cĩ điều kiện.....................................48 
3.3.4 Entropi nguồn Markov....................................................................49 
3.4 Mối quan hệ giữa lượng tin tương hỗ trung bình và Entropi .................50 
3.5 Tốc độ lập tin nguồn rời rạc và thơng lượng kênh rời rạc .....................52 
3.5.1 Tốc độ lập tin ......................................................................................52 
3.5.2 Thơng lượng kênh...........................................................................54 
CHƯƠNG 4. LÝ THUYẾT MÃ 56 
4.1 Khái niệm mã và điều kiện thiết lập mã ................................................56 
4.1.1 Mã hiệu và các thơng số cơ bản......................................................56 
4.1.2 ðiều kiện thiết lập bộ mã................................................................58 
4.2 Các phương pháp biểu diễn mã..............................................................60 
4.2.1 Biểu diễn bằng bảng liệt kê (Bảng đối chiếu mã)...........................60 
4.2.2 Biểu diễn bằng toạ độ mã................................................................60 
4.2.3 ðồ hình mã......................................................................................61 
4.2.4 Phương pháp hàm cấu trúc mã.......................................................62 
4.3 Mã cĩ tính phân tách được, mã cĩ tính prefix .......................................62 
4.3.1 ðiều kiện để mã phân tách được....................................................63 
4.3.2 Mã cĩ tính prefix.............................................................................65 
4.3.3 Bất đẳng thức Kraft.........................................................................66 
4.4 Mã thống kê tối ưu................................................................................67 
4.4.1 Giới hạn độ dài trung bình của từ mã ............................................67 
4.4.2 Tiêu chuẩn mã thống kê tối ưu .......................................................68 
4.4.3 Mã thống kê Fano –Shanon ............................................................69 
 4.5 Thuật tốn mã hố Lempel-Ziv..............................................................83 
4.6 Mã chống nhiễu.....................................................................................85 
4.6.1 Khái niệm về mã phát hiện sai và sửa sai .......................................86 
4.6.2 Cơ chế phát hiện sai ........................................................................87 
4.6.3 Xây dựng bộ mã sửa sai bằng bảng chọn........................................89 
4.6.4 Xây dựng bộ mã sửa sai bằng trọng số Hamming và khoảng cách 
Hamming..................................................................................................90 
4.5.5 Một số biện pháp xây dựng bộ mã phát hiện sai và sửa sai...........92 
4.7 Mã tuyến tính .........................................................................................94 
4.7.2 Nguyên lý giải mã...........................................................................96 
136 
4.7.3 Một số giới hạn của mã tuyến tính..................................................98 
4.8 Mã vịng ................................................................................................99 
4.8.1 Khái niệm:.......................................................................................99 
4.8.2 Nguyên lý lập mã..........................................................................100 
4.8.3 Nguyên lý giải mã.........................................................................102 
CHƯƠNG 5. GIỚI THIỆU VỀ HỆ MẬT MÃ 105 
5.1 Khái niệm hệ mật mã ...........................................................................105 
5.2 Phân loại các hệ thống mật mã ............................................................105 
5.3 Hệ mã cổ điển (Symmetric-key encryption)........................................106 
5.3.1 Khái niệm......................................................................................106 
5.3.2 Một số hệ mã cổ điển ....................................................................106 
5.3.3 Hệ mã DES ...................................................................................117 
5.4 Một số hệ mã hố cơng khai ................................................................121 
5.4.1 Khái niệm chung...........................................................................121 
 5.4.2 Hệ mã RSA....................................................................................123 
 5.4.3 Hệ mã Rabin..................................................................................126 
 5.4.4 Hệ mã Elgamal..............................................................................129 
 5.4.5 Hệ mã MHK..................................................................................130 
TÀI LIỆU THAM KHẢO............................................................................. 131 
MỤC LỤC......................................................................................................133