Download miễn phí Luận văn Nghiên cứu và xây dựng các mô hình chứng thực dựa trên các bài toán khó của lý thuyết đồ thị
MỤC LỤC
MỤC LỤC.2
DANH MỤC CÁC BẢNG.4
DANH MỤC CÁC HÌNH VẼ, ĐỒTHỊ.5
Chương 1. MỞ ĐẦU.6
1.1. Các lớp bài toán .6
1.2. Các bài toán khó trong lý thuyết đồthị.8
1.3. Các mô hình chứng thực lẫn nhau .9
1.3.1. Mô hình dựa vào hệmã .10
1.3.2. Mô hình dựa vào đồthị.13
1.4. Mục tiêu luận văn .14
1.5. Bốcục luận văn.14
Chương 2. CƠSỞTOÁN HỌC.16
2.1. Lý thuyết sốhọc và đại sốma trận .16
2.1.1. Một sốkhái niệm cơbản .16
2.1.2. Phép chia dưtrên m Z .17
2.1.3. Hàm phi-Euler .19
2.1.4. Một sốkết quảvề đại sốma trận.20
2.2. Lý thuyết đồthị.26
2.2.1. Định nghĩa đồthị.26
2.2.2. Đường đi và chu trình Hamilton.27
2.2.3. Đồthị đủcó hướng .29
Chương 3. ỨNG DỤNG ĐỒTHỊHAMILTON VÀO CHỨNG THỰC .32
3.1. Giao thức chứng thực.32
3.2.1. Sinh khóa .32
3.2.2. Quá trình chứng thực .33
3.2. Phân tích giao thức.44
3.2.1. Tính đúng đắn.44
3.2.2. Tính khảthi.46
Chương 4. THỰC NGHIỆM VÀ ĐÁNH GIÁ .48
4.1. Mục tiêu của thực nghiệm .48
4.2. Công cụvà môi trường hoạt động .49
4.3. Đánh giá kết quảthực nghiệm .49
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN .54
DANH MỤC TÀI LIỆU THAM KHẢO .55
PHỤLỤC.57
http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2013-10-26-luan_van_nghien_cuu_va_xay_dung_cac_mo_hinh_chung.wmWWZOPKa8.swf /tai-lieu/de-tai-ung-dung-tren-liketly-42519/Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung:
6
Chương 1. MỞ ĐẦU
Ngày nay, cùng với sự phát triển mạnh mẽ của khoa học và công nghệ, đặc
biệt là máy tính, người ta có khả năng giải quyết được nhiều bài toán rất phức tạp.
Tuy nhiên, còn những vấn đề là “không giải được” cho dù kỹ thuật máy tính có phát
triển và cũng có những vấn đề được xem là “quá phức tạp”, vượt mọi khả năng tính
toán thực tế vì mất quá nhiều thời gian. Việc nghiên cứu về độ phức tạp của thuật
toán đã cho phép chúng ta phân loại được các lớp bài toán theo từng mức độ phức
tạp khác nhau, và chỉ ra ranh giới giữa các lớp bài toán giải được và những lớp bài
toán không thể giải được trong thời gian đa thức.
1.1. Các lớp bài toán
Khái niệm thuật toán mà chúng ta sử dụng cho đến nay có tính chất là, kết quả
thực hiện mỗi phép toán được xác định duy nhất. Thuật toán với tính chất đó được
gọi là thuật toán tất định (deterministic algorithm). Bên cạnh đó, có những thuật
toán mà kết quả của nó không phải là một giá trị được xác định duy nhất mà là một
tập hữu hạn các giá trị được gọi là thuật toán không tất định (nondeterministic
algorithm), chẳng hạn như các thuật giải ngẫu nhiên, thuật giải heuristic…
Dựa vào thuật toán tất định và không tất định, ta có các lớp bài toán sau:
- Lớp P (Polynomial) bao gồm tất cả các bài toán giải được bằng thuật toán tất
định trong thời gian đa thức.
- Lớp NP (Non Derterministic Polynomial) bao gồm tất cả các bài toán có thể
giải được bởi thuật toán không tất định trong thời gian đa thức.
Rõ ràng thuật toán tất định là trường hợp đặc biệt của thuật toán không tất
định, do đó lớp P là lớp con của lớp NP.
Cho L1 và L2 là hai bài toán. Ta nói L1 dẫn về L2, ký hiệu L1 ∝ L2, nếu bất kỳ
thuật toán tất định trong thời gian đa thức giải được L2 thì cũng có thể được dùng để
giải L1.
7
Dễ thấy quan hệ “dẫn về” có tính bắc cầu, có nghĩa là nếu L1 ∝ L2 và L2 ∝ L3
thì L1 ∝ L3.
- Một bài toán L là NP-Hard nếu với mọi bài toán L’ thuộc NP ta có L’ ∝ L.
- Một bài toán L là NP-Complete nếu L thuộc NP và L là NP-Hard.
Như vậy, một bài toán là NP-Complete có thể giải được trong thời gian đa
thức nếu và chỉ nếu tất cả các bài toán NP-Complete khác giải được trong thời gian
đa thức. Nếu một bài toán NP-Hard giải được trong thời gian đa thức thì tất cả các
bài toán NP-Complete giải được trong thời gian đa thức. Người ta đã chỉ ra rằng,
mọi bài toán NP-Complete đều là NP-Hard nhưng ngược lại, một bài toán NP-Hard
không nhất thiết là NP-Complete.
Tóm lại, ta có mối quan hệ giữa các lớp P, NP và P, NP, NP-Complete (NPC)
như sau:
Hình 1.1: Mối quan hệ giữa lớp P và NP
Hình 1.2: Mối quan hệ giữa lớp P, NP và NPC
NP
P
NP
NP
P
8
1.2. Các bài toán khó trong lý thuyết đồ thị
Các lớp bài toán NP-Complete là rất rộng. Hầu hết các bài toán nổi tiếng mà
chúng ta đã biết như bài toán người bán hàng, bài toán balô, các bài toán tổ hợp,
phân tích ra thừa số… đều là các bài toán khó. Sau đây là một số bài toán khó thuộc
lớp NP-Complete trong lý thuyết đồ thị:
Bài toán phủ đỉnh (Vertex-Cover)
Bài toán được phát biểu như sau:
- Cho đồ thị G = (V, E) và số k ∈ *N sao cho k ≤ |V|
- Hỏi tồn tại hay không một tập con V’ của V sao cho |V’| < k và mỗi cạnh {u,
e} ∈ E thì một trong 2 đỉnh u hay e (hay cả đỉnh u và e ) phải thuộc V’.
Định lý 1.1: Bài toán phủ đỉnh là bài toán NP-Complete [1], [12].
Bài toán đồ thị con đủ (Clique Problem)
Bài toán được phát biểu như sau:
- Cho đồ thị G = (V, E) và k ∈ *N thoả mãn k ≤ |V|
- Hỏi tồn tại hay không một tập con V’ của V sao cho ⎜V’⎜≥ k mà mọi cặp
đỉnh trong V’ đều được nối bởi 1 cạnh trong E.
Định lý 1.2: Bài toán đồ thị con đủ là bài toán NP-Complete [12].
Bài toán đồ thị con đẳng cấu (Subgraph Isomorphism)
- Cho hai đồ thị: G1 = (V1, E1) và G2 = (V2, E2).
- Hỏi G1 có chứa đồ thị con G’ = (V’, E’) đẳng cấu với đồ thị G2, tức tồn tại
tập con V’ ⊆ V, E’ ⊆ E thỏa |V’| = |V2|, |E’| = |E2| và một song ánh f : V2 → V’ sao
cho ∀ (u, v) ∈ E2 khi và chỉ khi {f(u), f(v)} ∈ E’.
Định lý 1.3: Bài toán đồ thị con đẳng cấu là bài toán NP-Complete [12].
Bài toán chu trình Hamilton (Hamilton Cycle)
Chu trình Hamilton là chu trình sơ cấp đi qua tất cả các đỉnh của đồ thị (xem
Định nghĩa 2.15 – tr28).
Bài toán được phát biểu như sau:
- Cho đồ thị G = (V, E) có chu trình Hamilton H.
9
- Tìm trong đồ thị G một chu trình Hamilton đúng bằng chu trình H đã cho.
Định lý 1.4: Bài toán tìm một chu trình Hamilton cho trước là bài toán NP-
Complete [12].
Bài toán người bán hàng (Traveling Salesman)
Cho đồ thị G và 1 số k nguyên, mỗi cạnh e của G có một trọng số nguyên c(e).
Vấn đề đặt ra là có tồn tại một chu trình đi qua tất cả các đỉnh của G (mỗi đỉnh đúng
một lần) mà tổng trọng số các cạnh đã đi qua không vượt quá k?
Ta phát biểu lại bài toán như sau:
- Cho tập n thành phố C = {C1, C2, …, Cn} với khoảng cách
d(Ci, Cj) ∈ Z+ và một số nguyên dương k
- Hỏi có tồn tại một hoán vị π trên {1, 2, …, n} sao cho:
∑−
=
1
1
n
i
d(Cπ(i), Cπ(i+1)) + d(Cπ(m), Cπ(1)) ≤ k hay không?
Định lý 1.5: Bài toán người bán hàng là bài toán NP-Complete [1], [12].
1.3. Các mô hình chứng thực lẫn nhau
Chứng thực (Authentication) là một thủ tục có chức năng xác minh nhận dạng
(identity) của một đối tượng trước khi trao quyền truy xuất cho đối tượng này một
tài nguyên nào đó.
Có hai cách chứng thực phổ biến: Chứng thực một chiều (one way
authentication) và chứng thực hai chiều hay còn gọi là chứng thực lẫn nhau (mutual
authentication).
Chứng thực một chiều chỉ cung cấp cơ chế để một đối tượng (thường là máy
chủ) kiểm tra nhận dạng của đối tượng kia (người dùng) mà không cung cấp cơ chế
kiểm tra ngược lại, tức không cho phép người dùng kiểm tra nhận dạng của máy
chủ. Do đó, người sử dụng không có khả năng nhận biết được đây là máy chủ thật
hay giả mạo.
Chứng thực hai chiều cho phép hai đối tượng trong giao tác chứng thực lẫn
nhau, cho nên tính chính xác của quá trình chứng thực được đảm bảo.
10
Với những ưu điểm của cách chứng thực lẫn nhau mà hiện nay đã có
một số mô hình chứng thực lẫn nhau đang được nghiên cứu và ứng dụng như mô
hình dựa vào hệ mã, mô hình dựa vào đồ thị…
1.3.1. Mô hình dựa vào hệ mã
Giao thức Kerberos
Kerberos là một giao thức dùng để chứng thực trong các mạng máy tính hoạt
động trên đường truyền không an toàn với mục đích chống lại việc nghe lén hay gửi
lại các gói tin cũ và đảm bảo chứng thực lẫn nhau cho client và server.
Kerberos sử dụng một bên thứ ba tham gia vào quá trình chứng thực gọi là
"Trung tâm phân phối khóa" (Key Distribution Center - KDC). KDC bao gồm hai
chức năng: "Máy chủ xác thực" (Authentication Server - AS) và "Máy chủ cung cấp
thẻ" (Ticket Granting Server - TGS). "Thẻ" trong hệ thống Kerberos chính là các
chứng thực chứng minh nhận dạng của người sử dụng.
Mỗi người sử dụng (cả client và server) trong hệ thống chia sẻ một khóa
chung với máy chủ Kerberos. Việc sở h...
