Luận văn Thạc sĩ Khoa học: Ứng dụng mã Xyclic cục bộ xây dựng hệ mật

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN -------------------

PHẠM XUÂN CÔNG ỨNG DỤNG MÃ XYCLIC CỤC BỘ XÂY DỰNG HỆ MẬT

LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội – 2010

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN -------------------

PHẠM XUÂN CÔNG ỨNG DỤNG MÃ XYCLIC CỤC BỘ XÂY DỰNG HỆ MẬT

Chuyên ngành: Bảo đảm toán học cho máy tính và hệ thống tính toán Mã số: 60.46.35

ƯỜI HƯỚNG DẪN KHOA HỌC:

LUẬN VĂN THẠC SĨ KHOA HỌC

ẠM VIỆT TRUNG TS. PH

Hà Nội – 2010

MỤC LỤC

MỤC LỤC............................................................................................................. 1

CÁC CHỮ VIẾT TẮT.......................................................................................... 3

DANH MỤC BẢNG BIỂU................................................................................... 4

DANH MỤC HÌNH VẼ ........................................................................................ 5

MỞ ĐẦU............................................................................................................... 6

CHƯƠNG 1 - TỔNG QUAN VỀ HỆ MẬT...................................................10

1.1.

Khái quát chung hệ mật mã cổ điển...........................................................10 1.1.1. Mô hình hệ thống truyền tin mật...........................................................10 1.1.2. Một số hệ mật mã cổ điển điển hình......................................................11 1.2. Hệ mật khoá công khai...............................................................................13 1.2.1. Khái quát chung....................................................................................13 1.2.2. Nguyên tắc chung mã hoá với khoá công khai......................................14 1.2.3. Quá trình phát triển của hệ mật mã khoá công khai...............................14 Kết luận.....................................................................................................24 1.3.

CHƯƠNG 2 - LÝ THUYẾT VỀ MÃ XYCLIC CỤC BỘ VÀ PHÂN HOẠCH VÀNH ĐA THỨC................................................................................25

2.1.

2.2.

Khái niệm mã xyclic và vành đa thức.........................................................25 2.1.1. Mã tuyến tính........................................................................................25 2.1.2. Vành đa thức.........................................................................................26 2.1.3. Mã xyclic..............................................................................................28 2.1.4. Mã hoá cho mã xyclic...........................................................................30 2.1.5. Giải mã ngưỡng....................................................................................31 2.1.6. Khái niệm mã xyclic cục bộ..................................................................34 2.1.7. Mối quan hệ giữa mã xyclic và xyclic cục bộ........................................34 2.1.8. Mã xyclic cục bộ xây dựng trên các nhóm nhân xyclic.........................35 Phân hoạch vành đa thức theo nhóm nhân xyclic.......................................35 2.2.1. Phân hoạch của vành theo các nhóm nhân xyclic..................................35 2.2.2. Phân hoạch vành đa thức theo nhóm nhân xyclic đơn vị .......................37 2.2.3. Thuật toán xây dựng vành đa thức theo nhóm nhân xyclic đơn vị .........39 Kết luận.....................................................................................................41 2.3.

CHƯƠNG 3 - XÂY DỰNG HỆ MẬT MCELIECE TRÊN MÃ XCB..........42

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ệ

3.1. mật McEliece.........................................................................................................42 3.1.1. Tiêu chí lựa chọn bộ mã XCB để xây dựng hệ mật McEliece................42 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ộ ......42

3.2.

3.3.

3.4.

Sơ đồ khối xây dựng hệ mật McEliece với mã xyclic cục bộ .......................43 3.2.1. Sơ đồ mã hoá........................................................................................43 3.2.2. Sơ đồ giải mã........................................................................................46 Về một phương pháp xây dựng hệ mật McEliece trên mã XCB...................48 3.3.1. Phương pháp tạo khoá mã.....................................................................48 3.3.2. Thuật toán mã hoá................................................................................50 3.3.3. Thuật toán giải mã................................................................................53 Nghiên cứu thử nghiệm hệ mật McEliece trên mã xyclic cục bộ .................59 3.4.1. Quá trình tạo khoá................................................................................59 3.4.2. Quá trình mã hoá..................................................................................62 3.4.3. Quá trình giải mã..................................................................................63 3.5. Đánh giá hệ mật McEliece trên mã xyclic cục bộ .......................................66 Kết luận.....................................................................................................67 3.6.

KẾT LUẬN CHUNG...........................................................................................68

TÀI LIỆU THAM KHẢO...................................................................................69

CÁC CHỮ VIẾT TẮT

Bậc của đa thức (degree ) deg

UCLN Ước chung lớn nhất (gcd)

ord Cấp (order)

XCB xyclic c ục bộ

DANH MỤC BẢNG BIỂU

Bảng 2.1: Các mã xyclic trên vành Z 2[x]/x7+1

Bảng 2.2: Phân ho ạch vành Z2[x]/x5+1 theo nhóm nhân xyclic đơn vị

Bảng 2.3: Phân ho ạch vành với a(x) = 1 + x + x2

Bảng 2.4: Kết quả phân hoạch vành đa thức trên máy tính core 2 duo 2.26GHz

Bảng 3.1: Phân ho ạch vành đa thức theo nhóm nhân xyclic đơn vị với k =8

Bảng 3.2: Các l ớp kề lựa chọn để xây dựng bộ mã (64,8,32)

Bảng 3.3: Ma tr ận G1 (8,64)

Bảng 3.4: Ma tr ận sinh G (7,64)

Bảng 3.5: Các d ữ liệu nhị phân của 10 ký tự là: "1234567890"

Bảng 3.6: Đánh giá hiệu suất phần mềm mã hoá và giải mã

DANH MỤC HÌNH VẼ

Hình 1.1: Mô hình hệ thống truyền tin mật

Hình 2.1: Thi ết bị mã hoá cho mã xyclic (n,k) có đa thức sinh g(x)

Hình 2.2: Cấu trúc vành Z2[x] / xn+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ị

Hình 2.4. Ch ương trình tính phân hoạch vành theo nhóm nhân xyclic đơn vị

Hình 3.1: Sơ đồ khối xây dựng hệ mật McEliece với mã XCB – Sơ đồ mã hoá

Hình 3.2: Sơ đồ khối xây dựng hệ mật McEliece với mã XCB – Sơ đồ giải mã

Hình 3.3: Sơ đồ thuật toán mã hoá

Hình 3.4: Sơ đồ thuật toán giải mã

Hình 3.5: Ch ương trình phần mềm mã hoá và giải mã

MỞ ĐẦU

Ngày nay v ới sự phát tri ển mạnh mẽ của công ngh ệ thông tin và truy ền

thông, máy tính và mạng máy tính đang ngày càng đóng vai trò thi ết yếu trong mọi

lĩnh vực hoạt động của toàn xã hội. Dữ liệu trao đổi trên mạng chứa rất nhiều thông

tin quan trọng cần được bảo vệ nên an toàn thông tin truyền trên mạng đóng một vai

trò rất quan tr ọng. Trong nh ững th ập kỷ 70 và 80 c ủa th ế kỷ tr ước công ngh ệ mã

hoá thông tin đã có bước phát tri ển vượt bậc. Các công ngh ệ mã hoá hi ện đại đều

không dựa vào kh ả năng giữ bí mật về công ngh ệ mã hoá (thu ật toán là công khai)

mà chỉ dựa vào bí m ật chìa khoá gi ải mã, một hệ mật như vậy được gọi là hệ mật

khoá công khai. H ệ mật này đáp ứng được đầy đủ đòi hỏi về bảo mật thông tin và

phù hợp cho các ứng dụng rộng rãi trong cộng đồng. Trong thời gian gần đây, nhiều

thuật toán t ốt đã được xây d ựng song song v ới tốc độ phát tri ển của công ngh ệ

thông tin nói chung, tuy nhiên đó là những thuật toán và công nghệ mã hoá do nước

ngoài cung cấp, do vậy để bảo vệ các thông tin, đặt biệt trong lĩnh vực an ninh quốc

phòng, chúng ta phải tự mình xây dựng các giải pháp cho bảo mật thông tin.

Ý tưởng về một hệ mật khoá công khai được Diffie và Hellman đưa ra vào

năm 1976, sau đó Rivesrt, Shamir và Adleman đưa ra h ệ mật nổi ti ếng RSA vào

năm 1977. Ti ếp theo đó một số hệ mật dựa trên các thu ật toán khác nhau ra đời,

trong đó, quan trọng nhất là các hệ mật khoá công khai sau:

- Hệ mật RSA: Độ bảo mật của hệ RSA dựa trên độ khó của việc phân tích ra th ừa

số nguyên lớn.

- Hệ mật xếp ba lô Merkle – Hellman: Hệ này và các hệ liên quan dựa trên tính khó

giải của bài toán tổng các tập con (bài toán NP đầy đủ). Tuy nhiên, tất cả các hệ mật

xếp ba lô khác nhau đều đã chứng tỏ là không mật (ngoại trừ hệ mật Chor-Rivest).

- Hệ mật McEliece: Hệ mật này dựa trên lý thuy ết mã hoá đại số và vẫn còn được

coi là an toàn. H ệ mật McEliece d ựa trên bài toán gi ải mã cho các mã tuy ến tính

(cũng là một bài toán NP đầy đủ).

- Hệ mật ElGamal: Hệ mật ElGamal d ựa trên tính khó gi ải của bài toán logarithm

rời rạc trên các trường hữu hạn .

- Hệ mật Chor-Rivest: Hệ mật Chor-Rivest cũng được xem như một hệ mật xếp ba

lô, hiện nay nó vẫn được coi là an toàn.

- Hệ mật trên các đường cong Elliptic: Các hệ mật này là biến tướng của các hệ mật

khác (chẳng hạn như hệ mật ElGamal), chúng làm việc trên các đường cong Elliptic

chứ không phải là trên các trường hữu hạn. Hệ mật này đảm bảo độ mật với số khoá

nhỏ hơn các hệ mật khoá công khai khác.

Trong các hệ mật khoá công khai ở trên, duy nh ất có hệ mật McEliece dựa

trên lý thuyết mã đại số để xây dựng hệ mật, với ứng dụng cụ thể là mã Goppa.

Từ năm 1987, GS.TSKH. Nguy ễn Xuân Qu ỳnh và PGS.TS Nguy ễn Bình

lần đầu tiên đề xuất phương pháp xây d ựng mã xyclic c ục bộ (XCB) [1][2][3][4],

cùng với các kết quả nghiên cứu của các nghiên cứu sinh [5][6], mở ra khả năng có

thể nghiên cứu phát triển tiếp lý thuyết về mã xyclic cục bộ. Các kết quả nghiên cứu

trước đây đã đưa ra các ph ương pháp phân ho ạch tổng quát vành theo các nhóm

nhân xyclic khác nhau trong vành. Ph ương pháp gi ải mã cho xyclic c ục bộ dùng

phương pháp gi ải mã ng ưỡng biểu quyết theo đa số, giải mã ngưỡng một cấp hoặc

hai cấp ng ưỡng. Vi ệc cải tạo các mã xyclic c ục bộ thành các mã t ối ưu được sử

dụng theo các ph ương pháp sử dụng dấu kiểm tra ch ẵn, sử dụng dấu thông tin gi ả,

các lớp mã xyclic cục bộ tự trực giao và có khả năng trực giao đã được đưa ra.

Các ưu điểm nổi bật của mã xyclic c ục bộ là kh ả năng lựa chọn mã phong

phú, thuật toán mã hoá và gi ải mã là tường minh, có hướng mở cho các nghiên c ứu

kế ti ếp. Chính vì v ậy, chúng tôi đã ch ọn đề tài “ Ứng dụng mã xyclic c ục bộ xây

dựng hệ mật” với mục đích ứng dụng khả năng của mã xyclíc c ục bộ để xây dựng

một hệ mật khoá công khai dựa trên hệ mật McEliece.

Mục đích của luận văn

Xây dựng một hệ mật khoá công khai d ựa trên lược đồ hệ mật McEliece sử

dụng mã xyclic cục bộ.

Đối tượng nghiên cứu

Lý thuyết về mật mã, hệ mật khoá công khai, lý thuy ết số, đại số, lý thuyết

mã xyclic cục bộ.

Ý nghĩa khoa học và thực tiễn của luận văn

Về khoa học: Nghiên cứu của luận văn góp phần làm phong phú thêm về lý

thuyết mã xyclic cục bộ, chứng minh một khả năng mới xây dựng hệ mật khoá công

khai dựa trên lý thuyết mã đại số.

Về thực tiễn: Kết quả nghiên cứu sẽ đưa ra một khả năng có th ể ứng dụng

trong thực tế, góp phần nâng cao tính bảo mật của thông tin trên đường truyền.

Phương pháp ti ếp cận: Dựa trên c ơ sở toán h ọc về lý thuy ết đại số, lý

thuyết số học, các thuật toán để xây dựng các hệ mật khoá công khai, các gi ải thuật

lập trình.

Phương pháp nghiên c ứu: Nghiên c ứu lý thuy ết mới về mã xyclic c ục bộ.

Ứng dụng các kết quả mới nhất về mã xyclic cục bộ vào hệ mật McEliece.

Nội dung của luận văn

- Tìm hiểu hệ mật khoá công khai McEliece

- Nghiên cứu về mã xyclic cục bộ, tìm hi ểu một phương án phân ho ạch tổng quát

vành theo nhóm nhân xyclic đơn vị.

- Xây dựng một hệ mật dựa trên lược đồ McEliece sử dụng mã xyclic cục bộ.

Nội dung của luận văn được chia thành các chương sau:

Chương 1. Nghiên c ứu tổng quan về hệ mật: Khái quát chung v ề hệ mật mã c ổ

điển, sự ra đời của hệ mật khoá công khai, phân tích hệ mật khoá công

khai dựa trên thuật toán McEliece.

Chương 2. Các nghiên c ứu về mã xyclic c ục bộ, nghiên c ứu thu ật toán phân

hoạch vành d ựa trên nhóm nhân xyclic đơn vị. Viết chương trình và

chạy th ử phân ho ạch vành đa th ức. Nghiên c ứu ph ương án s ử dụng

mã xyclic cục bộ xây dựng hệ mật khoá công khai d ựa trên thuật toán

McEliece.

Chương 3. Xây d ựng hệ mật McEliece trên mã xyclic c ục bộ: Về một ph ương

pháp xây d ựng hệ mật McEliece trên mã xyclic c ục bộ, xây d ựng

thuật toán mã hoá và gi ải mã. Xây d ựng thu ật toán và vi ết ch ương

trình thử nghiệm hệ mật.

Kết luận. Kết luận về kết quả nghiên cứu và ki ến nghị về hướng phát tri ển tiếp

theo.

Chương 1 - TỔNG QUAN VỀ HỆ MẬT

Chương này trình bày t ổng quan về quá trình hình thành và phát tri ển các

hệ mật cổ điển và h ệ mật khoá công khai, trong đó đi sâu phân tích v ề hệ mật

McEliece làm tiền đề cho các chương tiếp theo.

1.1. Khái quát chung hệ mật mã cổ điển

1.1.1. Mô hình hệ thống truyền tin mật

Nhiệm vụ cơ bản của mật mã là t ạo ra kh ả năng liên l ạc trên m ột kênh

không mật cho hai ng ười sử dụng sao cho ng ười thám mã không th ể hiểu được nội

dung thông tin được truyền đi. Thông tin mà người gửi muốn gửi cho người nhận có

cấu trúc tu ỳ ý. Ng ười gửi sẽ mã hoá b ản tin (b ản rõ) b ằng một khoá đã được xác

định trước và gửi bản mã tới người nhận qua kênh thông tin. Ng ười thám mã không

thể xác định được nội dung của bản rõ, nhờ có khoá mật KD người nhận có thể giải

Thám mã

(Người thám mã)

Bản rõ

Bản mã

Bản rõ

Bộ giải mã

Bộ mã hoá

Nhận tin

Nguồn tin

(Người nhận)

(Người gửi)

Kênh an toàn truyền khoá

Nguồn khoá

mã và thu được bản rõ. Mô hình hệ thống truyền tin mật được mô tả trên hình sau:

Hình 1.1: Mô hình hệ thống truyền tin mật

Theo quan niệm toán học ta có định nghĩa về hệ mật như sau [11]:

Định nghĩa 1.1

Một hệ mật là bộ 5 (R, M, K, E, D) thoả mãn các điều kiện sau:

1. R là một tập hữu hạn các bản rõ có thể.

2. M là tập hữu hạn các bản mã có thể.

3. K (không gian khoá) là tập hữu hạn các khoá có thể.

4. Đối với mỗi k˛ K có một quy tắc mã ek ˛ E và một quy tắc giải mã tương ứng

dk ˛ D. Mỗi ek: R ﬁ M và dk: M ﬁ R là những hàm mà:

dk(ek(x)) = x với mọi bản rõ x ˛ R

Theo định ngh ĩa trên n ếu một bản rõ x được mã hoá b ằng ek và b ản mã

nhận được gi ải mã b ằng dk thì ta ph ải thu được bản rõ ban đầu x. Ng ười nh ận và

người gửi sẽ áp dụng thủ tục sau dùng h ệ mật khoá riêng. Tr ước tiên, họ chọn một khoá ngẫu nhiên k ˛ K. Tiếp theo, gi ả sử người gửi mu ốn gửi một thông báo cho

người nhận trên một kênh không mật và ta xem thông báo này là một chuỗi:

1 x2 … xn

x = x

với số nguyên n ‡ R, 1 £ i £ 1 nào đó. Với xi ˛ n, mỗi xi đều sẽ được mã hoá bằng

quy tắc mã ek với khoá k xác định trước. Người gửi sẽ tính:

i £ n yi = ek(xi), 1 £

Chuỗi bản mã nhận được: y = y 1 y2 … yn sẽ được gửi trên kênh. Khi nh ận được y,

người nhận sẽ giải mã bằng dk và thu được bản rõ x = x1x2 … xn.

Hàm mã hoá e k phải là hàm ánh x ạ một – một, nếu không vi ệc gi ải mã sẽ

không thể thực hiện được một cách tường minh. Chú ý rằng nếu R = M thì mỗi hàm

mã hoá sẽ là một phép hoán vị, tức là nếu tập các bản mã và tập các bản rõ là đồng

nhất, thì mỗi một hàm mã sẽ là một sự sắp xếp lại (hay hoán vị) các phần tử của tập

này.

Hệ mật mã cổ điển (hệ mã bí m ật hay h ệ mã đối xứng) là hệ mã trong đó

việc mã hoá và giải mã cùng sử dụng chung một khoá bí mật.

1.1.2. Một số hệ mật mã cổ điển điển hình 1.1.2.1 Mã dịch vòng

Hệ mật được xây dựng dựa trên số học modulo. Ký hiệu m là số chữ cái của

bộ chữ xây dựng bản rõ R. Mã dịch vòng được định nghĩa như sau. Theo định nghĩa 1.1, cho R = M = K = Zm với 0 ≤ k ≤ (m - 1) và x, y ˛ Zm, ta định nghĩa:

ek(x) = (x + k) mod m

và dk(x) = (y – k) mod m

Các hệ mã hiện đại về thực chất là sự cải tiến của hệ mã dịch vòng. Về bản

chất, mã hoá một văn bản tiếng Anh thông th ường là sự thiết lập sự tương ứng giữa

các ch ữ cái v ới các s ố theo modulo 26. Tính b ảo mật của hệ mã d ịch vòng nói

chung là không cao, người ta có thể dùng phương pháp tìm khoá vét cạn để xác định

bản rõ. Nh ư vậy, điều ki ện cần để một hệ mật an toàn là phép tìm khoá vét c ạn

không thể thực hiện được.

1.1.2.2 Mã thay thế

Mã thay th ế về bản ch ất là xem phép mã hoá và gi ải mã nh ư các hoán v ị

của các ký tự và được định nghĩa như sau. Theo định nghĩa 1.1, cho R= M = Z 26 , K chứa mọi hoán vị có thể của m ký hiệu. Với mỗi phép hoán vị p K, ta định nghĩa: ˛

-1 là hoán vị ngược của p

ep (x) = p (x) và dp (y) = p -1 (y), trong đó p .

Về mã này, v ới các văn bản ti ếng Anh khi c ần mã hoá, m ỗi khoá c ủa mã

thay thế là một trong số 26! hoán vị. Do vậy, áp dụng phương pháp tìm khoá vét cạn

sẽ khó kh ăn hơn. mã thay th ế có th ể dễ dàng bị thám mã b ằng phương pháp th ống

kê. Cả hai hệ mã dịch vòng và mã thay th ế được gọi là hệ thay thế đơn biểu. Về cơ

bản, cả hai hệ đều xoay quanh phép thay thế.

1.1.2.3 Mã hoán vị

Về ý tưởng mã hoán vị là thay đổi vị trí giữa các ký tự của bản rõ. Mã hoán

của {1, ..., m}.

-1

vị được định nghĩa như sau: Cho m là m ột số nguyên dương xác định nào đó. Theo định nghĩa 1.1, cho R = M = (Z 26)m và K gồm tất cả các hoán vị p Đối với một khoá p (tức là một hoán vị) ta xác định:

(1), ..., yp

(m))

ep (x1, ..., xm) = (xp (1), ..., xp (m)) và dp (y1, ..., ym) = (yp

1.1.2.4 Các hệ mã dòng

Trong các hệ mật nghiên cứu ở trên, các ph ần tử liên ti ếp của bản rõ được

mã hoá bằng cùng một khoá k. Bản mã y nhận được có dạng:

1y2 ... = eK(x1) eK(x2) ...

y = y

Các hệ mật thuộc dạng này thường được gọi là các mã kh ối. Trên một quan

điểm khác, ng ười ta xây dựng các hệ mã dòng. Ý t ưởng cơ bản ở đây là tạo ra một

dòng khoá z = z 1z2z3... và dùng nó để mã hoá một xâu bản rõ x = x 1x2x3... theo quy

tắc:

12Z1Z

y = yy...= e(x)e(x)...

Về mặt toán học mã dòng theo [11] được định nghĩa như sau:

Định nghĩa 1.2

Mật mã dòng là một bộ (R, M, K, L, F, E, D) thoả mãn các điều kiện sau:

1. R là tập hữu hạn các bản rõ có thể.

2. M là tập hữu hạn các bản mã có thể.

3. K là tập hữu hạn các khoá có thể (không gian khoá).

4. L là tập hữu hạn bộ chữ của dòng khoá.

i: K · R-1 ﬁ L

f 5. F = (f1f2 ...) là bộ tạo dòng khoá. Với i ≥ 1,

6. Với mỗi z ˛ L có một quy tắc mã ez ˛ E và một quy tắc giải mã tương ứng dz

˛ D thoả mãn dz(ez(x)) = x với mọi bản rõ x ˛ R.

i ≥ 1. Ta có thể coi mã khối là một trường hợp đặc biệt của mã dòng khi dùng khoá không đổi zi = K, với "

1.2. Hệ mật khoá công khai

1.2.1. Khái quát chung

Việc xây d ựng các h ệ mật khoá công khai là thi ết kế một hệ mật sao cho

khả năng tính toán để xác định quy tắc gi ải mã (d k) là rất thấp dù bi ết quy tắc mã

hoá ek. Vì vậy quy tắc mã hoá e k có th ể được công khai r ộng rãi. Ưu điểm của hệ

mật này là ng ười gửi có th ể gửi bản tin cho ng ười nh ận mà không c ần thông tin

trước về khoá m ật. Ng ười nh ận là ng ười duy nh ất có th ể gi ải mã thông tin nh ận

được nhờ sử dụng quy tắc giải mã dk.

Hàm mã khoá công khai e k là một hàm dễ tính toán. Vi ệc tìm hàm ng ược dk

(hàm gi ải mã) là c ực kỳ khó kh ăn. Điều ki ện cần thi ết ek phải là hàm m ột chi ều.

[11]

1.2.2. Nguyên tắc chung mã hoá với khoá công khai

Trong hệ thống có N đối tượng cùng trao đổi thông tin mật. Từng đối tượng

chọn cho mình một khoá lập mã k và hàm mã hoá e k được công khai. Như vậy có N

khoá lập mã công khai k 1 ,k2 ,k3, ..., kn. Khi đối tượng i mu ốn gửi thông tin cho đối

tượng j thì dữ liệu được chuyển thành từng khối với độ dài nào đó, mỗi khối P trong

jke của đối tượng j, thông tin gửi đi có dạng:

văn bản được mã hoá bằng khoá lập mã

(

)

d(M) = de(P) = P

jkM = e(P)

kk jj

k j

. Để giải mã, đối tượng j thực hiện: .

jke và

jkd là khoá lập mã và gi ải mã của đối tượng j nên các đối tượng

jkd trong th ời gian ch ấp nh ận

khác trong h ệ th ống không th ể tìm ra khoá gi ải mã

jke .

được mặc dù biết

1.2.3. Quá trình phát triển của hệ mật mã khoá công khai

Các hệ mật khoá công khai được nghiên c ứu và phát tri ển mạnh mẽ vào

cuối những năm 70 của thế kỷ trước. Các hệ mật điển hình đã được tập trung nghiên

cứu phát triển và đưa vào ứng dụng trong thực tế là hệ mật RSA, hệ mật RABIN, hệ

mật ELGAMAL, hệ mật CHOR-RIVEST, hệ mật McELIECE [11]..

1.2.3.1 Hệ mật RSA

Hệ RSA được xây d ựng trên c ơ sở mã m ũ, trong đó khoá l ập mã là c ặp

(b,n), gồm số mũ b và mod n. V ới n = p.q trong đó p và q là các s ố nguyên tố cực lớn. Còn b được chọn là một số nguyên ngẫu nhiên sao cho UCLN(b, F (n)) = 1, với

F (n) là giá tr ị hàm Euler c ủa n, ở đây F (n) = (p-1)(q-1). Đặt R = M = Z n và định

nghĩa K= {(n, p, q, a, b):

” ab 1 (mod F (n))

Với k=(n, p, q, a, b) ta xác định

k (y) = ya mod n

d ek (x) = xb mod n và

(x,y ˛ Zn). Các giá trị n và b được công khai và các giá trị p, q, a được giữ kín.

- Tạo khoá: Mỗi đối tượng trong hệ thống trao đổi thông tin cần tạo một khoá công

khai và một khoá riêng tương ứng theo các bước sau:

+ Tạo 2 số nguyên tố lớn ngẫu nhiên và khác nhau p và q.

+ Tính n = p.q và F (n) = (p - 1)(q - 1).

+ Chọn một số nguyên ngẫu nhiên b (0 < b < F (n)) sao cho: (b, F ) = 1

+ Sử dụng thuật toán Euclide mở rộng để tính a = b-1 mod F (n).

+ Khoá công khai là c ặp số (n,b). Khoá riêng bí mật là a.

- Mã hoá: B mã hoá m ột thông báo m để gửi cho A b ản mã cần gi ải. B ph ải thực

hiện:

+ Thu nh ận khoá công khai (n,b) của A.

+ Bi ểu diễn bản tin dưới dạng một số nguyên m trong khoảng [0,n - 1].

b mod n.

+ Tính c = m

+ G ửi bản mã c cho A.

- Giải mã: Khôi phục bản rõ m từ c. A phải thực hiện phép tính sau bằng cách dùng khoá riêng m = ca mod n.

- Đánh giá: Nếu ta ch ọn các số p và q vào kho ảng 100 ch ữ số, thì n s ẽ vào kho ảng

200 chữ số như vậy hệ mật RSA được coi là an toàn. Để tránh bị rơi vào các trường

hợp đặc biệt (n bị phân tích nhanh nhờ những thuật toán mới) thì cần phải chọn (p –

1) và (q – 1) có toàn các ước nguyên tố nhỏ, UCLN (p – 1, q – 1) phải là số nhỏ.

Trong thực tế tốc độ mã hoá theo thu ật toán RSA là r ất chậm do vậy người

ta không ứng dụng hệ mật RSA cho mã hoá kh ối dữ li ệu lớn mà th ường ch ỉ tập

trung cho các vấn đề như: xác nhận chủ thể, tạo vỏ bọc an toàn cho văn bản mật..

1.2.3.2 Hệ mật ELGAMAL

Hệ mật ElGamal được xây dựng trên bài toán logarithm r ời rạc. Việc mô tả

bài toán này được thi ết lập trong tr ường hữu hạn Zp, p là s ố nguyên t ố (Bài toán

pZ là nhóm nhân xyclicvà ph ần tử sinh

logarithm rời rạc trong Z p) (Nhóm nhân

pZ được gọi là ph ần tử nguyên th ủy). Hệ mật ElGamal theo [11] được định

của

nghĩa như sau:

Định nghĩa 1.5:

Cho p là một số nguyên tố sao cho bài toán logarithm r ời rạc trong Zp là khó gi ải.

pZ là phần tử nguyên thủy. Giả sử P =

pZ , C =

pZ x

pZ . Ta định nghĩa:

Cho a ˛

K = {(p, a, a, b): b ” a a (mod p)}

Các giá trị p, a, b được công khai, còn a giữ kín.

Với K = (p, a, a, b) và một số ngẫu nhiên bí mật k ˛ Zp, ta xác định:

ek(x, k) = (y1, y2)

trong đó: y1 = a k mod p

y2 = x bk mod p

pZ ta xác định:

ay )-1 mod p

với y1, y2 ˛

dk(x, k) = y2 ( 1

Bài toán logarithm rời rạc trong Zp

Đặc trưng của bài toán: I = (p, a, b) trong đó p là số nguyên tố, a ˛ Zp là phần tử

pZ .

nguyên thủy, b ˛

Mục tiêu: Hãy tìm một số nguyên duy nhất a, 0 £ a £ p – 2 sao cho:

aa ” b (mod p)

Bài toán logarithm r ời rạc trong Z p là đối tượng trong nhi ều công trình

nghiên cứu và được xem là bài toán khó n ếu p được chọn cẩn thận. Cụ thể là không

có một thuật toán th ời gian đa thức nào cho bài toán logarithm r ời rạc. Để gây khó

khăn cho các ph ương pháp tấn công đã biết, p ph ải có ít nh ất 150 ch ữ số và (p - 1)

phải có ít nh ất một th ừa số nguyên t ố lớn. Lợi th ế của bài toán logarithm r ời rạc

trong xây dựng hệ mật là khó tìm được các logarithm r ời rạc, song bài toán ng ược

lấy lũy thừa lại có thể tính toán hi ệu quả theo thu ật toán nhân và bình ph ương. Nói

cách khác, lũy thừa theo modulo p là hàm m ột chiều với các số nguyên tố p thích

hợp.

Elgamal đã phát tri ển một hệ mật khóa công khai d ựa trên bài toán

logarithm rời rạc. Hệ mật Elgamal là m ột hệ mật không t ất định vì b ản mã ph ụ

thuộc vào cả bản rõ x l ẫn giá tr ị ngẫu nhiên do ng ười mã hóa ch ọn. Bởi vậy, sẽ có

nhiều bản mã được mã từ cùng bản rõ.

1.2.3.3 Hệ mật xếp ba lô MERKLE – HELLMAN

Hệ mật xếp ba lô Merkle – Hellman n ổi ti ếng lần đầu được Merkle-

Hellman mô tả vào năm 1978. Mặc dù hệ mật này và một vài biến thể của nó đã bị

phá vào đầu những năm 1980, nhưng nó vẫn là một cống hiến có giá trị do sự tinh tế

về khái niệm và kỹ thuật thiết kế có tính nền tảng của mình. Hệ thống này xây dựng

trên cơ sở bài toán tổng tập con (là bài toán NP-đầy đủ).

Với một danh sách các cỡ (s1, s2, s3,.., sn) là một dãy siêu tăng nếu:

> (cid:229)

s i

= 1

với 2 ≤ j ≤ n. Nếu danh sách các c ỡ là một dẫy siêu tăng thì dạng tìm ki ếm của bài

toán tổng các tập con có th ể gi ải rất dễ dàng với thời gian O(n) và nghi ệm x (n ếu

tồn tại) phải là nghiệm duy nhất.

Giả sử s = (s1,...,sn) là một dẫy siêu tăng, xét hàm

n :{0,1}{0,...,

e s

s i

n } = 1 i

ﬁ (cid:229)

)

= (cid:229)

exxx s (,..., i sni 1

= 1

Hàm này được xác định như sau:

Từ đó có thể dùng es như một quy tắc mã hoá. Vì s là một dẫy siêu tăng nên

es là một đơn ánh và thu ật toán để giải trường hợp siêu tăng của bài toán t ổng các

tập con sẽ là thuật toán giải mã tương ứng. Tuy nhiên một hệ thống như vậy sẽ hoàn

toàn mất an toàn vì bất kỳ ai cũng có thể giải mã một bản tin theo cách trên. Vấn đề

cơ bản ở đây là bi ến đổi danh sách các c ỡ theo cách sao cho nó không còn là dãy

siêu tăng nữa. Người nhận sẽ không th ể áp dụng một phép bi ến đổi ngược để khôi

phục lại danh sách siêu t ăng các c ỡ. Mặt khác, ng ười thám mã (không bi ết phép

biến đổi được dùng) phải đối mặt với bài toán tổng quát (là một bài toán khó của bài

toán tổng các tập con) trong khi cố gắng giải mã một bản mã.

Một ki ểu bi ến đổi thích h ợp là phép bi ến đổi theo modulo, điều này có

> (cid:229)

s i

nghĩa là phép biến đổi modulo p được chọn sao cho:

Ta chọn thừa số a thoả mãn 1 ≤ a ≤ p-1. Sau đó xác định:

ti = a si mod p

1 ≤ i ≤ n. Danh sách các c ỡ t = (t 1,.., tn) là khoá công khai được dùng để mã hoá.

Các giá trị a, p dùng để xác định phép bi ến đổi theo modulo sẽ được giữ kín. Theo

[11] ta có định nghĩa sau:

> (cid:229)

Định nghĩa 1.6:

s i

= 1

Cho s = (s 1,....,sn) là một danh sách các s ố nguyên siêu tăng. Cho

là một số nguyên tố và 1 ≤ a ≤ p-1. Với 1 ≤ i ≤ n, ta xác định:

ti = a si mod p

và ký hiệu t = (t1,...,tn).

Giả sử P = {0,1}n, C = {0,...,n(p-1)} và cho K={(s,p,a,t)}. Trong đó s, a, p

và t là các số được xây dựng như trên t được công khai, còn p, a và s được giữ kín.

)

= (cid:229)

exxx t (,.. Kni i 1

= 1

Với K ={(s,p,a,t)} ta định nghĩa:

với 0 ≤ y ≤ n(p-1) ta xác định z = a-1 y mod p và giải bài toán tập con (s1,..., sn,z), ta

sẽ được:

dK(y) = (x1,...,xn)

1.2.3.4 Hệ mật McEliece

Hệ mật McEliece [11] s ử dụng nguyên lý t ương tự nh ư hệ mật Merkle-

Hellman. Phép giải mã là một trường hợp đặc biệt của bài toán NP đầy đủ. Trong hệ

thống này, bài toán NP được áp dụng ở đây là bài toán gi ải mã cho một mã sửa sai

(nhị phân) tuyến tính nói chung. Tuy nhiên, đối với nhiều lớp mã đặc biệt tồn tại các

thuật toán thời gian đa thức. Một trong những lớp mã này là mã Goppa, chúng được

dùng làm cơ sở cho hệ mật McEliece.

Định nghĩa 1.7

, các hàng của ma trận này tạo nên cơ Coi k, n là các s ố nguyên dương, k £ n. Mã C [n,k] là một không gian con k chiều của (Z2)n (không gian véc-tơ của tất cả các véc-tơ nhị phân n chiều). Ma trận sinh của mã C[n,k] là ma trận nhị phân k n·

sở của C.

Coi x,y ˛ (Z2)n, trong đó x = (x1, x2,..,xn) và y = (y1,…,yn). Ta xác định khoảng cách

Hamming:

d(x,y) = | {i: 1 £ i £ n, xi „ yi}|

tức là số các tọa độ mà ở đó x và y khác nhau.

Coi C là mã [n,k]. Khoảng cách mã C được định nghĩa như sau:

d(C) = min{d(x, y): x, y ˛ C, x „ y}

Mã [n, k] có khoảng cách d được ký hiệu là mã [n, k, d].

Mã sửa sai được dùng để sửa các sai ng ẫu nhiên x ảy ra khi truy ền số liệu

qua kênh có nhiễu. Giả sử G là một ma trận sinh đối với mã [n, k, d], x là véc-tơ nhị

phân k chi ều cần truyền. Người gửi sẽ mã hóa x thành m ột véc-tơ n chi ều y = x.G

rồi truyền y qua kênh.

Giả sử người nhận nhận được véc-tơ n chi ều r không gi ống y, ng ười nhận

sẽ giải mã r bằng chiến thuật giải mã “người láng giềng gần nhất”. Theo chiến thuật

này, người nhận sẽ tìm th ấy từ mã y’ có kho ảng cách tới r nhỏ nhất. Sau đó sẽ giải

mã r thành y’, rồi xác định véc-tơ k chiều x’ sao cho y’ = x’G. Ng ười nhận hy vọng

y’= y và b ởi vậy x’= x (t ức là ng ười nhận tin rằng các sai s ố trên đường truyền đã

được sửa). Dễ dàng th ấy rằng, nếu sai số trên đường truyền nhiều nhất là (d - 1)/2

thì sẽ sửa được tất cả các sai.

Trên thực tế, thuật toán giải mã này được thực hiện như sau: Vì |C| = 2 k nên người nhận so sánh r với mỗi từ mã phải kiểm tra, 2k véc-tơ là một số lớn theo hàm

mũ so v ới k. Nói cách khác, thu ật toán này không ph ải là thu ật toán th ời gian đa

thức.

Một bi ện pháp khác (t ạo cơ sở cho nhi ều thu ật toán gi ải mã th ực tế) dựa

trên khái ni ệm về syndrom. Ma tr ận kiểm tra tính ch ẵn lẻ của mã C[n,k,d] - có ma

trận sinh G - là một ma trận nhị phân (n - k) x n chi ều (ký hiệu là H). Các hàng của ^ H sẽ tạo cơ sở cho các ph ần bù tr ực giao của C (ký hi ệu là C ) và được gọi là mã ^ đối ngẫu với C. Các hàng của H là những véc-tơ độc lập tuyến tính, còn GH là một

ma trận không, cấp k x (n-k).

^ ^ Cho véc-tơ r˛ . Syndrom Hr là một (Z2)n, ta xác định syndrom của r là Hr

véc-tơ cột có (n-k) thành phần.

Định lý 1.1

Giả sử C là một mã [n, k] có ma tr ận sinh G và ma trận kiểm tra tính chẵn lẻ H. Khi đó y ˛ (Z2)n là một từ mã khi và chỉ khi

T H.y =

(cid:230) (cid:246) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) Ł ł

Hơn nữa nếu y ˛ C, e ˛ (Z2)n và r = y + e thì HrT = HeT.

Ta coi e là véc-tơ sai xuất hiện trong quá trình truyền từ mã y. Khi đó r biểu

diễn véc-tơ thu được. Định lý trên phát biểu rằng syndrom chỉ phụ thuộc vào các sai

số mà không ph ụ thuộc vào từ mã cụ thể nào được truyền đi. Điều này đưa tới một

cách giải mã gọi là giải mã theo syndrom:

- Tính s = HrT

- Nếu s là một véc-tơ toàn không, thì giải mã r thành r.

- Nếu không thì tính HeT cho từng véc-tơ sai (có trọng số 1).

- Nếu có một véc-tơ e nào đó thỏa mãn HeT = s thì giải mã r thành r-e.

- Ngược lại, tiếp tục tính He T cho các véc-t ơ sai có tr ọng số 2,3,..., [(d-1)/ 2] cho đến khi thỏa mãn HeT = s thì giải mã r thành r-e.

C(cid:229)

Theo thuật toán này, có th ể giải mã cho m ột véc-tơ nhận được trong nhi ều

i n

i=0

nhất bước (t là số sai có thể sửa được).

Phương pháp này làm vi ệc trên một mã tuy ến tính bất kỳ. Đối với một số

loại mã đặc biệt, thủ tục giải mã có th ể nhanh chóng h ơn. Tuy nhiên, trên th ực tế,

cách giải quyết này cho chiến thuật giải mã “người láng giềng gần nhất” vẫn là một

bài toán NP đầy đủ. Nh ư vậy, vẫn ch ưa có m ột thu ật toán th ời gian đa th ức cho

trường hợp tổng quát cho chi ến thu ật gi ải mã ng ười láng gi ềng gần nh ất. (Khi s ố

các sai số không bị giới hạn bởi [(d-1)/2]).

Cũng giống như bài toán tổng hợp tập con, có thể chỉ ra một trường hợp đặc

biệt “dễ”, sau đó ngụy trang sao cho nó giống với bài toán chung “khó”. Một trường

hợp “d ễ” được McEliece đề ngh ị là dùng m ột mã trong l ớp các mã Goppa. Trên

thực tế, mã này có thu ật toán giải mã hữu hiệu. Hơn nữa mã này rất dễ tạo và trong

cùng một lớp mã có thể tạo một số lượng lớn các mã khác nhau.

Các tham số của mã Goppa có d ạng n = 2 m, d = 2t +1 và k = n - mt. Để áp

dụng trong thực tế cho một hệ mật khóa công khai, McEliece đề nghị chọn m = 10

và t = 50. Điều này ứng với mã Goppa [1024,524,101]. M ỗi bản rõ là m ột véc-tơ

nhị phân có độ dài 524 và m ỗi bản mã là m ột véc-tơ nhị phân độ dài 1024. Khóa

công khai là một ma trận nhị phân 524 x 1024.

Hệ mật McEliece được mô tả như sau:

Cho G là m ột ma tr ận sinh c ủa một mã Goppa C [n, k, d ], trong đó n = 2 m, d =

2t+1 và k = n - mt.

Cho S là một ma trận khả nghịch cấp k k· trên Z2.

, ta đặt G’ = SGP. Giả sử P là một ma trận hoán vị cấp n n·

Cho P = (Z2)2, C = (Z2)n và ký hiệu: K = {(G, S, P, G’)}

Trong đó G, S, P được xây d ựng nh ư mô t ả ở trên và được gi ữ kín, còn G’ được

công khai.

k(x, e) = x.G’ + e.

Với K = (G, S, P, G’), ta định nghĩa: e

Ở đây, e ˛ (Z2)n là một véc-tơ ngẫu nhiên có trọng số t.

Người nhận giải mã bản mã y ˛ (Z2)n theo các bước sau:

1 = yP-1.

1. Tính: y

2. Giải mã y1, người nhận tìm được: y1 = x1 + e1, x1˛C.

3. Tính x0 ˛ (Z2)k sao cho: x0G=x1

0S-1

4. Tính x = x

Để minh họa cho các thủ tục mã và giải mã, ta xét ví dụ sau :

1 0 0 0 11 0

0 1 0 0 1 0 1

0 0 1 0 0 1 1

0 0 0 1 1 1 1

(cid:230) (cid:246) (cid:231) (cid:247) (cid:231) (cid:247) Ma tr ận (cid:231) (cid:247) (cid:231) (cid:247) Ł ł

Là ma trận sinh của mã Hamming [7, 4, 3]. Giả sử người nhận chọn ma trận

S và ma trận P như sau:

0 1 0 0 0 0 0

0 0 0 1 0 0 0

110 1

0 0 0 0 0 0 1

100 1

10 0 0 0 0 0

= (cid:231)

01 1 1

0 0 1 0 0 0 0

110 0

0 0 0 0 0 1 0

0 0 0 0 1 0 0

(cid:230) (cid:246) (cid:231) (cid:247) (cid:231) (cid:247) (cid:230) (cid:246) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) và (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) Ł ł (cid:231) (cid:247) (cid:231) (cid:247) Ł ł

Khi đó ma trận sinh công khai là :

1 1 110 0 0

110 0 1 0 0

10011 0 1

01011 1 0

(cid:230) (cid:246) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) Ł ł

Giả sử người gửi mã hóa bản rõ x = (1,1,0,1) bằng cách dùng một véc-tơ sai

ngẫu nhiên trọng số 1 có dạng e = (0,0,0,0,1,0,0). Bản mã tính được là:

y = xG’ + e

(cid:230) (cid:246) (cid:231) (cid:247) (cid:231) (cid:247) + = (1,1,0,1)(0,0,0,0,1,0,0) (cid:231) (cid:247) (cid:231) (cid:247) 1 1 1 1 0 0 0 1 1 0010 0 1 0 0110 1 01 0111 0 Ł ł

= (0, 1, 1, 0, 0, 1, 0) + (0, 0, 0, 0, 1, 0, 0)

= (0, 1, 1, 0, 1, 1, 0)

Khi người nhận nhận được bản mã y, trước hết tính:

(cid:230) (cid:246) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) - = = (1, 0, 0, 0, 1, 1, 1) (cid:231) (cid:247) = yyP 1 (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) 01 0 0 00 0 000 1 00 0 000 0 00 1 (0,1,1,0,1,1,0) 100 0 00 0 001 0 00 0 000 001 0 000010 0 Ł ł

Tiếp theo người nhận giải mã y1 để nhận được x1 = (1, 0, 0, 0, 1, 1, 0) (c ần 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 để ý là e1 „

tiên của x1). Cuối cùng người nhận tính:

(cid:230) (cid:246) (cid:231) (cid:247) - (cid:231) (cid:247) = == xS x (1,0,0,0)(1,1,0,1) (cid:231) (cid:247) (cid:231) (cid:247) 1 10 1 1 1 0 0 011 1 1 00 1 Ł ł

Đâ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ộ.

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:

T = 0, r = n - k

G . H

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,.., (cid:229) r ahi jij

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.

2.1.2. Vành đa thức

i, "

Nhóm hữu hạn , với G = { a 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 đó < f(x), + > tạo thành một nhóm còn < f(x), . > 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 x n+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 = .

- (cid:219) = Xét trong vành đa thức, đa thức a(x) = . Nhân (cid:229) aaa - (,,..., a 01 a x i ) n

2 n

- (cid:219) = a(x) với nhân tử x ta có: b(x) = a(x). x = x.( ) . Biểu ) (cid:229) baa - a x i (,,..., a- 10 n

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

(cid:229) n

( )a x nếu:

a(x) được gọi là phần tử đối xứng của += axaxcx ()()( ) = x 0

= (cid:229) (cid:229) với: , ˛ ˛ = axaxaxa x (),( ) iIj J

¨ ˙ 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:

m – 1, với "a(x) ˛ Rn.

max ord a(x) = 2

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

có n phần tử).

2 , x3 , …, xn-1 , 1 }

Ký hiệu là : I = { x, x

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:

2 , (a(x))3 , …}

A = { a(x), (a(x))

* 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:

2(x), …, a(x).qm-1(x)}

A(a,q) = { a(x), a(x).q(x), a(x).q

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).

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 Z 2[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 1 (7,7)

1 + x 2 (7,6)

1 + x + x3 3 (7,4)

1 + x2 + x3 3 (7,4)

1 + x + x2 + x4 4 (7,3)

4 (7,3) 1 + x2 + x3 + x4

7 (7,1) 1 + x + x2 + x3 + x4 + x5 + x6

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 ư

(cid:230) (cid:246) (cid:231) (cid:247) (cid:231) (cid:247) = G (cid:231) (cid:247) (cid:231) (cid:247) - .( ) Ł ł ( ) g x .( ) xg x ... 1 k xg 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:

(cid:230) (cid:246) (cid:246) 1 10100 0 (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) = = G (cid:231) (cid:247) (cid:231) (cid:247) 01 1010 0 00 1 101 0 (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) + + 00 0110 1 Ł ł Ł ł ++(cid:230) 1 x + 2 xx 2 xx 34 xx x + x + 3 x + 6 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) = x n + 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,1}, với j = 2,..,k-1. (cid:229) , với h0 = hk = 1, hj ˛ h x j

Ma trận kiểm tra của mã xyclic sinh bởi g(x) là:

* ( ) h x * .( ) xh x ... * .( )

1 r xh x

(cid:230) (cid:246) (cid:231) (cid:247) (cid:231) (cid:247) = H (cid:231) (cid:247) (cid:231) (cid:247) - (cid:231) (cid:247) Ł ł

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à:

7+1)/(1+x+x3) = (1+x)(1+x2+x3) = x4+x2+x+1

Ta có: h(x) = (x

2+x3+x4

h*(x) = 1+x

Ma trận kiểm tra:

24 xxx

5 x

(cid:230) (cid:246) + + (cid:230) (cid:246) x (cid:231) (cid:247) (cid:231) (cid:247) + 11011 10 0 x x = =+++ 0101 11 0 Hxxx (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) x ++ + 0010 11 1 Ł ł Ł ł

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

in k

n == =

1 ) ( fxfxxaxr x 0

- - + Ta có .()( ) (cid:229)

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 A. ời rạc ai ˛

Đầ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á

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) = . Thiết bị mã hoá cho mã (n,k) v ới (cid:229) g x i

đa thức sinh g(x) như hình sau:

1,2,..,k V1

gr-1

ai(x).xn-k Vào

+

1,..,n Ra H k+1,..,n V2

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à V 1 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

- 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à V 2 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.

y x x’ Kênh Giải mã

e y = x + e

- Thủ tục 2: Dẫn ra véc-tơ sai từ dãy dấu nhận được.

x y x’ Kênh Giải mã + e’

e y = x + e

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:

(cid:230) (cid:246) (cid:231) (cid:247) (cid:231) (cid:247) = G (cid:231) (cid:247) (cid:231) (cid:247) - .( ) Ł ł ( ) g x .( ) xg x ... 1 k xg x

Gọi h(x) = (x n + 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) = x deg h(x) . h(x -1). Khi đó, ma tr ận ki ểm tra c ủa mã

V(n,k) có dạng:

* ( ) h x * .( ) xh x ... * .( )

1 r xh x

(cid:230) (cid:246) (cid:231) (cid:247) (cid:231) (cid:247) = H (cid:231) (cid:247) (cid:231) (cid:247) - (cid:231) (cid:247) Ł ł

Ta có G.HT = 0.

Kênh Với v ˛ V bất kì, ta có v.HT = 0. v u = (u0, u1, ..., un-1 )

Xét mô hình truyền tin sau: e

u = v + e

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ã u i, 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 u i 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ã u j 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ã.

++ + Xét tổ hợp tuy ến tính các d ấu mã sau: , khi đó hệ a = ... U i UU ii 1

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ệ.

α ) chỉ nằm trong nhiều nhất là một tổng kiểm tra trong - Uj (j ≠ ik với Uik ˛

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ã U ik 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:

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:

012 xxx

- ==== . x = 1... 0

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

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 R 5; Z2[x]/ (x 5+1) = (1+x)(1+x+x 2+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ị

3 4 0 1 2

23 34 04 01 12

24 03 14 02 13

234 034 014 012 123

023 134 024 013 124

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:

012

024

034

023

123

013

014

134

234

124

0124

0234

0123

0134

1234

01234

Bảng 2.3: Phân hoạch vành với a(x) = 1 + x + x2

Đâ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ó N 1 = 3!.5 3 = 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ó: N 2 = 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:

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

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à (2 n-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.

Bắt đầu

Nhập K, i = 0

i = i + 1

Tính số đa thức trọng số i: Ci k

n = n+1

Tính trưởng lớp kề

Kiểm tra tồn tại

Sai

Đúng

Tính phần tử lớp kề

Lưu lớp kề ra tệp

n = Ci k

Sai

Đúng

i = k

Sai

Đúng

Hiển thị kết quả

Kết thúc

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ị

2.2.3. Thuật toán xây dựng vành đa thức theo nhóm nhân xyclic đơn vị

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

Hình 2.4. Chương trình tính phân hoạch vành theo nhóm nhân xyclic đơn vị

hiện phân hoạch vành đa thức.

Đâ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

k = 5 k = 7 k = 8 k = 9 k = 12 k = 16 k = 17

1 2 3 4 5 6 7

< 1s < 1s < 1s < 1s < 1s ~ 7 s ~ 23 s

108 byte 1008 byte 2.25 Kbyte 5 Kbyte 56 Kbyte 1.281 Kbyte 2.752 Kbyte

Stt Số dấu thông tin Thời gian tính toán Kích thước dữ liệu

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.

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

iG , khoá bí mật là Si, Gi, Pi.

khai và một khoá bí mật, khoá công khai là

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:

+ 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 ˛ )n (Z

- Tính y1 = y.P-1

- Sử dụng phương pháp giải mã y1 để có được y1 = x1 + e1

(Z )k sao cho x - Tính x0 ˛ .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].

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: M 1 = 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.

Ma trận sinh G’ [7 x 64]

Bản rõ

= (cid:229) (,8)(, ) j ii

= 1

Ma trận [7x7]

Ma trận [8x64]

Ma trận [1x512]

Véc tơ sai [1xn] có chứa 31 bít 1 và n≤ 512

Bản mã

Hình 3.1. Sơ đồ khối mã hoá của hệ mật McEliece với mã XCB

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ộ.

Ma trận S-1 [7x7]

Ma trận tổng kiểm tra

Ma trận P-1 [64x64]

Bản mã

Ma trận [7x7]

Ma trận [8x64]

Giải mã 2 cấp ngưỡng

Ma trận [8x64]

Thực hiện mã hóa theo sơ đồ hình 3.1

Ma trận [1x512]

Ma trận [1x n] có chứa tối đa 31 bít 1 và n≤ 512

Hình 3.2. Sơ đồ khối giải mã của hệ mật McEliece với mã XCB

Bản rõ

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 nhóm nhân xyclic đơn vị với k = 8 ta có:

1 12 13 14 15 123 124 125 126 127 135 136 1234 1235 1236 1237 1245 1246 1247 1256 1257 12345 12346 12347 12356 12357 12367 12457 123456 123457 123467 123567 7 07 17 27 017 027 037 047 057 137 147 0127 0137 0147 0157 0237 0247 0257 01237 01247 01257 01347 01357 01457 02357 012347 012357 012457 2 23 24 25 26 234 235 236 237 023 246 247 2345 2346 2347 0234 2356 2357 0235 2367 0236 23456 23457 02345 23467 02346 02347 02356 234567 023456 023457 023467 3 34 35 36 37 345 346 347 034 134 357 035 3456 3457 0345 1345 3467 0346 1346 0347 1347 34567 03456 13456 03457 13457 01345 13467 034567 134567 013456 013457 4 45 46 47 456 457 045 145 245 046 146 4567 0456 1456 2456 0457 1457 2457 0245 04567 14567 24567 01456 02456 12456 02457 014567 024567 124567 5 56 57 05 567 056 156 256 356 157 257 0567 1567 2567 3567 0156 0256 0356 1356 01567 02567 03567 12567 13567 23567 01356 012567 013567 023567 6 67 06 16 067 167 267 367 467 026 036 0167 0267 0367 0467 1267 1367 1467 01267 01367 01467 02367 02467 03467 12467 012367 012467 013467

0 01 02 03 04 012 013 014 015 016 024 025 0123 0124 0125 0126 0134 0135 0136 0145 0146 01234 01235 01236 01245 01246 01256 01346 012345 012346 012356 012456 0123456 1234567 0234567 0134567 0124567 0123567 0123467 0123457 01234567

Bảng 3.1. Phân hoạch vành đa thức theo nhóm nhân xyclic đơn vị với k =8

Trên cơ sở đó ta chỉ lựa chọn các lớp kề có trọng số là 3 để xây dựng bộ mã

(64,8,32).

(0) (1) (2) (3) (4) (5) (6) (7) a0

012 123 234 345 456 567 670 017 b0

023 134 245 356 467 057 016 127 c0

034 145 256 367 047 015 126 237 d0

045 156 267 037 014 125 236 347 e0

056 167 027 013 124 235 346 457 f0

024 135 246 357 046 157 026 137 g0

025 136 247 035 146 257 036 147 h0

Bảng 3.2. Các lớp kề lựa chọn để xây dựng bộ mã (64,8,32)

Số phần tử của các lớp kề có trọng số là 3 là:

3 8

56 C =

Thông qua phân ho ạch vành theo nhóm nhân xyclic đơn vị, xây d ựng ma

(0)

(012)

(034)

(045)

(023)

(056)

(024)

(025)

1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1

1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1

1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 1 0 0 1 0 0 0 1 1 1 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1 0 0 1

1 0 0 1 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 0 1 1 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 1

1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 1

1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 1 1 0 0 0 0 1 0 1 1 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1

1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 1 0 1 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 1

1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1

trận G1 [8 x 64] được cho trong bảng 3.3.

Bảng 3.3. Ma trận G1 (8 x 64)

Từ ma trận G1[8 x 64] lấy giá trị của các hàng từ 1 đến 7 cộng với hàng cuối

1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 1 1 0 0 1 0 1 1 0 0 0 1 0 1 1 0 1 1 1 1

1 0 0 1 1 1 1 1 0 1 0 1 0 0 0 0 1 0 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 1 1 0 1 0 1 0 0 0 0 0 1 0 0 1 1 1 1 1 1

1 1 0 1 0 0 0 1 0 0 1 1 1 0 0 1 0 1 0 0 1 1 0 1 0 1 1 1 0 1 1 1 0 1 1 0 1 0 1 0 1 1 1 0 0 1 1 0 1 0 1 0 0 0 1 1

1 0 0 0 1 0 1 1 0 1 0 0 1 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1 1 1 0 1 0 1 1 0 0 1 0 1 0 0 1 1 1 0 0 1 0 0 0 1 0 1 1 1

1 0 1 0 1 0 0 1 0 1 1 1 1 1 0 1 0 0 0 1 0 1 1 1 0 0 1 0 0 0 1 0 1 0 1 1 1 0 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 0 1 1

1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 0 1 0 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 1 0 1 0 0 1 0 1 0 1 1

1 0 0 0 0 1 0 0 1 1 0 0 0 1 1 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 0 1 1 0 0 0 0 1 0 0 1

1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1

cùng ta được ma trận sinh G [7 x 64]

Bảng 3.4. Ma trận sinh G(7,64)

Với bảng phân ho ạch trên khi d ịch vòng các ph ần tử trên cùng m ột lớp kề

hoặc hoán vị các lớp kề khác nhau ta xây d ựng được các ma trận sinh G khác nhau. Với lớp mã này ta có thể xây dựng được 88.8! @ 676 tỷ khóa .

Trên cơ sở lược đồ của hệ mật McEliece ta có khóa công khai G’=S.G.P,

ngoài việc hoán vị các vị trí trên phân hoạch để tạo ra các ma trận sinh G khác nhau,

ta còn có thể thay đổi ma trận S và P để tăng khả năng tạo khoá cho hệ mật.

3.3.2. Thuật toán mã hoá 3.3.2.1. Nguyên tắc chung

Để tăng khả năng tốc độ xử lý thông tin ta s ử dụng mã XCB (64,7,32) k ết

hợp với mã Elias (8,7,2): (512,49,64) = (64,7,32)(8,7,2)

Thông tin đầu vào được chia như sau:

7 bit 7 bit 7 bit 7 bit 7 bit 7 bit 7 bit Có chứa 31 bit 1 và độ dài ≤512 bit

Khi mã hoá ta sẽ mã hoá mỗi lần 7x7=49 bit chứa thông tin thông qua khóa

công khai G' = S.G.P

Trong đó: S là ma tr ận khả nghịch 7x7

G là ma tr ận sinh 7x64

P là ma tr ận hoán vị 64x64

Khi mã hoá ta nhân ma trận chứa thông tin M [7x7] với ma trận G'[7x64]

3.3.2.2. Thuật toán mã hoá

Bắt đầu

Đọc khóa công khai Gi’ (Gi’= S.Gi.P)

K = 0

Đọc tệp dữ liệu Đọc kích thước tệp T

Vectơ sai V lấy từ bản tin

Phân tích dữ liệu theo bit - M(49 bit dữ liệu ) - V(vectơ sai chứa tối đa 31 bit 1 và độ dài ≤512 bit)

K=K+Len(M)+Len(V)

Chèn thêm dấu giả thông tin

Sai

Có đủ 49 bit để mã hóa?

Đúng

Mã hoá dữ liệu với Gi’

Ma trận (8,64)

Cộng modulo 2

Sắp xếp về 512 bit

Ghi kết quả

512 bit đã mã hoá

Đúng

K < T

Sai

Kết thúc

Hình 3.3. Sơ đồ thuật toán mã hoá

Dữ liệu sau mã hoá là ma tr ận [8x64] với hàng th ứ 8 là t ổng ki ểm tra của

các hàng trên.

............

.............................................

= (cid:229)

Từ ma trận [8x64] thu được ta có thể đưa ra các tính chất sau:

7 a 0

k a 0

0 a 7

0 k

và (theo tính chất của ma trận)

= (cid:229)

....

7 a 7

k a 7

7 a 7

7 k

k 6

= (cid:229)

và (theo tính chất của ma trận)

0 b 7

0 b k

7 b 0

k b 0

và (theo tính chất của ma trận)

= (cid:229)

....

7 b 7

k b 7

7 b 7

7 b k

= (cid:229)

và (theo tính chất của ma trận)

7 c 0

k c 0

0 c 7

0 c k

và (theo tính chất của ma trận)

= (cid:229)

....

7 c 7

k c 7

7 c 7

7 c k

= (cid:229)

và (theo tính chất của ma trận)

7 0

k 0

0 7

0 k

và (theo tính chất của ma trận)

= (cid:229)

....

7 7

k 7

7 c 7

7 c k

và (theo tính chất của ma trận)

= (cid:229)

7 e 0

k e 0

0 e 7

0 e k

và (theo tính chất của ma trận)

= (cid:229)

....

7 e 7

k e 7

7 c 7

7 c k

= (cid:229)

và (theo tính chất của ma trận)

7 0

k 0

0 7

0 k

và (theo tính chất của ma trận)

= (cid:229)

....

7 7

k 7

7 7

7 k

k 6

= (cid:229)

và (theo tính chất của ma trận)

7 0

k 0

0 7

0 k

và (theo tính chất của ma trận)

= (cid:229)

....

7 7

k 7

7 7

7 k

= (cid:229)

và (theo tính chất của ma trận)

0 h k

7 h 0

k h 0

0 h 7

và (theo tính chất của ma trận)

= (cid:229)

....

7 h 7

k h 7

7 h 7

7 h k

và (theo tính chất của ma trận)

Sau khi mã xong 49 bit thông tin ta nh ận được ma trận [8,64] thực hiện sắp

xếp lại thông tin thành 512 bit, sau đó lấy tiếp thông tin phía sau 49 bit đến khi có

31 dấu 1 và có độ dài nhỏ hơn hoặc bằng 512 bít.

512 bít dữ liệu gửi đi 512 bit đã mã hoá ¯ Dữ liệu có chứa 31 bit 1 và có độ dài ≤ 512 bit

3.3.3. Thuật toán giải mã a) Nguyên tắc chung

Việc giải mã được thực hiện như sau:

- Từ 512 bit dữ liệu thu được khôi phục thành ma trận M1[8x64]

- Nhân ma trận M1 với ma trận nghịch đảo của P thu được ma trận M2.

M2 = M1.P-1

- Sử dụng các tổng kiểm tra giải mã cho M2 thu được ma trận M3[7x7]

- Nhân ma trận M3 với ma trận nghịch đảo của S thu được ma trận M.

M = M3.S-1 với ma trận M [7x7] là ma trận chứa 49 bit thông tin mã hoá.

Do sử dụng vectơ sai chứa thông tin nên ta phải thực hiện thêm một số bước sau:

- Mã hoá l ại ma tr ận M[7x7] thu được ma tr ận [8x64] ch ứa dữ li ệu mã hoá

chưa có véc-tơ sai (hàng thứ 8 bằng tổng các hàng phía trên).

- Sắp xếp thành chuỗi 512 bit, sau đó thực hiện cộng modulo 2 với 512 bit thu

được ta sẽ thu được véc-tơ sai.

b) Xây dựng các tổng kiểm tra

Do sử dụng mã xyclic cục bộ nên ta s ử dụng phương pháp gi ải mã ngưỡng

cho nên ta phải xây dựng các tổng kiểm tra để giải mã.

Các tổng kiểm tra cấp 1 (Giải mã cho các cặp dấu)

A(0) A(1) A(2) A(3) A(4) A(5) A(6) A(7)

a0 + a1 a1 + a2 a2 + a3 a3 + a4 a4 + a5 a5 + a6 a6 + a7 a7 + a0

Dựa trên phân ho ạch vành theo nhóm nhân xyclic đơn vị với k=8 ta xây

dựng được 32 tổng kiểm tra cho cặp dấu A0(a0 + a1) là:

c5 + g5 = S8 g4 + h4 = S16 d3 + c2 = S24 b0 + a2 = S0

d1 + c1 = S9 g6 + d6 = S17 c3 + h2 = S25 f3 + a3 = S1

d4 + h7 = S10 h0 + e5 = S18 c4 + f5 = S26 e0 + a4 = S2

e0 + d1 = S11 h3 + g1 = S19 d2 + e7 = S27 d5 + a5 = S3

e3 + g7 = S12 h6 + h1 = S20 e6 + f7 = S28 c6 + a6 = S4

f0 + e1 = S13 b2 + b5 = S21 f6 + h5 = S29 b7 + a7 = S5

f2 + c7 = S14 b3 + e2 = S22 g2 + g3 = S30 c0 + b1 = S6

g0 + f4 = S15 b4 + d7 = S23 a0 + a1 = S31 b6 + f1 = S7

Đối với tính ch ất của mã (512,49,64) = (64,7,32) (8,7,2) ta thi ết lập được

0 a 0

1 0

thêm 32 tổng kiểm tra cho cặp dấu : a+

b + = S a

7 d + = S

b + = S b

k 0232

k 2553

k=1k=1

k e 0143 k=1k=1

k=1k=1

7 a + = S

7 g + = S

b + = S e

(cid:229) (cid:229) (cid:229) (cid:229) (cid:229) (cid:229)

k 3333

k 3254

f k=1k=1

k e 3744 k=1k=1

k=1k=1

7 a + = S

7 e + = S

b + = S d

(cid:229) (cid:229) (cid:229) (cid:229) (cid:229) (cid:229)

k 0145

k 4755

k e 4434 k=1k=1

f k=1k=1

k=1k=1

7 a + = S

7 c + = S

(cid:229) (cid:229) (cid:229) (cid:229) (cid:229) (cid:229)

k 5535

k 2746

k 3256

d k=1k=1

f k=1k=1

d k=1k=1

7 a + = S

7 h + = S

(cid:229) (cid:229) (cid:229) (cid:229) (cid:229) (cid:229)

k 0447

k c 6636 k=1k=1

g k=1k=1

k c 3257 k=1k=1

b + = S a

7 h + = S

7 f + = S

(cid:229) (cid:229) (cid:229) (cid:229) (cid:229) (cid:229)

k 7737

k 4448

k=1k=1

g k=1k=1

k c 4558 k=1k=1

7 b + = S

7 d + = S

7 e + = S

(cid:229) (cid:229) (cid:229) (cid:229) (cid:229) (cid:229)

k 6649

k 2759

k c 0138 k=1k=1

g k=1k=1

d k=1k=1

b + = S f

7 e + = S

7 f + = S

(cid:229) (cid:229) (cid:229) (cid:229) (cid:229) (cid:229)

k 6139

k=1k=1

k h 0550 k=1k=1

k e 6760 k=1k=1

7 g + = S

7 h + = S

(cid:229) (cid:229) (cid:229) (cid:229) (cid:229) (cid:229)

k 6561

k c 5540 k=1k=1

k h 3151 k=1k=1

f k=1k=1

7 c + = S

7 h + = S

7 g + = S

(cid:229) (cid:229) (cid:229) (cid:229) (cid:229) (cid:229)

k 2362

k d 1141 k=1k=1

k h 6152 k=1k=1

g k=1k=1

7 h + = S

7 a + = S

(cid:229) (cid:229) (cid:229) (cid:229) (cid:229) (cid:229)

k 4742

k 0163

d k=1k=1

a k=1k=1

(cid:229) (cid:229) (cid:229) (cid:229)

For (i = 1..7) {

= (cid:229) ()( ) NiS i

‡ 33 )

A(i) = 1

if ( N(i) else

A(i) = 0

}

Để giải mã cho từng cặp dấu từ A0 đến A7 sử dụng thuật toán:

Sau đó xây d ựng 64 t ổng ki ểm tra cho c ấp ng ưỡng th ứ 2 thông qua phân

hoạch vành theo nhóm nhân xyclic đơn vị với k=8 và tính ch ất của mã (512,49,64)

để giải mã cho từng dấu thông tin:

T32 = A(7) + A(6) + A(4) + T0 = A(0) + a1

T33 = A(7) + A(6) + A(3) + T1 = A(0) + A(1) + a2

T34 = A(7) + A(6) + A(2) + T2 = A(7) + a7

T35 = A(7) + A(6) + A(1) + T3 = A(7) + A(6) + a6

T36 = A(7) + A(6) + A(0) + T4 = A(1) + b0

T37 = A(0) + A(1) + A(7) + T5 = A(2) + c0

T38 = A(0) + A(2) + A(3) + T6 = A(3) + d0

T39 = A(0) + A(3) + A(4) + T7 = A(4) + e0

T40 = A(0) + A(4) + A(5) + T8 = A(5) + f0

T41 = A(0) + A(5) + A(6) + T9 = A(6) + b6

T42 = A(7) + A(5) + A(4) + T10 = A(1) + A(2) + f3

T43 = A(7) + A(4) + A(3) + T11 = A(2) + A(3) + g0

T44 = A(7) + A(3) + A(2) + T12 = A(3) + A(4) + h3

T45 = A(7) + A(2) + A(1) + T13 = A(4) + A(5) + g4

T46 = A(1) + A(2) + A(3) + T14 = A(5) + A(6) + c5

T47 = A(2) + A(3) + A(4) + T15 = A(7) + A(0) + b7

T48 = A(3) + A(4) + A(5) + T16 = A(0) + A(2) + b1

T49 = A(4) + A(5) + A(6) + T17 = A(0) + A(3) + c1

T50 = T18 = A(0) + A(4) + d1

k a 0

= 1

(cid:229) T51 = T19 = A(0) + A(5) + e1

k a 1

= 1

(cid:229) T52 = A(0) + T20 = A(0) + A(6) + f1

k b 0

= 1

(cid:229) T53 = A(1) + T21 = A(7) + A(5) + b5

k 0

= 1

(cid:229) c T54 = A(2) + T22 = A(7) + A(4) + f7

k 0

= 1

(cid:229) d T55 = A(3) + T23 = A(7) + A(3) + e7

k e 0

= 1

(cid:229) T56 = A(4) + T24 = A(7) + A(2) + d7

k 0

= 1

(cid:229) f T57 = A(5) + T25 = A(7) + A(1) + c7

k b 6

= 1

(cid:229) T58 = A(6) + T26 = A(0) + A(1) + A(2) + a3

k a 7

= 1

(cid:229) T59 = A(7) + T27 = A(0) + A(1) + A(3) + b2

k a 2

= 1

(cid:229) T60 = A(0) + A(1) + T28 = A(0) + A(1) + A(4) + e2

k b 1

= 1

(cid:229) T61 = A(0) + A(2) + T29 = A(0) + A(1) + A(5) + d2

k c 1

= 1

(cid:229) T62 = A(0) + A(3) + T30 = A(0) + A(1) + A(6) + e2

k d 1

= 1

k Để giải mã cho từng dấu từ a0 đến a7 sử dụng thuật toán:

For ( i = 1 .. 7 ) { = (cid:229) ()( ) MiT i

‡ 33 )

a(i) = 1

if ( M(i) else

a(i) = 0

}

(cid:229) T63 = A(0) + A(4) + T31 = A(7) + A(6) + A(5) + a5

3.3.3.3. Thuật toán giải mã

Bắt đầu

Đọc Gi' = Si.Gi.Pi

-1

Đọc Pi

-1, Si

Đọc ma trận tổng kiểm tra của Gi

K = 0

Đọc tệp mã hóa Đọc kich thước tệp T

Phân tích dữ liệu theo bit M (512 bit dữ liệu mã hóa)

K=K+Len(M)

Sắp xếp về ma trận M1(8,64)

-1

-1 Giải mã dữ liệu M2 = M1 * Pi M3 = Giải mã sửa sai M2 theo tổng kiểm tra 2 cấp ngưỡng M = M3* Si

49 bit dữ liệu của bản tin

Mã hóa lại dữ liệu với Gi’ tạo Ma trận (8,64)

Sắp xếp thành 512 bít

Cộng Modulo 2

Ghép dữ liệu

Vectơ sai có chứa dữ liệu

Ghi kết quả

Đúng

K < T

Sai

Hình 3.4. Sơ đồ thuật toán giải mã

Kết thúc

3.4. Nghiên cứu thử nghiệm hệ mật McEliece trên mã xyclic cục bộ

Phần này là ví d ụ về xây dựng hệ mật McEliece trên mã xyclic c ục bộ. Dữ

liệu được mã hoá là một chuỗi 10 ký tự là: "123456789012347". Chuỗi này theo mã

ASCII sẽ được đọc thành các giá trị là:

Ký tự Mã ASCII Giá trị nhị phân Xử lý bit trên máy tính

1 2 3 4 5 6 7 8 9 0 31 32 33 34 35 36 37 38 39 30

10001100 00110001 01001100 00110010 11001100 00110011 00101100 00110100 10101100 00110101 01101100 00110110 11101100 00110111 00011100 00111000 10011100 00111001 00001100 00110000 Bảng 3.5. Các dữ liệu nhị phân của 10 ký tự là: "1234567890"

Dữ li ệu đầu vào được xây d ựng thành 1 ma tr ận M(7x7) và m ột đoạn dữ

liệu còn lại là 31 bit

10 0011 0

0010 0 1 1

00110 0 1

M x (77)

10 0 001 0

= (cid:231)

110010 1

0110 0 0 1

10110 0 1

(cid:230) (cid:246) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) Ł ł

11011000001110010011100000011001000110001001100110011000010110011101100

Đoạn dữ liệu cuối có chứa 31 bit 1 được xắp sếp như sau:

3.4.1. Quá trình tạo khoá

Quá trình t ạo khoá được th ực hi ện từ phân ho ạch vành theo nhóm nhân

xyclic đơn vị với k=8 và các l ớp kề có trọng số bằng 3 để tạo ra ma tr ận sinh G và

các tổng kiểm tra để giải mã.

0 012 013 014 015 016 024 025 1 123 124 125 126 127 135 136 2 234 235 236 237 023 246 247 3 345 346 347 034 134 357 035 4 456 457 045 145 245 046 146 5 567 056 156 256 356 157 257 6 067 167 267 367 467 026 036 7 017 027 037 047 057 137 147

Từ phân ho ạch trên ta xây d ựng được ma tr ận [8x64] t ương ứng với cách

(0)

(012)

(013)

(014)

(015)

(016)

(024)

(025)

1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1

1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1

1 0 0 0 0 1 0 1 1 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 1

1 0 0 0 1 0 0 1 1 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 1

1 0 0 1 0 0 0 1 1 1 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1 0 0 1 1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 1 1

1 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 1 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1

1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 1 0 1 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 1

1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1

sắp xếp của phân hoạch là:

Ta xây dựng ma tr ận sinh G[7x64] t ừ ma tr ận [8x64] (c ộng từng hàng từ 1

1 0 0 0 0 0 0 1

1 0 0 0 0 1 0 0

1 0 0 0 1 1 1 0

1 0 0 1 1 0 1 0

1 0 1 1 0 0 1 0

1 1 1 0 0 0 1 0

1 0 0 1 1 1 1 1

1 0 1 1 0 1 1 1

0 1 0 0 0 0 0 1

1 1 0 0 0 1 1 0

1 1 0 0 1 0 0 1

1 1 0 1 0 1 1 1

1 1 1 0 1 0 1 1

1 0 0 1 0 0 1 1

0 1 0 1 0 0 0 0

0 1 1 0 1 1 0 0

0 0 1 0 0 0 0 1

1 1 1 0 0 1 1 1

0 1 1 0 1 0 1 0

0 1 1 1 0 0 0 1

0 1 0 0 0 1 1 1

0 0 1 0 1 0 1 1

1 0 1 1 0 1 1 1

1 0 0 0 0 0 0 1

0 0 0 1 0 0 0 1

0 1 1 1 0 1 1 1

1 0 1 1 1 0 1 1

0 0 1 0 0 0 1 0

0 0 0 1 0 0 0 1

0 1 1 1 0 1 1 1

0 1 0 0 0 1 0 0

0 1 1 1 0 1 1 1

0 0 0 0 1 0 0 1

0 0 1 1 1 1 1 1

0 1 0 1 0 0 1 1

1 0 0 0 1 0 1 1

0 0 1 1 1 0 1 0

0 1 0 1 1 0 0 1

1 0 1 1 1 1 0 1

0 0 0 0 1 1 0 0

0 0 0 0 0 1 0 1

0 0 0 1 1 0 1 1

0 0 1 0 0 1 1 1

0 1 0 1 1 1 1 1

1 0 1 0 1 1 1 1

0 1 0 0 1 1 1 0

0 1 0 0 0 0 0 1

1 0 1 1 0 0 0 1

0 0 0 0 0 0 1 1

0 0 0 0 1 0 0 1

0 0 0 1 1 1 0 1

0 0 1 1 0 1 0 1

0 1 1 0 0 1 0 1

1 1 0 0 0 1 0 1

0 0 1 1 1 1 1 1

0 1 1 0 1 1 1 1

đến 7 với hàng thứ 8):

Nhân ma trận G với ma trận S và P ta được ma trận G':

G'= S. G .P

S là ma trận khả nghịch (7x7)

1 110 0 0 0

00 1101 0

11011 0 1

01 10 1 1 1

và

S -

111101 0

= (cid:231)

01 110 0 0 00111 0 0 0 0011 1 0

= (cid:231)

00 1110 0

110111 0

0 0 0 0 1 1 1 10 0 0 0 1 1

11 10 11 0

110 0 0 0 1

(cid:230) (cid:246) (cid:230) (cid:246) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:247) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) Ł ł Ł ł

P là ma trận hoán vị [64 x 64]

100... 0

001... 0

010... 0

...............

00... 1

(cid:230) (cid:246) (cid:230) (cid:246) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) - (cid:231) (cid:247) (cid:231) (cid:247) và (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) (cid:231) (cid:247) Ł ł Ł ł

Ta có G' là ma trận [8x64]

0 0 0 1 1 0 1 1 0 1 0 0 0 0 0 1 1 1 1 1 0 1 0 1 1 0 0 1 1 1 0 0 0 1 0 0 1 1 1 0 1 1 1 0 1 0 1 1 1 1 0 0 0 1 1 0 0 0 0 1 0 1 0 0

0 0 0 1 1 1 0 1 0 1 0 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 1 1 0 1 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 1 1 1 0 0 0 1 1 0 0 1 0 1 0

0 0 0 0 1 1 1 1 0 0 1 0 1 1 0 1 0 1 1 0 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 0 1 0 0 1 0 1 1 0 0 0 0 1 1 1 1 0 1 0 0 1 0

1 0 0 0 0 1 1 1 1 0 0 1 0 1 1 0 1 0 1 1 0 1 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 1 0 0 1 1 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1

1 1 0 0 0 0 1 1 0 1 0 0 1 0 1 1 0 1 0 1 1 0 1 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 1 0 1 1 0 1 0 0 1 1 1 1 0 0 0 0 1 0 1 1 0 1 0 0

1 1 1 0 0 0 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 0 1 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 1 0 1 1 0 1 0 0 1 1 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 1 1 0 0 0 1 0 1 0 1 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 1 0 1 1 1 1 0 1 1 1 0 0 1 1 1 1 1 0 1 0 0 0 1 1 1 0 0 1 1 0 1 0

Xây dựng các tổng kiểm tra cấp 1 theo vị trí của ma trận 8x64 cho các c ặp

dấu

(0,0)+(0,1) (0,8)+(0,2) (0,14)+(0,22) (0,15)+(0,7)

(1-7,0)+(1-7,1) (1-7,8)+(1-7,2) (1-7,14)+(1-7,22) (1-7,15)+(1-7,7)

(0,28)+(0,36) (0,31)+(0,55) (0,32)+(0,5) (0,35)+(0,43)

(1-7,28)+(1-7,36) (1-7,31)+(1-7,55) (1-7,32)+(1-7,5) (1-7,35)+(1-7,43)

(0,48)+(0,17) (0,52)+(0,60) (0,54)+(0,33) (0,56)+(0,25)

(1-7,48)+(1-7,17) (1-7,52)+(1-7,60) (1-7,54)+(1-7,33) (1-7,56)+(1-7,25)

(0,12)+(0,34) (0,18)+(0,46) (0,19)+(0,61) (0,20)+(0,26)

(1-7,12)+(1-7,34) (1-7,18)+(1-7,46) (1-7,19)+(1-7,61) (1-7,20)+(1-7,26)

(0,16)+(0,3) (0,21)+(0,29) (0,23)+(0,41) (0,24)+(0,4)

(1-7,16)+(1-7,3) (1-7,21)+(1-7,29) (1-7,23)+(1-7,41) (1-7,24)+(1-7,4)

(0,39)+(0,63) (0,40)+(0,6) (0,42)+(0,9) (0,47)+(0,53)

(1-7,39)+(1-7,63) (1-7,40)+(1-7,6) (1-7,42)+(1-7,9) (1-7,47)+(1-7,53)

(0,59)+(0,49) (0,62)+(0,57) (0,10)+(0,13) (0,11)+(0,30)

(1-7,59)+(1-7,49) (1-7,62)+(1-7,57) (1-7,10)+(1-7,13) (1-7,11)+(1-7,30)

(0,27)+(0,37) (0,38)+(0,44) (0,45)+(0,58) (0,50)+(0,51)

(1-7,27)+(1-7,37) (1-7,38)+(1-7,44) (1-7,45)+(1-7,58) (1-7,50)+(1-7,51)

Qua 64 tổng kiểm tra này, lần lượt sẽ tìm được các cặp dấu thông tin:

A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(0)

0,1+0,2 0,2+0,3 0,3+0,4 0,4+0,5 0,5+0,6 0,6+0,7 0,7+0,8 0,0+0,1

A(2)+A(6)+A(7)+(0,26)

A(4)+A(5)+(0,52)

A(0)+A(1)+(1-7,2)

(0,0)

A(3)+A(6)+A(7)+(0,19)

A(4)+A(5)+(1-7,52)

A(0)+A(2)+(0,9)

A(0)+(0,1)

A(4)+A(6)+A(7)+(0,12)

A(4)+A(7)+(0,20)

A(0)+A(3)+(0,43)

A(1)+(0,8)

A(5)+A(6)+A(7)+(0,5)

A(5)+A(6)+(0,47)

A(0)+A(4)+(0,36)

A(1)+(1-7,8)

A(0)+A(2)+A(3)+(0,17)

A(5)+A(6)+(1-7,47)

A(0)+A(5)+(0,29)

A(2)+(0,42)

A(0)+A(3)+A(4)+(0,49)

A(5)+A(7)+(0,13)

A(0)+A(6)+(0,22)

A(2)+(1-7,42)

A(0)+A(4)+A(5)+(0,60)

A(6)+A(7)+(0,6)

A(0)+A(7)+(0,15)

A(3)+(0,35)

A(0)+A(5)+A(6)+(0,53)

A(6)+A(7)+(1-7,6)

A(1)+A(2)+(0,16)

A(3)+(1-7,35)

A(1)+A(2)+A(7)+(0,55)

A(0)+A(1)+A(2)+(0,3)

A(1)+A(2)+(1-7,16)

A(4)+(0,28)

A(2)+A(3)+A(7)+(0,58)

A(0)+A(1)+A(3)+(0,10)

A(1)+A(7)+(0,41)

A(4)+(1-7,28)

A(3)+A(4)+A(7)+(0,51)

A(0)+A(1)+A(4)+(0,44)

A(2)+A(3)+(0,48)

A(5)+(21)

A(4)+A(5)+A(7)+(0,46)

A(0)+A(1)+A(5)+(0,37)

A(2)+A(3)+(1-7,48)

A(5)+(1-7,21)

A(1)+A(2)+A(3)+(0,24)

A(0)+A(1)+A(6)+(0,30)

A(2)+A(7)+(0,34)

A(6)+(0,14)

A(2)+A(3)+A(4)+(0,56)

A(0)+A(1)+A(7)+(0,23)

A(3)+A(4)+(0,59)

A(6)+(1-7,14)

A(3)+A(4)+A(5)+(0,62)

A(0)+A(6)+A(7)+(0,40)

A(3)+A(4)+(1-7,59)

A(7)+(0,7)

A(4)+A(5)+A(6)+(0,39)

A(1)+A(6)+A(7)+(0,33)

A(3)+A(7)+(0,27)

A(0)+A(1)+(0,2)

Xây dựng 64 tổng kiểm tra cấp 2 cho từng dấu thông tin

Qua các tổng kiểm tra này, ta tạo được khoá giải mã được cho từng cặp dấu

thông tin.

3.4.2. Quá trình mã hoá

Quá trình mã hoá thực hiện các bước sau:

- Nhân ma trận chứa thông tin M[7x7] với ma trận G'[7x64] ta được ma trận

I[8x64] với hàng cuối cùng của I là tổng modulo 2 của các hàng ở trên (các hàng từ

0 1 1 0 1 0 0 1 0 0 0 1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 1 0 1 1 0 1 1 1 0 0 0 0 1 0 1 0 1 1 0 1 0 1 1 1 0 0 0 0 1

0 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 0 1 0 0 1

1 1 0 0 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 1 0 1 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 1 1 0 1 0 1 0

0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 1 0 0 1 1 0 0 1 1

0 1 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 1 0 0 1 1 0

1 0 1 0 1 0 0 1 0 1 0 1 1 1 0 0 1 0 1 1 0 1 1 1 0 1 1 0 0 0 0 0 1 1 0 0 1 1 1 1 1 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 1 1 0 1 0

0 0 1 0 0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 0 1 1 1 0 1 0 0 0 0 1 1 0 0 1 0 1 1 1 1 1 0 1 1 0 0 0 1 1 0 0 0 0

0 1 0 0 0 1 0 0 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 1 1 1 0 1 1 1 0 1

1 đến 7).

Sắp xếp ma tr ận này thành chu ỗi 512 bit thông tin. C ộng modulo 2 chu ỗi

11011000001110010011100000011001000110001001100110011000010110011101100

này với chuỗi thông tin có chứa 31 bít 1 ở trên :

ta được 512 bít đã được mã hoá và ghi vào tệp.

3.4.3. Quá trình giải mã

- Đọc dữ liệu 512 bit thông tin

1 0 1 1 0 0 0 1 0 0 1 0 0 1 1 1 1 1 0 0 1 0 0 0 0 0 1 1 0 1 0 1 1 0 0 1 0 1 1 0 1 1 1 0 0 0 0 1 0 1 0 1 1 0 1 0 1 1 1 0 0 0 0 1

0 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 0 1 0 0 1

1 1 0 0 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 1 0 1 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 1 1 0 1 0 1 0

0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 1 0 0 1 1 0 0 1 1

0 1 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 0 1 0 0 0 1 0 1 0 0 1 1 0

1 0 1 0 1 0 0 1 0 1 0 1 1 1 0 0 1 0 1 1 0 1 1 1 0 1 1 0 0 0 0 0 1 1 0 0 1 1 1 1 1 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 1 1 0 1 0

0 0 1 0 0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 0 1 1 1 0 1 0 0 0 0 1 1 0 0 1 0 1 1 1 1 1 0 1 1 0 0 0 1 1 0 0 0 0

0 1 0 0 0 1 0 0 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 1 1 1 0 1 1 1 0 1

- Sắp xếp thành ma trận 8x64

- Nhân ma trận 8x64 với ma trận P-1

- Sử dụng các tổng kiểm tra để tạo lại ma trận thông tin 7x7.

0 1 1 0 1 0 0

0 1 0 1 1 1 1

1 1 0 0 0 1 0

0 1 1 0 0 1 1

0 1 0 1 1 1 0

1 0 1 0 1 0 0

0 0 1 0 0 1 0

Ø ø Œ œ Œ œ Œ œ Œ œ Œ œ Œ œ Œ œ Œ œ Œ œ º ß

- Nhân ma tr ận này với ma tr ận S-1 thu được ma tr ận thông tin (7x7) ban

đầu

1 0 0 0 1 1 0

0 0 1 0 0 1 1

0 0 1 1 0 0 1

M= 1 0 0 0 0 1 0

1 1 0 0 1 0 1

0 1 1 0 0 0 1

1 0 1 1 0 0 1

Ø ø Œ œ Œ œ Œ œ Œ œ Œ œ Œ œ Œ œ Œ œ Œ œ º ß

- Thực hiện lại quá trình mã hoá nhân ma tr ận M[7x7] với ma trận G' ta thu