Lý thuyết Thông tin

- 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.
- Vậy chúng ta có một song ánh giữa các từ mã với các đa thức mã.
- 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.
- 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.
- Mặc khác trên trư ng GF(2) chúng ta có xn + j = xj * (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).
- [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.
- 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.
- Chúng ta suy ra f(x) cũng là một đa thức mã.
- Ch ng minh Trước hết chúng ta chứng minh nếu v(x.
- Thực vậy, chúng ta có ⎛ p ⎞ p ⎝ i =0 ⎠ i =0 trong đó p là bậc của q(x) và p + r ≤ n – 1.
- 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.
- 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.
- Vì vậy do định nghĩa của g(x) chúng ta suy ra r(x.
- 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.
- 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.
- Trước hết chúng ta thấy do bậc của v(x.
- Từ định lý này chúng ta có thể biểu diễn đa thức sinh g(x) như sau g(x.
- 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.
- n – k nên chúng ta suy ra q(x.
- Thế vào trên chúng ta suy ra điều phải chứng minh.
- Đầu tiên chúng ta biểu diễn v(x) v(x.
- 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.
- 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.
- 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 x 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à .
- 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 .
- 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 xn–k * u(x.
- Chúng ta có u(x.
- Nhân u(x) với xn–k = x3 rồi chia cho g(x) chúng ta được.
- 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.
- 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.
- 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.
- (0 … 0hkhk–1 … h0)T = 0 Vì vậy nếu chúng ta đặt 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 h 0 L 0⎥ k n4 k4 ⎢ k k −1 ⎥ hk −2 L h0 0 ⎢ 0 hk hk −1 L h1 h0 0 L 0⎥ H ( n − k )×n.
- 0 thì chúng ta suy ra v × HT = 0.
- 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.
- Thật vậy nếu w là từ mã w × HT = 0 thì chúng ta có hay b0 + b1a + b2a2.
- Nhân a vào đẳng thức trên chúng ta suy ra b0a + b1a2 + b2a3.
- 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.
- 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).
- Thật vậy nếu w là từ mã b b w × HT = 0 thì chúng ta có H × wT = 0 hay viết ngược lại Nhân ma trận B sau với H ⎡a 0 0 ⎤ ⎢0 a 3 0.
- chúng ta được ⎡ a a n −1 1.
- n −1) L a Chúng ta có (B×H)×wT = B×(H×wT.
- Từ đây chúng ta suy ra hệ sau, gọi là hệ (1.
- Từ đây chúng ta nhận được hệ (2) sau y1 + y2.
- yr2 Vì vậy chúng ta có hệ (3) sau y1 + y2.
- 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.
- Mà theo Bổ đề 13.2 chúng ta có det A.
- Từ Bổ đề 11.5 chúng ta suy ra g(x) chia hết cho f1(x), f3(x), f5(x.
- Vì vậy theo định nghĩa của đa thức sinh chúng ta suy ra g(x.
- Kết hợp với trên chúng ta suy ra det A = p(y1, y2.
- 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à 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).
- Chúng ta có ma trận kiểm tra của bộ mã như sau.
- a2 a3 a4 a5 a6 a7 a8 a9 a 10 a 11 a 12 a 12 ⎣1 a a 42 ⎦ 3 a6 a9 a 12 a 15 a 18 a 21 a 24 a 27 a 30 a 33 a 36 a 39 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 .
- Theo Ví dụ 11.7 chúng ta có đa thức tối thiểu của a3 là f3(x.
- 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.
- Từ đây chúng ta có khái niệm khoá.
- 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.
- 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.
- 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ã.
- 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 Để 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 c = ONHJ |SA I |ODOG |COTAR .
- Giả sử chúng ta có ma trận khoá như sau B Y D G Z W S F U P L A R K X C O I V E Q N M H T Sự thay thế sẽ được thực hiện như sau.
- Đầ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: S E N D S U P P L I E S k: V E N U S S E N D S U P Chuỗi mật mã N I A X K M T C O A Y 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.
- 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.
- đây chúng ta xem một ví dụ đơn giản về cách bẻ gãy.
- 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.
- 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.
- Chúng ta có thể kết hợp đồng th i cả hai cách trên.
- 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.
- Đế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.
- Đô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).
- 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.
- Tuy nhiên như chúng ta sẽ thấy rất khó để đạt được điều này.
- 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.
- 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.
- 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.
- (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) Chú ý chúng ta có Vậy Π có hàm ngược của nó cũng chính là nó, Π.
- 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⊕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ó, ℜ.
- ℜ[Π(XL, XR)] như sau Để đơ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 f=Ποℜ thực hiện trước.
- 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.
- Theo Hệ quả 14.4 chúng ta có ke kd ≡ N (mod n) tức là 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.
- 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