Luận văn Ứng dụng mã Xyclic cục bộ xây dựng hệ mật

è ø = =y yP = (1, 0, 0, 0, 1, 1, 1) Tiếp theo người nhận giải mã y1 để nhận được x1 = (1, 0, 0, 0, 1, 1, 0) (cần để ý là e1 ¹ e do phép nhân với P-1). Sau đó lập x0 = (1, 0, 0, 0) (bốn thành phần đầu tiên của x1). Cuối cùng người nhận tính: 1 0 1 1 0 1 1 1 0 0 (1,0,0,0) (1,1,0,1) 0 1 1 1 1 0 0 1 - æ ö ç ÷ ç ÷ ç ÷ ç ÷ è ø = = =x S x Đây chính là bản rõ cần nhận được. 1.3. Kết luận Trong chương này đã đề cập tới các nội dung về các hệ mật mã cổ điển và các hệ mật mã khoá công khai, trên cơ sở phân tích các ưu nhược điểm của các hệ mật, chúng ta nhận thấy rằng trong các hệ mật khoá công khai chỉ có hệ mật McEliece là sử dụng lý thuyết mã đại số cụ thể là mã Goppa để xây dựng hệ mật. Với sự phát triển của lý thuyết xây dựng mã xyclic cục bộ, chúng ta hoàn toàn có thể tự xây dựng một hệ mật khoá công khai dựa trên lược đồ McEliece sử dụng mã xyclic cục bộ. 25 Chương 2 - LÝ THUYẾT VỀ Mà XYCLIC CỤC BỘ VÀ PHÂN HOẠCH VÀNH ĐA THỨC 2.1. Khái niệm mã xyclic và vành đa thức 2.1.1. Mã tuyến tính a) Mã tuyến tính Mã tuyến tính độ dài n là mã mà từ mã của nó có các dấu mã là các dạng tuyến tính. Mã tuyến tính (n,k) là mã tuyến tính độ dài n trong đó ta có thể chỉ ra được vị trí của k dấu thông tin trong từ mã. Mã tuyến tính ngẫu nhiên là mã tuyến tính có các dấu mã được chọn ngẫu nhiên từ các dạng tuyến tính có thể có. b) Ma trận sinh và ma trận kiểm tra Để đơn giản cho việc mô tả mã tuyến tính người ta thường sử dụng ma trận sinh G[k x n]. Ma trận này chứa k véc-tơ hàng độc lập tuyến tính tạo nên không gian mã V(n,k). Trong đại số tuyến tính ta biết rằng với mỗi G sẽ tồn tại ma trận H[r x n] thỏa mãn: G . HT = 0, r = n - k Ma trận H được gọi là ma trận kiểm tra của mã tuyến tính (n, k). Ta thấy rằng H chứa r véc-tơ hàng trực giao với các véc-tơ hàng của G. Hiển nhiên là nếu a là một véc-tơ mã a Î V(n,r) thì a.HT = 0. Ở đây, H cũng là một ma trận sinh của một mã tuyến tính V(n,r) và G lại chính là ma trận kiểm tra của mã này. Ta có thể viết ra r phương trình: 1 0, 1,2,.., n j ij j a h i r = = =å Các phương trình này còn được gọi là các tổng kiểm tra của mã tuyến tính. 26 2.1.2. Vành đa thức Nhóm hữu hạn , với G = { ai, "i } thì G gọi là nhóm xyclic sinh bởi a, và a được gọi là phần tử sinh của nhóm. Vành đa thức là tập hợp các đa thức thực hiện được hai phép toán cộng (+) và nhân (.) đa thức theo modulo xn + 1, trong đó tạo thành một nhóm còn tạo thành nửa nhóm. Ký hiệu vành đa thức là Rn. Nếu xét trên trường nhị phân GF(2) thì vành đa thức được kí hiệu dưới dạng Z2[x]/xn+1. Trên vành đa thức Z2[x]/xn+1 ta định nghĩa phép nhân modulo như sau: a(x), b(x) là các đa thức của vành, a(x).b(x) = c(x) (mod xn+1) cũng là một đa thức của vành. Ví dụ, trên vành Z2[x]/x5+1: a(x) = 1 + x4, b(x) = x, phép nhân hai đa thức này là c(x) = a(x).b(x)= (1+x4)(x)= x5+x = x+1 (mod x5+1). Ideal I của vành đa thức gồm tập các đa thức a(x) là bội của một đa thức g(x) thỏa mãn: - g(x) là ước của xn + 1. - deg g(x) = min deg a(x) với mọi a(x) Î I, a(x) ¹ 0. Ký hiệu Ideal I trong vành đa thức là I = . Xét trong vành đa thức, đa thức a(x) = 1 0 n i i i a x - = å 0 1 1( , ,..., )na a a a -Û = . Nhân a(x) với nhân tử x ta có: b(x) = a(x). x = x.( 1 0 n i i i a x - = å ) 1 0 2( , ,..., )n nb a a a- -Û = . Biểu diễn của véc tơ b là dịch vòng sang phải một cấp so với của véc-tơ a. * Phần tử đối xứng a(x) được gọi là phần tử đối xứng của ( )a x nếu: 1 0 0 ( ) ( ) ( ) - = + = = å n i i a x a x c x x với: ( ) , ( ) Î Î = =å åi ji j i I j J a x a x a x a x , 27 I È J = S = {0,1,2,,n-1} , I Ç J = Æ Định lý 2.1 (Với n lẻ): Trong vành luôn luôn tồn tại đa thức có bậc lớn nhất bằng m. Ký hiệu: m = max deg fi(x). Cấp lớn nhất của một đa thức trong vành được xác định: max ord a(x) = 2m – 1, với "a(x) Î Rn. Ví dụ: n = 9: x9 + 1 = (1+ x)(1 + x + x2)(1 + x3 + x6) ® m = 6 ® max ord a(x) = 26 – 1 = 63 Xét đa thức a(x) Î Rn ( Z2[x]/(xn+1) ). * Nhóm nhân xyclic đơn vị Nhóm nhân xyclic đơn vị là nhóm bao gồm mọi đơn thức có bậc <n (nhóm có n phần tử). Ký hiệu là : I = { x, x2 , x3 , , xn-1 , 1 } Nhóm nhân xyclic đơn vị I bao gồm n phần tử với phần tử sinh là x. Nhóm nhân này nhóm nhân cấp n. * Nhóm nhân xyclic với phần tử sinh a(x) Nhóm nhân xyclic với phần tử sinh a(x) bao gồm các phần tử là luỹ thừa của phần tử sinh và có thể viết: A = { a(x), (a(x))2 , (a(x))3 , } * Cấp số nhân xyclic trên vành đa thức Xét vành đa thức Z2[x]/ xn+1 với n lẻ, giả sử a(x) là số hạng đầu tiên của cấp số nhân xyclic và q(x) là công bội của cấp số nhân. Cấp số nhân xyclic trên vành đa thức là một tập con có dạng: A(a,q) = { a(x), a(x).q(x), a(x).q2(x), , a(x).qm-1(x)} Trong đó, m là số số hạng của cấp số nhân này, a(x).qm(x) º a(x) mod (xn+1). 28 2.1.3. Mã xyclic a) Định nghĩa Định nghĩa 2.2 Mã xyclic (n, k) là ideal I = của vành đa thức Z2[x]/xn+1. Mã xyclic là một bộ mã tuyến tính có tính chất sau: Nếu a(x) là một từ mã thì dịch vòng của a(x) cũng là một từ mã thuộc bộ mã này. Ví dụ: Xét các mã xyclic trên vành Z2[x]/x7+1, ta có 7 ideal tương ứng với 7 bộ mã xyclic: Ta có: x7+1 = (1+x)(1+x+x3)(1+x2+x3) Bảng 2.1: Các mã xyclic trên vành Z2[x]/x7+1 Đa thức sinh g(x) Mã (n,k) Khoảng cách Hamming d0 1 (7,7) 1 1 + x (7,6) 2 1 + x + x3 (7,4) 3 1 + x2 + x3 (7,4) 3 1 + x + x2 + x4 (7,3) 4 1 + x2 + x3 + x4 (7,3) 4 1 + x + x2 + x3 + x4 + x5 + x6 (7,1) 7 b) Ma trận sinh của mã xyclic Vì mã xyclic (n, k) là một mã tuyến tính nên ta có thể mô tả nó thông qua ma trận sinh G chứa k véc-tơ hàng độc lập tuyến tính. Ta có thể thiết lập G như sau: 29 1 ( ) . ( ) ... . ( )k g x x g x G x g x- æ ö ç ÷ ç ÷= ç ÷ ç ÷ è ø Ví dụ: Mã xyclic (7,4) có đa thức sinh g(x) = 1 + x + x3, ma trận sinh của mã này có thể mô tả như sau: 3 2 4 2 3 5 3 4 6 1 1 0 1 0 0 01 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 x x x x x G x x x x x x æ ö+ + æ ö ç ÷ ç ÷+ +ç ÷ ç ÷= = ç ÷ ç ÷+ + ç ÷ ç ÷ç ÷+ + è øè ø c) Ma trận kiểm tra của mã xyclic Vì g(x) là ước của xn + 1 nên ta có thể viết g(x).h(x) = xn + 1. Đa thức h(x) được gọi là đa thức kiểm tra. Vì g(x).h(x) º 0 mod xn + 1 nên g(x) và h(x) được gọi là các đa thức trực giao. Ta có h(x) = 0 k j j j h x = å , với h0 = hk = 1, hj Î {0,1}, với j = 2,..,k-1. Ma trận kiểm tra của mã xyclic sinh bởi g(x) là: * * 1 * ( ) . ( ) ... . ( )r h x x h x H x h x- æ ö ç ÷ ç ÷= ç ÷ ç ÷ç ÷ è ø Trong đó, r = n – k, và h*(x) là đa thức đối ngẫu của h(x): h*(x) = xdeg h(x).h(x-1). Ví dụ: Ma trận mã kiểm tra cho mã xyclic (7,4) với đa thức sinh g(x) = 1+x+x3 là: Ta có: h(x) = (x7+1)/(1+x+x3) = (1+x)(1+x2+x3) = x4+x2+x+1 h*(x) = 1+x2+x3+x4 Ma trận kiểm tra: 30 2 3 4 3 4 5 2 4 5 6 1 1 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1 1 x x x H x x x x x x x x æ ö+ + + æ ö ç ÷ ç ÷= + + + =ç ÷ ç ÷ ç ÷ç ÷+ + + è øè ø 2.1.4. Mã hoá cho mã xyclic a) Mô tả từ mã Mã xyclic (n,k) được gọi là mã xyclic hệ thống nếu ta có thể chỉ rõ vị trí của các dấu thông tin và các dấu kiểm tra trong từ mã. Thông thường thì các dấu thông tin được sắp xếp ở k vị trí bậc cao, còn lại là dấu kiểm tra. fn-1 fn-2 ... fr fr-1 fr-2 ... f0 k dấu thông tin r dấu kiểm tra Ta có ( ) 1 0 . ( ) ( ) n i n k i i f x f x x a x r x - - = = = +å b) Thuật toán mã hoá hệ thống Thuật toán xây dựng từ mã xyclic như sau: Đầu vào: Tin rời rạc ai Î A. Đầu ra: Từ mã fi(x) tương ứng với ai. Bước 1: Mô tả ai trong tập tin cần mã hoá (gồm 2k tin) bằng một đa thức ai(x) với deg ai(x) không vượt quá k – 1. Bước 2: Nâng bậc của ai(x) bằng cách nhân nó với xn-k. Bước 3: Chia ai(x).xn-k cho đa thức sinh g(x) để tìm phần dư ri(x). Bước 4: Xây dựng từ mã xyclic: fi(x) = ai(x).xn-k + ri(x). c) Thiết bị mã hoá 31 Thiết bị mã hoá có cốt lõi là thiết bị chia cho g(x) để lấy dư, thực chất là otomat nhớ dạng của g(x). Giả sử g(x) = 1 0 r i i i g x - = å . Thiết bị mã hoá cho mã (n,k) với đa thức sinh g(x) như hình sau: Hình 2.1 : Thiết bị mã hoá cho mã xyclic (n,k) có đa thức sinh g(x) Thiết bị này hoạt động như sau: - k nhịp đầu (chia và tính phần dư): Mạch và V1 mở, V2 đóng, thiết bị hoạt động như một bộ chia để tính dư. Kết thúc nhịp thứ k, toàn bộ phần dư nằm trong r ô nhớ từ 1 đến r. Trong quá trình này, các dấu thông tin ai(x).xn-k được đưa qua mạch hoặc H. - r nhịp sau (đưa ra các dấu kiểm tra (phần dư) ra đầu ra). Mạch và V1 đóng, thiết bị hoạt động như một thanh ghi dịch nối tiếp. Mạch và V2 mở, các dấu kiểm tra được lần lượt đưa ra từ bậc cao tới bậc thấp. Kết thúc nhịp thứ n, toàn bộ từ mã được đưa ra đầu ra. 2.1.5. Giải mã ngưỡng a) Hai thủ tục giải mã Mọi phương pháp giải mã đều có thể tiến hành theo một trong 2 thủ tục giải mã sau: - Thủ tục 1: Dẫn ra bản tin từ dãy dấu nhận được. 1 2 r + + + g1 g2 gr-1 V1 1,2,..,k V2 k+1,..,n ai(x).xn-k Vào Ra H 1,..,n + 32 - Thủ tục 2: Dẫn ra véc-tơ sai từ dãy dấu nhận được. b) Giải mã theo syndrom Giả sử v Î V là mã xyclic (n,k) có đa thức sinh g(x). Ma trận sinh của V(n,k) có dạng: 1 ( ) . ( ) ... . ( )k g x x g x G x g x- æ ö ç ÷ ç ÷= ç ÷ ç ÷ è ø Gọi h(x) = (xn + 1) / g(x), ta có deg g(x) = r, deg h(x) = k. Gọi h*(x) là đa thức đối ngẫu của h(X), h*(x) = xdeg h(x). h(x-1). Khi đó, ma trận kiểm tra của mã V(n,k) có dạng: * * 1 * ( ) . ( ) ... . ( )r h x x h x H x h x- æ ö ç ÷ ç ÷= ç ÷ ç ÷ç ÷ è ø Ta có G.HT = 0. Với v Î V bất kì, ta có v.HT = 0. Xét mô hình truyền tin sau: u = v + e Kênh Giải mã x x’ y = x + e y e + e’ Kênh Giải mã x x’ y = x + e y e Kênh v e u = (u0, u1, ..., un-1 ) 33 Ta có S(u) = u.HT = (v+r).HT = e.HT = S(e). S(e) là một véc-tơ r chiều đặc trưng cho véc-tơ sai e có n chiều. Ta gọi S(u) là syndrom của véc-tơ nhận được u. Quá trình giải mã dựa trên việc phân tích trạng thái của S(u) được gọi là giải mã theo syndrom. Tập r tổng kiểm tra trong S(u) tạo nên hệ tổng kiểm tra. Mỗi tổng kiểm tra trong hệ sẽ trong hệ sẽ chứa một thông tin nhất định về dấu cần giải mã ui, thông tin đó có thể nhiều, ít hoặc không có gì. Ngoài ra mỗi tổng kiểm tra này còn chứa thông tin về các dấu mã uj khác. Để giải mã cho ui hiển nhiên rằng ta cần xây dựng một hệ tổng kiểm tra chứa nhiều thông tin nhất về ui. Trên cơ sở đó ta đưa ra khái niệm hệ tổng kiểm tra trực giao sau: Định nghĩa: Hệ J tổng kiểm tra được gọi là trực giao với ui nếu: - Mỗi tổng kiểm tra trong hệ đều chứa ui. - Dấu mã uj (j¹i) chỉ nằm tối đa trong một tổng kiểm tra. Nhận xét: - Hệ tổng kiểm tra trực giao chứa nhiều thông tin về ui và chứa ít thông tin về các dấu mã khác. - Sai ở một dấu mã uj chỉ làm ảnh hưởng tới nhiều nhất là một tổng kiểm tra trong hệ. - Sai ở ui sẽ làm thay đổi tất cả các giá trị của các tổng kiểm tra trong hệ. - Ta có thể sửa được sai cho dấu ui dựa trên thông tin về giá trị của các tổng kiểm tra bằng phương pháp bỏ phiếu (giải mã ngưỡng theo đa số). Khi đó khoảng cách mã Hamming đạt được theo phương pháp này sẽ thỏa mãn điều kiện: d0 = J + 1. Hệ tổng kiểm tra được gọi là có khả năng trực giao nếu nó là hệ tổng kiểm tra trực giao với một tổ hợp tuyến tính nào đó các dấu mã. 34 Xét tổ hợp tuyến tính các dấu mã sau: 1 2 ... mi i i U U Ua = + + + , khi đó hệ tổng kiểm tra có khả năng trực giao sẽ gồm các tổng kiểm tra thỏa mãn điều kiện: - α nằm trong tất cả các tổng kiểm tra trong hệ. - Uj (j ≠ ik với Uik Î α ) chỉ nằm trong nhiều nhất là một tổng kiểm tra trong hệ. Nhận xét: - Dựa trên hệ tổng kiểm tra có khả năng trực giao ta có thể giải mã được cho giá trị của α bằng phương pháp ngưỡng. - Để giải mã cho một dấu mã Uik cụ thể ta phải sử dụng nhiều bước (nhiều cấp ngưỡng). 2.1.6. Khái niệm mã xyclic cục bộ Mã xyclic cục bộ là mã hệ thống tuyến tính (n,k), trong đó: - k dấu thông tin được chọn là k đơn thức có dạng xi (với i = 0,1,..,k-1) và là nhóm nhân xyclic cấp k của vành Z2[x]/xn + 1. - r = n – k dấu kiểm tra được chọn là một tập con không rỗng tuỳ ý nào đó các lớp kề của nhóm nhân này. 2.1.7. Mối quan hệ giữa mã xyclic và xyclic cục bộ Theo quan điểm xây dựng mã xyclic thông thường, mã xyclic là một Ideal của vành đa thức, trong đó mỗi từ mã là một phần tử của Ideal đó trên vành đa thức. Theo quan điểm xây dựng mã xyclic cục bộ, mỗi dấu mã là một phần tử của Ideal, toàn bộ từ mã là một bộ phận của vành gồm n phần tử xác định của Ideal. Như vậy, ta hoàn toàn có thể dùng lý thuyết xây dựng các đa thức sinh của mã xyclic để tạo các trưởng lớp kề cho các mã xyclic cục bộ. Với quan điểm đó, lớp kề được xây dựng theo cách sau đây sẽ tạo nên một mã xyclic: 35 Mã xyclic cục bộ được xây dựng từ trưởng lớp kề là một đa thức sinh g(x) thỏa mãn: - Đa thức sinh là ước của xn+1 - Bậc của đa thức sinh bằng r với r = n – k. - Sử dụng r dấu thông tin giả khi tạo lớp kề này, tức là cho trước: 0 1 2 1... 0-= = = = =nx x x x . Trên cơ sở phân tích như vậy thì mã xyclic là một lớp kề đặc biệt của mã xyclic cục bộ, hay mã xyclic là một dạng đặc biệt của mã xyclic cục bộ. 2.1.8. Mã xyclic cục bộ xây dựng trên các nhóm nhân xyclic Trên Z2[x]/(xn + 1), xét nhóm nhân xyclic sau: A = {ai(x)}, i = 1,2, Giả sử ord a(x) = l. Mỗi nhóm nhân xyclic sẽ tạo nên một mã xyclic (l,k,d) nào đó. Số các nhóm nhân xyclic tạo nên các mã (l, k, d) có cùng tham số là j(l), trong đó j(l) là hàm Euler, j(l) là số các số nguyên nguyên tố cùng nhau với l. Bằng cách dịch vòng các phần tử trong mỗi nhóm nhân, ta cũng có thể tạo ra các mã xyclic (l, k, d) có cùng tham số. Như vậy số các mã xyclic có cùng tham số có thể tạo ra là: N = l.j(l). 2.2. Phân hoạch vành đa thức theo nhóm nhân xyclic 2.2.1. Phân hoạch của vành theo các nhóm nhân xyclic Khi nghiên cứu các vành đa thức Z2[x]/ xn+1, chúng ta đã có những phát triển mới trong phân hoạch vành đa thức để làm cơ sở xây dựng các mã xyclic cục bộ và mã xyclic. Vành đa thức Z2[x]/ xn+1 có thể phân hoạch thành các lớp kề tương ứng với các nhóm nhân xyclic nào đó. Các nhóm nhân này được gọi là cá nhóm nhân sinh của phân hoạch hoặc là lớp kề sinh. Dựa vào các lớp kề này, chúng ta có thể tạo ra được các mã xyclic cục bộ và các mã xyclic khác nhau. Phân hoạch của vành là chia vành thành các tập con không giao nhau, với mỗi tập con là một cấp số nhân xyclic và hợp của các tập con bằng vành. Phân 36 hoạch vành thành tập hợp các cấp số nhân xyclic khác nhau. Tuỳ theo cách chọn a(x) mà có các phân hoạch khác nhau. Phân hoạch vành đa thức được gọi là không suy biến nếu phân hoạch này bao gồm tất cả các phần tử khác không của vành. Ngược lại, phân hoạch được gọi là suy biến. Ví dụ: xét vành R5; Z2[x]/ (x5+1) = (1+x)(1+x+x2+x3+x4). Trong ví dụ này, chúng ta sử dụng số mũ của các hạng tử xuất hiện trong đa thức làm kí hiệu, chẳng hạn q(x) = 1 + x + x2 được kí hiệu là (012). Chọn a(x) = x, I = {xi, i = 0,1,2,3,4}. Phân hoạch vành R5 thành các phần tử: Bảng 2.2: Phân hoạch vành Z2[x]/x5+1 theo nhóm nhân xyclic đơn vị 1 2 3 4 0 01 12 23 34 04 02 13 24 03 14 012 123 234 034 014 013 124 023 134 024 0123 1234 0234 0134 0124 01234 Trong vành này có 31 phần tử khác không và được phân hoạch thành 7 lớp kề: có 6 lớp kề có cấp 5 và 1 lớp kề cấp 1. Chọn phần tử khác làm phân hoạch: a(x) = 1 + x + x2 ~ (012). A = {(1 + x + x2)i, i = 0,..,14}. Lúc này có phân hoạch khác: Bảng 2.3: Phân hoạch vành với a(x) = 1 + x + x2 012 024 3 034 023 1 123 013 4 014 134 2 234 124 0 34 13 0124 12 14 0234 04 24 0123 23 02 0134 01 03 1234 01234 37 Đây là nhóm nhân xyclic cấp 15, có a(x) = 1+ x + x2. Để phân hoạch vành Rn, trước tiên xác định nhóm nhân xyclic A, số phần tử nhóm nhân nhiều nhất là max ord a(x) và các đa thức. Các bước thực hiện: - Chọn a(x) thuộc vành Rn. - Xây dựng nhóm nhân xyclic A = {ai(x)}. - Xây dựng các lớp kề của A. Về thực chất là xây dựng cấp số nhân xyclic có công bội a(x), có phần tử sinh b(x) Î Rn, b(x) không thuộc A và không thuộc bất cứ cấp số nhân nào chúng ta thiết lập. Nhận xét: Với cách lựa chọn nhóm nhân khác nhau có thể lựa chọn xây dựng các bộ mã khác nhau. Ví dụ với mã [15, 5] ta có số lượng các bộ mã có thể thiết lập được như sau: + Phân hoạch theo nhóm nhân xyclic đơn vị [15, 5], ta có N1 = 3!.53 = 750 bộ mã khác nhau cùng tham số. + Phân hoạch theo nhóm nhân xyclic cực đại (có cấp 15) ta có: N2 = 8.15 = 120 bộ mã khác nhau cùng tham số. + Phân hoạch theo nhóm nhân xyclic cấp 3, ta có: N3 = 5!.35 = 120.243 = 29160. Tổng số N1 + N2 + N3 = 30030 là số phân hoạch khác nhau của vành. 2.2.2. Phân hoạch vành đa thức theo nhóm nhân xyclic đơn vị Ta ký hiệu vành đa thức Z2[x]/xn+1 có nhóm nhân xyclic đơn vị được biểu diễn: I = {x0, x1,.., xn-1} với hạt nhân phân hoạch chính là x. Phân hoạch của vành đa thức theo nhóm nhân xyclic đơn vị được chỉ ra trên hình dưới: 38 Vấn đề cơ bản là phải xây dựng thuật toán xác định chính xác các lớp kề cần có và các phần tử trong các lớp kề. Với cấu trúc trên hình 2.2, vành đa thức bao gồm nhóm nhân xyclic đơn vị và các lớp kề được tạo từ nhóm nhân xyclic đơn vị I. Việc xây dựng phân hoạch vành là phải xác định các lớp kề của vành, được thực hiện như sau: Bước 1. Chọn A(x) không thuộc nhóm nhân I, là tổ hợp của các đơn thức trong nhóm nhân I, A(x) chính là trưởng lớp kề. Tiếp theo lần lượt xây dựng các phần tử trong lớp kề này bằng cách nhân với hạt nhân phân hoạch. Bước 2. Tiếp tục thực hiện bước 1 cho đến khi quét hết các lớp kề có thể có của vành đa thức. Phân hoạch này có số phần tử của vành là (2n-1) đa thức khác 0. Trong các nghiên cứu trước đây đều phân hoạch vành với k nhỏ, tuy nhiên để phân hoạch được vành với các k lớn cần phải xây dựng một thuật toán tổng quát để tính toán được hết các phần tử và các lớp kề của phân hoạch. I = {x0, x1,.., xn-1} Các lớp kề trên vành Hình 2.2. Cấu trúc vành Z2[x] / xn+1 39 2.2.3. Thuật toán xây dựng vành đa thức theo nhóm nhân xyclic đơn vị Bắt đầu Tính trưởng lớp kề Tính phần tử lớp kề Kiểm tra tồn tại Tính số đa thức trọng số i: Cik n = Cik Kết thúc i = k Đúng Sai Đúng Sai Đúng Sai Hiển thị kết quả n = n+1 Hình 2.3. Sơ đồ thuật toán tính phân hoạch vành theo nhóm nhân xyclic đơn vị Nhập K, i = 0 i = i + 1 Lưu lớp kề ra tệp 40 Dựa vào thuật toán trên, ta có thể xây dựng chương trình phần mềm để thực hiện phân hoạch vành đa thức. Hình 2.4. Chương trình tính phân hoạch vành theo nhóm nhân xyclic đơn vị Đây là hình ảnh mô tả phần mềm thực hiện và đánh giá khả năng thực hiện chương trình trên máy tính tốc độ cao. Bảng 2.4: So sánh phân hoạch vành đa thức trên máy tính core 2 duo 2.26GHz Stt Số dấu thông tin Thời gian tính toán Kích thước dữ liệu 1 k = 5 < 1s 108 byte 2 k = 7 < 1s 1008 byte 3 k = 8 < 1s 2.25 Kbyte 4 k = 9 < 1s 5 Kbyte 5 k = 12 < 1s 56 Kbyte 6 k = 16 ~ 7 s 1.281 Kbyte 7 k = 17 ~ 23 s 2.752 Kbyte 41 Với kết quả nghiên cứu ở trên mới chỉ ra khả năng phân hoạch của vành theo nhóm nhân xyclic đơn vị. Tuy nhiên, để phát triển các lý thuyết về mã xyclic cục bộ, chúng ta cần tìm các khả năng phân hoạch khác đem lại sự đa dạng cho lý thuyết mã xyclic cục bộ. 2.3. Kết luận Trong chương này, chúng ta nghiên cứu xây dựng một thuật toán hoàn chỉnh và viết chương trình máy tính để phân hoạch vành đa thức theo nhóm nhân xyclic đơn vị, điều đó hỗ trợ rất nhiều cho nghiên cứu, phát triển mã xyclic cục bộ. Phân hoạch vành với k lớn cho phép lựa chọn được lớp kề để lựa chọn, xây dựng các bộ mã xyclic cục bộ, nhờ đớ ta có nhiều phương án lựa chọn mã xyclic cục bộ để ứng dụng vào hệ mật McEliece. Chính vì vậy, việc ứng dụng mã xyclic cục bộ để xây dựng hệ mật McEliece là có tính khả thi. Các kết quả của chương này làm tiền đề cho việc xây dựng sơ đồ khối và các sơ đồ thuật toán của hệ mật McEliece trên mã xyclic cục bộ ở chương sau. 42 Chương 3 - XÂY DỰNG HỆ MẬT McELIECE TRÊN Mà XCB Hiện nay trên thế giới các hệ mật 40 bit được cung cấp miễn phí, hệ mật 128 bit được coi là hệ mật tốt. Chúng ta lựa chọn hệ mật 49 bit nằm trong khoảng cho phép. Để ứng dụng mã xyclic cục bộ vào hệ mật McEliece, tránh các nhược điểm của hệ mật McEliece sử dụng mã Goppa, chúng ta lựa chọn mã xyclic cục bộ với phân hoạch k = 8 kết hợp với mã ghép Elias để đảm bảo tốc độ mã hoá và giải mã. Theo các kết quả nghiên cứu đã đưa ra trong chương 2, chọn phân hoạch có các lớp kề có cùng trọng số và có trọng số lẻ (trọng số bằng 3) để xây dựng các thuật toán mã hoá và giải mã. 3.1. Tiêu chí lựa chọn bộ mã xyclic cục bộ và mô hình toán học để xây dựng hệ mật McEliece 3.1.1. Tiêu chí lựa chọn bộ mã XCB để xây dựng hệ mật McEliece + Mã xyclic cục bộ được lựa chọn phải tồn tại một thuật toán hiệu quả để sửa được t lỗi. + Cấu trúc mã xyclic cục bộ cho phép sửa được t lỗi khi kết hợp với ma trận S và P thì không tìm ra được cấu trúc của mã xyclic cục bộ đó. + Mã xyclic cục bộ (n,k) được xây dựng từ các lớp kề có cùng trọng số, và có trọng số lẻ làm dấu kiểm tra, là mã xyclic cục bộ có khả năng trực giao. + Số lượng khóa tồn tại trong lớp mã phải đủ lớn. 3.1.2. Mô hình toán học xây dựng hệ mật McEliece với mã xyclic cục bộ 3.1.2.1 Tạo khoá Mỗi đối tượng trong hệ thống trao đổi thông tin cần tạo ra một khoá công khai và một khoá bí mật, khoá công khai là 'iG , khoá bí mật là Si, Gi, Pi. Các bên tham gia hệ mật McEliece chia sẻ chung các tham số: n, k, t. Khóa bí mật: 43 + G là ma trận sinh của một mã XCB có khả năng sửa sai t lỗi theo phương pháp giải mã ngưỡng, có số lượng phân phối khóa đủ lớn. + S là ma trận khả nghịch [k x k] trên Z2. + P là ma trận hoán vị [n x n] trên Z2. Khóa công khai: (G’,t) G’ = S.G.P 3.1.2.2 Mã hoá và giải mã Mã hóa x là bản rõ cần mã hoá có độ dài k bit. y là bản mã hoá: y = ek(x,e) = x.G’ + e e Î (Z2)n : véc-tơ ngẫu nhiên độ dài n và có trọng số t được lựa chọn từ bản tin. Véc-tơ e chứa chính xác t bít 1. Giải mã Cần giải mã bản mã y Î (Z 2 )n - Tính y1 = y.P-1 - Sử dụng phương pháp giải mã y1 để có được y1 = x1 + e1 - Tính x0 Î (Z2) k sao cho x 0 .G = x 1 - Tính x = x0.S -1 3.2. Sơ đồ khối xây dựng hệ mật McEliece với mã xyclic cục bộ 3.2.1. Sơ đồ mã hoá Trong lược đồ mã hoá này, ta sử dụng mã XCB (64,7) để xây dựng ma trận sinh G. Ma trận S là ma trận khả nghịch [7x7], ma trận đơn vị P là ma trận hoán vị cấp [64x64]. Khoá công khai G' = S.G.P là ma trận [7x64]. 44 Bản rõ m được tách ra thành từng đoạn dữ liệu 49 bit và lấy một đoạn dữ liệu có chứa 31 bit 1 và có độ dài tối đa 512 bit làm véc-tơ sai e. Các đoạn dữ liệu 49 bit được sắp xếp thành ma trận [7x7], và được mã hoá bằng khoá công khai G' tạo ra ma trận [8x64] với hàng thứ 8 bằng tổng các cột từ 1 đến 7. Từ ma trận này được chuyển thành ma trận [1 x 512]. Véc-tơ sai e được cộng modulo 2 với ma trận [1x512] tạo thành dữ liệu mã hóa: M1 = m.G’ + e. Các phần dữ liệu tiếp theo tiếp tục được mã hoá theo chu trình trên cho đến khi kết thúc. 45 Ma trận [7x7] Ma trận sinh G’ [7 x 64] Ma trận [8x64] 7 1 ( ,8) ( , ) j i i j = = å Ma trận [1x512] Bản rõ Bản mã Hình 3.1. Sơ đồ khối mã hoá của hệ mật McEliece với mã XCB Véc tơ sai [1xn] có chứa 31 bít 1 và n≤ 512 Å 46 3.2.2. Sơ đồ giải mã Dữ liệu được lấy lần lượt 512 bít một lần để tạo thành ma trận [8x64]. Sau đó ma trận này được nhân với ma trận P-1 [64x64] thành ma trận M2: M2 = M1.P-1 Qua thuật giải mã xyclic cục bộ dựa trên phương pháp giải mã ngưỡng theo đa số, ta thu được dữ liệu 49 bít mã hoá là ma trận M3. Sau khi nhân M3 với ma trận S-1 [7x7] ta thu được m: m = M3.S-1 ta sẽ thu được 49 bít dữ liệu của bản rõ. Để giải mã vectơ sai e có chứa 31 bít 1 được cộng thêm, ta lại tiếp tục thực hiện mã hoá lại 49 bít đó theo phần 3.2.1 ta sẽ thu được 512 bít mã hoá. Sử dụng 512 bít này cộng modulo 2 với 512 bít đã mã hoá ban đầu ta thu được vectơ e có chứa 31 bít 1 của bản rõ đã cộng thêm trong quá trình mã hoá. Sơ đồ giải mã được trình bày trên hình 3.2. Phương án được lựa chọn với mục đích nâng cao hiệu quả truyền tin của hệ mật mã hoá khoá công khai McEliece với mã xyclic cục bộ. 47 Ma trận P-1 [64x64] Ma trận [8x64] Ma trận [7x7] Ma trận [1x512] Ma trận [8x64] Ma trận tổng kiểm tra Ma trận S-1 [7x7] Thực hiện mã hóa theo sơ đồ hình 3.1 Ma trận [1x n] có chứa tối đa 31 bít 1 và n≤ 512 Bản rõ Bản mã Hình 3.2. Sơ đồ khối giải mã của hệ mật McEliece với mã XCB + Giải mã 2 cấp ngưỡng 48 3.3. Về một phương pháp xây dựng hệ mật McEliece trên mã XCB 3.3.1. Phương pháp tạo khoá mã Hệ mật McEliece trên mã xyclic cục bộ sử dụng ma trận sinh G dựa trên phân hoạch vành theo