Nghiên cứu hệ mật trên vành đa thức có hai lớp kề xyclic

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (3.81 MB, 24 trang )

Trang 1<div class="page_container" data-page="1">

TRAN THE HIẾU

NGHIÊN CUU HE MAT TREN VANH ĐA THỨC CÓ HAI LỚP KE XYCLIC

Chuyên ngành: Kỹ Thuật Viễn Thơng

Mã số: 60.52.02.08

TĨM TẮT LUẬN VĂN THẠC SĨ

Hà Nội - 2016

</div>Trang 2<div class="page_container" data-page="2">

Người hướng dẫn khoa học: GS.TS. Nguyễn Bình

Phản biện 1: TS. Nguyễn Chiến Trinh

Phản biện 2: TS. Dư Đình Viên

Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện Cơng

nghệ Bưu chính Viễn thơng

Vào lúc: 8 giờ 30 ngày 27 tháng 2 năm 2016

Có thể tìm hiểu luận văn tại:

- Thư viện của Học viện Công nghệ Bưu chính Viễn thơng

</div>Trang 3<div class="page_container" data-page="3">

MỞ DAU

Tính cấp thiết của đề tài

Hiện nay đã có một số nghiên cứu về các mã xyclic và các đặc tính của vành

đa thức có hai lớp kề xyclic, tuy nhiên chưa thấy nghiên cứu nào về xây dựng hệ mật trên vành đa thức có hai lớp kề xyclic. Việc xây dựng, đánh giá tính an tồn, xác định ưu nhược điểm của hệ mật xây dựng trên vành đa thức có hai lớp kề xyclic, qua đó đề xuất khả năng áp dụng của hệ mật này vào thực thế là một yêu cầu

thực tiễn.

Xuất phát từ những cơ sở khoa học và thực tiễn đó, em đã quyết định chọn đề

tài: “Nghiên cứu hệ mật trên vành da thức có hai lop ké xyclic” Tổng quan về vấn đề nghiên cứu:

Mã xyclic được Eugene Prange nghiên cứu đầu tiên năm 1957. Sau đó q trình nghiên cứu về mã xyclic tập trung theo cả hai hướng sửa lỗi ngẫu nhiên và sửa lỗi cụm. Rất nhiều lớp mã xyclic đã được xây dựng trong những năm này, bao

gồm các mã BCH, các mã Reed-Solomon, các mã hình hoc Euclidean. Một

trong các hướng nghiên cứu trên thế giới hiện nay là đánh giá một số giới hạn mã xyclic hoặc đề xuất phương án giải mã tối ưu cho mã xyclic.

Tại Việt Nam, mở đầu một hướng nghiên cứu mới về mã sửa sai đó là mã xyclic cục bộ LCC (Local Cyclic Code). Các mã LCC xây dựng theo các nhóm nhân và cấp số nhân trên vành đa thức. Bên cạnh đó là các nghiên cứu tường minh về các phương pháp giải mã ngưỡng theo các hệ tơng kiểm tra trực giao. Các cơng trình này đều có ý nghĩa về mặt lý thuyết, đề xuất được cấu trúc đại số mới trên vành đa thức như phân hoạch, nhóm nhân, cấp số nhân. Một số nghiên cứu đã cơng

bố về mã xyclic có liên quan như: [1], [4],...

Việc nghiên cứu truyền thống về mã xyclic đã khá hồn chỉnh, tuy nhiên van chưa thấy cơng trình nào nghiên cứu hệ mật trên vành đa thức có hai lớp kề xyclic. Đây là vành đa thức đặc biệt vì trong phân tích x "+ 7 của vành chi gồm hai đa thức bất khả quy, dẫn đến rất ít bộ mã tốt có thể tạo ra trên vành này [3]. Tuy

</div>Trang 4<div class="page_container" data-page="4">

nhiên với tốc độ tính tốn nhanh là một ưu điểm của các mã xyclic. Do đó việc tim hiểu, xây dựng hệ mật trên vành đa thức này vẫn là một van đề mở.

Mục đích nghiên cứu:

Mục đích nghiên cứu của luận văn là tìm hiểu đặc điểm và cấu trúc của vành

đa thức có hai lớp kề xyclic. Dựa trên các kết quả nghiên cứu, luận văn đưa ra mô hình hệ mật dựa trên vành đa thức có 2 lớp kể xyclic. Qua đó khảo sát tính an

tồn và phân tích hiệu năng của hệ mật này.

Đối tượng và phạm vi nghiên cứu:

Đối tượng nghiên cứu của luận văn này được giới hạn trong việc nghiên cứu

các đặc điểm và cau trúc của vành đa thức có hai lớp kề xyclic. Tập trung nghiên

cứu xây dựng hệ mật trên vành đa thức có hai lớp kề xyclic. Khảo sát đánh giá tính an tồn và hiệu năng của của hệ mật trên vành đa thức có hai lớp kề xyclic.

Phương pháp nghiên cứu:

Phương pháp nghiên cứu tổng hợp và phân tích dé tìm ra các cấu trúc đại số để xây dựng mã xyclic, các đặc điểm của vành đa thức có hai lớp kề xyclic qua đó làm cơ sở lý luận dé xây dựng hệ mật trên vành đa thức có hai lớp kề xyclic.

Luận van sử dụng các cơng cụ tốn học va các cơng cụ của lý thuyết mã, sử dụng một số công nghệ lập trình, mơ phỏng trong một số vấn dé của đề tài dé kết quả nghiên cứu được trực quan hơn, chứng minh cho tính khả thi của kết quả

nghiên cứu.

Ý nghĩa khoa học và thực tiễn

Luận văn xây dựng một hệ mật dựa trên vành đa thức có hai lớp kề xyclic, đưa ra phân tích hiệu năng và tính an tồn của hệ mật này qua đó đề xuất khả năng áp

dụng của hệ mật này trong thực tế.

Các mã xyclic có tốc độ tính tốn nhanh và có thé dùng cho các hệ thống có tài nguyên hạn chế. Do đó việc áp dụng hệ mật này vào trong thực tế là hồn tồn

có cơ SỞ.

</div>Trang 5<div class="page_container" data-page="5">

Bồ cục của luận văn

Luận văn mô tả hệ mật xây dựng trên vành đa thức có hai lớp kề xyclic và

phân tích sơ bộ về hiệu năng và đánh giá tính an tồn của hệ mật này. Luận văn

được trình bày trong 3 chương:

Chương I: Tổng quan về các vành đa thức có hai lớp kề xyclic

Chương II: Xây dựng hệ mật dựa trên vành đa thức có hai lớp kề xyclic

Chương III: Phân tích một loại tấn cơng và đánh giá sơ bộ tính an tồn, hiệu năng của hệ mật xây dựng trên vành đa thức có 2 lớp kể xyclic

</div>Trang 6<div class="page_container" data-page="6">

CHUONG I: TONG QUAN VE VÀNH ĐA THỨC CÓ HAI

LỚP KE XYLIC

1.1. Tim hiểu về nhóm nhân xyclic trên vành đa thức

1.1.1. Định nghĩa nhóm nhân xyclic trên vành đa thức

- Một số định nghĩa

- Các thuật ngữ về nhóm nhân xylic trên vành đa thức

1.1.2. Các loại nhóm nhân xyclic trên vành đa thức

- Khảo sát về nhóm nhân xyclic trên vành đa thức.

1.2. Cấp số nhân xyclic trên vành đa thức

1.2.1. Khái niệm về cấp số nhân xyclic trên vành đa thức

- Tìm hiểu về cấp số nhân trên vành đa thức có hai lớp kề xyclic

1.2.2. 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 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 xyclic với cùng một cơng

Tìm hiểu về điều kiện dé vành đa thức có hai lớp kề xyclic có phan tử nghịch đảo hoặc khả đảo ứng dụng cho việc xây dựng hệ mật ở chương sau.

1.3. Xây dựng M-day lồng ghép trên vành đa thức có hai lớp kề xyclic

1.3.1. Vành đa thức có hai lớp kề

- Tìm hiểu về vành đa thức có hai lớp kề

1.3.2. M-dãy xây dựng trên vành đa thức

Xét vành đa thức Z¿[xj⁄x” + 1 với n là số lẻ. Theo cách thơng thường thì các M-dãy có thé được tạo từ bat kỳ các thức nguyên thủy g(x) có bậc là m theo phương

trình đồng dư sau:

</div>Trang 7<div class="page_container" data-page="7">

a(x) = b(x).x' mod g(x); i = 1,2,3... (1.17)

Trong đó: g(x) - da thức nguyên thủy; deg g(x) =m

b(x) — đa thức mam; deg b(x) <m — Ï

Chu kỳ của M-day là: 7 = 2” -7. Từ đây ta có thé xây dựng các M-dãy với độ

dai lớn như các dãy giả ngẫu nhiên được sử dụng rộng rãi trong các ứng dụng củaviễn thông.

1.3.3. Xây dựng M-dãy lồng ghép từ các cấp số nhân xyclic trên vành đa thức có hai lớp kề

Bỏ dé 1.15: M-dãy lồng ghép trên vành đa thức có hai lớp kề có thé được tạo từ phương trình đồng dư sau:

b(x) = c(x)a' (x) mod h(x); i = 1,2,...,2"- 1 (1.18)

Trong đó: ord a(x) = 2" - 1

Số lượng các đa thức a(x) là: N, =ø(2` -1)

Trọng số W(a(x)) = w„ là một số chan.

Trọng số W(h(x)) = w„ là một số lẻ với degh(x) =n -1. Số lượng các đa thức A(x) tính như sau:

N,= sứ 1/2 c?i, = 2>? (1.19)

c(x) là đa thức mầm với deg c(x) <m- Ï.

Số lượng các M-dãy lồng ghép tính theo cơng thức:

</div>Trang 8<div class="page_container" data-page="8">

Nhóm nhân A bao gồm tất cả các phan tử có trọng số chan trong vành đa

thức, trừ phần tử e¿(x). Trong A, có 2” - 7 đa thức có bậc bằng m - l.

Xét nhóm nhân A lấy theo modulo h(x), ta nhận thay có 2” - 7 đa thức có

trọng số lẻ và 2"! - 1 đa thức có trọng số chăn. Do đó, có tất cả các đa thức với bậc

thỏa mãn điều kiện sau:

deg a’ (x)mod h(x) <m-1 (1.21)

Rõ ràng đây là một M-dãy lồng ghép.

Việc tạo dãy ngẫu nhiên rất tốn kém và việc lưu trữ không hiệu quả, do vậy

ta phải sử dụng dãy giả ngẫu nhiên, các dãy này có tính tiền định và được xây dựng từ các bit mầm.

Các M-day tạo theo phương pháp này có ưu điểm: (1) có phân bố gần giống

ngẫu nhiên, (2) dé thực hiện, (3) độ dài lớn tùy ý. Trên cơ sở đó ta có thé sử dụng

các M-dãy này vao việc tạo khóa cho các hệ mật khóa bi mật nói chung.

1.4. Kết luận chương.

Trong chương này, luận văn tập chung tìm hiểu về vành đa thức có hai lớp

kề xyclic, các phần tử khả đảo qua đó làm cơ sở lý thuyết cho việc xây đựng hệ mật

trên vành đa thức ở chương II

Việc tạo ra M-dãy giả ngẫu nhiên cũng có ý nghĩa đặc biệt trong việc tạo

khóa cho các hệ mật khóa bí mật, giúp giải quyết vấn đề lưu trữ khóa, nâng cao hiệu

năng của hệ mật.

</div>Trang 9<div class="page_container" data-page="9">

CHƯƠNG II. XÂY DUNG HE MAT TREN VANH ĐA THỨC

CĨ HAI LỚP KÈ XYCLIC

2.1. Xây dựng hệ mật khóa cơng khai dựa trên vành đa thức có 2 lớp kề

xyclic.

2.1.1. Hệ mật khóa cơng khai

Ý tưởng xây dựng một hệ mật khố cơng khai (hay dùng chung) là tìm một

hệ mật khơng có khả năng tính tốn để xác định đ, khi biết e,. Nếu thực hiện được như vậy thì quy tac mã e¿ có thé được cơng khai bằng cách cơng bố nó trong một danh bạ (bởi vậy nên có thuật ngữ hệ mật khố cơng khai). Ưu điểm của hệ mật

khố cơng khai là ở chỗ Alice (hoặc bat kỳ ai) có thé gửi một bản tin đã mã cho Bob

(mà không cần thông tin trước về khoá mật) bang cách dùng mật mã công khai ¿. Người nhận A sẽ là người duy nhất có thể giải được bản mã này bằng sử dụng luật

</div>Trang 10<div class="page_container" data-page="10">

2.1.1.2. Ưu điểm của hệ mật khóa cơng khai:

+ Khơng sử dụng kênh an tồn (đây là nhược điểm của hệ mật khóa bí mật).

+ Dễ bảo vệ, lưu trữ và sinh khóa.+ Dễ tạo các dịch vụ an toàn khác.

Vi dụ: Với n người dùng:

Bảng 2.1: So sánh số khóa cần tạo và lưu giữ giữa hai hệ mật khóa bí mật và hệ mật

khóa cơng khai với n người dùng.

Số khóa cần tạo Số khóa cần lưu giữ bí mật

u cầu dé xây dựng mật mã khóa cơng khai là: hàm lập mã thi dé (với khóa

cơng khai), nhưng hàm giải mã thì khó khi khơng có khóa bí mật. Đó là các hàm

cửa sập một chiều (trapdoor oneway functions): tính xi thi dễ, tinh ngược lại phải

khó, nhưng với cửa lật là khóa bí mật thì tính ngược, tức giải mã, cũng phải dễ.

Từ những yêu cầu khó khăn trên luận văn đã tìm hiểu về các phần tử khả nghịch đề xây dựng hệ mật khóa cơng khai trên vành đa thức có hai lớp kề xyclic.

Trong các vành đa thức có hai lớp kề xyclic tất cả các phần tử có nghịch đảo

hoặc mở rộng khả nghịch [1]. Nhưng, trong mở rộng của nó thậm chí vành Z.|x]

u tố nghịch phải có các yếu tố với trong số lẻ. Các phan tử nghịch đảo hoặc mở rộng khả nghịch này đáp ứng yêu cầu dé cập ở mục 2.1.

</div>Trang 11<div class="page_container" data-page="11">

Bồ dé 2.1: Trong Z¿/xJ tập hợp các đa thức với trong số lẻ và khả nghịch

Với một phần tử khả nghịch tùy ý, chúng ta có thể tìm nghịch đảo của nó

theo thuật tốn 2,226 trong [2].

Bồ đề 2.2: Trong Z2, [x] chúng ta có:

lIze(x)I=2?$~1 (2.2)

Tất cả các yếu tố khả nghịch trong Z,,[x] thuộc các nhóm nhân khác nhau với các lity đăng với giá trị 2.(2°~1 -1).

Vì vậy, Nếu: w(s,) — chan thì w(s,) - lẻ

Hoặc nếu : w(S¡) — lẻ thì w(s„) — chăn

+ Bước 3: Bob sử dụng thuật toán 2,226 trong [2] dé tính tg khóa riêng

với đầu vào sg

Thuật tốn 2,226 tính tốn phần tử nhân nghịch đảo trong F,m được mô tả

như sau:

</div>Trang 12<div class="page_container" data-page="12">

Đầu vào: Chọn một vành đa thức khác không g(x) € F,m (Các phần tử thuộc trường F,m được biểu diễn dưới dạng Z,[x]Af(x)) , trong đó ƒ(x) € Z,[x] là một đa

thức bat khả quy bậc m trên Z,)

Đầu ra: g(x)" EF ym.

1. Sử dung thuật toán Euclidean cho vành đa thức (thuật tốn 2.221 trong [1]) để tìm ra hai vành đa thức s(x) và t(x) € Zplx] sao cho

2. Quay về giá tri (s(x)).

Số bac trong F,m có thé được xác định và biểu diễn qua thuật tốn nhân bình

phương (Thuật tốn 2.143 trong [2]).

Chúng ta có :

Tg.Sg = I mod x?Š + 1 (2.4)

+ Bước 4: Bob chọn p = s + ÏÌ với l Sl Ss- Ï

Bob tính khóa công khai.

</div>Trang 13<div class="page_container" data-page="13">

Từ co sở lý thuyết trên sau đây là sơ đồ hệ mật khóa cơng khai dựa trên vành đa thức có hai lớp kề xyclic.

l,s,Kg: là khoa cơng khai của Bob

Tg :là khóa bí mật của Bob

Hình 2.2: Sơ đồ hệ mật khóa cơng khai dựa trên vành đa thức có hai lớp kề

</div>Trang 15<div class="page_container" data-page="15">

Trong mơ hình mật mã cơ điển trước đây mà hiện nay đang được nghiên cứu Alice (người gửi) và Bob (người nhận) chọn một cách bí mật khố K. Sau đó dùng K dé tạo luật mã hoá e, và luật giải mã d, . Trong hệ mật này d; hoặc giống e¿ hoặc

dễ dàng nhận được từ nó (ví dụ trong hệ DES q trình giải mã hoàn toàn tương tự

</div>Trang 16<div class="page_container" data-page="16">

như q trình mã nhưng thủ tục khố ngược lại). Các hệ mật thuộc loại này được

gọi là hệ khố bí mật, nếu để lộ e, thì làm cho hệ thống mất an toàn.

2.2.1.1. Sơ đồ khối chức năng của hệ mật khóa bí mật.

Bản rõ M Ban mã C

Nguồn tin | „| Bộ mã hố Kênh mở

(khơng an tồn)

Hình 2.3: Sơ đồ khối chức năng hệ mật khóa bí mật.

Một hệ mật là một bộ gồm 5 tham số (P, C, K, E, D) thoả mãn các điều kiện

sau [4]:

a) P là một tập hữu hạn các bản rõ có thể. b) C là một tập hữu hạn các bản mã có thẻ.

c) K là một tập hữu hạn các khố có thé (khơng gian khố). d) Đối với mỗi k e K có một quy tắc mã e, e E

en: PC

và một quy tắc giải mã tương ứng d, e D

dy:C >P

sao cho: đ;¿(e¿(x))= x với mọi x eP.

2.2.1.2. Uu, nhược điểm của mật mã khóa bi mật

Uu điểm:

- Mật mã khóa bí mật (mật mã cơ điên) nói chung đơn giản, tức là các yêu câu

về phần cứng khơng phức tạp, thời gian tính tốn nhanh.

</div>Trang 17<div class="page_container" data-page="17">

- Mật mã khóa bí mật có tính hiệu quả, thông thường tốc độ mã Rina = 1 (số bit

đầu ra mã hóa bằng với số bit đầu vào) dé sử dụng cho các ứng dụng nhạy cảm với

độ trễ và các ứng dụng di động thời gian thực.

Nhược điểm:

- Phải ding kênh an tồn dé truyền khóa (Khó thiết lập và chi phí tốn kém).

- Việc tạo khóa và giữ bí mật khóa phức tạp. Khi làm việc trên mạng nếu dùng mật mã khóa bí mật sẽ phải tạo và lư trữ số lượng khóa nhiều.

- Nếu sử dụng mật mã khóa bí mật sẽ khó xây dựng các dịch vụ an toàn khác như các dịch vụ đảm bảo tính tồn vẹn của dữ liệu, dịch vụ xác thực và chữ ký SỐ.

Do đó các dịch vụ này sẽ được thực hiện bởi mat mã khóa cơng khai.

- Các thuật tốn là song ánh, vì vậy nếu biết M và K thì chắc chắn biết C. Thám mã có thê suy luận ra K, kết hợp với C tại kênh mở có thể suy ra M.

Vì các nhược điểm này nên hệ mật khóa bí mật ít được dùng trong thực tế.

2.2.2. Hệ mật khóa bí mật dựa trên vành đa thức có hai lớp kề xyclic.

Ở phần trên của hệ mật khóa cơng khai, nếu chúng ta chọn / = 0 thì hệ mật

này trở thành hệ mật khóa bí mật. Khi đó khóa riêng và khóa chung của hệ mật

khóa cơng khai ở trên sẽ giống nhau.

Trong trường hợp này, thông tin về Kz & c là chỉ trong s bit.

Trong hệ mật này, các khóa tương đương và khóa được xác định như sau:

Sp = k(x)+ XieA(X° + x9"); Te = [k?(x)] Spi số = k”()

Với w(k(x)) - lẻ, k (x) € Z„[x]

</div>Trang 18<div class="page_container" data-page="18">

A là một tập con thuộc § = {0,/, ..., s-1}

Số các tập con như A bằng 23.

Nếu k(x) không được tiết lộ. Hệ mật này trở thành hệ mật khóa bí mật.

Đây là một hệ thống mật mã khối với tham số sau đây:

Tham số Sử dụng phần tử khả đảo |Sử dụng phần mở rộng Chiêu dài khóa (bits) s-1 s

Chiều dai ban rõ (bits) s s-] Chiều dai ban mã (bits) s s

Chúng ta có thể sử dụng hệ mật này trong lược đồ feistel cho cấu trúc giống

</div>Trang 19<div class="page_container" data-page="19">

d =m = e (K'g)~1=(034)(234) mod (05)

=> m= (024)

2.3. Kết luận chương.

Trọng tâm của chương II là trình bày sơ lược hệ mật khóa bí mật, hệ mật

khóa cơng khai. Dựa vào các phan tử khả đảo trong vành đa thức có hai lớp kề

xyclic để xây dựng hệ mật trên vành đa thức có hai lớp kề xyclic. Trình bày về q

trình tạo khóa, mã hóa và giải mã. Cũng như đưa ra từng ví dụ cụ thể trên hệ mật

này.

</div>Trang 20<div class="page_container" data-page="20">

CHUONG III. PHAN TÍCH MOT DẠNG TAN CÔNG VA

ĐÁNH GIA SƠ BO TINH AN TOAN, HIEU NANG CUA HE

MAT XAY DUNG TREN VANH DA THUC CO HAI LOP KE

Khi xây dựng một hệ mật người ta thường xem xét tới các tiêu chuân sau:

> Độ mật cần thiết.

> Kích thước khơng gian khóa.

> Tính đơn giản và tốc dộ mã hóa và giải mã.

> Tinh lan truyén sai.

> Tinh mở rộng ban tin.

Việc tan công của thám mã có thê được thực hiện với các gia định: > Tan công chỉ với bản mã.

> Tan công với ban rõ đã biết.

> Tan công với các ban rõ được chon.> Tan công với các ban mã được chọn.

3.1. Phan tích một dang tấn cơng với bản mã được lựa chọn.

Nếu kẻ tan cơng có 2 cặp (mạ, c¡) và (m;c;)

Tuy nhiên, khi có M = 25-1 thé cặp (m, c) kẻ tan công cần một không gian lưu trữ rất lớn dé lưu trữ chúng, đặc biệt là khi sg được thay đổi định kỳ và có

N =2?8-1 — 2° khả năng lựa chọn khóa có thé trong S,,[x]. Thì hệ mật vẫn có thé

an tồn.

</div>