Lý thuyết Thông tin BÀI 13 MÃ VÒNG 13.1 Giới thiệu 13.2 Các tính chất của mã vòng 13.3 Ma trận sinh và ma trận kiểm tra của mã vòng 13.4 Mã BCH 13.1 Gi i thi u Định nghĩa 13.1 M t mã tuy n tính C(n, k) đ ợc gọi là mã vòng n u w = a0a1…an–2an–1 là m t từ mã thì v = an–1a0a1…an–2 cũng là m t từ mã. Nói cách khác mã vòng là mã có tính vòng, có nghĩa là dịch vòng một từ mã thì kết quả cũng là một từ mã. Chú ý đây chúng ta thấy việc dịch vòng được thực hiện từ trái sang phải (gọi là dịch phải), tuy nhiên với từ mã có chiều dài n bit thì việc dịch vòng ngược lại từ phải sang trái i bit (gọi là dịch trái) thì kết quả cũng giống với việc dịch phải (n – i) bit. Vì vậy nếu chúng ta dịch trái (dịch từ phải sang trái) một từ mã thì kết quả cũng là một từ mã. Tuy nhiên đây khi nói dịch thì chúng ta hiểu là dịch phải. Đa th c mã N u w = a0a1…an–2an–1 là m t từ mã thì w(x) = a0 + a1x + … + an–2xn - 2 + an–1xn - 1 là đa thức mã t ơng ứng v i từ mã w. Vậy chúng ta có một song ánh giữa các từ mã với các đa thức mã. Mỗi đa thức mã là một đa thức trên trư ng GF(2) và có bậc ≤ n – 1. Như sau này chúng ta sẽ thấy, chúng ta sẽ dựa vào các đa thức mã này để chứng minh các tính chất của mã vòng. Ví dụ 13.1 Bảng sau đây trình bày một mã vòng C(7, 4). Các bạn có thể kiểm tra rằng mã này là một mã tuyến tính và có tính vòng. Thông báo u = a0 … ak–1 0000 1000 0100 1100 0010 1010 0110 1110 0001 1001 0101 1101 0011 1011 Từ mã w = b0 … bn–1 0000000 1101000 0110100 1011100 0011010 1110010 0101110 1000110 0001101 1100101 0111001 1010001 0010111 1111111 Đa thức mã w(x) = b0 + b1x + … + bn–2xn - 2 + bn–1xn - 1 0 1 + x + x3 x + x2 + x4 1 + x2 + x3 + x4 x2 + x3 + x5 1 + x + x2 + x5 x + x3 + x4 + x5 1 + x4 + x5 x3 + x4 + x6 1 + x + x4 + x6 x + x2 + x3 + x6 1 + x2 + x6 x2 + x4 + x5 + x6 1 + x + x2 + x3 + x4 + x5 + x6 Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 103 Lý thuyết Thông tin 0111 1111 0100011 1001011 x + x5 + x6 1 + x3 + x5 + x6 Chú ý Vì tổng của hai từ mã là một từ mã nên tổng của hai đa thức mã là một đa thức mã. w(i), w(i)(x) w(i) là từ mã do dịch từ mã w i bit, và w(i)(x) là đa thức mã t ơng ứng của w(i). Chú ý chúng ta coi w chính là w(0). Bây gi chúng ta sẽ tìm mối liên hệ giữa w(i)(x) với w(x). Chúng ta dựa vào ví dụ trên để tìm mối liên hệ này. i 0 1 2 3 4 5 6 w(i) 1101000 0110100 0011010 0001101 1000110 0100011 1010001 w(i)(x) 1 + x + x3 x + x2 + x4 = x * (1 + x + x3) = x * w(x) x2 + x3 + x5 = x2 (1 + x + x3) = x2 * w(x) x3 + x4 + x6 = x3 (1 + x + x3) = x3 * w(x) 1 + x4 + x5 = x4 + x5 + x7 mod 7 x + x5 + x6 = x5 + x6 + x8 mod 7 1 + x2 + x6 = x6 + x7 mod 7 + x9 mod 7 Chúng ta thấy rằng w(i)(x) = xi * w(x) tuy nhiên nếu w(i)(x) có xp với p ≥ n thì xp được thay bằng xp mod n. Mặc khác trên trư ng GF(2) chúng ta có xn + j = xj * (xn + 1) + xj hay xn + j mod (xn + 1) = xj Từ đây chúng ta có bổ đề sau về mối liên hệ giữa w(i)(x) với w(x). Bổ đề 13.1 w(i)(x) = [xi * w(x)] mod (xn + 1) 13.2 Các tính chất của mã vòng Trong phần này chúng ta sẽ dẫn ra một số tính chất của mã vòng. Định lý 13.1 Đa thức mã khác 0 có b c nhỏ nhất là duy nhất. Hay nói cách khác không tồn t i hai đa thức mã khác 0, khác nhau và cùng có b c nhỏ nhất. Ch ng minh Giả sử tồn tại hai đa thức mã khác 0, khác nhau và cùng có bậc nhỏ nhất là r, 0 < r < n. g(x) = g0 + g1x + … + gr–1xr - 1 + xr f(x) = f0 + f1x + … + fr–1xr - 1 + xr Từ đây suy ra đa thức mã g(x) + f(x) có bậc nhỏ hơn r, mâu thuẫn. Chứng minh hoàn tất. Chúng ta kí hiệu đa thức mã có bậc nhỏ nhất là g(x) và kí hiệu là g(x) = g0 + g1x + … + gr–1xr - 1 + xr Định lý 13.2 H số tự do g0 của g(x) ph i bằng 1. Ch ng minh Giả sử g0 = 0. Suy ra g(x) = x * (g1 + … + gr–1xr - 2 + xr - 1) Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 104 Lý thuyết Thông tin Đặt f(x) = (g1 + … + gr–1xn - 2 + xr - 1). Chúng ta suy ra f(x) cũng là một đa thức mã. Vì từ mã tương ứng với f(x) là kết quả của việc dịch trái 1 bit hay dịch phải (n – 1) bit từ mã tương ứng với g(x). Mà bậc của f(x) bằng r – 1 và dĩ nhiên f(x) khác 0. Điều này mâu thuẫn với định nghĩa của g(x). Từ đây suy ra điều phải chứng minh. Định lý 13.3 M t đa thức v(x) trên tr ờng GF(2) có b c ≤ n – 1 là đa thức mã n u và chỉ n u nó là m t b i số của g(x). Tức là nó có thể vi t v(x) = q(x) * g(x). Ch ng minh Trước hết chúng ta chứng minh nếu v(x) = q(x) * g(x) và bậc của v(x) ≤ n – 1 thì v(x) là đa thức mã. Thực vậy, chúng ta có v(x) = q(x) * g(x) = ⎜⎜ ∑ qi x i ⎟⎟ * g ( x ) = ∑ qi (x i * g ( x ) ) ⎛ p ⎝ i =0 ⎞ ⎠ p i =0 trong đó p là bậc của q(x) và p + r ≤ n – 1. Mà do x * g(x) với 0 ≤ i ≤ p là đa thức mã (tương ứng với từ mã do từ mã g(x) dịch i bit). Nên v(x) là đa thức mã vì bằng với một tổ hợp tuyến tính của các đa thức mã. Bây gi nếu v(x) là đa thức mã thì chia v(x) cho g(x) chúng ta được v(x) = q(x) * g(x) + r(x) trong đó r(x) là đa thức dư và có bậc nhỏ hơn bậc của g(x). Nhưng đối với các đa thức trên trư ng GF(2) chúng ta có thể suy ra r(x) = q(x) * g(x) + v(x) Nên r(x) là một đa thức mã. Vì vậy do định nghĩa của g(x) chúng ta suy ra r(x) = 0. Chứng minh hoàn tất. Từ định lý này chúng ta gọi tên đa thức g(x) là đa thức sinh, vì từ g(x) có thể sinh ra tất cả các đa thức mã khác. i Định lý 13.4 Đa thức sinh của m t mã vòng C(n, k) có b c r = n – k. Ch ng minh Gọi r là bậc của đa thức sinh g(x). Từ định lý trên chúng ta có mỗi đa thức mã v(x) là một bội số của g(x) v(x) = q(x) * g(x) Vì vậy có bao nhiêu từ mã thì có bấy nhiêu đa thức q(x). Trước hết chúng ta thấy do bậc của v(x) ≤ n – 1 nên bậc của q(x) ≤ (n – 1) – r. Do đó có tổng cộng 2n – r đa thức q(x) (vì q(x) có n – r hệ số thuộc trư ng GF(2)) Mặt khác số lượng từ mã là 2k. Từ đây suy ra n – r = k hay r = n – k Chứng minh hoàn tất. Từ định lý này chúng ta có thể biểu diễn đa thức sinh g(x) như sau g(x) = g0 + g1x + … + gn – kxn – k trong đó g0 = gn – k = 1. Định lý 13.5 Đa thức sinh của m t mã vòng C(n, k) là m t c số của xn + 1. Ch ng minh Từ Bổ đề 13.1 chúng ta suy ra g(i)(x) = [xi * g(x)] mod (xn + 1) Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 105 Lý thuyết Thông tin hay chúng ta có thể viết xi * g(x) = q(x) * (xn + 1) + g(i)(x) Bây gi chọn i = k và để ý bậc g(x) = n – k nên chúng ta suy ra q(x) = 1 tức là xk * g(x) = (xn + 1) + g(i)(x) Từ đây suy ra xn + 1 = xk * g(x) + g(i)(x) (i) Mà do g (x) là một đa thức mã nên g(i)(x) phải là một bội của g(x), tức là chúng ta có thể viết g(i)(x) = g(x) * a(x). Thế vào trên chúng ta suy ra điều phải chứng minh. xn + 1 = g(x) * (xk + a(x)) Định lý 13.6 N u g(x) là m t đa thức có b c (n – k) và là c số của (xn + 1) thì g(x) sinh ra mã vòng C(n, k), hay nói cách khác g(x) là đa thức sinh của m t mã vòng C(n, k) nào đó. Ch ng minh Xét k đa thức g(x), x * g(x), …, xk – 1 * g(x). Các đa thức này đều có bậc ≤ n – 1. Gọi v(x) là một tổ hợp tuyến tính của k đa thức này với các hệ số ai ∈ GF(2). v(x) = a0g(x) + a1x * g(x) + … + ak – 1xk – 1 * g(x) v(x) là một đa thức có bậc ≤ n – 1 và là bội số của g(x). Có tất cả 2k đa thức v(x) khác nhau và tạo nên một không gian tuyến tính của các đa thức mã với g(x), x * g(x), …, xk – 1 * g(x) là các đa thức làm cơ s . Vì vậy 2k tổ hợp (a0a1 … ak – 1) tương ứng với 2k đa thức này tạo nên một mã tuyến tính C(n, k). Bây gi chúng ta chứng minh mã này có tính vòng, tức là chứng minh nếu v là một từ mã thì dịch v 1 bit chúng ta được v(1) cũng là một từ mã. Điều này cũng tương đương với nếu v(x) là một đa thức mã thì v(1)(x) cũng là một đa thức mã. Đầu tiên chúng ta biểu diễn v(x) v(x) = b0 + b1x + … + bn – 1xn – 1 thì v(1)(x) = bn – 1 + b0x + b1x2 + … + bn – 2xn – 1 Theo Bổ đề 13.1 chúng ta có v(1)(x) = [x * v(x)] mod (xn + 1) Dựa vào biểu diễn của v(x) và v(1)(x) chúng ta suy ra x * v(x) = bn – 1(xn + 1) + v(1)(x) n Do v(x) và (x + 1) đều là bội của g(x) nên v(1)(x) cũng là bội của g(x). Vì vậy v(1)(x) cũng là đa thức mã. Chứng minh hoàn tất. 13.3 Ma tr n sinh và ma tr n kiểm tra của mã vòng Ma trận sinh c a mã vòng Từ các định lý trên chúng ta suy ra một từ mã là một tổ hợp tuyến tính của các từ mã tương ứng với các đa thức mã g(x), x * g(x), …, xk – 1 * g(x). Và với chú ý rằng các đa thức g(x), x * g(x), …, xk – 1 * g(x) độc lập tuyến tính với nhau. Vì vậy ma trận sinh của mã vòng C(n, k) sẽ là, trong đó g0 = gn – k = 1. Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 106 Lý thuyết Thông tin G k ×n k7 k4 1 444 −7 + 14448 64444 −4 ⎡ 6444n4 8⎤ ⎢g g1 g 2 L g n− k 0 0 L 0 ⎥ ⎥ ⎢ 0 0 L 0 ⎥ ⎢ 0 g 0 g1 L g n − k −1 g n − k = ⎢⎢ 0 0 g 0 L g n − k − 2 g n − k −1 g n − k L 0 ⎥⎥ ⎢M M M M M ⎥ M M M M ⎥ ⎢ g1 g 2 L g n−k ⎥ g0 ⎢0 0 L 0 ⎥⎦ ⎢⎣ Ví dụ 13.2 Tìm một mã vòng C(7, 4). Theo các tính chất của mã vòng chúng ta suy ra đa thức sinh của mã có bậc bằng 3 và là một ước số của x7 + 1. Phân tích đa thức này ra thừa số chúng ta được x7 + 1 = (1 + x)(1 + x + x3)(1 + x2 + x3) đây chúng ta có hai thừa số của x7 + 1 cùng có bậc bằng 3, mỗi thừa số sẽ sinh ra một mã vòng C(7, 4). Bây gi chúng ta chọn chẳng hạn g(x) = (1 + x + x3) Từ đây chúng ta suy ra ma trận sinh của mã vòng này là G4×7 ⎡1 ⎢0 =⎢ ⎢0 ⎢ ⎣0 1 0 1 0 0 0⎤ 1 1 0 1 0 0⎥⎥ 0 1 1 0 1 0⎥ ⎥ 0 0 1 1 0 1⎦ Bộ mã này chính là bộ mã được trình bày trong Ví dụ 13.1. Mã vòng dạng hệ thống Để tìm mã vòng dạng hệ thống, chúng ta biến đổi từ ma trận sinh thành ma trận sinh dạng hệ thống. đây chúng ta chú ý rằng do tính vòng nên từ dạng hệ thống loại 1 chúng ta có thể dịch vòng k bit để biến đổi sang dạng hệ thống loại 2 và ngược lại. Ví dụ từ ma trận sinh trong Ví dụ 13.2 chúng ta biến đổi như sau thì được ma trận sinh hệ thống dạng 2: h3 = h3 + h1, h4 = h4 + h1 + h2 trong đó hi là hàng thứ i của ma trận. Ght ( 4×7 ) ⎡1 ⎢0 =⎢ ⎢1 ⎢ ⎣1 1 0 1 0 0 0⎤ 1 1 0 1 0 0⎥⎥ 1 1 0 0 1 0⎥ ⎥ 0 1 0 0 0 1⎦ ⎡1 ⎢0 =⎢ ⎢0 ⎢ ⎣0 0 0 0 1 1 0⎤ 1 0 0 0 1 1⎥⎥ 0 1 0 1 1 1⎥ ⎥ 0 0 1 1 0 1⎦ Và từ đây chúng ta có thể có được ma trận sinh hệ thống dạng 1 bằng cách dịch vòng k = 4 bit. Kết quả chúng ta có ma trận sinh hệ thống dạng 1 như sau Ght ( 4×7 ) Mã hoá thành từ mã hệ thống Ngoài việc dùng ma trận sinh hệ thống để mã hoá một thông báo thành từ mã hệ thống chúng ta có thể dùng cách sau đây để mã hoá thông báo u = a0a1...ak - 1 thành từ mã hệ thống dạng 2 w = b0b1...bn–k–1a0a1...ak - 1 trong đó n – k bit bi là các n – k bit kiểm tra. Gọi u(x) là đa thức tương ứng với thông báo u. Vì vậy bậc của u(x) ≤ k – 1. Chia xn–k * u(x) cho g(x) chúng ta được Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 107 Lý thuyết Thông tin Từ đây suy ra xn–k * u(x) = q(x) * g(x) + a(x) xn–k * u(x) + a(x) = q(x) * g(x) Vì xn–k * u(x) + a(x) là bội của g(x) nên nó là đa thức mã. Và để ý từ mã tương ứng với đa thức mã này có k bit sau là k bit thông báo, đó chính là từ mã hệ thống dạng 2 tương ứng với thông báo u. Ví dụ 13.3 Cho mã vòng C(7, 4) có ma trận sinh là g(x) = (1 + x + x3). Hãy mã hoá thông báo u = 1010 thành từ mã hệ thống dạng 2. Chúng ta có u(x) = 1 + x2. Nhân u(x) với xn–k = x3 rồi chia cho g(x) chúng ta được. x3 * (1 + x2) = x3 + x5 = x2 * (1 + x + x3) + x2 Từ đây suy ra w(x) = x2 + x3 + x5 là đa thức mã và từ mã tương ứng w = 0011010 là từ mã hệ thống dạng 2 tương ứng với u. Ma trận kiểm tra c a mã vòng Để tìm ma trận kiểm tra của mã vòng chúng ta có thể sử dụng cách đã biết là tìm ma trận kiểm tra từ ma trận sinh hoặc ma trận sinh hệ thống. Tuy nhiên đối với mã vòng chúng ta có một cách xác định ma trận kiểm tra nhanh chóng hơn. Trước hết vì g(x) là một ước số của xn + 1 nên chúng ta có thể biểu diễn xn + 1 = g(x) * h(x) Và chúng ta gọi h(x) là đa thức đối ngẫu của g(x). Để ý h(x) có bậc k và có thể được biểu diễn như sau, trong đó h0 = hk = 1 h(x) = h0 + h1x + … + hkxk Gọi v(x) = a0 + a1x + … + an – 1xn – 1 là đa thức mã tương ứng với từ mã v = (a0a1…an – 1) Chúng ta có thể biểu diễn như sau trong đó q(x) có bậc ≤ k – 1 v(x) = q(x) * g(x) Bây gi chúng ta nhân v(x) với h(x) và được v(x) * h(x) = q(x) * g(x) * h(x) = q(x) * (xn + 1) = q(x) + xn * q(x) Do q(x) có bậc ≤ k – 1 nên từ đây chúng ta suy ra các hệ số của xk, xk + 1, …, xn–1 trong v(x) * h(x) bằng 0. Từ cách tính hệ số của xk, xk + 1, …, xn–1 trong v(x) * h(x) theo các hệ số ai và hj của v(x) và h(x) chúng ta suy ra n – k đẳng thức sau ∑h k i =0 k ∑h i =0 ∑h k i =0 k −i k −i k −i ai = 0 ai +1 = 0 M ai + n − k −1 = 0 Từ các đẳng thức này chúng ta suy ra các tích vectơ sau bằng 0 (a0a1 … an – 1) * (hkhk–1 … h00 … 0)T = 0 (a0a1 … an – 1) * (0hkhk–1 … h0 … 0)T = 0 M Vì vậy nếu chúng ta đặt (a0a1 … an – 1) * (0 … 0hkhk–1 … h0)T = 0 Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 108 Lý thuyết Thông tin H ( n − k )×n +4 −7 − 144 k7 n4 k4 1 444 ⎡ 64444 8⎤ 8 644 ⎢h h hk −2 L h0 0 0 L 0⎥ k −1 ⎢ k ⎥ 0 L 0⎥ ⎢ 0 hk hk −1 L h1 h0 = ⎢⎢ 0 hk L h2 h1 h0 L 0 ⎥⎥ 0 ⎢M M M M M⎥ M M M M ⎢ ⎥ 0 L 0 hk hk −1 hk −2 L h0 ⎥ ⎢0 ⎢⎣ ⎥⎦ thì chúng ta suy ra v × HT = 0. Từ đây suy ra H là một ma trận kiểm tra của mã vòng. Ví dụ 13.4 Cho mã vòng C(7, 4) có ma trận sinh là g(x) = (1 + x + x3). Từ đây suy ra h(x) = (1 + x + x2 + x4) Và chúng ta có ma trận kiểm tra của bộ mã như sau H 3×7 ⎡1 0 1 1 1 0 0⎤ = ⎢⎢0 1 0 1 1 1 0⎥⎥ ⎢⎣0 0 1 0 1 1 1⎥⎦ Chú ý Mã vòng là mã cho phép thiết kế các mạch mã hoá, sửa sai và giải mã dễ dàng và hiệu quả nên được sử dụng rộng rãi trong thực tế. Bây gi chúng ta sẽ trình bày ứng dụng của trư ng GF(2m) trong việc xây dựng các mã vòng. Trước hết chúng ta có định lý sau. Định lý 13.7 Cho a là m t ph n t khác 0 của tr ờng GF(2m) có chu kỳ là n, đa thức tối thiểu f(x) của a có b c là m. Thì mã có ma tr n sau làm ma tr n kiểm tra là m t mã vòng C(n, n – m), trong đó mỗi ph n t trong ma tr n bên d i đ ợc thay th bằng vectơ m thành ph n t ơng ứng của nó. Hm×n = [1 a a2 … an – 2 an–1] Hơn n a mã vòng này có đa thức sinh chính là f(x). Ch ng minh Trước hết chúng ta chứng minh rằng nếu w = (b0b1b2…bn–2bn–1) là một từ mã thì v = (bn– 1b0b1…bn–3bn–2) cũng là một từ mã, từ đó suy ra mã có tính vòng. Thật vậy nếu w là từ mã thì chúng ta có w × HT = 0 hay b0 + b1a + b2a2 + … + bn–2an–2 + bn–1an–1 = 0 trong đó các bi ∈ GF(2) còn các aj ∈ GF(2m). Nhân a vào đẳng thức trên chúng ta suy ra b0a + b1a2 + b2a3 + … + bn–2an–1 + bn–1an = 0 hay bn–1 + b0a + b1a2 + b2a3 + … + bn–2an–1 = 0 tức là (bn–1b0b1…bn–3bn–2) cũng là một từ mã. Thứ hai vì đa thức tối thiểu của a có bậc là m nên m phần tử 1, a, a2, …, am–1 là độc lập tuyến tính. Từ đó suy ra m hàng của H là độc lập tuyến tính. Vì vậy mã thực sự là mã vòng C(n, n – m). Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 109 Lý thuyết Thông tin Cuối cùng nếu biểu diễn f(x) = f0 + f1x + f2x2 + … + fm–1xm–1 + fmxm–1 (với chú ý f0 = fm = 1) thì do f(a) = 0 nên chúng ta suy ra w = (f0f1… fm0 … 0) (gồm n thành phần) là một từ mã. Và không tồn tại đa thức mã v(x) nào có bậc nhỏ hơn m, vì nếu ngược lại lúc đó chúng ta có do v × HT = 0 suy ra v(a) = 0. Điều này mâu thuẫn với định nghĩa f(x) là đa thức tối thiểu của a. Chứng minh hoàn tất. Ví dụ 13.5 Xét trư ng GF(24) và a có đa thức tối thiểu là f(x) = 1 + x + x4 như trong Ví dụ 11.7. Chú ý a có chu kỳ là 15. Thì ma trận sau là ma trận kiểm tra của mã vòng C(15, 11) có đa thức sinh chính là f(x) H 4×15 ⎡1 ⎢0 =⎢ ⎢0 ⎢ ⎣0 0 0 0 1 0 0 1 1 0 1 0 1 1 1⎤ 1 0 0 1 1 0 1 0 1 1 1 1 0 0⎥⎥ 0 1 0 0 1 1 0 1 0 1 1 1 1 0⎥ ⎥ 0 0 1 0 0 1 1 0 1 0 1 1 1 1⎦ Nếu đa thức tối thiểu của a là f(x) = 1 + x + x2 + x3 + x4 thì a có chu kỳ là 5 và các phần tử 1, a, ..., a4 được biểu diễn dưới dạng vectơ như sau: 1 = (1000) a = (0100) a2 = (0010) a3 = (0001) a4 = 1 + a + a2 + a3 = (1111) Từ đây suy ra ma trận sau là ma trận kiểm tra của mã vòng (5, 1) H 4×5 ⎡1 ⎢0 =⎢ ⎢0 ⎢ ⎣0 0 0 0 1⎤ 1 0 0 1⎥⎥ 0 1 0 1⎥ ⎥ 0 0 1 1⎦ 13.4 Mã BCH nhị phân Mã BCH có tên viết tắt của ba ngư i sáng lập ra nó đó là Bose, Chaudhuri và Hocquenghem. Đây là mã vòng có khả năng sửa được nhiều lỗi. Bây gi chúng ta sẽ đưa ra qui trình để xây dựng mã BCH nhị phân có khả năng sửa được nhiều lỗi. Đối với các số nguyên dương m và t bất kỳ chúng ta sẽ xây dựng một mã BCH nhị phân có các thông số sau: Độ dài từ mã: n = 2m – 1 Số bit kiểm tra: n – k ≤ mt Khoảng cách Hamming: dmin ≥ 2t + 1 Trước hết chúng ta chứng minh định lý sau đây. Định lý 13.8 Cho a là m t ph n t của tr ờng GF(2m) có đa thức tối thiểu là m t đa thức căn b n b c m. Thì mã có ma tr n sau làm ma tr n kiểm tra là m t mã vòng có kho ng cách Hamming ≥ 2t + 1, trong đó mỗi ph n t trong ma tr n bên d i đ ợc thay th bằng vectơ m thành ph n t ơng ứng của nó. Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 110 Lý thuyết Thông tin ⎡1 a ⎢ 3 ⎢1 a H = ⎢1 a 5 ⎢ M ⎢M ⎢1 a 2t −1 ⎣ a2 a6 a 10 M a 2( 2t −1) a n−2 L a 3( n − 2 ) L a 5( n − 2 ) L M M ( 2 t −1)(( n − 2 ) L a ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ( 2 t −1)(( n −1) ⎥ a ⎦ a n −1 a 3( n −1) a 5( n −1) M Hơn n a đa thức sinh g(x) của b mã là đa thức b i số chung nhỏ nhất của các đa thức tối thiểu của các ph n t a, a3, a5, …, a2t–1. Ch ng minh Từ định lý chúng ta suy ra a có chu kỳ là n = 2m – 1 và vì vậy a là một phần tử cơ s của trư ng GF(2m). Trước hết chúng ta chứng minh rằng nếu w = (b0b1b2…bn–2bn–1) là một từ mã thì v = (bn– b b 1 0 1…bn–3bn–2) cũng là một từ mã, từ đó suy ra mã có tính vòng. Thật vậy nếu w là từ mã thì chúng ta có w × HT = 0 hay viết ngược lại H × wT = 0 Nhân ma trận B sau với H chúng ta được ⎡a 0 ⎢0 a 3 ⎢ B = ⎢0 0 ⎢ ⎢M M ⎢⎣ 0 0 ⎡ a ⎢ 3 ⎢ a B × H = ⎢ a5 ⎢ ⎢ M ⎢a 2t −1 ⎣ a2 a6 a 10 M a 2 ( 2t −1) 0 0 a5 M 0 a3 a9 a 15 M 0 ⎤ 0 ⎥⎥ 0 ⎥ L ⎥ M M ⎥ L a 2t −1 ⎥⎦ L L a 3( 2t −1) a n −1 L a 3( n −1) L a 5( n −1) L M M ( 2 t −1)(( n −1) L a 1⎤ ⎥ 1⎥ 1⎥ ⎥ M⎥ 1⎥⎦ Chúng ta có (B×H)×wT = B×(H×wT) = B×0 = 0 Mà chúng ta để ý nếu dịch vòng ma trận (B×H) 1 cột theo chiều từ trái sang phải được thì kết quả là ma trận H. Từ đây suy ra H×vT = 0 với v là kết quả của việc dịch vòng w 1 bit (theo chiều từ trái sang phải). Hay nói cách khác v × HT = 0. Từ đây suy ra mã có tính vòng. Thứ hai để chứng minh bộ mã có khoảng cách Hamming ≥ 2t + 1 chúng ta chỉ cần chứng minh mỗi tập 2t cột của ma trận H là độc lập tuyến tính. Thật vậy giả sử tồn tại r cột k k có các phần tử đi đầu là a 1 , a 2 , …, a kr là có tổng bằng 0 trong đó r ≤ 2t. Từ đây chúng ta suy ra hệ sau, gọi là hệ (1) a k1 ⎛⎜ a k1 ⎞⎟ ⎠ ⎝ M +a 3 k2 k + ⎛⎜ a 2 ⎞⎟ ⎝ ⎠ 3 ( )3 + … + a kr =0 + … + a kr =0 Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 111 ⎛⎜ a k1 ⎞⎟ ⎠ ⎝ 2t −1 ⎛ k ⎞ + ⎜⎜ a 2 ⎟⎟ ⎝ ⎠ 2t −1 Lý thuyết Thông tin ( )2t −1 + … + a kr =0 Mỗi phương trình trong hệ 1 có dạng p(a) = 0 trong đó p(a) là đa thức của a. Đặt a với i = 1, 2, …, r. Từ đây chúng ta nhận được hệ (2) sau + y2 + … + yr = 0 y1 3 3 + y2 + … + yr3 = 0 y1 ki = yi M y12t - 1 + y22t - 1 + … + yr2t - 1= 0 Để ý trong trư ng GF(2m) thì (y1 + y2 + … + yr)2 = y12 + y22 + … + yr2 Vì vậy chúng ta có hệ (3) sau + y2 + … + yr = 0 y1 y12 + y22 + … + yr2 = 0 y13 + y23 + … + yr3 = 0 y14 + y24 + … + yr4 = 0 M y12t - 1 + y22t - 1 + … + yr2t - 1= 0 y12t + y22t + … + yr2t = 0 Chúng ta chỉ lấy r phương trình đầu và viết dưới dạng ma trận sau, gọi là (4) ⎡ 1 ⎢ y ⎢ 12 ⎢ y1 ⎢ ⎢ M ⎢⎣ y1 r −1 1 y2 2 y2 M r −1 y2 1 ⎤ ⎡ y1 ⎤ ⎡0⎤ y r ⎥⎥ ⎢⎢ y 2 ⎥⎥ ⎢⎢0⎥⎥ 2 L y r ⎥ × ⎢ y 3 ⎥ = ⎢0 ⎥ ⎥ ⎢ ⎥ ⎢ ⎥ M M ⎥ ⎢ M ⎥ ⎢M⎥ r −1 L y r ⎥⎦ ⎢⎣ y r ⎥⎦ ⎢⎣0⎥⎦ L L Phương trình (4) có dạng Ay = 0, trong đó các phần tử của ma trận A và của vectơ y là các phần tử của trư ng GF(2m). Các phần tử y1, y2, …, yr là khác phần tử 0 vì vậy phương trình Az = 0 là có nghiệm không tầm thư ng trong trư ng GF(2m). Vì vậy det A = 0 (là phần tử 0 của trư ng GF(2m)). Mà theo Bổ đề 13.2 chúng ta có det A = ∏ ( y i − y j ) với i, j ∈ {1, 2, i> j m …, r}. (Chú ý trong trư ng GF(2 ) phép trừ giống với phép cộng). Mà do các phần tử aq k với q = 1, 2, …, n = 2m – 1 là phân biệt nhau nên (yi – yj) ≠ 0 ∀ i ≠ j (Chú ý yi = a i ). Vì vậy det A = ∏ ( y i − y j ) ≠ 0. Mâu thuẫn. Từ đây suy ra điều phải chứng minh. i> j Cuối cùng gọi g(x) = g0 + g1x + g2x2 + … + gn–1xn–1 là đa thức sinh của bộ mã. Do (g0g1g2 … gn–1) là từ mã và (g0g1g2 … gn–1)× HT = 0, nên suy ra g(a) =0 3 g(a ) = 0 g(a5) = 0 M g(a2t–1) = 0 Nếu đặt f1(x), f3(x), f5(x), …, f2t–1(x) là các đa thức tối thiểu lần lượt của các phần tử a, a3, a5, …, a2t–1. Từ Bổ đề 11.5 chúng ta suy ra g(x) chia hết cho f1(x), f3(x), f5(x), …, f2t–1(x). Đặt p(x) là bội số chung nhỏ nhất của f1(x), f3(x), f5(x), …, f2t–1(x). Suy ra g(x) chia hết cho p(x). Suy ra bậc của g(x) ≥ bậc của p(x). Mặt khác nếu biểu diễn p(x) bằng p(x) = p0 + p1x + p2x2 + … + pn–1xn–1 Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 112 Lý thuyết Thông tin trong đó pn–1 không nhất thiết bằng 1. (Chú ý các đa thức tối thiểu đều là ước của x 2 −1 + 1 nên p(x) cũng vậy và có bậc ≤ n = 2m – 1.) Thì do tất cả p(a), p(a3), p(a5), …, p(a2t–1) đều bằng 0 nên (p0p1p2 … pn–1)× HT = 0 nên (p0p1p2 … pn–1) là từ mã, từ đó suy ra p(x) là đa thức mã. Vì vậy theo định nghĩa của đa thức sinh chúng ta suy ra g(x) = p(x). Chứng minh hoàn tất. m Bổ đề 13.2 Ma tr n A sau có định thức bằng ∏(y i> j i − y j ) v i i, j ∈ {1, 2, …, r}. Định thức này đ ợc gọi là định thức Vandermonde. ⎡ 1 ⎢ y ⎢ 12 A = ⎢ y1 ⎢ ⎢ M ⎢⎣ y1 r −1 y2 y2 2 M y2 1 ⎤ L y r ⎥⎥ 2 L yr ⎥ ⎥ M M ⎥ r −1 L y r ⎥⎦ L 1 r −1 Ch ng minh Thật vậy, det A là một đa thức đồng đều det A = p(y1, y2, ..., yr) trong đó p(y1, y2, ..., yr) là một tổng của các thành phần, mỗi thành phần bao gồm tích của các yik với mọi i = 1, 2, ..., r sao cho tổng bậc của mỗi thành phần là bằng nhau. Dễ thấy bậc của mỗi thành phần của p bằng 1 + 2 + … + (r – 1) = r(r – 1)/2. Chú ý nếu yi = yj thì det A = 0. Từ đây suy ra p(y1, y2, ..., yr) chia hết cho (yi – yj) ∀i ≠ j. Kết hợp với trên chúng ta suy ra det A = p(y1, y2, ..., yr) = ∏ ( y i − y j ) với i, j ∈ {1, 2, …, r}. i> j Chứng minh hoàn tất. Ví dụ 13.6 Cho m = 4, t = 2 chúng ta sẽ xây dựng một mã vòng có chiều dài từ mã là 24 – 1 = 15 và có khoảng cách Hamming d ≥ 5. Chúng ta sẽ xây dựng bằng cách dựa vào trư ng GF(24). Cho a là phần tử có đa thức tối thiểu là đa thức căn bản có bậc 4 sau f1(x) = 1 + x + x4 Trư ng này chính là trư ng GF(24) trong Ví dụ 11.7. a có chu kỳ n = 2m – 1 = 15. Chúng ta có ma trận kiểm tra của bộ mã như sau. ⎡1 a H =⎢ 3 ⎣1 a a2 a3 a4 a5 a6 a7 a8 a9 a 10 a 11 a 12 a 12 a6 a9 a 12 a 15 a 18 a 21 a 24 a 27 a 30 a 33 a 36 a 39 a 14 ⎤ ⎥ a 42 ⎦ Thay mỗi phần tử ai bằng vectơ (m = 4 thành phần) tương ứng chúng ta được Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 113 Lý thuyết Thông tin ⎡1 ⎢0 ⎢ ⎢0 ⎢ 0 H =⎢ ⎢1 ⎢ ⎢0 ⎢0 ⎢ ⎣⎢0 0 0 0 1 0 0 1 1 0 1 0 1 1 1⎤ 1 0 0 1 1 0 1 0 1 1 1 1 0 0⎥⎥ 0 1 0 0 1 1 0 1 0 1 1 1 1 0⎥ ⎥ 0 0 1 0 0 1 1 0 1 0 1 1 1 1⎥ 0 0 0 1 1 0 0 0 1 1 0 0 0 1⎥ ⎥ 0 0 1 1 0 0 0 1 1 0 0 0 1 1⎥ 0 1 0 1 0 0 1 0 1 0 0 1 0 1⎥ ⎥ 1 1 1 1 0 1 1 1 1 0 1 1 1 1⎦⎥ Và đa thức sinh g(x) là bội số của hai đa thức tối thiểu tương ứng với phần tử a và a3. Theo Ví dụ 11.7 chúng ta có đa thức tối thiểu của a3 là f3(x) = 1 + x + x2 + x3 + x4. Từ đây suy ra g(x) = f1(x) * f3(x) = (1 + x + x4) * (1 + x + x2 + x3 + x4) = 1 + x4 + x6 + x7 + x8 Chú ý Trong trư ng hợp đa thức tối thiểu của a không phải là đa thức căn bản thì chúng ta sẽ tìm được mã vòng có chiều dài n ≠ 2m + 1, với n là chu kỳ của a. Trư ng hợp này sinh viên tự lấy ví dụ. Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 114 Lý thuyết Thông tin BÀI 14 GI I THI U V M T MÃ HOÁ 14.1 Giới thiệu 14.2 Một số phép mật mã đơn giản 14.3 Bẻ gãy (breaking) một hệ mật mã 14.4 Kết hợp các phương pháp mật mã hoá 14.5 Sự không chắc chắn và sự bảo mật hoàn hảo (perfect secrecy) 14.6 Các hàm một chiều (one-way function) 14.7 Cơ s toán học của mật mã hóa 14.1 Gi i thi u Mã hoá bảo mật (hay mật mã hóa) có một lịch sử lâu đ i. Trước hết nó đã từng được sử dụng từ rất lâu trong các cuộc chiến tranh cổ đại và sau đó kéo dài cho đến tận bây gi . Tuy nhiên từ khi chiếc máy tính đầu tiên ra đ i và kéo theo sau đó là cả một cuộc cách mạng dữ dội về thông tin và truyền thông đã làm thay đổi cuộc sống của con ngư i. Chúng ta không còn trao đổi và xử lý thông tin theo những cách thức truyền thống tốn nhiều th i gian và công sức mà càng ngày càng chuyển nhiều trao đổi qua những môi trư ng điện tử nhanh chóng và hiệu quả. Chẳng hạn như các giao dịch tài chính, chuyển khoản, mua sắm, đăng ký kết hôn, đăng ký khai sinh, … càng ngày càng được thực hiện qua môi trư ng mới, môi trư ng điện tử. Tuy nhiên chúng ta cần nhấn mạnh rằng đi kèm với sự phát triển của khoa học kỹ thuật, các thiết bị điện tử hiện đại hoàn toàn có thể “bắt” được các thông tin đang được truyền đi trên mạng, trên internet hay qua điện thoại vô tuyến, hữu tuyến, sóng vệ tinh, … Vì vậy nhu cầu bảo mật thông tin ngày càng tr nên quan trọng và cấp thiết. Trong các bài học sau đây chúng ta chủ yếu trình bày những nét chính của lĩnh vực mật mã hóa dữ liệu. Nếu muốn nghiên cứu chuyên sâu chi tiết, bạn đọc có thể tham khảo thêm từ các tài liệu tham khảo được nêu hoặc từ nguồn tài nguyên phong phú trên internet. Trước hết trong bài học này chúng ta sẽ trình bày các vấn đề và các khái niệm cơ bản của bảo mật. Thông báo, văn bản (message, plaintext) Thông báo, văn b n là m t chuỗi h u h n kí hi u lấy từ m t b ng ch cái ∑ và th ờng đ ợc kí hi u là m. đây ∑ thư ng là bảng chữ cái tiếng Anh gồm 26 kí tự, thỉnh thoảng có thêm cả kí tự khoảng trắng. Mật mã hóa (encryption), phép mật mã hoá e(m) M t mã hoá là vi c bi n đổi m t thông báo sao cho nó không thể hiểu nổi đối v i bất kỳ ai ngo i trừ ng ời nh n đ ợc mong muốn. D hiểu hơn m t mã hóa là vi c “ngụy trang” hay “che dấu” thông báo, văn b n d i m t d ng khác để cho nh ng ng ời “ngoài cu c” không thể xác định đ ợc thông báo, văn b n gốc. Phép m t mã hóa th ờng đ ợc kí hi u là e(m), v i m là thông báo c n m t mã hóa. Trong thực tế, mật mã hoá được xem như là một hàm, một ánh xạ hay một giải thuật với một tập các thông số (ngoài thông số cần có là thông báo cần mã hoá). Từ đây chúng ta có khái niệm khoá. Khoá (key), khóa mã hóa, khóa giải mã Khoá là m t thông số đ u vào của phép mã hoá hoặc gi i mã (nó không ph i là thông báo cũng nh là chuỗi m t mã). Khóa dùng để mã hóa kí hi u là ke và khóa dùng để gi i mã kí hi u là kd. Trong m t số h m t mã hóa 2 khóa này chính là m t lúc Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 115 Lý thuyết Thông tin đó chúng ta gọi chung là k, ng ợc l i trong m t số h m t mã hóa 2 khóa này là khác nhau. Tuy nhiên gi a 2 khóa này th ờng có m t mối liên h v i nhau. Một phép mật mã hoá có thể có nhiều khoá mã hóa (tương ứng có nhiều khóa giải mã). Các khóa này thư ng được sinh ra từ một khóa mã hóa ban đầu nào đó được chọn trước. Chuỗi mật mã (cipher, ciphertext, cryptogram) Chuỗi m t mã là chuỗi “ngụy trang”, tức là chuỗi k t qu t ơng ứng của chuỗi thông báo qua phép m t mã hóa và th ờng đ ợc kí hi u là c. c = e(m, ke). Phép giải mã (decryption) d(c, kd) Phép gi i mã là quá trình xác định thông báo gốc từ chuỗi m t mã c và khóa gi i mã kd và th ờng đ ợc kí hi u là d(c, kd). d(c, kd) = m. Chúng ta có thể xem phép giải mã như là một ánh xạ ngược của phép mã hóa. Hệ mật mã (cryptosystem) M t cách hình thức, m t h m t mã đ ợc định nghĩa là m t b bốn (M, K1, K2, C). Trong đó M là t p các thông báo m trên các b ng ch cái ∑, K1 là t p h u h n các khoá mã hóa ke, K2 là t p h u h n các khoá gi i mã kd, C là t p các chuỗi m t mã c trên b ng ch cái Γ, ngoài ra còn có thêm gi thi t rằng tồn t i các hàm hay gi i thu t e và d sao cho e: M × K1 → C và đối v i mỗi cặp (m, ke) ∈ M × K1, d: C × K2 → M d(e(m, ke) , kd) = m Chú ý Chúng ta thông thư ng giữa ke và kd có mối liên hệ với nhau và thư ng được sinh ra theo từng cặp nên trong nhiều trư ng hợp chúng ta có thể xem một hệ mật mã như là một bộ ba (M, K, C) trong đó K là tập hợp các khóa mã hóa k. Trong ngữ cảnh của lý thuyết mật mã hóa đôi lúc chúng ta nói mã hóa thay cho mật mã hóa và hệ mã thay cho hệ mật mã. Hệ mật mã khóa bí mật (secret key cryptosystem) H mã khóa bí m t hay còn gọi là h mã đối xứng (symmetric cryptosystem) là h mã mà trong đó vi c mã hóa và gi i mã dùng chung m t khóa bí m t. Hệ mật mã khóa công khai (public key cryptosystem) H mã khóa công khai hay còn gọi là h mã bất đối xứng (assymmetric cryptosystem) là h mã mà trong đó vi c mã hóa và gi i mã s dụng 2 khóa khác nhau, từ khóa này không thể tìm ra khóa kia m t cách d dàng. Khóa dùng để mã hóa th ờng đ ợc thông báo công khai và đ ợc gọi là khóa công khai (public key), còn khóa dùng để gi i mã đ ợc gi bí m t và đ ợc gọi là khóa bí m t hay khóa riêng t (private key). Chú ý Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 116 Lý thuyết Thông tin Hiện nay có một số hệ mã đối xứng dùng 2 khóa khác nhau cho việc mã hóa và giải mã. Cả 2 khóa này đều được giữ bí mật vì từ khóa này có thể xác định được khóa kia không khó khăn. Dĩ nhiên nó cũng không được gọi là hệ mã khóa “công khai” được. 14.2 M t số phép m t mã đơn gi n Phép thay thế đơn giản Trong phép này, khoá là m t hoán vị π của b ng ch cái ∑ và mỗi kí hi u của thông báo đ ợc thay bằng nh của nó qua hoán vị π. Thư ng thư ng, khoá được biểu diễn như một chuỗi 26 kí tự, chẳng hạn nếu khoá là UXEOS…, thì nó biểu thị rằng bất kỳ một sự xuất hiên của A trong thông báo thì được thay bằng U, B được thay bằng X, C được thay bằng E, D được thay bằng O, E được thay bằng S, … Các khoảng trắng thư ng được giữ nguyên không bị thay thế. Phép thay thế n-gram Thay vì thay thế đối với các kí tự, ngư i ta có thể thay thế cho từng cụm 2 kí tự (gọi là digram) hoặc từng cụm 3 kí tự (gọi là trigram) và tổng quát cho từng cụm n kí tự (gọi là ngram). Nếu bảng chữ cái ∑ gồm 26 kí tự tiếng Anh thì phép thay thế n-gram sẽ có khoá là một hoán vị của 26n n-gram khác nhau (có 26n chuỗi khác nhau chiều dài n). Trong trư ng hợp digram thì hoán vị gồm 262 digram và có thể biểu diễn tốt nhất bằng một dãy 2 chiều 26 × 26 trong đó các hàng biểu diễn kí hiệu đầu tiên, các cột biểu diễn kí hiệu thứ hai, nội dung của các ô biểu diễn chuỗi thay thế. Ví dụ bảng 2 chiều sau biểu thị AA được thay bằng EG, AB được thay bằng RS, BA được thay bằng BO, BB được thay bằng SC, … A B … A EG BO B RS SC … Phép hoán vị bậc d Đối với một số nguyên dương d bất kỳ, chia thông báo m thành từng khối có chiều dài d. Rồi lấy một hoán vị π của 1, 2, …, d và áp dụng π tới mỗi khối. Chẳng hạn nếu d = 5 và π = (4 1 3 2 5), thì có nghĩa là hoán vị (1 2 3 4 5) sẽ được thay bằng hoán vị mới (2 4 3 1 5). Ví dụ nếu chúng ta có thông báo m = JOHN |IS A |GOOD |ACTOR thì qua phép mật mã này sẽ tr thành chuỗi mật mã sau c = ONHJ |SA I |ODOG |COTAR Để giải mã ngược lại ta phải tìm hoán vị ngược π - 1. Trong trư ng hợp này chúng ta có π - 1 = (2 4 3 1 5). Tổng quát nếu π = (i1 i2 … in) thì π - 1 = (j1 j2 … jn) trong đó ji k = k , có nghĩa là trong π - 1 vị trí thứ i1 chứa giá trị 1, vị trí thứ i2 chứa giá trị 2, … Phương pháp Vigenère và Caesar Trong phương pháp này, khoá bao gồm một chuỗi của d kí tự. Chúng được viết lặp lại bên dưới thông báo và được cộng modulo 26, với chú ý rằng bảng chữ cái được đánh số từ A = 0 đến Z = 25. Các kí tự khoảng trắng sẽ được giữ nguyên không cộng. Chẳng hạn với d = 3, nếu khoá là chuỗi ABC thì thông báo m= M A R Y I S G O O D với khoá Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 117 Lý thuyết Thông tin k= A B C A B C A B C A tr thành c= M B T Y J U G P Q D Trong trư ng hợp d = 1, như vậy khoá chỉ là một kí tự đơn, thì được gọi là phương pháp Caesar vì được cho là được sử dụng lần đầu b i Julius Caesar. Phương pháp Playfair Đây là một sơ đồ dựa trên sự thay thế digram trong đó khoá là một hình vuông kích thước 5 × 5 chứa một sự sắp xếp nào đó của 25 kí tự của bảng chữ cái (không tính kí tự J vì sự xuất hiện ít của nó và có thể thay nó bằng I). Giả sử chúng ta có ma trận khoá như sau B W L C Q Y S A O N D F R I M G U K V H Z P X E T Sự thay thế sẽ được thực hiện như sau. Chẳng hạn nếu digram cần thay thế là AV thì trong hình chữ nhật có A, V là hai đỉnh chéo nhau thay A bằng đỉnh kề của nó theo đư ng thẳng đứng chính là O và tương tự thay V bằng đỉnh kề của nó theo đư ng thẳng đứng chính là K. Tương tự nếu digram cần thay thế là VN thì chuỗi thay thế là HO. Nếu các kí tự của digram nằm trên hàng ngang thì chuỗi thay thế là các kí tự bên phải của chúng. Chẳng hạn nếu digram là WU thì chuỗi thay thế là SP, nếu digram là FP thì chuỗi thay thế là UW, nếu digram là XR thì chuỗi thay thế là LK. Tương tự nếu các kí tự của digram nằm trên hàng dọc thì chuỗi thay thế là các kí tự bên dưới của chúng. Chẳng hạn nếu digram là SO thì chuỗi thay thế là AN, nếu digram là MR thì chuỗi thay thế là DI, nếu digram là GH thì chuỗi thay thế là UG. Trong trư ng hợp digram là một cặp kí tự giống nhau chẳng hạn OO hoặc là một kí tự được đi kèm một khoảng trắng chẳng hạn B฀ thì có nhiều cách xử lý, cách đơn giản nhất là giữ nguyên không biến đổi digram này. Phương pháp khoá tự động (autokey) Trong phương pháp này, có một khoá “mồi” (priming key), cái mà thư ng là ngắn và được sử dụng để kh i đầu quá trình mật mã hoá. Quá trình mã hoá được tiếp tục bằng cách sử dụng cả bản thân thông báo lẫn chuỗi mật mã (cryptogram) đang chạy. Xét ví dụ sau: Giả sử khoá mồi là VENUS và thông báo là SEND SUPPLIES. Đầu tiên sử dụng thông báo như một khoá đang chạy, chúng ta mã hoá bằng phép cộng mod 26. (Chú ý các khoảng trắng sẽ được bỏ qua) m: k: Chuỗi mật mã S V N E E I N N A D U X S S K U S M P E T P N C L D O I S A E U Y S P H Sử dụng chuỗi mật mã trên như là một khoá với khoá mồi như cũ chúng ta được kết quả mã hoá như sau. m: k: Chuỗi mật mã S V N E E I N N A D U X S S K U N H P I X P A P L X I I K S E M Q S T L Phương pháp biến đổi tuyến tính Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 118 Lý thuyết Thông tin Ý tư ng cơ bản là chia thông báo thành những khối có chiều dài d và gắn khối này với một vectơ x, gồm d số nguyên, và rồi nhân vectơ x này với một ma trận không suy biến (tức có định thức khác 0) sẽ được chuỗi mật mã y = Ux. Việc giải mã được thực hiện bằng cách nhân y với ma trận nghịch đảo U - 1 của U, x = U - 1y. Để đảm bảo các phép toán được thực hiện trên một trư ng, các tính toán sẽ được tính trong modulo của một số nguyên tố. Chẳng hạn lấy bảng chữ cái ∑ gồm 37 kí tự như sau và được đánh số lần lượt từ 0 đến 36: 10 chữ số từ 0 đến 9, khoảng trắng, và 26 kí tự chữ cái. Với bảng chữ cái này, nếu chọn d = 2 và ma trận làm khoá là: ⎡3 13⎤ k=U= ⎢ ⎥ ⎣ 22 15⎦ Thông báo m = FRIEND được biểu diễn như là m = FR | IE | ND = 15, 27 | 18, 14 | 23, 13 Thì ⎡ 3 13⎤ ⎡15 18 23⎤ ⎡ 26 14 16 ⎤ ⎢ 22 15⎥ × ⎢ 27 14 13 ⎥ = ⎢32 14 35⎥ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦ Vậy chuỗi mật mã là c = 26, 32 | 14, 14 | 16, 35 = Q, W | E, E | G, Z = QWEEGZ 14.3 Bẻ gãy (breaking) m t h m t mã Bẻ gãy một hệ mật mã có nghĩa là gì? Nó có nghĩa là việc xác định được văn bản hay thông báo gốc từ những gì có thể biết được. Chúng ta cần phân tích những khả năng có thể bị bẻ gãy của một hệ mật mã, có như vậy mới giúp chúng ta xây dựng được những yêu cầu, tiêu chuẩn đối với một hệ mật mã an toàn và cho ra đ i những hệ mật mã này và những hệ mật mã ngày càng an toàn hơn (cái mà sẽ được trình bày trong các bài sau). Nói chung việc xây dựng và bẻ gãy các hệ mật mã đó là một quá trình chiến đấu giữa hai bên, một bên là những ngư i xây dựng còn một bên là những ngư i tìm các yếu điểm của cách xây dựng để vượt qua. Chính quá trình bẻ gãy đã giúp cho việc xây dựng ngày càng tốt hơn, tuy nhiên ngược lại các kỹ thuật bẻ gãy cũng ngày càng phát triển và tinh vi hơn. Đây có thể xem là một trư ng hợp điển hình của quá trình chiến đấu và phát triển không ngừng của hai mặt của một vấn đề. Quay tr lại với việc bẻ gãy, những chuyên gia mật mã hay những kẻ tấn công thư ng được giả thiết biết đầy đủ thông tin về hàm mã hoá e, hàm giải mã d và khóa mã hóa ke. Thêm vào đó, họ cũng có thể có nhiều thông tin hỗ trợ như các thống kê về ngôn ngữ, kiến thức về ngữ cảnh, vân vân. Họ sẽ chắn chắn có một chuỗi mật mã nào đó, và tất cả những gì mà họ thiếu là khoá gi i mã kd từ đó họ có thể sử dụng d để giải mã c một cách chính xác. Và vì vậy vi c bẻ gãy có thể qui v vi c tìm/tính khóa gi i mã kd từ những gì họ biết. Việc bẻ gãy có thể minh họa như hình ảnh bên dưới. Bộ phát sinh khoá k ke m Bộ mã hoá e kd c = e(m, k) Bộ giải mã d Những kẻ tấn công Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM m 119 Lý thuyết Thông tin Hình 14.1 Mô hình của một hệ mật mã Những giả thiết trên là hoàn toàn thực tế. Thật vậy những phương pháp mã hóa và giải mã hầu như không thể giữ bí mật. Đối với những phương pháp mã hóa đơn giản thì những kẻ tấn công đã biết đầy đủ. Còn đối với những phương pháp mã hóa phức tạp thì thư ng không phải do một ngư i nghĩ ra mà là do một nhóm hoặc nhiều ngư i cùng nghĩ ra. Thậm chí ngay cả khi chỉ do một ngư i nghĩ ra thì khi áp dụng vào các hệ thống truyền thông vẫn có thể có nhiều ngư i quản lý hệ thống đó biết. Chính vì vậy việc giữ bí mật phương pháp mã hóa là rất khó. Bí mật lúc này giống như một “cây kim trong bọc”, lâu ngày cũng có thể bị phát hiện. Mà một khi một ngư i khác đã biết thì nhiều ngư i có thể biết. Và điều này cũng đúng đối với phép giải mã. Chính vì hiểu được điều này nên mới có sự ra đ i của hệ mã khóa công khai như đã được giới thiệu trên. Trong hệ mã khóa công khai, giải thuật mã hóa, giải mã, và cả khóa mã hóa đều được công khai, chỉ có duy nhất một cái cần giữ bí mật đó là khóa dùng để giải mã. Điều này cũng giống các loại ổ “khóa bi” hay “khóa số vòng” trong thực tế. Chúng ta nhớ rằng, nguyên lý chế tạo của các loại ổ “khóa bi” hay “khóa số vòng” hoàn toàn có thể biết được, nhưng để m được ổ khóa chúng ta cần phải có chìa. Có ba khả năng tấn công cái mà chúng ta dự đoán đối phương có thể sẽ tấn công trên hệ thống của chúng ta: 1. Tấn công chỉ dựa trên chuỗi mật mã (crytogram-only attack): Đây là trư ng hợp đối phương chỉ biết một vài mẫu chuỗi mật mã c. 2. Tấn công dựa trên văn bản đã biết (known-plaintext attack): Trư ng hợp này thực tế hơn trư ng hợp (1). Trong trư ng hợp này những ngư i tấn công được giả thiết là đã biết một độ dài đáng kể của văn bản thông báo và chuỗi mật mã tương ứng, và từ đó cố gắng tìm ra khoá (mã hóa cũng như giải mã). Đây là một sự tấn công dữ dội khó chống đỡ hơn nhiều nhưng ngày nay được xem như là một chuẩn an toàn tối thiểu phải đạt được. Thật vậy vào th i điểm hiện tại, tiêu chuẩn thích hợp nhất để đánh giá một hệ mật mã là khả năng của nó để chống đỡ sự tấn công thậm chí còn mạnh hơn như sau 3. Tấn công dựa trên văn bản được chọn (chosen-plaintext attack): Trong trư ng hợp này, những ngư i tấn công có thể đã có được một số lượng tuỳ ý của các cặp thông báo và chuỗi mật mã tương ứng (m, c). Không khó để thấy rằng không có hệ thống (hay phương pháp) mật mã nào đã mô tả mục 14.2 trên đây có thể chống đỡ một cuộc tấn công dựa trên văn bản được chọn. Trư ng hợp liên quan đến khả năng bị tấn công của nó đối với sự tấn công dựa trên văn bản đã biết là phức tạp hơn. Chẳng hạn, xét hệ thống đơn giản nhất – hệ thống dùng phương pháp thay thế đơn giản – sao cho khoá k là một hoán vị của 26 chữ cái trong đó A → P, B → F, vân vân. Bây gi nếu thông báo m được g i là “silly message” bao gồm chữ A được lặp lại n lần, thì trong chuỗi mật mã c tương ứng, chữ P sẽ được lặp lại n lần. Không thành vấn đề chúng ta có n lớn bao nhiêu, cặp thông báo - chuỗi mật mã cụ thể này sẽ không sinh ra khoá k. Tuy nhiên bằng việc dựa vào các thống kê về xác suất xuất hiện của các kí tự, đồng th i duyệt qua các phương án chọn khóa theo thứ tự được đánh giá là hợp lý nhất đến ít hợp lý hơn cộng với sự trợ giúp tính toán với tốc độ nhanh của các siêu máy tính, việc tìm ra khóa sẽ là không quá khó và tốn nhiều th i gian. Shannon và nhiều nhà nghiên cứu khác bằng những nghiên cứu về thống kê và entropy của tiếng Anh đã phát biểu rằng Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 120 Lý thuyết Thông tin V i nh ng chuỗi m t mã có chi u dài 30 kí tự hoặc hơn biểu di n cho nh ng chuỗi thông báo có nghĩa trong ti ng Anh thì g n nh chắc chắn có thể tìm ra khóa của nó trong các ph ơng pháp mã hóa nói trên. Tóm lại có thể nói rằng nếu đã cho một chiều dài vừa đủ của thông báo và chuỗi mật mã, bất kỳ hệ thống hay phương pháp mật mã trên đều có thể bị bẻ gãy (crack), tức là khóa có thể được tìm thấy. đây chúng ta xem một ví dụ đơn giản về cách bẻ gãy. Ví dụ 14.1 Giả sử một hệ mật mã được biết là dựa trên phương pháp Caesar với bảng chữ cái gồm 27 kí tự được đánh số như sau A = 0, B = 1, …, Z = 25, khoảng trắng = 26 và phép cộng thực hiện theo mod 27. Chúng ta chộp được chuỗi mật mã c sau HWXGOQCCZOXGOXBORCST Chúng ta đề nghị cách tấn công sau để tìm khoá chưa biết k0. Chọn các khoá dự tuyển cho k0 một cách ngẫu nhiên và đổi ngược chuỗi mật mã, theo từng kí tự, cho đến khi nào thông báo có ý nghĩa. Vì vậy, nếu đầu tiên chúng ta chọn k0 = E, chúng ta sẽ đổi ngược c và nhận được DSTC … tại ngữ cảnh này chúng ta thấy rằng E không phải là khoá k0. Lại chọn k0 = Z, cái này sẽ đổi ngược c thành JYZ … cái này bác bỏ Z. Sự lựa chọn kế tiếp (theo linh cảm ???!!!) của chúng ta là k0 = P và nhanh chóng thấy rằng chuỗi mật mã đã được biến đổi thành chuỗi văn bản có nghĩa THIS BOOK IS IN CODE Tại ngữ cảnh này chúng ta không đảm bảo rằng không có cặp thông báo-khoá khác mà sẽ sinh ra cùng chuỗi mật mã trên. Tuy nhiên thủ tục kiểm tra của những khoá khác cũng tương tự như vậy. 14.4 K t hợp các ph ơng pháp m t mã hoá Một cách tự nhiên để tăng tính bảo mật là kết hợp nhiều phương pháp mật mã hoá với nhau. Hai cách như vậy, được Shannon đề nghị từ năm 1949, vẫn tạo nên cơ s của nhiều hệ mật mã thực tế. Đó là 1. Cách dùng tổng trọng số: Nếu S1, S2, …, Sn là các hệ mã hoá có cùng không gian ∑ pi = 1 thì tổng của chúng n thông báo và 0 < pi < 1 và i =1 ∑ pi S i n i =1 là hệ mật mã dùng Si với xác suất pi. Lấy ví dụ trong trư ng hợp n = 2 tức là có 2 hệ mã hóa S1, S2.. Thì hệ thống p1S1 + p2S2 có m + n khóa k1, k2, …, km, k1’, k2’, …, kn’ trong đó khóa ki được sử dụng với xác suất p1qi còn khóa kj’ được sử dụng với xác suất p2qi’. 2. Cách dùng tích: Áp dụng các hệ thống (hay phương pháp) nối tiếp nhau, đầu ra của hệ thống này, chẳng hạn S1, là đầu vào của hệ thống kế tiếp, chẳng hạn S2. Dĩ nhiên tập hợp đầu ra của hệ thống đi trước S1 phải là tập con của tập hợp đầu vào của hệ thống đi sau kế tiếp S2. Nếu thực hiện được thì chúng ta kí hiệu hệ thống kết hợp này là S = S1 ο S2. Giả sử S1 có các khóa k1, k2, …, km, mỗi khóa ki được dùng với xác suất qi, S2 có các khóa k1’, k2’, …, kn’, mỗi khóa kj’ được dùng với xác suất qj’, thì S = S1 ο S2 có mn khóa với Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 121 Lý thuyết Thông tin các xác suất qiqj’. Chú ý rằng S1 ο S2 thư ng có ít hơn mn khóa có hiệu quả, vì một vài phép biến đổi của tích có thể trùng nhau. 3. Chúng ta có thể kết hợp đồng th i cả hai cách trên. S3 ο (p1S1 + p2S2) = p1S3 ο S1 + p2S3 ο S2 (p1S1 + p2S2) ο S3 = p1S1 ο S3 + p2S2 ο S3 S1 ο (S2 ο S3) = (S1 ο S2) ο S3 Chú ý S1 ο S2 tổng quát không bằng với S2 ο S1. 14.5 Sự không chắc chắn và sự b o m t hoàn h o (perfect secrecy) Xét một hệ mật mã (M, K, C) và giả thiết rằng M = {m1, m2, …, mn} là một tập hữu hạn các thông báo. Gọi pi là xác suất thông báo mi được g i đi, qj là xác suất khóa kj được chọn và việc chọn khóa độc lập với thông báo được g i đi. Từ hai sự phân bố xác suất này chúng ta suy ra sự phân bố xác suất của chuỗi mật mã c P (c ) = ∑ pi k j n i =1 trong đó vế phải được tính tổng trên tất cả các cặp thông báo - khóa (mi, kj) sao cho e(mi, kj) = c. Đến đây chúng ta có thể coi việc mật mã hóa tương tự như một kênh truyền thông được trình bày trong BÀI 9, trong đó tập thông báo M là một nguồn r i rạc không nhớ, còn hàm mã hóa e với các khóa k là kênh truyền. Chúng ta có H ( M ) = − ∑ pi log pi n i =1 H ( K ) = − ∑ q j log q j H (C ) = − ∑ P (c) log P(c) n i =1 Chúng ta gọi H(K | C) là sự không chắc chắn về khóa, H(M | C) là sự không chắc chắn về thông báo. Đôi khi chúng ta kí hiệu hệ mật mã (M, K, C) bằng S và rồi kí hiệu sự không chắc chắn về khóa, H(K | C), là H(S). Định lý 14.1 Sự không chắc chắn v khóa quan h v i sự không chắc chắn v thông báo bằng H(K | C) = H(M | C) + H(K | M, C) Ch ng minh H(M | C) = = H(K | C) = = H(M, C) - H(C) H(M, K, C) - H(K | M, C) - H(C) H(K, C) - H(C) H(M, K, C) - H(M | K, C) - H(C) Nhưng H(M | K, C) = 0 Nên H(K | C) Từ đây suy ra điều phải chứng minh. = H(M, K, C) - H(C) Hệ quả 14.1 Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 122 Lý thuyết Thông tin Sự không chắc chắn v khóa l n hơn hoặc bằng sự không chắc chắn v thông báo. Vì H(M | C) là độ bất ng trung bình về thông báo m khi nhận được chuỗi mật mã c nên chúng ta có thể nói rằng một hệ mật mã (M, K, C) là hoàn hảo nếu H(M | C) = H(M). Có nghĩa là việc nhận được chuỗi mật mã c không giúp chúng ta biết thêm gì về thông báo m. Hay nói cách khác nguồn M và C độc lập với nhau. Tuy nhiên như chúng ta sẽ thấy rất khó để đạt được điều này. Định lý 14.2 M t h m t mã (M, K, C) là hoàn h o n u và chỉ n u P(m | c) = P(m) v i mọi thông báo m ∈ M và chuỗi m t mã c ∈ C. Hệ quả 14.2 M t h m t mã (M, K, C) là hoàn h o n u và chỉ n u P(c | m) = P(c) v i mọi thông báo m ∈ M và chuỗi m t mã c ∈ C. Định lý 14.3 Đi u ki n c n để m t h m t mã (M, K, C) là hoàn h o là nó có số l ợng khóa ít nhất là bằng số l ợng thông báo. Ch ng minh Xét tập thông báo M = {m1, m2, …, mn} và một khóa k cố định. Khóa này sẽ ánh xạ các thông báo mi khác nhau thành các chuỗi mật mã khác nhau ci. Vì hệ mật mã là hoàn hảo nên dựa vào hệ quả trên đây chúng ta có P(ci | mi) = P(ci) đồng th i P(ci | mj) = P(ci) với mọi j ≠ i. Vì vậy phải có một khóa k’ khác nào đó cái mà ánh xạ mj thành ci. Điều này đúng cho mọi j (1 ≤ j ≤ n), và tất cả các khóa như vậy phải khác nhau. Vì vậy phải có ít nhất là n khóa. Ví dụ 14.2 Một ví dụ cổ điển về hệ mật mã hoàn hảo là “one-time pad”. Nó được giới thiệu lần đầu b i G. S. Vernam vào năm 1926. Nó hoạt động như sau. Giả sử bảng chữ cái Σ là bảng chữ cái tiếng Anh gồm 26 kí tự (các dấu chấm câu và khoảng trắng được bỏ qua) và các kí tự này được biểu diễn theo đúng thứ tự thành các số nguyên từ 0 đến 25.. Thông báo m g i đi gồm n kí tự. Để mã hóa m, sinh một chuỗi ngẫu nhiên n kí tự từ bảng chữ cái Σ, mỗi kí tự sẽ có một xác suất được chọn là 1/26 và việc chọn các kí tự là độc lập lẫn nhau. Dãy ngẫu nhiên này (z1, z2, ..., zn) sẽ làm khóa cho phép mã hóa sau. C = e(m, k) = (y1, y2, ..., yn) trong đó yi = xi + zi (mod 26) Dễ dàng thấy rằng hệ thống này có 26n khóa có thể, vì vậy H(K) = n log 26 Vì các khóa này đều có khả năng được chọn như nhau nên chúng ta có P(k | c) = 1/26n Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 123 Lý thuyết Thông tin với bất kỳ khóa k nào. Hệ mật mã này đã được chứng minh là hệ mật mã hoàn hảo. Tuy nhiên có một vài hạn chế lớn trong việc sử dụng các hệ mật mã này. 1. Không có một phương pháp toán học để sinh ra các chuỗi ngẫu nhiên độc lập làm khóa. Chỉ có một số phương pháp toán học sinh ra các chuỗi “giả ngẫu nhiên” mà thôi, tuy nhiên chúng không đảm bảo được rằng sẽ đạt được mức độ bảo mật giống như trư ng hợp ngẫu nhiên thật sự. 2. Chiều dài các khóa đúng bằng chiều dài thông báo và phải được truyền đến bên nhận để bên nhận dùng cho việc giải mã. Như vậy khóa này cũng có thể bị bắt được trên đư ng truyền và vì vậy đến lượt nó lại cần phải được mã hóa!!! Mặc dù có những hạn chế như vậy nhưng chúng cũng đã được sử dụng khá nhiều trong thực tế trước đây. 14.6 Các hàm m t chi u (one-way function) Ý tư ng dùng các hàm một chiều để mã hóa là cốt lõi của các phương pháp mật mã hóa. Tuy nhiên rất khó để đưa ra một định nghĩa toán học chính xác cho nó. Một cách không hình thức, một hàm một chiều là một hàm f: S → T, trong đó S, T là hai tập bất kỳ sao cho 1. Với bất kỳ x ∈ S, f(x) là dễ dàng để tính. 2. Đã cho một y = f(x) với một x nào đó chưa được biết, thì rất “khó” (hoặc không khả thi) để tìm ra được x đối với phần lớn các y thuộc T. Khó đây đồng nghĩa với việc phải tốn rất nhiều th i gian và chi phí để tìm ra x. Nó rõ ràng rằng, đã cho f(x), một cách tìm x là tìm kiếm vét cạn thông qua tất cả những giá trị x có thể của S. Tuy nhiên điều này sẽ không khả thi nếu S quá lớn, chẳng hạn nếu S là tập tất cả những chuỗi nhị phân 200 bit (có 2200 chuỗi như vậy). Ví dụ 14.3 Cho S là tập tất cả các cặp số nguyên tố (p, q) và f(p, q) = p × q Dễ thấy rằng từ p, q chúng ta dễ dàng tìm ra f(p, q) nhưng ngược lại trong trư ng hợp p và q là các số nguyên tố khá lớn, chẳng hạn có khoảng 100 chữ số, từ f(p, q) chúng ta phải tốn rất “nhiều” th i gian mới có thể tìm ra p và q. Một ví dụ khác như sau. Cho S = {1, 2, ..., p - 1} với p là một số nguyên tố khá lớn (chẳng hạn có 200 chữ số). Có khá nhiều đa thức f(x) (là song ánh) trên S f(x) = a0 + a1x + a2x2 + ... + anxn (mod p) sao cho từ x chúng ta dễ dàng tính được f(x) nhưng điều ngược lại thì rất khó. Bài toán mật khẩu (password) Một trong những ứng dụng đầu tiên của các hàm một chiều là vào việc giải quyết bài toán về bảo mật các mật khẩu trong các mô hình chứng thực (xác nhận quyền hợp lệ) điện tử (electronic authentication scheme). Ví dụ xét một hệ thống máy tính truy xuất từ xa trong đó mỗi ngư i sử dụng (user) phải đăng nhập (log on) vào hệ thống bằng cách g i đi một mật khẩu (password) bí mật. Rất nguy hiểm về mặt bảo mật nếu chúng ta lưu danh sách những ngư i sử dụng và password của họ trong một dạng không mã hóa trong một file trên máy, vì nó gần như không thể giữ bí mật nội dung file được. R. M. Needham đã đề nghị giải pháp sau đây cho bài toán này. Cho f là một hàm một chiều nào đó trong đó miền xác định của nó là tập các password có thể (là những chuỗi kí tự). Khi một ngư i sử dụng mới tham gia vào hệ thống, anh ta sẽ Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 124 Lý thuyết Thông tin chọn một password, gọi là pi, cho mình. Thay vì máy tính lưu trữ pi, nó sẽ lưu trữ chuỗi f(pi) cái mà dễ dàng tính được từ pi. Một ngư i bất kỳ không có quyền hợp lệ là có thể xem được nội dung của file cái mà chứa danh sách tên ngư i sử dụng tương ứng. Có nghĩa là file này không cần được giữ bí mật. Khi ngư i sử dụng ui đăng nhập vào hệ thống, anh ta chỉ cần gõ vào tên đăng nhập ui và mật khẩu pi của anh ta, máy tính sẽ tính f(pi) và so sánh nó với phần tử (ui , f(pi)) trong file. Sự trùng khớp cho phép ui truy xuất vào hệ thống. Còn những ngư i không có quyền hợp lệ muốn bẻ gãy hệ thống bằng cách ăn cắp password thì phải tìm pi từ f(pi) tức là tìm hàm ngược của f. 14.7 Cơ sở toán học của m t mã hóa Kí hiệu ước số chung lớn nhất c số chung l n nhất của các số nguyên n1, n2, …, nk đ ợc kí hi u là gcd(n1, n2, …, nk). Hàm-phi Euler φ(n) V i n là số tự nhiên, φ(n) đ ợc định nghĩa là số các số tự nhiên nhỏ hơn n và nguyên tố cùng nhau v i n. Ví dụ φ(4) = 2 (bao gồm 1 và 3), φ(5) = 4, φ(6) = 1, φ(7) = 6, φ(8) = 4. Ta có một số kết quả sau. 1. Với p nguyên tố thì φ(p) = p - 1, 2. Với p nguyên tố, k là số tự nhiên thì φ(pk) = pk – pk - 1 = pk - 1(p – 1) 3. Với m, n là các số tự nhiên nguyên tố cùng nhau thì φ(mn) = φ(m) φ(n) Định lý 14.4 Định lý Fermat N u p là số nguyên tố, a là m t số nguyên thì ap ≡ a (mod p) N u p không là c số của a thì ap – 1 ≡ 1 (mod p) Ví dụ 14.4 45 ≡ 4 (mod 5), 47 ≡ 4 (mod 7), 47 - 1 ≡ 1 (mod 7), 105 - 1 ≡ 0 (mod 5) Định lý 14.5 Định lý Fermat mở rộng (Euler) N u a và m nguyên tố cùng nhau thì aφ(m) ≡ 1 (mod m) Trong trư ng hợp m là nguyên tố thì φ(m) = m – 1 ta có định lý Fermat. Hệ quả 14.3 V i a, b, c, m là các số tự nhiên, a ≡ b (mod φ(m)), c và m nguyên tố cùng nhau (tức gcd(c, m) = 1) thì ca ≡ cb (mod m) Thật vậy a ≡ b (mod φ(m)) nên a = kφ(m) + b suy ra ca ≡ ckφ(m) + b ≡ ckφ(m) × cb≡ 1 × cb ≡ cb (mod m) Hệ quả 14.4 Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 125 Lý thuyết Thông tin N u e, d là các số nguyên thõa mãn e.d ≡ 1 (mod φ(m)) thì v i mọi số c nguyên tố cùng nhau v i m ta có (c e ) d ≡ c(mod m) Hệ quả này được suy ra từ hệ quả trên bằng cách áp dụng a = e.d còn b = 1. Căn nguyên th y (primitive root) Cho n và a là các số tự nhiên nguyên tố cùng nhau và 1 ≤ a ≤ n. N u ∀ d, 1≤ d < φ(n) mà ad ≠ 1 (mod n) thì a đ ợc gọi là căn nguyên thủy của n. Ví dụ, 2 là căn nguyên thủy của 5 b i vì trong mod 5 21 = 2, 22 = 4, 23 = 3, 24 = 1 Nhận xét Không phải mọi số nguyên đều có căn nguyên thủy. 8 là số tự nhiên nhỏ nhất không có căn nguyên thủy. Định lý 14.6 Số n có căn nguyên thủy n u và chỉ n u n là 1, 2, 4 hoặc n có d ng pk hoặc 2pk trong đó p là m t số nguyên tố lẽ và k là số tự nhiên. N u n có căn nguyên thủy thì nó có chính xác φ(φ(n)) căn nguyên thủy. Bổ đề 14.1 Mỗi số tự nhiên mà không ph i là số chính ph ơng (bình ph ơng của m t số tự nhiên khác) là căn nguyên thủy của m t số nguyên tố nào đó. Nhận xét Nếu n là số tự nhiên khá lớn (có vài trăm chữ số), cho đến bây gi chưa có một giải thuật hiệu quả (chạy trong th i gian “chấp nhận được”) để tìm căn nguyên thủy của nó. Hàm logarit rời rạc Cho n là m t số tự nhiên bất kỳ có căn nguyên thủy là a. V i x, y là các số tự nhiên trong đó (0 ≤ x < φ(n)) và thõa y = ax (mod n) thì x đ ợc gọi là logarit rời r c của y v i cơ số a và tính trong mod n và đ ợc vi t x = loga y (mod n) Nhận xét Hàm ax trên là một hàm một chiều. Tức là từ x chúng ta dễ dàng tính được y, nhưng ngược lại từ y rất khó để tính được x. Hiện tại chưa có một giải thuật hiệu quả nào, chạy trong th i gian “chấp nhận được”, thực hiện được điều này. ng dụng hàm một chiều để giải quyết bài toán phân phối khóa Một trong những bài toán cơ bản của các phương pháp mật mã hóa cổ điển là làm thế nào để phân phối khóa một cách an toàn. Nếu thông báo không thể được truyền đi an toàn thì liệu khóa có thể được truyền đi một cách an toàn ? Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 126 Lý thuyết Thông tin Năm 1976, Diffie và Hellman đã đề nghị một cách rất hiệu quả để giải quyết bài toán này bằng cách dựa trên tính chất một chiều của hàm logarit r i rạc đã nói trên và sau đó phương pháp này đã được hiện thực b i Hewlett Packard và tập đoàn Mitre. Xét một tập những ngư i sử dụng ui (1 ≤ i ≤ n) muốn truyền thông với nhau. Cho p là một số nguyên tố rất lớn (p lớn hơn n nhiều) và có căn nguyên thủy là a. Mỗi ngư i sử dụng ui sẽ sinh ra một cách độc lập một số tự nhiên xi ngẫu nhiên trong khoảng {1, 2, ..., p - 1} và giữ nó bí mật. Tuy nhiên, anh ta sẽ công bố khóa công khai của anh ta là y i = a xi (mod p) Khi ui và uj truyền thông với nhau thì chúng sẽ sử dụng khóa giữa chúng như sau k ij = a xi x j (mod p ) Để tính được kij, uj sẽ dựa vào y i = a (mod p) đã công bố công khai của ui và khóa xj bí mật của nó, rồi tính kij bằng cách sau xi k ij = y i j (mod p ) x Và đối ui để tính được kij cũng sẽ làm tương tự như trên. Bằng cách này, dễ nhận thấy rằng, một ngư i khác ui và uj muốn biết được kij là rất khó. Đến đây chúng ta kết luận bài này bằng một phát biểu dựa trên ý kiến của Shannon. Bất kỳ một hệ mật mã nào cũng có thể bị bẽ gãy vấn đề là chúng ta sẽ xây dựng hệ mật mã sao cho việc bẻ gãy là tốn nhiều th i gian và chi phí. Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 127 Lý thuyết Thông tin BÀI 15 CHU N M T MÃ HÓA D LI U - DES 15.1 Giới thiệu 15.2 Giải thuật mã hóa và giải mã 15.3 Độ an toàn của DES 15.1 Gi i thi u Sau chiến tranh Thế giới lần II, chính phủ, quân đội Mỹ và một số công ty Mỹ nhận thấy tầm quan trong của việc bảo mật dữ liệu đã tiến hành xây dựng các công cụ mã hóa. Đối với dân chúng, mặc dù vấn đề này cũng thu hút được sự quan tâm nhưng việc bảo mật thông tin truyền nhận vẫn còn theo phương pháp truyền thống là dùng cục xi để niêm phong. Cuộc cách mạng máy tính và thông tin điện tử đã tác động lên xã hội và làm thay đổi cách thức truyền thông thông thư ng của dân chúng. Chính phủ Mỹ đã sớm nhận ra rằng cùng với sự bùng nổ của cuộc cách mạng máy tính, sẽ là sự bùng nổ và tăng trư ng của các dịch vụ truyền thông, tài chính điện tử … Lúc đó nhu cầu bảo mật thông tin của các cơ quan và dân chúng sẽ ngày càng tăng và sẽ m ra một chân tr i rộng lớn của việc ứng dụng mã hóa bảo mật vào trong việc bảo mật thông tin. IBM là một trong những công ty đầu tiên nghiên cứu về vấn đề này và đã lập một nhóm nghiên cứu vào cuối thập niên 1960. Nhóm này đứng đầu là Horst Feistel đã lập ra hệ mã hóa khóa bí mật có tên gọi là Lucifer. Và nó đã có khách hàng đầu tiên là tập đoàn bảo hiểm Lloyd’s of London vào năm 1971. Vào những năm 1973 - 4 Cục Tiêu chuẩn Quốc gia Hoa Kỳ (National Bureau of Standards – NBS) đã khuyến khích những ai quan tâm g i những đề nghị đối với chuẩn mật mã hóa dữ liệu. Các yêu cầu cơ bản đối với giải thuật mật mã hóa là 1. Có tính bảo mật cao. 2. Công khai, dễ hiểu. Khả năng bảo mật được chốt vào khóa chứ không vào bản thân giải thuật (cái mà không thể giữ bí mật được) 3. Nó có thể triển khai trên các thiết bị điện tử kích thước nhỏ. Năm 1977 dựa vào Lucifer, NBS công bố chuẩn mật mã hóa dữ liệu Hoa Kỳ (Data Encryption Standard - DES). DES đã được sử dụng rộng rãi không chỉ Mỹ mà còn nhiều nước trên thế giới trong gần 3 thập kỷ qua. Nó dùng khóa có độ dài 56 bit để mã hóa các khối dữ liệu 64 bit. Cả bên mã hóa lẫn bên giải mã đều dùng chung một khóa. Và DES thuộc vào hệ mã khóa bí mật. 15.2 Gi i thu t mã hóa và gi i mã Trên quan điểm toán học, DES có thể được xem như một chuỗi mật mã đơn giản trên bảng chữ cái 264 kí tự. Tức là thông báo được “bẻ” ra thành từng khối 64 bit và mỗi khối như vậy được xem là một kí tự. Thông báo 64 bit DES Chuỗi mật mã 64 bit Khóa 56 bit Hình 15.1 Mô hình DES Khóa k được chọn là một trong 256 chuỗi 56 bit và từ nó trích ra 16 khóa con k1, k2, …, k16. Mỗi khóa con ki là một chuỗi con 48 bit của khóa k 56 bit. Mỗi khóa con này được sử dụng trong một khối mã hóa (thực hiện một vòng mã hóa) để biến đổi 64 bit đầu vào của Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 128 Lý thuyết Thông tin khối thành 64 bit đầu ra. Kí hiệu mỗi khối mã hóa này là EB. Những khối mã hóa này sẽ được dùng nối kế tiếp nhau như hình minh họa bên dưới. đây, DES có sử dụng phép hoán vị kh i đầu (IP – initial permutation) và hoán vị ngược của nó (IP - 1) lượt cuối tuy nhiên chúng thật sự không mang ý nghĩa mật mã hóa. k1 Thông báo 64 bit 32 IP 32 EB 1 Hình 15.2 k2 32 32 EB 2 k16 32 32 32 32 EB 16 IP - 1 Chuỗi mật mã 64 bit Hình ảnh 16 vòng mã hóa của DES Cách tạo các khóa con Input: - Khóa k ban đầu 56 bit. Khóa này được giữ bí mật. - Phép hoán vị P56 để hoán vị chuỗi 56 bit. - Dãy 16 số si nguyên dương, mỗi số xác định số bước dịch vòng sang trái cho mỗi khóa con tương ứng. Dãy 16 số này là (1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1) - Phép chọn S48 mô tả 48 vị trí được chọn từ một chuỗi có 56 bit. Output: - Các khóa con ki 48 bit. B c 1. Dùng phép hoán vị P56 để hoán vị k được kết quả là h. Viết h thành hLhR trong đó hL là 28 bit đầu của h còn hR là 28 bit sau của h. B c 2. Dịch vòng hL và hR sang trái si bit (ứng với việc tạo ra khóa ki). Ghép hai kết quả con này lại được kết quả là g. B c 3. Áp dụng phép chọn S48 để chọn ra 48 bit 48 vị trí đã cho được kết quả là khóa con ki. Quá trình mã hóa c a các khối EBi Input: - Chuỗi w 64 bit xuất ra từ khối trước đó. - Khóa ki tương ứng với khối EBi. - 8 hộp thay thế Sj - box, (j = 1, 2, …, 8) cho biết công khai. Mỗi hộp là một ma trận 4 × 16 (4 hàng và 16 cột). Mỗi hàng là mỗi vectơ 16 thành phần, mỗi thành phận nhận giá trị nguyên từ 0 đến 15 và không có hai thành phần nào giống nhau. Nói cách khác mỗi hàng là một hoán vị nào đó của dãy số nguyên từ 0 đến 15: (0, 1, 2, …, 15). - Phép hoán vị P32 để hoán vị một chuỗi 32 bit. Output: - Chuỗi 64 bit kết quả (sẽ là đầu vào của khối kế tiếp). B c 1. Viết w = a0a1…a63 = XLXR trong đó XL là 32 bit đầu của w, XR là 32 bit sau của w, tức XL = a0a1…a31, XR = a32a33…a63. Trong bước này chỉ có 32 bit sau XR được biến đổi còn 32 bit đầu XL vẫn giữ nguyên. Quá trình biến đổi XR như sau. Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 129 Lý thuyết Thông tin B1. 1. Từ chuỗi XR 32 bit chúng ta sinh ra chuỗi E 48 bit (để sau này đem cộng với khóa 48 bit) bằng cách nhặt ra 8 lần mỗi lần 6 bit cụ thể như sau. Lần đầu dịch vòng XR sang phải 1 bit được kết quả a63a32a33…a61a62 rồi nhặt ra 6 bit đầu là a63a32a33a34a35a36. Lần hai dịch vòng kết quả vừa rồi sang trái 4 bit được kết quả a35a36…a63a32a33a34 rồi nhặt ra 6 bit đầu là a35a36a37a38a39a40. Các lần kế tiếp lại dịch kết quả của lần trước sang trái 4 bit rồi nhặt ra 6 bit đầu. Xếp 8 lần nhặt 6 bit này thành 8 hàng ta được kết quả sau. a63 a32 a33 a34 a35 a36 a35 a39 a 43 a36 a 40 a 44 a37 a 41 a 45 a38 a 42 a 46 a39 a 43 a 47 a 40 a 44 a 48 a 47 a51 a55 a59 a 48 a52 a56 a60 a 49 a53 a57 a61 a50 a54 a58 a62 a51 a55 a59 a63 a52 a56 a60 a32 48 bit kết quả này ta gọi là E. B1. 2. Viết khóa con ki theo thứ tự từ trái qua, thành 8 hàng mỗi hàng 6 bit như trên. Cộng 8 hàng trên với 8 hàng của khóa theo phép XOR bit. Kết quả là một “ma trận” M có kích thước 8 × 6, ma trận này dùng để định vị “tọa độ” các thành phần trong các S - box. M 8× 6 = b11 b21 b31 b12 b22 b32 b13 b23 b33 b14 b24 b34 b15 b25 b35 b16 b26 b36 b41 b51 b42 b52 b43 b53 b44 b54 b45 b55 b46 b56 b61 b71 b81 b62 b72 b82 b63 b73 b83 b64 b74 b84 b65 b75 b85 b66 b76 b86 B1. 3. Mỗi hàng bj1 bj2 bj3 bj4 bj5 bj6 bj7 bj8 sẽ được dùng với hộp Sj - box (là ma trận 4 × 16) tương ứng theo cách sau (ma trận 4 × 16). Hai bit bj1bj8 tạo nên giá trị chỉ ra chỉ số hàng của Sj - box (đánh số bắt đầu bằng 0). Bốn bit bj2 bj3 bj4 bj5 bj6 bj7 tạo nên giá trị chỉ ra chỉ số cột của Sj - box (đánh số bắt đầu bằng 0). Phần tử tương ứng với hàng và cột này sẽ được chọn. Đây là một giá trị nguyên trong khoảng từ 0 đến 15, (được biểu diễn thành một chuỗi 4 bit). 8 hàng của M sẽ cho phép chọn ra được 8 phần tử trong 8 Sj - box tương ứng, mỗi phần tử sẽ là một chuỗi 4 bit. Viết 8 chuỗi này theo thứ tự ta được chuỗi kết quả N 32 bit. B1. 4. Dùng phép hoán vị P32 để hoán vị chuỗi N bước trên ta được chuỗi kết quả R của Bước 1. Chúng ta có thể xem tất cả các bước biến đổi trong Bước 1 này tạo thành một phép biến đổi Ti (tương ứng với khối EBi) biến đổi nữa chuỗi bên phải XR (32 bit) của chuỗi thông báo w (64 bit) thành chuỗi kết quả XR* = Ti(XR) (32 bit) Đến cuối bước này chuỗi văn bản w = XLXR được biến đổi thành chuỗi sau Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 130 w = XLXR → XLTi(XR) = XLXR* B Lý thuyết Thông tin c 2. Cộng XL với XR* theo phép XOR và thay XL bằng kết quả này. Nếu kí hiệu phép XOR là ⊕ thì chúng ta viết bước này như sau: XL ⊕ XR* Đến cuối bước này chuỗi văn bản w = XLXR được biến đổi thành chuỗi sau w = XLXR → XLTi(XR) = XLXR* → (XL⊕XR*)XR Ta có thể xem từ lúc bắt đầu quá trình mã hóa của khối EBi cho đến cuối bước này chúng ta đã thực hiện một phép biến đổi Π được biểu diễn như sau. Π(XL, XR) = (XL⊕Ti(XR), XR) Một số tài liệu gọi Π là ánh xạ “nâng” theo Ti (có chứa khóa ki trong quá trình tính toán của Ti). Chú ý chúng ta có Π2(XL, XR) = Π(XL⊕Ti(XR), XR) = (XL⊕Ti(XR)⊕Ti(XR), XR) = (XL, XR) Vậy Π có hàm ngược của nó cũng chính là nó, Π. Đây là cơ s cho việc giải mã sau này. B c 3. Dùng phép đảo vế dữ liệu để chuyển 32 bit đầu thành 32 bit sau và ngược lại. Nếu chúng ta kí hiêu phép đảo về là ℜ thì chúng ta có thể định nghĩa ℜ như sau: ℜ(XL, XR) = XR, XL trong đó XL và XR lần lượt là nửa đầu và nửa sau của chuỗi X. Đến cuối bước này chuỗi văn bản w = XLXR được biến đổi thành chuỗi sau w = XLXR → Π(XL, XR) = (XL⊕Ti(XR), XR) = (XL⊕XR*, XR) → (XL⊕XR*, XR) = XR(XL⊕XR*) Chúng ta cũng thấy rằng hàm ℜ có hàm ngược của nó cũng chính là nó, ℜ. Đến đây ta có thể xem quá trình mã hóa của một khối EBi như là một hàm f được biểu diễn như sau f(XL, XR) = ℜ[Π(XL, XR)] Để đơn giản chúng ta có thể viết f như sau trong đó hàm nào đứng trước có nghĩa là được thực hiện trước. f=Ποℜ Và rõ ràng hàm f có hàm ngược của nó là f -1 = ℜ ο Π Cuối cùng chúng ta có thể biểu diễn giải thuật mã hóa của DES như sau: IP o ∏ T1 oℜ o ∏ T2 oℜ o K o ∏ T15 oℜ o ∏ T16 o IP −1 Chú ý vòng thứ 16 không sử dụng phép đảo vế dữ liệu như các vòng trước. Vì vậy nếu chúng ta xem lại Hình 15.2 sẽ thấy khối EB cuối do không thực hiện phép đảo vế dữ liệu như các khối trước nên đầu ra của nó được đảo chéo. Từ đây chúng ta cũng xác định được qui trình giải mã IP o ∏ T16 oℜ o ∏ T15 oℜ o K o ∏ T2 oℜ o ∏ T1 o IP −1 15.3 Đ an toàn của DES Ban đầu, DES có vẻ như vững chắc, tuy nhiên sau một th i gian dài sử dụng DES đã bộc lộ ra những yếu điểm. Yếu điểm chỗ chiều dài của khóa chỉ 56 bit là không đủ lớn. Số lượng khóa có thể sinh ra là không đủ lớn so với số lượng chip và tốc độ xử lý của các siêu máy tính ngày nay, nhất là các dàn máy song song chuyên dụng phục vụ cho việc giải mã. Năm 1997 một nhóm nghiên cứu đã sử dụng một siêu máy tính để dò các loại khóa có thể Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 131 Lý thuyết Thông tin sinh ra của DES và đã tìm ra được khóa trong vòng chưa đầy 2 gi đồng hồ. Chính vì vậy một số hệ mã mới đã được ra đ i chẳng hạn như Giải thuật Mã hóa Dữ liệu Quốc tê (International Data Encryption Algorithm - IDEA) dùng khóa với chiều dài 128 bit hoặc Chuẩn Mã hóa Nâng cao (Advanced Encryption Standard - AES) với khóa có chiều dài còn lớn hơn. Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 132 Lý thuyết Thông tin BÀI 16 H MÃ KHÓA CÔNG KHAI RSA 16.1 Giải thuật mã hóa và giải mã RSA 16.2 Độ an toàn của RSA Hệ mã khóa công khai RSA do ba nhà nghiên cứu Rivest, Shamir và Adleman đề xuát vào năm 1978. Việc xây dựng nó đặt trên nên tảng các bài toán số học mà đặc biệt là các bài toán về các số nguyên tố lớn. 16.1 Gi i thu t mã hóa và gi i mã RSA Quá trình mã hóa Chúng ta sẽ mã hóa từng khối kí tự một. Mỗi khối kí tự có chiều dài m (kí tự). Số m này sẽ được lựa chọn sao cho phù hợp. Nếu văn bản ban đầu có chiều dài không là bội số của m thì chúng ta sẽ bổ sung thêm nhiều lần một kí tự X nào đó để chiều dài này là bội số của m. Input: - Số tự nhiên m là chiều dài của khối kí tự cần mã hóa. - Khối kí tự w cần mã hóa có chiều dài m (kí tự). - Số nguyên n (n = pq với p và q là hai số nguyên tố đủ lớn, thư ng lớn hơn số M được tính bên dưới). - Số tự nhiên ke đủ lớn sao cho, gcd(ke, φ(n)) = 1, đồng th i tồn tại số tự nhiên kd thỏa ke × kd ≡ 1 (mod φ(n)). Thư ng ke được khuyên nên chọn là một số nguyên tố. đây cặp số (n, ke) chính là khóa công khai còn (n, kd) chính là khóa bí mật. Bí mật được chốt số kd. Output: - Chuỗi mật mã c (là chuỗi các kí số). B c 1. Biểu diễn khối kí tự w thành một số nguyên trong khoảng {1, 2, ..., n}. Thông thư ng cách biểu diễn như sau. Mỗi kí tự của w trong bảng chữ cái (giả sử là bảng chữ cái latinh gồm 26 kí tự) được biểu diễn bằng một số có hai chữ số. Chẳng hạn, A là 01, B là 02, …, Z là 26. Kết quả chuỗi w được biểu diễn thành một chuỗi các kí số và có chiều dài là 2m (kí số). Gọi chuỗi số này là N. Rõ ràng N có giá trị không vượt quá giá trị cực đại sau đây M = 2626…26 (m lần số 26) M = 26(100m - 1)/99 N<M Các số nguyên tố p, q dùng để tính n thư ng lớn hơn số M này. p, q > M > N Như vậy N sẽ nguyên tố cùng nhau với p, q và dĩ nhiên là nguyên tố cùng nhau với n. B c 2. Số tự nhiên ke được chọn đủ lớn để N k e > n với đa số các số N trên. Chuỗi mật mã c chính là chuỗi số có được thông qua phép toán sau. c ≡ N k e (mod n) Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 133 Lý thuyết Thông tin Dĩ nhiên số c nhỏ hơn n và với việc chọn ke thỏa N k e > n thì c không thể trùng với N k e được. Quá trình giải mã Input: - Chuỗi mật mã c (là chuỗi các kí số). - Số nguyên n đã cho giải thuật mã hóa. - Khóa bí mật kd. Output: - Khối kí tự w ban đầu cần mã hóa. B c 1. Theo Hệ quả 14.4 chúng ta có (N ) ke kd tức là ≡ N (mod n) c k d ≡ N (mod n) Vậy chuỗi N được tính bằng cách (với N < n) N ≡ c k d (mod n) B c 2. Chiều dài của N sẽ là 2m hoặc 2m – 1 kí số. Nếu N dài 2m – 1 kí số thì thêm số 0 vào vị trí đầu bên trái của N (để đủ 2m kí số). Tách từng hai kí số một từ trái sang và biến đổi thành kí tự chữ trong bảng chữ cái đã cho ta được khối kí tự cần mã hóa ban đầu w. Nhận xét Mấu chốt của hệ mã khóa công khai RSA nằm chỗ cho dù biết chuỗi mật mã c và khóa công khai ke, nếu không biết được khóa bí mật kd thì việc tìm ra N là rất khó. Ta có ke × kd ≡ 1 (mod φ(n)). Vậy để tìm khóa kd chúng ta phải biết φ(n). Việc tìm φ(n) dựa vào n đã biết không dễ hơn so với việc phân tích n ra thành các thừa số nguyên tố, b i vì khi đã biết φ(n) thì chúng ta có thể giải ra p và q bằng một hệ hai phương trình hai biến. n = pq φ(n) = (p – 1) × (q – 1). Khó đây nằm chỗ chúng ta phải làm việc với những số nguyên rất rất lớn. Chẳng hạn bảng sau đây cho chúng ta thấy độ phức tạp của các thuật toán phân tích một số nguyên n ra thừa số nguyên tố bằng các thuật toán hiệu quả nhất hiện nay trên một máy tính có tốc độ xử lý 1 tỉ phép tính trong 1 giây. (Tham khảo từ trang 5 và 6 sách số [5]) Số chữ số thập phân 50 75 100 200 300 500 Số phép tính bit 1,4 × 1010 9,0 × 1012 2,3 × 1015 1,2 × 1023 1,5 × 1029 1,3 × 1039 Th i gian 14 giây 2,5 gi 26 ngày 15 gi 3,8 × 106 năm 4,9 × 1012 năm 4,2 × 1022 năm Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 134 Lý thuyết Thông tin 16.2 Đ an toàn của RSA Nếu p và q là các số nguyên tố khoảng 100 chữ số thập phân thì n có khoảng 200 chữ số. Việc phân tích n thành p và q như bảng trên cho thấy tốn một khoảng th i gian hàng triệu năm với những máy tính rất mạnh. Sau khi tìm ra hệ mã này, Rivest, Shamir và Adleman đã công bố trên một bài báo khoa học đăng MIT. Sau đó trên cột báo Martin Gardner’s của t báo Scientific American, họ có đưa ra l i thách thức bạn đọc bẻ khóa một mẩu tin nhỏ đã được mã hóa với n = 114381625757888867669235779976146612010218296721242362562561842 935706935245733897830597123563958705058989075147599290026879543541 e = 9007 Mẩu tin “first solver wins one hundred dollars” xuất hiện trong dạng mã hóa với A = 01, B = 02, …, Z = 26 và chỉ được giải mã vào ngày 26/4/1994 bằng một cố gắng tổng lực mang tính quốc tế (qua internet) với việc sử dụng 1600 cái bao gồm các trạm làm việc (workstations), các máy cỡ lớn (mainframes) và các siêu máy tính (supercomputers) tấn công trong vòng 8 tháng liên tục để phân tích số nêu trên ra thừa số nguyên tố. Thực tế này cho thấy rằng thuật toán RSA là rất an toàn, vì không mấy khi có điều kiện để huy động một lực lượng tính toàn hùng hậu như thế vào công việc giải mã một mẫu tin. Nhận xét Giải thuật mã hóa RSA mặc dù rất an toàn nhưng tốc độ mã hóa và giải mã chậm, chậm hơn giải thuật DES nhiều lần (hàng ngàn lần). Vì vậy ngư i ta thư ng kết hợp hai phương pháp mã hóa DES và RSA theo cách sau: 1. Dùng DES để mã hóa khối văn bản. 2. Dùng RSA để mã hóa khóa mà DES đã dùng để mã hóa khối văn bản. Sự kết hợp này tích hợp được cả ưu điểm nhanh chóng của DES và ưu điểm an toàn của RSA. Các giải thuật mã hóa DES và RSA còn được ứng dụng vào rất nhiều vấn đề khác của việc mật mã hóa chẳng hạn như việc xác nhận chủ thể (xác nhận ngư i g i văn bản để tránh sự giả mạo) hay còn gọi là chữ ký điện tử. Tuy nhiên trong khuôn khổ của môn học này không đủ th i lượng cho phép chúng ta trình bày vấn đề này. Để tìm hiểu thêm bạn đọc có thể xem thêm các tài liệu tham khảo. Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 135 Lý thuyết Thông tin TÀI LI U THAM KH O [1] [2] [3] [4] [5] [6] [7] Masud Mansuripur, Introduction to Information Theory, Prentice–Hall, Inc, 1987 Robert B.Ash, Information Theory, Dover Publications, Inc, New York, 1990 C. E. Shannon, A Mathematical Theory of Communication, The Bell System Technical Journal, Vol. 27, pp. 379–423, 623–656, July, October, 1948. Dominic Welsh, Codes and Cryptography, Arendon Press, Oxford, 1987 Phạm Huy Điển, Hà Huy Khoái, Mã hóa thông tin. Cơ sở toán học & ứng dụng, NXB ĐHQG Hà Nội, 2004 Đặng Văn Chuyết, Nguyễn Tuấn Anh, Cơ sở Lý thuy t truy n tin (t p m t và hai), NXB Giáo dục, 1998 Nguyễn Thúy Vân, Lý thuy t mã, NXB Khoa học Kỹ thuật, 2000 Ngư i soạn Hồ Văn Quân - Khoa CNTT - ĐH Bách Khoa Tp.HCM 136