BỘ THÔNG TIN VÀ TRUYỀN THÔNG
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
NGUYỄN TRUNG HIẾU
NHÓM NHÂN CYCLIC VÀ MÃ CYCLIC TRÊN VÀNH ĐA THỨC
CHUYÊN NGÀNH: KỸ THUẬT ĐIỆN TỬ
MÃ SỐ: 9520203 (mã cũ 62.52.02.03)
TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT
HÀ NỘI - 2017
Công trình được hoàn thành tại:
Học viện Công nghệ Bưu chính Viễn thông
Người hướng dẫn khoa học:
GS.TS. Nguyễn Bình
TS. Nguyễn Ngọc Minh
Phản biện 1: PGS.TS. Đỗ Quốc Trinh
Phản biện 2: PGS.TS. Nguyễn Hiếu Minh
Phản biện 3: PGS.TS. Đặng Văn Chuyết
Luận án sẽ được bảo vệ trước hội đồng chấm luận văn tại:
Học viện Công nghệ Bưu chính Viễn thông
Vào lúc: ....... giờ ....... ngày ....... tháng ....... năm ……
Có thể tìm hiểu luận án tại:
Thư viện Quốc gia Việt Nam
Thư viện Học viện Công nghệ Bưu chính Viễn thông
i
MỞ ĐẦU
Lý do nghiên cứu
Việc nghiên cứu truyền thống về mã cyclic đã khá hoàn chỉnh, tuy nhiên loại mã này có nhược điểm là số lượng từ mã được tạo ra hạn chế, độ dài của mã chỉ cố định ở một số giá trị cụ thể. Trong những năm trở lại đây một phương pháp khác để xây dựng mã cyclic (gọi là mã cyclic cục bộ) được nghiên cứu dựa trên phân hoạch vành đa thức. Về mặt lý thuyết có thể tồn tại mối quan hệ giữa mã cyclic và cyclic cục bộ, điều đó thôi thúc nghiên cứu sinh nghiên cứu sâu hơn lý thuyết về mã cyclic cục bộ (mã cyclic được xây dựng từ nhóm nhân cyclic, cấp số nhân cyclic), tìm hiểu, chứng minh mối quan hệ có thể tồn tại giữa mã cyclic và mã cyclic cục bộ. Mục đích nghiên cứu
Mục đích chính của luận án là góp phần hoàn thiện lý thuyết và thực nghiệm về nhóm nhân cyclic và mã cyclic trên các vành đa thức, khảo sát và chứng minh mối quan hệ giữa mã cyclic cục bộ và mã cyclic truyền thống. Trên cơ sở kết quả nghiên cứu lý thuyết đạt được sẽ đề xuất một số ứng dụng có thể về mã sửa lỗi và mật mã trong các hệ thống truyền thông. Đối tượng và phạm vi nghiên cứu
Đối tượng nghiên cứu của luận án là các đa thức, nhóm nhân cyclic, cấp số nhân cyclic và mã cyclic trên vành đa thức.
Phạm vi nghiên cứu của luận án này được giới hạn trong việc nghiên cứu mối quan hệ giữa nhóm nhân cyclic, cấp số nhân cyclic với mã cyclic truyền thống, cấp của đa thức và phương pháp xây dựng nhóm nhân cyclic có cấp cực đại trên vành đa thức, trên cơ sở đó có thể đề xuất một số mã cyclic tốt và phương pháp hiện thực hóa các mã cyclic trên FPGA. Phương pháp và công cụ nghiên cứu
Phương pháp nghiên cứu của đề tài là phân tích và tổng hợp dựa vào các công cụ toán học, đặc biệt là đại số, lý thuyết mã hóa, lý thuyết xác suất,...
Luận án sử dụng các công cụ toán học, kết hợp với việc tính toán, mô phỏng trên máy tính và các chương trình phần mềm xử lý (C++, Matlab, VHDL, Excel).
ii
Ý nghĩa khoa học và thực tiễn của đề tài
Những kết quả trong luận án này góp phần phát triển hoàn thiện lý thuyết mã cyclic, mã cyclic cục bộ nói riêng và lý thuyết mã sửa lỗi nói chung. Các đóng góp chính của Luận án:
- Kiến thiết các nhóm nhân cyclic có cấp cực đại trên vành đa thức thông qua việc đề xuất phương pháp xác định đa thức có cấp cực đại.
- Chứng minh sự tương đương giữa nhóm nhân cyclic, cấp số nhân cyclic với mã cyclic truyền thống.
- Đề xuất một số bộ mã cyclic tốt xây dựng trên vành đa thức.
Cấu trúc của Luận án
Nội dung luận án bao gồm phần mở đầu, kết luận và ba chương nội dung. Trong đó, Chương 1 trình bày tổng quan vấn đề nghiên cứu, lý thuyết cơ bản về vành đa thức, mã cyclic làm cơ sở cho các nội dung nghiên cứu của luận án. Trong Chương 2, luận án tập trung trình bày các kết quả nghiên cứu mới và hai đóng góp quan trọng của Luận án là đề xuất phương pháp kiến thiết các nhóm nhân cyclic có cấp cực đại thông qua việc xác định cấp của đa thức với nhiều hướng tiếp cận; chứng minh mối quan hệ tương đương giữa mã cyclic truyền thống với mã cyclic xây dựng trên nhóm nhân, cấp số nhân trên vành đa thức [J2], [J3], [J4], [J5], [C3], [C4], [C5]. Ở Chương 3, Luận án trình bày phương pháp tìm mã cyclic tốt và danh sách một số mã cyclic tốt được đề xuất, cũng như mô phỏng đánh giá bộ mã, đề xuất phương pháp xây dựng bộ mã trên cấu kiện phần cứng FPGA, ở cuối chương luận án trình bày ứng dụng của nhóm nhân cyclic, cấp số nhân cyclic trong việc làm khóa một số hệ mật [J1], [J6], [C1], [C2].
1
CHƯƠNG 1
TỔNG QUAN CÁC VẤN ĐỀ CẦN NGHIÊN CỨU
Tóm tắt: Nội dung của chương trình bày lý thuyết tổng quan về vành đa thức, nhóm nhân cyclic, cấp số nhân cyclic và mã cyclic. Các tiêu chuẩn đánh giá mã sửa lỗi cũng được giới thiệu trong chương này. Chương này cũng sẽ tập trung khảo sát các nghiên cứu liên quan đến mã cyclic để từ đó tìm ra các hạn chế của các nghiên cứu trước đây và đề xuất hướng nghiên cứu, phạm vi nghiên cứu và phương thức tiếp cận của luận án. 1.1. GIỚI THIỆU CHUNG
Phần này trình bày tổng quan về lịch sử phát triển của lý thuyết mã hoá, mã sửa lỗi, mã tuyến tính, mã cyclic và đề cập đến mã cyclic xây dựng trên vành đa thức. 1.2. VÀNH ĐA THỨC
Phần này đề cập đến các khái niệm cơ bản về vành đa thức, phép tính trên vành đa thức, đa thức bất khả quy, đa thức đối xứng, vành đa thức có hai lớp kề cyclic. Tiếp đến là các nội dung liên quan đến chu trình, lũy đẳng, đặc biệt bổ đề 1.2 đề cập đến tính chất và hệ quả về lũy đẳng nuốt được sử dụng cho các chứng minh kết quả chính của luận án. 1.3. MÃ TUYẾN TÍNH
Phần này đưa ra khái niệm về mã tuyến tính, tiếp theo trình bày về mã cyclic, một số mã có tính chất tương tự có thể xây dựng trên vành đa thức, và một số tiêu chuẩn đánh giá mã tuyến tính phổ biến.
1.3.1. Mã cyclic truyền thống 1.3.2. Một số mã tuyến tính khác 1.3.3. Một số tiêu chuẩn đánh giá mã tuyến tính
1.4. PHÂN HOẠCH VÀNH ĐA THỨC VÀ MÃ CYCLIC CỤC BỘ
Phần này trình bày về lý thuyết về nhóm nhân cyclic, nhóm nhân cyclic đối xứng, cấp của đa thức và phân bố đa thức theo cấp trong nhóm nhân cyclic. Tiếp đến là các nội dung liên quan đến cấp số nhân cyclic, phân hoạch vành đa thức và mã cyclic cục bộ.
1.4.1. Nhóm nhân cyclic
Nhóm nhân cyclic trong vành đa thức là tập hợp các phần tử bằng lũy thừa của một phần tử gọi là phần tử sinh. Trong vành đa thức có
2
nhiều nhóm nhân mỗi nhóm nhân có thể gồm nhiều nhóm nhân cyclic, số nhóm nhân bằng số các lũy đẳng có thể có trong vành.
(1.16)
Bổ đề 1.3: Xét là một phần tử sinh của nhóm nhân cyclic A,
là phần tử sinh của nhóm nhân cyclic ( được gọi là đối
xứng của nhóm nhân A). Ta có:
(1.19)
Cấp của đa thức (ký hiệu ) là số
nguyên dương 𝑚 nhỏ nhất thỏa mãn:
hoặc (1.21)
Định lý 1.2: Xét vành đa thức với
trong đó là các đa thức bất khả quy, cấp cực đại của một đa thức
nào đó được xác định như sau:
. - Nếu 𝑛 lẻ thì
thì . - Nếu 𝑛 chẵn, có dạng
Trong đó .
Bổ đề 1.4 trình bày về phân bố đa thức theo cấp trong nhóm nhân cyclic, trong khi bổ đề 1.5 nói về số đa thức đạt cấp cực đại trên vành.
1.4.2. Cấp số nhân cyclic
Cấp số nhân cyclic (CGP - Cyclic Geometic Progressions) trên vành đa thức là một tập hợp con có dạng sau:
(1.23)
1.4.3. Phân hoạch vành đa thức
Quá trình phân hoạch vành đa thức thực chất là quá trình phân chia các phần tử trong vành đa thức thành các tập (hay các lớp kề) không
3
trùng nhau. Các phần tử sinh của nhóm nhân sinh được gọi là các hạt nhân của phân hoạch. Trong mỗi phân hoạch vành đa thức, các lớp kề của nó là các cấp số nhân cyclic với cùng một công bội. Dựa vào các lớp kề này ta có thể tạo được mã LCC và các mã cyclic khác nhau. Trong vành đa thức, số phân hoạch là khá lớn nên có thể xây dựng được nhiều mã cyclic có đặc tính sửa lỗi tốt.
Các kiểu phân hoạch vành đa thức phổ biến: a) Phân hoạch chuẩn b) Phân hoạch cực đại c) Phân hoạch cực tiểu d) Phân hoạch vành thành các cấp số nhân có cùng trọng số e) Phân hoạch vành thành các phần tử có cùng tính chẵn lẻ của trọng số
f) Phân hoạch vành thành các cấp số nhân theo modulo h(x)
1.4.4. Mã cyclic cục bộ trên vành đa thức
Mã cyclic cục bộ là một mã tuyến tính có các dấu mã là một tập con không trống tuỳ ý các lớp kề trong phân hoạch của vành đa thức theo một nhóm nhân cyclic .
Nhận xét: - Nếu chỉ chọn 1 lớp kề, khi đó mã LCC trở thành mã cyclic. - Nếu các lớp kề được chọn có chứa nhóm nhân cyclic đơn vị
thì ta có mã LCC hệ thống.
Tập các trưởng lớp kề tạo mã sẽ mô tả đầy đủ mã LCC. Có hai cách biểu diễn mã cyclic cục bộ phổ biến là: a) Biểu diễn theo trưởng lớp kề; b) Biểu diễn theo ma trận sinh.
Hai lớp mã LCC phổ biến là: a) Mã cyclic cục bộ tự trực giao
(OLCC); b) Mã LCC có khả năng trực giao (OALCC). 1.5. HƯỚNG NGHIÊN CỨU CỦA LUẬN ÁN VÀ MỘT SỐ KẾT QUẢ LIÊN QUAN
Trên thế giới, việc nghiên cứu cấu trúc đại số cho các cấu trúc mã hiện nay vẫn đang được nghiên cứu và hoàn thiện như mã LDPC, mã Turbo nhằm mục đích tối ưu hóa các mã kênh, mã truyền tin trong các mạng thông tin di động thế hệ mới. Đối với mã cyclic, một số hướng
4
nghiên cứu trên thế giới hiện nay đã khá hoàn thiện và hiện đang xem xét một số giới hạn của mã cyclic, đánh giá trọng số của mã cyclic, đề xuất phương án giải mã tối ưu cho mã cyclic. Một số nghiên cứu đề cập đến mã tuyến tính và đặc tính của các đa thức sinh dựa trên cấu trúc trellis, đề xuất xây dựng mã khác dựa trên mã cyclic. Hiện nay các công trình nghiên cứu đề cập đến mã cyclic đều đang tìm thêm các ứng dụng dựa trên tính chất dịch vòng của mã cyclic ví dụ tính các chuỗi nhảy tần tối ưu trong thông tin di động, xây dựng cấu trúc đại số mới để hình thành mã quasi cyclic, hay quasi cyclic LDPC, hiện thực hóa các mã cyclic trên các cấu kiện phần cứng. Tuy nhiên, việc nghiên cứu các mã cyclic còn chưa chặt chẽ và mang tính tổng thể đối với vành đa thức.
Ở Việt Nam, vào năm 1987 đã bắt đầu một hướng nghiên cứu mới về mã sửa lỗi đó là mã cyclic cục bộ (LCC) được thực hiện trênh vành số. Tuy nhiên chỉ tới khi được xây dựng trên các vành đa thức vào năm 1996 các nghiên cứu về mã LCC mới được thúc đẩy mạnh mẽ và thu được nhiều kết quả khích lệ về: phân hoạch vành đa thức, mã LCC tự trực giao, mã LCC có khả năng trực giao, mã LCC đối xứng và tự đối xứng, các mã cyclic trên vành đa thức có 2 lớp kề cyclic,... Các công trình này đều có ý nghĩa về mặt lý thuyết, đạt được những thành tựu và kết quả nhất định. Tuy nhiên, lý thuyết và thực nghiệm về mã cyclic cục bộ và mã cyclic trên vành đa thức vẫn chưa hoàn thiện và có một số hướng nghiên cứu mở.
Nghiên cứu sinh xác định luận án nghiên cứu việc kiến thiết nhóm nhân cyclic có cấp cực đại, mối quan hệ của mã cyclic cục bộ (mã cyclic xây dựng từ nhóm nhân cyclic, cấp số nhân cyclic trên vành đa thức) với mã cyclic truyền thông, phương pháp lựa chọn mã cyclic tốt, ứng dụng của nhóm nhân cyclic, cấp số nhân cyclic trong mã sửa lỗi, mật mã, và khả năng thực hiện các bộ mã cyclic trên cấu kiện phần cứng. 1.6. KẾT LUẬN CHƯƠNG
Trong chương này, Luận án đã trình bày cơ sở lý thuyết cho các nội dung nghiên cứu của luận án bao gồm các nội dung về vành đa thức, vành đa thức có hai lớp kề cyclic, tính chất đa thức, chu trình, luỹ đẳng, mã tuyến tính, mã cyclic truyền thống, một số tiêu chuẩn đánh giá mã tuyến tính, nhóm nhân cyclic, cấp số nhân cyclic, phân hoạch vành đa thức và mã cyclic cục bộ. Ở cuối chương trình bày hướng nghiên của của luận án và thảo luận một số kết quả nghiên cứu liên quan từ đó làm rõ hơn nội dung nghiên cứu của luận án.
5
CHƯƠNG 2
CẤP CỦA ĐA THỨC VÀ QUAN HỆ GIỮA NHÓM NHÂN CYCLIC, CẤP SỐ NHÂN CYCLIC VỚI MÃ CYCLIC TRUYỀN THỐNG
Tóm tắt: Trong chương này, Luận án trình bày các kết quả nghiên cứu về phương pháp kiến thiết nhóm nhân cyclic có cấp cực đại, mối quan hệ giữa nhóm nhân cyclic, cấp số nhân cyclic với mã cyclic truyền thống góp phần bổ sung và hoàn thiện lý thuyết về mã cyclic. Nội dung chương 2 được bố cục gồm ba phần và kết luận chương. Phần đầu tiên giới thiệu chung về nội dung của chương và các vấn đề liên quan. Nội dung tiếp theo trình bày một số kết quả nghiên cứu mới của tác giả về cấp của đa thức. Phần cuối cùng trình bày kết quả nghiên cứu mới về mối quan hệ giữa nhóm nhân cyclic, cấp số nhân cyclic với mã cyclic truyền thống qua đó chứng minh được sự tương đương giữa nhóm nhân và cấp số nhân cyclic với mã cyclic truyền thống. 2.1. GIỚI THIỆU
Đến thời điểm hiện tại, chưa có công trình nào tập trung nghiên cứu và có kết quả đầy đủ về cấp của đa thức, về kiến thiết nhóm nhân cyclic có cấp cực đại trên vành đa thức. Đặc biệt cũng chưa có tiêu chuẩn toán học nào cho việc tìm kiếm đa thức có cấp cực đại trên vành. Chính điều này gợi mở cho nghiên cứu sinh hướng nghiên cứu về xác định cấp của đa thức, từ đó kiến thiết nhóm nhân cyclic có cấp cực đại trên vành đa thức. Các kết quả nghiên cứu sẽ được trình bày chi tiết trong mục 2.2.
Cũng trên cơ sở nghiên cứu về mã cyclic cục bộ (xây dựng từ nhóm nhân cyclic, cấp số nhân cyclic trên vành đa thức), nghiên cứu sinh thấy rằng có thể tồn tại mối quan hệ giữa mã cyclic cục bộ (hay nhóm nhân cyclic, cấp số nhân cyclic) với mã cyclic truyền thống và việc chứng minh bằng toán học, khảo sát đánh giá mối quan hệ này hiện nay vẫn là một vấn đề mở cần được nghiên cứu. Việc chứng minh được mối quan hệ này sẽ góp phần làm sáng tỏ mối liên hệ và tạo ra cầu nối giữa các cách xây dựng mã cyclic khác nhau. Một kết quả nghiên cứu về vấn đề này được trình bày trong mục 2.3.
Khi giải quyết được hai nội dung lý thuyết quan trọng như đề cập sẽ góp thêm sở cứ cho việc đề xuất một sơ đồ phân loại mã tuyến tính dựa trên cấu trúc đại số và mã cyclic cục bộ.
6
2.2. XÁC ĐỊNH CẤP CỦA ĐA THỨC
Việc xác định được cấp của đa thức, đặc biệt cấp cực đại của đa thức có ý nghĩa quan trọng trong lý thuyết mã hóa. Nếu đa thức là phần tử sinh của nhóm nhân cyclic thì cấp đa thức chính là cấp của nhóm nhân, khi đa thức được sử dụng làm khóa trong các hệ mật thì ở góc độ nào đó cấp đa thức giúp xác định một phần độ phức tạp của hệ mật. Ngoài ra, xác định được cấp đa thức giúp chỉ ra bộ mã cyclic tối ưu, hoặc hạ bậc của đa thức để tạo ra bộ mã cyclic tối ưu xây dựng trên vành nhỏ hơn (chi tiết tại chương 3). Như vậy, trong nội dung nghiên cứu này luận án sẽ đề xuất một số phương pháp và thuật toán xác định cấp của đa thức trên vành, đồng thời cũng đề xuất đánh giá về xác suất chọn đa thức có cấp cực đại trên vành đa thức có hai lớp kề cyclic. 2.2.1. Đề xuất phương pháp xác định cấp của tích các đa thức
Hiện tại vẫn chưa có phương pháp chung để xác định cấp của đa thức trên vành, do đó trong nội dung này luận án tập trung trình bày một hướng nghiên cứu xác định cấp của đa thức thông qua việc tìm cấp của đa thức là tích của các đa thức thông qua việc đề xuất và chứng minh đầy đủ hai bổ đề liên quan.
Bổ đề 2.1: Xét đa thức ; trong đó là các đa
thỏa mãn [J5]: thức có cấp tương ứng là 𝑚𝑖. Khi đó, cấp của
(2.1)
Bổ đề 2.2: Xét . Cấp của đa thức
xác định như sau [J5]:
và
1) Trường hợp 1: Xét hai đa thức ), (hoặc cấp 𝑚 thì
(2.2)
2) Trường hợp 2: Nếu và
và không đối xứng nhau, cấp tương ứng của , là , với ,
(2.3)
7
Đặc biệt nếu , thì
Hệ quả: - Cấp của đa thức là tích hai đa thức bất kỳ thuộc cùng CMG hoặc hai CMG đối xứng không lớn hơn cấp cực đại của CMG đó.
- Có thể tìm đa thức cấp cực đại bằng việc lấy tích của các đa thức có cấp là nguyên tố cùng nhau.
2.2.2. Đề xuất phương pháp xác định cấp của nhị thức
Nhị thức là một đa thức có biểu diễn khá đơn giản và có khả năng đạt cực đại trên vành đa thức. Việc nghiên cứu cấp của nhị thức có thể tìm ra nhị thức đạt cấp cực đại hoặc làm cơ sở tìm đa thức có cấp phù hợp để nhân với nhị thức tạo thành đa thức có cấp cực đại. Trong phần này, luận án trình bày kết quả nghiên cứu về cấp của nhị thức thông qua đề xuất và chứng minh hoàn chỉnh một định lý, một bổ đề, đồng thời đề xuất một thuật toán xác định cấp nhị thức.
Định lý 2.1: Cấp của nhị thức trên được xác
định [J3]: (2.5)
Bổ đề 2.3: Trên vành đa thức [J5].
+ Các nhị thức với là các nhị thức có cấp lớn nhất.
+ Nhị thức (1 + 𝑥) có cấp cực đại trong số tất cả các nhị thức. Thuật toán xác định cấp của nhị thức (𝟏 + 𝒙) [J3]
) VÀO: Giá trị n RA: Cấp của nhị thức (1 + 𝑥) trên vành đa thức ( 1. Chuyển nhị thức về mảng có kích thước bằng giá trị
𝑛 của vành. 2. Đặt và
3. Lấy
4. So sánh với :
4.1. Nếu thì và lặp lại bước 2
4.2. Nếu , dừng chương trình và in kết quả
8
Thực hiện thuật toán xác định cấp của nhị thức (1 + 𝑥), thu được kết quả khảo sát trên một số vành đa thức [J3].
Từ kết quả chạy thuật toán, ta có thể nhận thấy rằng nhị thức (1 + 𝑥) có khả năng đạt cấp cực đại trên khá nhiều vành, do đó có thể lựa chọn làm phần tử sinh để tạo ra nhóm nhân đạt cấp cực đại trên những vành mà nhị thức này đạt cấp cực đại. Ngoài ra, ta có một phương pháp để tìm đa thức 𝑎(𝑥) có cấp cực đại từ nhị thức (1 + 𝑥), bằng cách chọn
(với điều kiện ).
Kết quả nghiên cứu này góp phần khẳng định rằng việc xác định đa thức đạt cấp cực đại trở nên khá dễ dàng, do đó bài toán quan trọng trong việc xây dựng các CMG có cấp cực đại đã có một hướng giải quyết mới và hiệu quả. Kết quả này được công bố trong [J3], [J5].
2.2.3. Đề xuất thuật toán cải tiến để tìm và liệt kê cấp của đa thức trên vành
Hai phương pháp được trình bày ở trên đã góp phần hoàn thiện lý thuyết và mở ra hướng tiếp cận mới. Trong phần này nghiên cứu sinh tiếp tục trình bày một phương pháp thực nghiệm đó là đề xuất thuật toán tìm và liệt kê cấp của đa thức trên vành.
Thuật toán sử dụng phương pháp vét cạn để xác định cấp của tất cả các phần tử trên mỗi vành đa thức nên độ phức tạp thuật toán là khá cao, đặc biệt là đòi hỏi thời gian tính toán lớn và kém hiệu quả đối với các vành lớn. Trên cơ sở các tính chất của nhóm nhân cyclic, đa thức và cấp của đa thức đã trình bày trong chương 1, kết hợp một số bổ đề liên quan để xây dựng một thuật toán cải tiến giúp giảm độ phức tạp thuật toán, giảm thời gian tính toán trong việc tìm cấp của các đa thức. a) Ý tưởng chủ đạo của thuật toán là sử dụng các kết quả nghiên cứu về cấp đa thức và CMG đối xứng, cụ thể:
(1) Tìm cấp cực đại của đa thức trên vành bằng việc kiểm tra chiều dài cực đại của các lớp kề cyclic (hay chính là các chu trình). Độ phức tạp O(n).
(2) Áp dụng bổ đề 1.4. Tìm các CMG, các đa thức ở vị trí thứ 𝑘
với cấp , trong đó 𝑚 là cấp của đa thức sinh của CMG.
(3) Áp dụng bổ đề 1.3 để tìm các CMG đối xứng.
9
b) Độ phức tạp thuật toán: , N là số nhóm
nhân cyclic đạt cấp cực đại độc lập (theo bổ đề 1.5 [C5]).
c) Thuật toán cải tiến do nghiên cứu sinh đề xuất [C5]
INPUT: integer n. OUTPUT: order of all polynomials. 1. Set all
2. For k from 1 to ( ) do 2.1. If then continue
2.2. Convert k to polynomial
2.3. Set 2.4. Set 2.5. While (1) do 2.5.1. Set
to an integer M
2.5.2. Convert inversely 2.5.3.
then break the loop
2.5.3. If End while 2.6. For i from 1 to count 2.6.1.
2.6.2. 2.6.3. , and
and
2.6.4. End for End for
Sử dụng cùng cấu hình máy tính để chạy hai thuật toán, kết quả cho thấy thuật toán cải tiến do nghiên cứu sinh đề xuất đã rút ngắn thời gian tính toán một cách đáng kể so với thuật toán vét cạn, đặc biệt khi vành lớn hơn, thuật toán cải tiến có thời gian tính toán ngắn hơn đến hàng nghìn lần và thực hiện được với những vành lớn mà thuật toán vét cạn không thể thực hiện trong cùng một cấu hình máy tính [C5].
10
2.2.4. Xác suất lựa chọn đa thức có cấp cực đại
Nhóm nhân cyclic có cấp cực đại trong các vành đa thức có hai lớp kề cyclic là cơ sở để xây dựng các mã cylic cục bộ có ứng dụng hiệu quả trong viễn thông và trong lĩnh vực bảo mật. Có thể đánh giá khả năng tìm phần tử sinh đạt cấp cực đại trên vành đa thức có hai lớp kề cyclic thông qua tính xác suất chọn theo công thức sau:
Số phần tử đạt cấp cực đại (2.7) Số phần tử được lựa chọn
với 𝑛 là số phần tử trong nhóm nhân cyclic đơn vị; số phần tử (trừ đơn thức và lũy đẳng nuốt); là tổng là hàm Phi-Euler.
Bảng 2.3 chỉ ra kết quả khảo sát xác suất tìm cấp cực đại của phần .
tử trên vành đa thức có hai lớp kề cyclic của 35 giá trị đầu tiên của Bảng 2.3: Kết quả khảo sát 35 giá trị
TT 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 n 5 11 13 19 29 37 53 59 61 67 83 101 107 131 139 163 173 173 TT 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 n 179 181 197 211 227 269 293 317 347 349 389 419 421 443 461 467 491 p(n) ~0,5 ~0,586 ~0,42 ~0,534 ~0,494 ~0,378 ~0,529 ~0,65 ~0,35 ~0,53 ~0,658 ~0,45 ~0,66 ~0,575 ~0,559 ~0,530 ~0,529 ~0,529 p(n) ~0,663 ~0,315 ~0,492 ~0,377 ~0,664 ~0,531 ~0,530 ~0,532 ~0,665 ~0,445 ~0,531 ~0,629 ~0,318 ~0,665 ~0,444 ~0,665 ~0,557
11
Từ bảng này, có thể nhận thấy xác suất thấp nhất là 0,31 và phần lớn xác suất là trên 0,5. Trong khi chưa có được tiêu chuẩn lựa chọn phần tử sinh có cấp cực đại thì việc đánh giá xác suất lựa chọn phần tử sinh như kết quả ở trên khẳng định rằng khả năng lựa chọn phần tử nguyên thủy (không phải đơn thức) đạt cấp cực đại thông thường đạt trên 50%. Kết quả nghiên cứu này được công bố trong [J2]. 2.3. QUAN HỆ GIỮA NHÓM NHÂN CYCLIC, CẤP SỐ NHÂN CYCLIC VỚI MÃ CYCLIC TRUYỀN THỐNG
Một số nghiên cứu trước đây đã dự đoán hoặc cho ví dụ trong một số trường hợp riêng về một quan hệ giữa nhóm nhân cyclic, cấp số nhân cyclic với mã cyclic truyền thống, tuy nhiên cho đến hiện tại vẫn chưa có công trình nghiên cứu nào đưa ra chứng minh toán học chặt chẽ cho trường hợp tổng quát về mối quan hệ này. Trong nội dung này của luận án, nghiên cứu sinh sẽ đề xuất một cách chứng minh toán học chặt chẽ cho mối quan hệ này trong trường hợp tổng quát và kết quả thực nghiệm trên công cụ mô phỏng mối quan hệ giữa nhóm nhân cyclic, cấp số nhân cyclic trên vành đa thức với mã cyclic truyền thống.
2.3.1. Cơ sở toán học
2.3.1.1. Quan hệ giữa phép nhân và ánh xạ tuyến tính trên .
2.3.1.2. Một tính chất của tích vô hướng
2.3.2. Sự tương đương của nhóm nhân cyclic, cấp số nhân cyclic với mã cyclic truyền thống
Bổ đề 2.4: Mã cyclic cục bộ xây dựng từ một cấp số nhân cyclic cũng là một mã cyclic truyền thống. Mã cyclic này được xây dựng trên vành đa thức có bậc là cấp của cấp số nhân cyclic trong phân hoạch của vành đa thức xây dựng cấp số nhân cyclic [J4].
Việc chứng mình hoàn chỉnh bổ đề 2.4 đưa đến khẳng định rằng mã cyclic cục bộ xây dựng từ cấp số nhân cyclic là một mã cyclic, từ đây có thể mở ra một phương án mới để xây dựng các lớp mã cyclic. Với phương án tiếp cận này, việc xây dựng các mã cyclic (nhất là với các mã cyclic ở trên các vành lớn) trở nên đơn giản hơn, ta chỉ cần khảo sát các cấp số nhân cyclic trên các vành nhỏ cũng có thể xây dựng được các mã cyclic ở trên các vành lớn, trong khi đối với các vành lớn (số mũ 𝑛 lớn), việc phân tích giá trị (𝑥𝑛 + 1) ra thành các đa thức bất khả quy cũng là một trở ngại cho việc xây dựng mã cyclic.
12
2.3.3. Thuật toán xác định nhóm nhân cyclic tương đương mã cyclic truyền thống
Từ kết quả bổ đề 2.4, khi
thì cấp số nhân cyclic tương đương nhóm nhân cyclic, do đó có thể nhận định rằng mã LCC xây dựng trên nhóm nhân cyclic cũng tương đương với mã cyclic truyền thống. Phần này sẽ trình bày kết quả khảo sát và đánh giá về sự tương đương giữa mã LCC xây dựng trên nhóm nhân cyclic và mã cyclic truyền thống. Thuật toán xác định mã cyclic truyền thống tương đương [C3]
VÀO:
truyền thống tương đương với CMG RA: Mã cyclic
Bước 1:
.
- Xây dựng - Đặt
. - Lập ma trận mã LCC từ các phần tử của CMG - Sử dụng thuật toán Gauss-Jordan để chuyển ma trận lập được ở trên về dạng ma trận hệ thống.
- Loại bỏ các hàng bằng 0 (nếu có) của ma trận mã, được ma trận sinh .
Bước 2:
- Chuyển đổi ma trận sinh về dạng các phần tử trong
nhóm - Đặt
- Tính
- Từ đa thức sinh , được ma trận mã tương đương với mã
cyclic truyền thống.
Nghiên cứu sinh đã xây dựng chương trình phần mềm và chạy thuật toán xác định các mã tương đương được trình bày trong [C3] và phụ lục của luận án.
13
2.4. MỘT CÁCH PHÂN LOẠI MÃ TUYẾN TÍNH MỚI
Từ quan điểm xây dựng mã cyclic và LCC, có thể thực hiện mô tả mã cyclic theo quan điểm xây dựng mã LCC dựa trên phân hoạch vành đa thức. Nghiên cứu các mã LCC trong mối quan hệ với mã cyclic nói riêng và trong hệ thống mã tuyến tính xây dựng trên các cấu trúc đại số nói chung, với các dạng phân hoạch khác nhau có thể cho ra các loại mã sửa lỗi khác nhau, hệ thống phân loại các mã tuyến tính xây dựng trên các cấu trúc đại số được trình bày trong hình 2.3 [C4].
Hình 2.3. Sơ đồ phân loại mã tuyến tính dựa trên cấu trúc đại số và mã LCC [C4]
2.5. KẾT LUẬN CHƯƠNG
Chương 2 đã trình bày kết quả nghiên cứu mới góp phần hoàn thiện lý thuyết về mã cyclic. Các kết quả đã được công bố trong các công trình [J2], [J3], [J4], [J5], [C3], [C5] tập trung vào hai nội dung chính:
14
1) Kiến thiết các nhóm nhân cyclic trên vành đa thức thông qua việc đề xuất phương pháp xác định cấp của đa thức và đa thức đạt cấp cực đại, đồng thời chứng minh hoàn chỉnh một số bổ đề quan trọng, cụ thể: (a) Đề xuất phương pháp xác định cấp của đa thức là tích các đa thức trên vành đa thức với đóng góp quan trọng nhất là đề xuất và chứng minh hoàn chỉnh bổ đề 2.2 [J5]; (b) Đề xuất phương pháp xác định cấp của nhị thức trên vành đa thức với đóng góp là đề xuất và chứng minh hoàn chỉnh bổ đề 2.3 [J3], [J5]; (c) Đề xuất thuật toán cải tiến để tìm và liệt kê cấp của đa thức trên vành đa thức [C5]; (d) Đánh giá xác suất tìm phần tử có cấp cực đại trên vành đa thức có hai lớp kề cyclic [J2]. 2) Chứng minh sự tương đương giữa các nhóm nhân cyclic, cấp số nhân cyclic với mã cyclic truyền thống, với việc trình bày một chứng minh về lý thuyết (bổ đề 2.4), xây dựng thuật toán (thuật toán 2.4), sau đó tiến hành khảo sát, đánh giá và xây dựng được một phụ lục minh chứng cho tính tương đương này [J4], [C3].
Ở cuối chương, Luận án đã trình bày và thảo luận một sơ đồ phân loại các mã tuyến tính dựa trên cấu trúc đại số và mã cyclic cục bộ, góp phần khẳng định mối quan hệ giữa mã cyclic với mã cyclic cục bộ và vai trò của mã LCC trong hệ thống mã tuyến tính, mã sửa lỗi [C4].
CHƯƠNG 3
ỨNG DỤNG NHÓM NHÂN CYCLIC, CẤP SỐ NHÂN CYCLIC
Tóm tắt: Các kết quả đạt được trong chương 2 là cơ sở để tiếp tục nghiên cứu ứng dụng của nhóm nhân cyclic, cấp số nhân cyclic trong mã sửa lỗi và mật mã. Một đặc điểm nổi bật của các bộ mã cyclic xây dựng từ nhóm nhân cyclic, cấp số nhân cyclic là có độ dài thay đổi được có khả năng ứng dụng trong LTE, mã mạng. Trong số các nhóm nhân trên một vành đa thức thì nhóm nhân có cấp cực đại có độ ngẫu nhiên của các phần tử cao nhất do đó có thể sử dụng các phần tử có cấp cao nhất trong nhóm nhân cấp cực đại trên vành đa thức làm khóa cho một số hệ mật. Trong chương này, luận án sẽ trình bày phương pháp xây dựng mã cyclic, tiếp đến đề xuất một số mã cyclic tốt xây dựng từ nhóm nhân cyclic, cấp số nhân cyclic gồm phương pháp tìm mã cyclic tốt, danh sách một số mã cyclic tốt được đề xuất, mô phỏng đánh giá bộ mã, đồng thời đề xuất phương pháp xây dựng bộ mã trên cấu kiện phần
15
cứng FPGA. Nội dung cuối, luận án trình bày ứng dụng của nhóm nhân cyclic, cấp số nhân cyclic làm khóa cho một số hệ mật. 3.1. PHƯƠNG PHÁP XÂY DỰNG MÃ CYCLIC 3.1.1. Phương pháp xây dựng mạch mã hóa
Trên cơ sở đã xác định được các nhóm nhân sinh, sẽ tạo được cấp số nhân cyclic tương đương với lớp kề mới, phần tử sinh của lớp kề (trưởng lớp kề) tương ứng số hạng đầu của cấp số nhân cyclic. Nếu gắn dấu thông tin cho nhóm nhân sinh, ta sẽ tạo được mã LCC tương ứng với nhóm nhân đó. Có hai cách chọn nhóm nhân sinh:
+ Cách thứ nhất: Chọn nhóm nhân đơn vị I, các dấu thông tin được gắn vào nhóm nhân đơn vị I để tạo mã.
+ Cách thứ hai: Chọn nhóm nhân sinh là nhóm nhân cyclic bất kỳ. nhân với nhóm nhân sinh đó sẽ tạo ra được
Chọn phần tử đầu tiên cấp số nhân cyclic tương ứng với một lớp kề tạo mã. 3.1.2. Phương pháp xây dựng mạch giải hóa
Có nhiều phương pháp giải mã cho mã cyclic và LCC, trong số đó giải mã ngưỡng là một phương pháp khá hiệu quả và có sơ đồ giải mã đơn giản. Các phương pháp giải mã ngưỡng bao gồm: Giải mã ngưỡng theo đa số (MTD) các tổng kiểm tra; Giải mã ngưỡng theo đa số 1 biểu quyết (MTD + 1); giải mã ngưỡng theo đa số 2 biểu quyết (MTD + 2). Các phương pháp giải mã ngưỡng đều sử dụng các OCS, hoặc các
OACS, hoặc CS liên hệ. 3.2. ĐỀ XUẤT MỘT SỐ MÃ CYCLIC TỐT TRÊN VÀNH ĐA THỨC
3.2.1. Phương pháp tìm mã cyclic tốt
𝑘−1 𝑖=0
Phần này trình bày phương pháp tìm mã cyclic (n,k,d) tốt phù hợp theo các tiêu chí đánh giá đề cập trong chương 1. Các kết quả nghiên cứu liên quan đến mã cyclic xây dựng từ nhóm nhân, cấp số nhân cyclic.
3.2.1.1. Mã cyclic tối ưu xây dựng từ nhóm nhân, cấp số nhân cyclic Định lý 3.1: Mã cyclic (2𝑘 − 2, 𝑘) trên vành đa thức 𝑍2[𝑥]/(𝑥𝑘 + 𝑥𝑖 1) sử dụng tất cả đa thức khác không (trừ đa thức 𝑒0(𝑥) = ∑ ) làm dấu mã là mã tối ưu đạt giới hạn Griesmer và thỏa mãn giới hạn Plotkin, có khoảng cách mã 𝑑0 = 2𝑘−1 − 1 [J6].
Định lý 3.2: Mã cyclic (2𝑘−1 − 1, 𝑘) trên vành đa thức 𝑍2[𝑥]/(𝑥𝑘 + 1) với 𝑘 lẻ và sử dụng tất cả đa thức trọng số lẻ (trừ đa
16
𝑘−1 𝑖=0
) làm dấu mã là mã tối ưu đạt giới hạn Griesmer 𝑥𝑖
thức 𝑒0(𝑥) = ∑ và thỏa mãn giới hạn Plotkin, có khoảng cách 𝑑0 = 2𝑘−2 − 1 [J6].
Đối với mã cyclic xây dựng từ các nhóm nhân cyclic thì có thể xây dựng các bộ mã này như sau:
+ Nếu cấp cực đại của các đa thức thuộc vành 𝑍2/(𝑥𝑘 + 1) bằng 2𝑘−1 − 1 thì chọn đa thức có cấp cực đại làm phần tử sinh của bộ mã. + Nếu cấp cực đại của các đa thức thuộc vành 𝑍2/(𝑥𝑘 + 1) không nhỏ hơn 2𝑘−1 − 1 thì chọn đa thức thuộc vành lớn hơn (vành 𝑍2/(𝑥𝑝 + 1), với 𝑝 > 𝑘) và có cấp bằng với 2𝑘−1 − 1 sau đó hạ bậc đa thức theo ℎ(𝑥) thì được đa thức mới có thể chọn làm phần tử sinh của bộ mã.
và
hỗn hợp trên hai vành đa thức bất kỳ. Xét 2 vành ta tìm được đa thức nếu trên vành
Việc hạ bậc đa thức theo ℎ(𝑥) như vậy là trường hợp phân hoạch với thỏa mãn điều thì ta
kiện: là tích của một số đa thức bất khả quy và có thể thực hiện được phân hoạch hỗn hợp trên hai vành này [J6].
Dựa trên kết quả hai định lý 3.1, 3.2 cùng với phân tích ℎ(𝑥), có thể nhận thấy rằng luôn có thể xây dựng được các bộ cyclic mã tối ưu trên các vành đa thức từ các cấp số nhân (hay lớp kề) cyclic. 3.2.1.2. Mã cyclic tốt xây dựng từ cấp số nhân cyclic Các mã cyclic tối ưu (𝑛, 𝑘, 𝑑) được nghiên cứu và đề xuất ở trên có ưu điểm là sửa lỗi tốt (𝑑 lớn), xây dựng bộ mã dễ dàng, tuy nhiên tồn tại một nhược điểm lớn là hiệu suất mã (𝑘/𝑛) thường khá nhỏ, do đó nghiên cứu sinh đề xuất phương pháp tìm mã cyclic tốt xây dựng từ các cấp số nhân/ lớp kề cyclic với các giá trị (𝑛, 𝑘, 𝑑) phù hợp, đặc biệt là đề xuất các mã tốt xây dựng từ 3 lớp kề cyclic trên vành. Để tìm mã cyclic tốt xây dựng trên 3 lớp kề cyclic sử dụng phương pháp giải mã ngưỡng, ta thực hiện theo các bước sau đây [J6]:
Bước 1: + Cho giá trị 𝑘 của vành đa thức 𝑍2/(𝑥𝑘 + 1). + Lập phân hoạch cho vành đa thức, xác định số lớp kề 𝑚 (số lượng lớp kề trong vành)
+ Cho 𝑖 = 2
Bước 2: + Gán 𝑗 = 𝑖 + 1 Bước 3: + Lập mã gồm 3 lớp kề {1, 𝑖, 𝑗}
17
+ Xác định giá trị 𝑛 trong bộ mã (𝑛, 𝑘, 𝑑) , trong đó 𝑛 là tổng số phần tử của 3 lớp kề được chọn (cũng là độ dài từ mã).
+ Tính tổng kiểm tra của bộ mã theo cả 3 trường hợp CS trực giao, CS có khả năng trực giao, CS liên hệ, sau đó lưu lại số CS của bộ mã ứng với mỗi trường hợp. Từ số tổng kiểm tra sẽ tính được khoảng cách Hamming 𝑑.
+ Nếu 𝑗 = 𝑚 thì chuyển sang bước 4, nếu 𝑗 < 𝑚 thì tăng 𝑗 và lặp lại bước 3.
Bước 4: + Nếu 𝑖 = 𝑚 − 1 thì chuyển sang bước 5, nếu 𝑖 < 𝑚 − 1 thì tăng 𝑖 và lặp lại bước 2.
Bước 5: Tính toán bộ tham số (𝑛, 𝑘, 𝑑) ứng với các bộ mã, so sánh với các giới hạn tối ưu. Liệt kê bộ mã (𝑛, 𝑘, 𝑑) tốt nhất thu được.
Hình 3.3: Lưu đồ thuật toán tìm bộ mã cyclic tốt xây dựng từ cấp số nhân cyclic [J6]
18
Từ các bước trên có thể xây dựng được lưu đồ thuật tìm các bộ mã cyclic tốt theo lưu đồ thuật toán như trên hình 3.3.
Trên cơ sở thuật toán nghiên cứu sinh đã viết chương trình và xây dựng được một bảng kết quả một số mã cyclic tốt được xây dựng trên 3 lớp kề cyclic và được công bố trên [J6].
Thực hiện tìm mã cyclic tốt với nhiều lớp kề hơn cũng cho những bộ mã tốt, tuy nhiên lại phải trả giá về hiệu suất mã (tỉ số 𝑘/𝑛 thấp). Hướng nghiên cứu tiếp theo, nghiên cứu sinh sẽ tiếp tục tìm các bộ mã cyclic tốt với nhiều lớp kề hơn, các bộ mã cyclic tốt ứng với các phương pháp giải mã khác.
3.2.2. Mô phỏng, đánh giá một số bộ mã mã cyclic tốt
Kết quả mô phỏng đối với một hệ thống thông tin vô tuyến số
điểm-điểm cho một số bộ mã như sau: a) Bộ mã cyclic (255,9,127)
Hình 3.5. Kết quả mô phỏng bộ mã cyclic (255,9,127)
Bộ mã này đạt giới hạn Griesmer và Plotkin. Kết quả mô phỏng như hình 3.5. Trong mô phỏng ứng với bộ mã này, sử dụng nhiễu Gauss trắng cộng trên kênh truyền. Thử nghiệm với các phương pháp điều chế khác nhau (QPSK, 16QAM,...), cho chất lượng rất tốt. Hình 3.5 thể hiện kết quả mô phỏng của bộ mã ứng với điều chế 64QAM, 128QAM và hai trường hợp khác (chỉ điều chế, và không điều chế, không mã hóa).
19
b) Bộ mã cyclic (15,5,7) Bộ mã này xây dựng trên vành 𝑍2/(𝑥5 + 1) đạt giới hạn Griesmer và Plotkin. Kết quả mô phỏng bộ mã cyclic (15,5,7) như hình 3.6. Thử nghiệm với các phương pháp điều chế QPSK, 4QAM, 16QAM cho chất lượng khá tốt. Kết quả mô phỏng cũng cho thấy đường truyền sử dụng cùng một bộ mã, thì điều chế QPSK cho 𝐵𝐸𝑅 tốt hơn 16QAM.
Hình 3.6. Kết quả mô phỏng bộ mã cyclic (15,5,7)
c) Bộ mã cyclic (27,9,9) Chọn mã cyclic cục bộ xây dựng từ ba lớp kề cyclic {(1), (11), (61)} trên vành Z2/(x9+1), tiến hành xây dựng bộ mã hóa và giải mã ta thu được bộ mã cyclic (27,9,9). Kết quả mô phỏng trên hình 3.7.
So sánh với trường hợp truyền dẫn sử dụng bộ mã cyclic (15,5,7) và trường hợp truyền dẫn tín hiệu chỉ điều chế (QPSK, 16QAM) không mã hóa. Kết quả mô phỏng cho thấy dù sử dụng phương pháp điều chế nào thì bộ mã cyclic (15,5,7) đạt giới hạn tối ưu Griesmer và Plotkin (có khả năng sửa 𝑡 = 3 bit lỗi, và 𝑡/𝑛 = 3/15) cho khả năng sửa lỗi tốt hơn (hay tỉ số 𝐵𝐸𝑅 thấp hơn) bộ mã cyclic (27,9,9) là mã cyclic tốt (có khả năng sửa 𝑡 = 4 bit lỗi, và 𝑡/𝑛 = 4/27). Nghiên cứu sinh cũng đã mô phỏng đánh giá bộ mã với điều chế 64QAM, 128QAM thì cho tỉ lệ lỗi lớn và khả năng sửa lỗi không tốt như mã (255,9,127).
20
Hình 3.7. Kết quả mô phỏng bộ mã cyclic (27,9,9)
3.2.3. Đề xuất thực hiện các bộ mã trên FPGA
Nhằm kết hợp ưu điểm của cấu kiện logic khả trình và hướng tới xây dựng một mạch điện tử thực hiện được chức năng một số bộ mã cyclic, luận án trình bày phương pháp xây dựng mạch mã hoá và giải mã trên cấu kiện logic khả trình FPGA để thực hiện chức năng của một số bộ mã. Kết quả liên quan được công bố tại [J1], [C1]. 3.3. ĐỀ XUẤT PHƯƠNG PHÁP TẠO KHÓA CHO MỘT SỐ HỆ MẬT
Nghiên cứu sinh đã nghiên cứu ứng dụng CMG và CGP làm khóa để xây dựng hệ mật mã khối kết hợp sơ đồ Lai-Massey với sơ đồ Feistel và ứng dụng vào hàm băm công bố trong bài báo [C2].
Trong phần này luận án đề xuất một hướng tiếp cận mới về sự tương đương của vành đa thức có hai lớp kề cyclic với trường số. Từ đó trình bày ứng dụng của nhóm nhân cyclic có cấp cực đại trên một số vành đa thức có hai lớp kề cyclic đặc biệt làm khóa cho một số hệ mật. 3.3.1. Quan hệ giữa vành đa thức có hai lớp kề cyclic và trường số Trong phần này, luận án đã đề xuất và chứng minh mối quan hệ tựa đồng cấu chỉ xảy ra đối với một số vành đa thức có hai lớp kề cyclic đặc biệt, các vành đa thức này được liệt kê trong phụ lục của luận án. Có thể sử dụng quan hệ tựa đồng cấu này để xây dựng một số hệ mật trên vành đa thức có 2 lớp kề cyclic.
3.3.2. Hệ mật Omura-Massey trên vành đa thức có hai lớp kề cyclic Trong phần này, trên cơ sở hệ mật gốc, kết hợp với tính chất đặc biệt của một số vành đa thức có hai lớp kề cyclic được trình bày ở phần
21
trên, nghiên cứu sinh sẽ trình bày hệ mật O-M và một số biến thể mới của hệ mật O-M được xây dựng trên vành đa thức có hai lớp kề cyclic trong đó sử dụng phần tử có cấp cao nhất của nhóm nhân cyclic đạt cấp cực đại trên vành làm khóa cho hệ mật.
3.3.2.1. Hệ mật O-M gốc 3.3.2.2. Hệ mật O-M trên vành đa thức có hai lớp kề cyclic a) Tạo khóa Khóa công khai: ℤ2[𝑥]/(𝑥𝑛 + 1) A chọn ngẫu nhiên (𝑚, 𝑛) làm khóa riêng: 𝑚. 𝑛 ≡ 1 mod (2𝑛−1 − 1) B chọn ngẫu nhiên (𝑢, 𝑣) làm khóa riêng: 𝑢. 𝑣 ≡ 1 mod (2𝑛−1 − 1) b) Quá trình truyền thông A muốn gửi bản tin 𝑀(𝑥) tới B
𝐴 tính: [𝑀(𝑥)]𝑚 mod (𝑥𝑛 + 1)
→
← 𝐵 tính: [𝑀𝑚(𝑥)]𝑢 mod (𝑥𝑛 + 1)
→
𝐴 tính: [𝑀𝑚𝑢(𝑥)]𝑛 mod (𝑥𝑛 + 1) = [𝑀(𝑥)]𝑢 mod (𝑥𝑛 + 1)
← 𝐵 tính:
[𝑀𝑢(𝑥)]𝑣 mod (𝑥𝑛 + 1) = 𝑀(𝑥)
𝐴(𝑚, 𝑛) 𝐵(𝑢, 𝑣)
c) Nhận xét - Hệ mật là an toàn nếu bài toán logarit rời rạc trên vành đa thức có hai lớp kề cyclic là bất khả giải.
- Hệ mật này là không xác thực. - Hệ số mở rộng bản tin của hệ mật này là 3. 3.3.2.3. Một số biến thể của hệ mật O-M trên vành đa thức có hai lớp kề cyclic
Nghiên cứu sinh đã tiếp tục nghiên cứu mở rộng ứng dụng và trình bày hai biến thể của hệ mật trong luận án.
a) Hệ mật O-M cộng trên vành đa thức có hai lớp kề cyclic
22
b) Hệ mật O-M có tính nhân trên vành đa thức có hai lớp kề cyclic Nhận xét: Để tránh phép tấn công “Kẻ đứng giữa” (Man in the
midle) có thể sử dụng thêm các phương pháp xác thực. 3.4. KẾT LUẬN CHƯƠNG
Chương 3 của luận án đã trình bày kết quả chính và mới là: Đề xuất phương pháp tìm mã cyclic tốt thông qua việc chứng minh hai định lý về mã cyclic tối ưu, xây dựng thuât toán tìm kiếm mã cyclic tốt và bước đầu lập được bảng một số mã cyclic tốt, thông qua kết quả mô phỏng, đánh giá hiệu năng của các bộ mã có thể nhận xét rằng kết quả nghiên cứu đã góp phần chỉ ra cách xác định các mã cyclic tốt có thể ứng dụng vào thực tế [J6]; Đề xuất việc xây dựng các thiết bị mã hóa và giải mã ngưỡng cho các nhóm nhân cyclic và cấp số nhân cyclic trên cấu kiện logic khả trình FPGA. Kết quả nghiên cứu được công bố trong các bài báo [J1], [C1]; Nghiên cứu sinh cũng trình bày một đề xuất ứng dụng nhóm nhân, cấp số nhân cyclic làm khóa cho một số hệ mật là một hướng nghiên cứu mở có thể tiếp tục nghiên cứu [C2].
KẾT LUẬN
Những đóng góp chính của luận án:
1) Đề xuất một số phương pháp xác định đa thức có cấp cực đại, bao gồm kết quả quan trọng: Đề xuất và chứng minh bổ đề về cấp của đa thức là tích của các đa thức trên vành; Đề xuất và chứng minh bổ đề về cấp nhị thức trên vành đa thức, đồng thời đánh giá cấp nhị thức trên vành đa thức; Đề xuất thuật toán cải tiến xác định cấp của đa thức trên vành; Đánh giá xác suất tìm phần tử có cấp cực đại giúp kiến thiết các nhóm nhân và mã cyclic trên vành đa thức có hai lớp kề cyclic ([J2], [J3], [J5], [C5]).
2) Chứng minh được sự tương đương của nhóm nhân cyclic, cấp số nhân cyclic với mã cyclic truyền thống, góp phần mở ra một hướng tiếp cận mới là xây dựng mã cyclic truyền thống từ các nhóm nhân cyclic, cấp số nhân cyclic trên vành đa thức có bậc bằng cấp của nhóm nhân cyclic, cấp số nhân cyclic ([J4], [C3], [C4]).
3) Đề xuất phương pháp tìm mã cyclic tốt xây dựng từ nhóm nhân cyclic, cấp số nhân cyclic trên vành đa thức và bước đầu lập được bảng một số mã cyclic tốt, đánh giá khả năng thực hiện các bộ mã cyclic cục bộ trên cấu kiện phần cứng (như FPGA) ([J1], [J6], [C1]).
23
[J1] Nguyen Trung Hieu, Dang Hoai Bac, Nguyen Ngoc Minh (2012), “An FPGA- based implementation method for local cyclic code encoder/decoder”, Journal of Science and Technology, Vietnam, ISSN 0866 708X, 50(2A), pp. 38-49. [J2] Nguyen Trung Hieu, Ngo Duc Thien, Tran Duc Su (2012), “On constructing cyclic multiplicative groups with maximum order over polynomial ring with two cyclotomic cosets”, Tạp chí Nghiên cứu khoa học và Công nghệ Quân sự, Hà Nội, Việt Nam, ISSN 1859-1043, Số 17, 02-2012, tr. 133-140.
[J3] Nguyễn Trung Hiếu, Nguyễn Văn Trung, Nguyễn Bình (2013), “Về cấp của các đa thức trên vành”, Tạp chí Khoa học và Công nghệ, Việt Nam, ISSN 0866 708X, 51(1A) , tr. 101-107.
[J4] Nguyễn Văn Trung, Nguyễn Trung Hiếu (2015), “Mã cyclic cục bộ xây dựng từ một lớp kề cyclic”, Tạp chí Nghiên cứu khoa học và Công nghệ Quân sự, Hà Nội, Việt Nam, ISSN 1859-1043, số Đặc san KH-CNQS, 10-2015, tr. 331-336. [J5] Nguyễn Trung Hiếu, Ngô Đức Thiện (2016), “Một phương pháp tìm kiếm các đa thức có cấp cực đại trên vành đa thức”, Tạp chí Khoa học và Công nghệ các trường Đại học Kỹ thuật, Việt Nam, ISSN 2354-1083, số 110, 2016, tr. 75-80.
[J6] Nguyễn Trung Hiếu, Nguyễn Bình (2017), “Một số bộ mã cyclic tốt xây dựng trên vành đa thức”, Tạp chí Khoa học công nghệ Thông tin và Truyền thông, Việt Nam, ISSN 2525-2224, số 01 (CS.01) 2017, tr. 20-27.
[C1] Hieu T. Nguyen, Minh N. Nguyen, Cuong L. Nguyen, E. Custovic (2011), “An FPGA-based Implementation for Repeated Square-and-Multiply Polynomials”, Proceedings of the 6th International Conference on Broadband Communications & Biomedical Applications, November 21 - 24, 2011, Melbourne, Australia, ISBN: 978-0-9872129-0-0, pp. 173-178 (publication in IEEE Xplore).
[C2] Ngô Đức Thiện, Nguyễn Trung Hiếu, Nguyễn Toàn Thắng, Đặng Hoài Bắc (2013), “Một phương pháp xây dựng hệ mật mã khối kết hợp sơ đồ Lai-Massey với sơ đồ Feistel và ứng dụng vào hàm băm”, Kỷ yếu Hội nghị Quốc gia về Điện tử - Truyền thông (REV2013-KC01), Hà Nội, Việt Nam, ngày 17-18/12/2013, tr. 75-80.
[C3] Nguyễn Trung Hiếu, Nguyễn Văn Trung, Phạm Việt Trung (2013), “Sự tương đương giữa mã Cyclic cục bộ xây dựng trên nhóm nhân Cyclic và mã Cyclic truyền thống”, Kỷ yếu Hội nghị Quốc gia về Điện tử - Truyền thông (REV2013- KC01), Hà Nội, Việt Nam, ngày 17-18/12/2013, tr. 225-230.
[C4] Nguyen Trung Hieu, Nguyen Van Trung, Nguyen Binh (2014), “A Classification of Linear Codes Based on Algebraic Structures and Local Cyclic Codes”, Proceedings of The 2014 International Conference on Advanced Technologies for Communications, October 15-17, 2014, Hanoi, Vietnam, ISBN: 978-1-4799-6955-5, pp. 349-354 (publication in IEEE Xplore).
[C5] Nguyễn Trung Hiếu (2015), “Một số phương pháp mới xác định cấp của đa thức trên vành đa thức sử dụng tính chất của nhóm nhân cyclic đối xứng”, Hội thảo quốc gia 2015 về Điện tử, Truyền thông và Công nghệ thông tin (ECIT-2015), tháng 12/2015, TP. Hồ Chí Minh, Việt Nam, tr. 248-252.
CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA TÁC GIẢ
