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.
10 trang |
Chia sẻ: vietpd | Lượt xem: 1590 | Lượt tải: 2
Bạn đang xem nội dung tài liệu 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ị, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
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 hoặc e (hoặc 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 phương thức 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 phương thức 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ữu thông tin về khóa chính là bằng chứng để
chứng minh nhận dạng của một người sử dụng. Trong mỗi giao dịch giữa hai người
sử dụng trong hệ thống, máy chủ Kerberos sẽ tạo ra một khóa phiên dùng cho phiên
giao dịch đó.
Có thể tóm lược thủ tục chứng thực của Kerberos như sau (Hình 1.3):
1- Người dùng đăng nhập vào máy con và yêu cầu AS cung cấp thẻ xác nhận
người dùng (Ticket - granting - Ticket).
2- AS kiểm tra quyền truy cập của người dùng trong cơ sở dữ liệu, phát sinh
và mã hóa thẻ xác nhận người dùng và khóa phiên bằng mật khẩu của người dùng,
sau đó gửi cho máy con.
3- Máy con yêu cầu người dùng cung cấp mật khẩu và sử dụng mật khẩu làm
khóa để giải mã thông điệp do AS gửi đến. Sau đó gửi yêu cầu truy xuất dịch vụ có
chứa thông tin về tên người dùng, địa chỉ mạng, thời gian cho TGS.
4- TGS kiểm tra yêu cầu và cung cấp thẻ truy xuất dịch vụ (Service Granting
Ticket) cho máy con.
11
5- Máy con gửi yêu cầu truy xuất dịch vụ cho máy chủ.
6- Máy chủ kiểm tra thẻ truy xuất dịch vụ, quyền truy cập của máy con và
thực hiện chứng thực lẫn nhau với máy con (nếu có yêu cầu).
Hình 1.3: Thủ tục chứng thực Kerberos
Giao thức Kerberos đòi hỏi đồng hồ của tất cả những máy tính liên quan phải
được đồng bộ. Nếu không đảm bảo điều này, cơ chế chứng thực sẽ không hoạt
động. Thiết lập mặc định của giao thức Kerberos là sai lệch giữa các đồng hồ không
quá 10 phút.
Giao thức SSL (Secure Sockets Layer)
Để tạo ra một liên kết giữa client và server, SSL sử dụng giao thức bắt tay
(handshake protocol), đây là giao thức phức tạp nhất của SSL dùng để chứng thực
lẫn nhau, thống nhất các thuật toán xác thực thông điệp (Message Authentication
Code) và mã hóa. Giao thức này cũng được dùng để trao đổi các khóa bí mật dùng
cho mã hóa, xác thực thông điệp và được thực hiện trước khi truyền dữ liệu.
Giao thức bắt tay gồm 4 giai đoạn, được mô tả theo hình sau:
Kerberos
Máy chủ chứng
thực (AS)
Máy chủ cấp
thẻ (TGS)
Máy con (C)
Cấp thẻ xác nhận người dùng
Yêu cầu thẻ xác nhận người dùng
Yêu cầu thẻ truy xuất dịch vụ
Cấp thẻ truy xuất dịch vụ
Máy chủ (S)
Yêu cầu dịch vụ
Cung cấp dịch vụ chứng thực
12
Hình 1.4: Thủ tục bắt tay SSL
Client
client_hello
server_hello
Chứng thực khóa server
Khóa bí mật của server
Yêu cầu cung cấp chứng thực
Kết thúc server_hello
Chứng thực khóa client
Khóa bí mật của client
Xác minh chứng thực khóa
Thay đổi thông số mã
Kết thúc
Thay đổi thông số mã
Kết thúc
Giai đoạn 1:
Thiết lập các thông số bảo mật
như phiên bản của giao thức,
nhận dạng phiên giao dịch, thuật
toán mật mã, phương pháp nén
và số ngẫu nhiên ban đầu
Giai đoạn 2:
Server có thể gửi chứng thực
khóa, trao đổi khóa và yêu cầu
client cung cấp chứng thực khóa
Giai đoạn 3:
Client gửi chứng thực khóa khi
được yêu cầu từ phía server, trao
đổi khóa với server. Client cũng
có thể gửi xác minh chứng thực
khóa công khai cho server
(certificate verification)
Giai đoạn 4:
Thay đổi các thông số của thuật
toán mật mã và kết thúc giao
thức bắt tay.
Server
13
1.3.2. Mô hình dựa vào đồ thị
Trong những năm gần đây nhờ sự hỗ trợ của công nghệ thông tin và máy tính
điện tử, đồ thị càng ngày càng trở thành công cụ hiệu quả, năng động giải quyết các
bài toán trong nhiều lĩnh vực khác nhau. Chẳng hạn, đồ thị có thể sử dụng để giải
các bài toán tối ưu trên mạng, các bài toán về lập lịch, thời khóa biểu, phân bố tần
số cho các trạm phát thanh, truyền hình cũng như xây dựng các hệ mã, thuật toán
dựa trên đồ thị như mã dòng (stream ciphers), mã khối (block ciphers) [13] hay
thuật toán chia sẽ khóa bí mật chung [10].
Bên cạnh việc phát triển các hệ mã, người ta cũng chú ý đến việc xây dựng các
giao thức chứng thực dựa trên các bài toán thuộc lớp NP-Complete trong lý thuyết
đồ thị và đã đạt được nhiều kết quả khả quan. Điển hình đó là giao thức chứng thực
lẫn nhau dựa vào đồ thị đẳng cấu cho mạng không dây (WLAN) của nhóm tác giả
Trần Ngọc Bảo và Nguyễn Đình Thúc [6]. Giao thức đề nghị ngoài việc đảm bảo an
ninh cho mạng máy tính còn có khả năng chống được một số kiểu tấn công phổ
biến, như tấn công lặp lại (replay attacks), tấn công người trung gian (man-in-the-
middle attacks) và tấn công đánh cắp phiên làm việc (session hight-jacking). Hay
dựa vào giao thức Woo-Lam (Woo-Lam protocol), nhóm tác giả XIE Hong-bo, WU
Yuan-cheng, ZHOU Ming-tian đã đề xuất mô hình chứng thực lẫn nhau dựa trên đồ
thị có hướng [16]…
Ngoài ra, dựa vào nguyên tắc hoạt động của giao thức Tri thức trị không (zero-
knowledge protocol) mà càng ngày có nhiều mô hình chứng thực được xây dựng
dựa trên đồ thị, như đồ thị đẳng cấu (graph isomorphism) [7], [9]; đồ thị con đẳng
cấu (subgraph isomorphism) [7]; tô màu đồ thị (graph colourability) [7]…
Và như chúng ta biết, bài toán tìm một chu trình Hamilton cho trước trong một
đồ thị là một bài toán khó thuộc lớp NP-Complete (Định lý 1.4). Tuy nhiên qua
khảo sát cho thấy, việc ứng dụng bài toán trên vào quá trình xây dựng các mô hình
chứng thực lẫn nhau vẫn chưa có nhiều công trình công bố mà chủ yếu mới dừng lại
ở việc ứng dụng chu trình hamilton vào xây dựng các giao thức chứng thực dựa trên
Tri thức trị không [9], hay kết hợp với hệ mã ma trận [5].
14
1.4. Mục tiêu luận văn
Như trên đã phân tích, không tồn tại một thuật toán tất định trong thời gian đa
thức để giải một bài toán thuộc lớp NP-Complete. Do đó, việc tập trung đi sâu vào
nghiên cứu, tìm hiểu các bài toán thuộc lớp NP-Complete, đặc biệt là các bài toán
khó trong lý thuyết đồ thị có ý nghĩa rất lớn trong việc phát triển một số hệ mã cũng
như xây dựng các mô hình chứng thực cho các hệ thống đòi hỏi phải có tính bảo
mật cao.
Dựa vào các yêu cầu trên, luận văn tập trung nghiên cứu những vấn đề sau:
i) Tìm hiểu các mô hình chứng thực người dùng, trong đó tập trung vào các
mô hình chứng thực lẫn nhau (mutual authentication).
ii) Khảo sát, nghiên cứu một số bài toán khó trong lý thuyết đồ thị thuộc lớp
NP-Complete, đặc biệt là bài toán chu trình Hamilton.
iii) Trên cơ sở các mô hình nghiên cứu, luận văn xây dựng giao thức chứng
thực dựa trên một bài toán khó trong lý thuyết đồ thị vừa đảm bảo tính đúng đắn,
tính hiệu quả vừa có khả năng chống được các kiểu tấn công phổ biến, như tấn công
lặp lại (replay attack), tấn công vét cạn (brute-force attack) và tấn công người trung
gian (man-in-the-middle attack).
iv) Xây dựng một chương trình ứng dụng nhằm thực nghiệm và đánh giá giao
thức trên.
1.5. Bố cục luận văn
Ngoài phần mục lục và danh mục các bảng, hình vẽ, tài liệu tham khảo, luận
văn được bố cục thành 4 chương:
Chương 1. Mở đầu
Ở chương này, luận văn trình bày một cách khái quát về khái niệm độ phức
tạp qua các lớp P, NP, NP-Complete. Trên cơ sở đó giới thiệu một số bài toán điển
hình trong lý thuyết đồ thị thuộc lớp NP-Complete.
Chương 2. Cơ sở toán học
15
Trình bày một số khái niệm cơ bản về lý thuyết số học, đại số ma trận và lý
thuyết đồ thị có liên quan đến việc xây dựng giao thức chứng thực ở Chương 3.
Chương 3. Ứng dụng đồ thị Hamilton vào chứng thực
Trong chương này, luận văn sẽ trình bày giao thức chứng thực người dùng dựa
trên chu trình Hamilton. Qua đó phân tích và đánh giá tính đúng đắn, tính khả thi về
mặt lý thuyết của giao thức.
Chương 4. Thực nghiệm và đánh giá
Trên cơ sở những kết quả đạt được, luận văn sẽ tiến hành xây dựng hoàn chỉnh
một ứng dụng chứng thực dựa vào phương pháp chia sẽ bí mật chung nhằm minh
họa cho giao thức được đưa ra ở Chương 3. Qua đó tiến hành thực nghiệm để đánh
giá mức độ hiệu quả về không gian, thời gian và tính an toàn của giao thức làm cơ
sở cho việc đưa ra một số kiến nghị, đề xuất cũng như định hướng cho việc phát
triển tiếp theo của luận văn trong thời gian tới.