Ứng dụng đồ thị hamilton vào chứng thực

32 Chương 3 ỨNG DỤNG ĐỒ THỊ HAMILTON VÀO CHỨNG THỰC Qua khảo sát các mô hình chứng thực lẫn nhau ở Chương 1, chúng ta thấy quá trình chứng thực thường được thực hiện qua nhiều giai đoạn, trong đó có những giai đoạn kiểm tra về quyền truy cập, sinh khóa phiên (Kerberos), có những giai đoạn tiến hành chứng thực lẫn nhau khóa của client và server (SSL)… Đồ thị đủ có hướng Km có m! chu trình Hamilton phân biệt nhau (Định lý 2.9). Việc tìm một chu trình Hamilton đúng bằng chu trình cho trước trong đồ thị Km là một bài toán khó, không thể giải quyết được trong thời gian đa thức. Và cũng từ nghiên cứu một số mô hình chứng thực dựa trên các bài toán khó thuộc lớp NP- Complete trong lý thuyết đồ thị, luận văn đã chọn bài toán chu trình Hamilton để xây dựng giao thức chứng thực người dùng trong môi trường mạng máy tính. 3.1. Giao thức chứng thực Giao thức chứng thực được thực hiện trong luận văn sẽ dựa vào phương thức chứng thực lẫn nhau mô phỏng quá trình chứng thực giữa Client và Server. Client muốn đăng nhập vào Server, trước hết Server kiểm tra xem Client có quyền đăng nhập hay không. Đồng thời, Client cũng kiểm tra xem Server có đúng là Server mà mình cần đăng nhập. Nếu trong quá trình kiểm tra, Client hoặc Server phát hiện bên kia là giả mạo thì lập tức ngắt kết nối. Ngược lại, quá trình chứng thực thành công. 3.2.1. Sinh khóa - n = pq là tích của 2 số nguyên tố lớn phân biệt nhau từ 128 đến 1024 bits (tương ứng n trong khoảng 256 đến 2048 bits). - Đồ thị đủ có hướng Km = (V, E), với: + V = {v1, v2, …, vm} = {1, 2, … , m} là tập đỉnh của đồ thị, |V| = m, m > 1 + E là tập cạnh, được biểu diễn bởi ma trận kề Am×m = (aij)m×m , aij ∈ *nZ , và: aij = 0 nếu không có cạnh (vi, vj) aij ≠ 0 nếu có cạnh (vi, vj) ∀ i, j ∈ [1, m] 33 - Tập ngẫu nhiên U ⊆ V, U = {u1, u2, …, uK}, ui # uj ∀ i, j ∈ [1, K] ∧ i # j (3 ≤ K ≤ m) - StrPass là chuỗi ký tự bất kỳ (giống như mật khẩu). Lúc này, Client và Server sẽ lưu thông tin chung (chỉ có Client và Server biết) gồm 5 giá trị (Uid, StrPass, p, q, U) để làm khóa bí mật (Uid là tên đăng nhập của người dùng - giống như Username), còn đồ thị đủ có hướng Km = (V, E) đóng vai trò như khóa công khai. 3.2.2. Quá trình chứng thực Sau khi phát sinh khóa cho Client, quá trình chứng thực giữa Client và Server được thực hiện theo các bước sau: 1) Bước 1: Client gửi cặp thông tin cho Server - B1.1: Sinh ngẫu nhiên số nguyên tố nC ∈ Zϕ(n) - B1.2: Gửi cặp thông tin cho Server 2) Bước 2: Server kiểm tra UId , tính và gửi D1 cho Client - B2.1: Server kiểm tra UId, nếu không có trong CSDL của Server thì thông báo cho Client UId chưa được đăng ký và kết thúc quá trình chứng thực. Ngược lại, chuyển qua bước B2.2. - B2.2: Sinh ngẫu nhiên số nguyên tố nS ∈ Zϕ(n) sao cho (nS mod m) ≠ (nC mod m) - B2.3: Đặt X = [x1 x2 … xK] là vectơ 1 chiều (1×K), với x1 = nC , x2 = nS , xt ∈ Zn (t = 3,…,K) là các số ngẫu nhiên thoả điều kiện:∀i ≠ j∈ [1, K] thì (xi mod m) ≠ (xj mod m) - B2.4: Tìm ma trận kề Hm×m biểu diễn chu trình Hamilton trong đồ thị Km: i) Gọi hstr là giá trị của hàm băm SHA (256 bits) lên chuỗi ký tự StrPass hstr = SHA256(StrPass) = a[1..64] , với a[i] ∈ {0, 1, 2,… , d, e, f} ii) Tính a = a[1].1663 + a[2].1662 +…+ a[63].161 + a[64].160 iii) Đặt b = NextPrime(a), là số nguyên tố đầu tiên sau số a. iv) For i = 1 to m-1 do hi = (i.b) mod m 34 Khi đó [h1, h2, …, hm-2, hm-1, m, h1] là chu trình Hamilton trong đồ thị Km (xem 3.2.1) và được biểu diễn bởi ma trận kề: Hm×m = (hij)m×m , với: ija nếu có đường đi hi đến hj trong chu trình Hamilton 0 nếu không có đường đi hi đến hj trong chu trình Hamilton - B2.5: Xây dựng ma trận vuông B = (bij )K×K từ ma trận Hm×m theo quy tắc: i) Bỏ đi những hàng trong ma trận Hm×m mà không thuộc tập U (tức trong ma trận Hm×m, với ∀i ∉ U, bỏ đi các phần tử hit với t = [1, m]). ii) Tương ứng với mỗi hàng được bỏ trong ma trận Hm×m, bỏ luôn cột mà tại đó có giá trị ≠ 0 (tức sau khi bỏ phần tử hit , kiểm tra nếu hit ≠ 0 thì bỏ cột t trong ma trận Hm×m). - B2.6: Tính ( ) (( ) mod )Cnij K Kb n× ××= =K K ij K KS s - B2.7: Tính D1 = (X . S) mod n và gửi cho Client 3) Bước 3: Client giải mã và kiểm tra D1, tính và gửi D2 cho Server - B3.1: Tìm ma trận kề H’m×m biểu diễn chu trình Hamilton trong đồ thị Km: i) Gọi h’str là giá trị của hàm băm SHA (256 bits) lên chuỗi ký tự StrPass h’str = SHA256(StrPass) = a’[1..64] , với a’[i] ∈ {0, 1, 2,… , d, e, f} ii) Tính a’ = a’[1].1663 + a’[2].1662 +…+ a’[63].161 + a’[64].160 iii) Đặt b’ = NextPrime(a’), là số nguyên tố đầu tiên sau số a’. iv) For i = 1 to m-1 do h’i = (i.b’) mod m Khi đó [h’1, h’2, …, h’m-2, h’m-1, m, h’1] là chu trình Hamilton trong đồ thị Km (xem 3.2.1) và được biểu diễn bởi ma trận kề: H’m×m = (h’ij)m×m , với: ij'a nếu có đường đi h’i đến h’j trong chu trình Hamilton 0 nếu không có đường đi h’i đến h’j trong chu trình Hamilton - B3.2: Xây dựng ma trận vuông B’= (b’ij )K×K từ ma trận H’m×m theo quy tắc: i) Bỏ đi những hàng trong ma trận H’m×m mà không thuộc tập U (tức trong ma trận H’m×m, với ∀i ∉ U, bỏ đi các phần tử h’it với t = [1, m]). hij = h’ij = 35 ii) Tương ứng với mỗi hàng được bỏ trong ma trận H’m×m, bỏ luôn cột mà tại đó có giá trị ≠ 0 (tức sau khi bỏ phần tử h’it , kiểm tra nếu h’it ≠ 0 thì bỏ cột t trong ma trận H’m×m). - B3.3: Tính ij ( ) (( ' ) mod )C n K K ij K Kc b n× × ×= =K KC - B3.4: Tính C’K×K = (c’ij )K×K theo công thức: c’ji = 0 nếu cij = 0 c’ji = (cij )-1 mod n nếu cij ≠ 0 ⇔ ( c’ji × cij ) ≡ 1 mod n - B3.5: Tính X’ = [x’1 x’2 … x’K] = (D1 . C’) mod n - B3.6: Kiểm tra nếu x’1 ≠ nC thì kết thúc, thông báo quá trình chứng thực bị thất bại. Ngược lại, chuyển qua bước B3.7 (có nS = x’2 ). - B3.7: Tính D’K×K = (d’ij )K×K = (( ' ) mod )Snij K Kb n × - B3.8: Tính D2 = (X’. D’) mod n và gửi cho Server 4) Bước 4: Server giải mã và kiểm tra D2 - B4.1: Tính S’K×K = (s’ij )K×K = (( ) mod )Snij K Kb n × - B4.2: Tính S”K×K = (s”ij )K×K theo công thức: s”ji = 0 nếu s’ij = 0 s”ji = (s’ij )-1 mod n nếu s’ij ≠ 0 ⇔ ( s”ji × s’ij ) ≡ 1 mod n - B4.3: Tính X” = [x”1 x”2 … x”K] = (D2 . S”) mod n - B4.4: Kiểm tra nếu ∃i ∈ [1, K] mà x”i ≠ xi thì kết thúc, gửi thông báo quá trình chứng thực bị thất bại. Ngược lại, thông báo quá trình chứng thực thành công. 5) Bước 5: Client và Server cập nhật lại tập U - B5.1: Client: U = {u1, u2, …, uK} với ui = (x’i mod m) + 1, i = [1, K] - B5.2: Server: U = {u1, u2, …, uK} với uj = (xj mod m) + 1, j = [1, K] Tóm lại, ta có thể mô phỏng quá trình chứng lẫn nhau giữa Client và Server theo sơ đồ sau: 36 Hình 3.1: Sơ đồ chứng thực lẫn nhau giữa Client và Server Ví dụ 3.1: - Cho p = 3, q = 5 n = p.q = 3.5 = 15; ϕ (n) = (p-1)(q-1) = 8 nZ = 15Z = {0, 1, 2, 3, …, 14} * nZ = * 15Z = {1, 2, 4, 7, 8, 11, 13, 14} ( )nϕZ = 8Z = {0, 1, 2, 3, 4, 5, 6, 7} - Đồ thị đủ có hướng K5 = (V, E), với số đỉnh m = 5 + V = {1, 2, 3, 4, 5} + E được biểu diễn bởi ma trận: A5×5 = (aij)5×5 , aij ∈ *15Z Tính D1 = E(nC,n,X,S) Giải mã và kiểm tra D2 Client Server Sinh (nC) D1 Giải mã và kiểm tra D1 D2 Gửi message thông báo quá trình chứng thực thành công/ thất bại Cập nhật tập U Cập nhật tập U Kiểm tra (Uid) Sinh (nS,X) Tính D2 = E(nS,nC,n,X’,D’) 37 A5×5 = 0 7 2 4 1 8 0 1 7 13 1 4 0 8 14 2 8 7 0 11 4 1 7 11 0 ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ - Tập U = {2, 4, 5}, |U| = K = 3 - Uid = “Client” - StrPass = “password” Lúc này khóa bí mật, khóa công khai giữa Client và Server là: + Khóa bí mật: (Uid, StrPass, p, q, U) = (“Client”, “password”, 3, 5, {2, 4, 5}) + Khóa công khai: K5 Quá trình thực hiện chứng thực giữa Client và Server: 1) Bước 1: - B1.1: Sinh nC = 3 - B1.2: Gửi cho Server 2) Bước 2: - B2.1: Server kiểm tra UId. Nếu UId có trong CSDL thì chuyển qua bước B2.2. - B2.2: Sinh nS = 2 (vì 2 mod 5 ≠ 3 mod 5) - B2.3: Đặt X = [x1 x2 x3] = [3 2 9] - B2.4: Tìm ma trận kề H5×5 biểu diễn chu trình Hamilton trong đồ thị K5: i) hstr = SHA256(“password”) = “5e884898da28047151d0e56f8dc6292 773603d0d6aabbdd62a11ef721d1542d8” 5 2 1 3 4 38 ii) Tính a = 5.1663 + e.1662 + 8.1661 + 8.1660 + 4.1659 + 8.1658 + 9.1657 + 8.1656 + d.1655 + a.1654 + 2.1653 + 8.1652 + 0.1651 + 4.1650 + 7.1649 + 1.1648 + 5.1647 + 1.1646 + d.1645 + 0.1644 + e.1643 + 5.1642 + 6.1641 + f.1640 + 8.1639 + d.1638 + c.1637 + 6.1636 + 2.1635 + 9.1634 + 2.1633 + 7.1632 + 7.1631 + 3.1630 + 6.1629 + 0.1628 + 3.1627 + d.1626 + 0.1625 + d.1624 + 6.1623 + a.1622 + a.1621 + b.1620 + b.1619 + d.1618 + d.1617 + 6.1616 + 2.1615 + a.1614 + 1.1613 + 1.1612 + e.1611 + f.1610 + 7.169 + 2.168 + 1.167 + d.166 + 1.165 + 5.164 + 4.163 + 2.162 + d.161 + 8.160 = 42758200014260304871795218010112217441437394933425264440882 844866153524052696 iii) Đặt b = NextPrime(a) = 4275820001426030487179521801011221 7441437394 933425264440882844866153524052763 iv) Có: h1 = 1.b mod 5 = 3 ; h2 = 2.b mod 5 = 1; h3 = 3.b mod 5 = 4 ; h4 = 4.b mod 5 = 2. ⇒ [h1, h2, h3, h4, 5, h1] = [3, 1, 4, 2, 5, 3] là chu trình Hamilton trong đồ thị K5 và được biểu diễn bằng ma trận kề H5×5: H5×5 = 0 0 0 4 0 0 0 0 0 13 1 0 0 0 0 0 8 0 0 0 0 0 7 0 0 ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ - B2.5: Do {1, 3} ∉ U = {2, 4, 5} nên trong ma trận H5×5 bỏ hàng thứ 1 và cột thứ 4 (vì h14 = 4 # 0); bỏ hàng thứ 3 và cột thứ 1 (vì h31 = 1 # 0), ta có: 5 2 1 3 4 39 B3×3 = 0 0 13 8 0 0 0 7 0 ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ - B2.6: Tính S4×4 = (sij)3×3 = 3 3(( ) mod 15)C n ijb × s11 = (0)3 mod 15 = 0 s12 = (0)3 mod 15 = 0 s13 = (13)3 mod 15 = 7 s21 = (8)3 mod 15 = 2 s22 = (0)3 mod 15 = 0 s23 = (0)3 mod 15 = 0 s31 = (0)3 mod 15 = 0 s32 = (7)3 mod 15 = 13 s33 = (0)3 mod 15 = 0 Vậy: S3×3 = 0 0 7 2 0 0 0 13 0 ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ - B2.7: D1 = 3 3( . )mod 15X S × = ([3 2 9] 0 0 7 2 0 0 0 13 0 ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ ) mod 15 = [4 2 6] Gửi D1 cho Client. 3) Bước 3: - B3.1: Tìm ma trận kề H’5×5 biểu diễn chu trình Hamilton trong đồ thị K5: i) h’str = SHA256(“password”) = “5e884898da28047151d0e56f8dc6292 773603d0d6aabbdd62a11ef721d1542d8” 40 ii) Tính a’ = 5.1663 + e.1662 + 8.1661 + 8.1660 + 4.1659 + 8.1658 + 9.1657 + 8.1656 + d.1655 + a.1654 + 2.1653 + 8.1652 + 0.1651 + 4.1650 + 7.1649 + 1.1648 + 5.1647 + 1.1646 + d.1645 + 0.1644 + e.1643 + 5.1642 + 6.1641 + f.1640 + 8.1639 + d.1638 + c.1637 + 6.1636 + 2.1635 + 9.1634 + 2.1633 + 7.1632 + 7.1631 + 3.1630 + 6.1629 + 0.1628 + 3.1627 + d.1626 + 0.1625 + d.1624 + 6.1623 + a.1622 + a.1621 + b.1620 + b.1619 + d.1618 + d.1617 + 6.1616 + 2.1615 + a.1614 + 1.1613 + 1.1612 + e.1611 + f.1610 + 7.169 + 2.168 + 1.167 + d.166 + 1.165 + 5.164 + 4.163 + 2.162 + d.161 + 8.160 = 42758200014260304871795218010112217441437394933425264440882 844866153524052696 iii) Đặt b’ = NextPrime(a’) = 4275820001426030487179521801011221 7441437394 933425264440882844866153524052763 iv) Có: h’1 = 1.b’ mod 5 = 3 ; h’2 = 2.b’ mod 5 = 1; h’3 = 3.b’ mod 5 = 4 ; h’4 = 4.b’ mod 5 = 2 ⇒ [h’1, h’2, h’3, h’4, 5, h’1] = [3, 1, 4, 2, 5, 3] là chu trình Hamilton trong đồ thị K5 và được biểu diễn bằng ma trận kề H’5×5: H’5×5 = 0 0 0 4 0 0 0 0 0 13 1 0 0 0 0 0 8 0 0 0 0 0 7 0 0 ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ - B3.2: Do {1, 3} ∉ U = {2, 4, 5} nên trong ma trận H’5×5 bỏ hàng thứ 1 và cột thứ 4 (vì h’14 = 4 # 0); bỏ hàng thứ 3 và cột 1 (vì h’31 = 1 # 0), có: 5 2 1 34 41 B’3×3 = 0 0 13 8 0 0 0 7 0 ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ - B3.3: Tính C3×3 = (cij)3×3 = 3 3(( ' ) mod 15)C n ijb × . Thực hiện tương tự như tính S3×3, có: C3×3 = 0 0 7 2 0 0 0 13 0 ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ - B3.4: Tính C’3×3 = (c’ij)3×3: c11 = 0 ⇒ c’11 = 0 c12 = 0 ⇒ c’21 = 0 c22 = 0 ⇒ c’22 = 0 c23 = 0 ⇒ c’32 = 0 c31 = 0 ⇒ c’13 = 0 c33 = 0 ⇒ c’33 = 0 c13 = 7 ⇒ c’31 = (7)-1 mod 15 ⇒ c’31 = 13 c21 = 2 ⇒ c’12 = (2)-1 mod 15 ⇒ c’12 = 8 c32 = 13 ⇒ c’23 = (13)-1 mod 15 ⇒ c’23 = 7 Vậy: C’3×3 = 0 8 0 0 0 7 13 0 0 ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ - B3.5: X’ = (D1.C’) mod 15 = ([4 3 6] 0 8 0 0 0 7 13 0 0 ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ ) mod 15 = [3 2 6] - B3.6: Kiểm tra thấy: x’1 = nC = 3 nên chuyển qua bước B3.7 (có nS = 2). - B3.7: Tính D’3×3 = (d’ij)3×3 = 3 3(( ' ) mod 15)S n ijb × Với B’3×3 có được ở bước B3.2: 42 B’3×3 = 0 0 13 8 0 0 0 7 0 ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ Ta có: d’11 = (0)2 mod 15 = 0 d’12 = (0)2 mod 15 = 0 d’13 = (13)2 mod 15 = 4 d’21 = (8)2 mod 15 = 1 d’22 = (0)2 mod 15 = 0 d’23 = (0)2 mod 15 = 0 d’31 = (0)2 mod 15 = 0 d’32 = (7)2 mod 15 = 4 Vậy: D’3×3 = 0 0 4 1 0 0 0 4 0 ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ - B3.8: D2 = (X’.D’) mod 15 = ([3 2 6] 0 0 4 1 0 0 0 4 0 ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ ) mod 15 = [2 9 12] Gửi D2 cho Server 4) Bước 4: - B4.1: Tính S’3×3 = (s’ij )3×3 = 3 3(( ) mod 15)S n ijb × Với B3×3 có được ở bước B2.5: 43 B3×3 = 0 0 13 8 0 0 0 7 0 ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ Thực hiện tương tự như tính D’3×3, có: S’3×3 = 0 0 4 1 0 0 0 4 0 ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ - B4.2: Tính S”3×3 = (s”ij )3×3: s’11 = 0 ⇒ s”11 = 0 s’12 = 0 ⇒ s”21 = 0 s’22 = 0 ⇒ s”22 = 0 s’23 = 0 ⇒ s”32 = 0 s’31 = 0 ⇒ s”13 = 0 s’33 = 0 ⇒ s”33 = 0 s’13 = 4 ⇒ s”31 = (4)-1 mod 15 ⇒ s”31 = 4 s’21 = 1 ⇒ s”12 = (1)-1 mod 15 ⇒ s”12 = 1 s’32 = 4 ⇒ s”23 = (4)-1 mod 15 ⇒ s”23 = 4 Vậy: S”3×3 = 0 1 0 0 0 4 4 0 0 ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ - B4.3: X” = (D2 . S”) mod 15 = ([2 9 12] 0 1 0 0 0 4 4 0 0 ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ ) mod 15 = [3 2 6] - B4.4: Kiểm tra thấy: ∀i ∈ [1, 3] luôn có x”i = xi. Vậy quá trình chứng thực thành công, cho phép thực hiện kết nối giữa Client và Server. 44 5) Bước 5: - B5.1: Client: U = {u1, u2, u3} = {4, 3, 2} - B5.2: Server: U = {u1, u2, u3} = {4, 3, 2} 3.2. Phân tích giao thức 3.2.1. Tính đúng đắn Trước hết, chúng ta thấy hàm băm 256 bits SHA (Secure Hash Algorithm) dùng để chuyển một đoạn dữ liệu nhất định thành một đoạn dữ liệu có chiều dài không đổi (256 bits) với xác suất khác biệt cao. Thuật toán này được đánh giá là “an toàn” bởi các lý do sau: - Không thể tính toán ngược từ giá trị đầu ra được tạo bởi hàm băm SHA để biết giá trị đầu vào. - Việc tìm hai đoạn dữ liệu nhất định có cùng kết quả được tạo bởi hàm băm SHA là không khả thi. Bất cứ thay đổi nào trên đoạn dữ liệu gốc, dù nhỏ, cũng sẽ tạo nên một giá trị băm hoàn toàn khác với xác suất rất cao. Như vậy, với giao thức được xây dựng theo các bước ở nội dung 3.2, ta thấy: Tương ứng mỗi giá trị đầu vào khác nhau, hàm băm SHA luôn cho ra một kết quả khác nhau. Do đó, cùng một giá trị của StrPass, ở bước B2.4 và B3.1 ta luôn có: hstr = h’str ⇒ a = a’ ⇒ b = NextPrime(a) = NextPrime(a’) = b’. ⇒ ∀ i ∈ (0, m) thì hi = i.b mod m = i.b’ mod m = h’i (1) Vì 0 < hi = i.b mod m < m và hi # hj với ∀ i, j ∈ (0, n) ∧ i # j (Bổ đề 2.1). Suy ra, {h1, h2, …, hm-2, hm-1, m} sẽ là một hoán vị của tập {1, 2, 3,..., m} hay nói cách khác h1, h2, …, hm-2, hm-1, m có thể xem là m đỉnh của đồ thị Km. Vì Km là đồ thị đủ có hướng nên nó có chu trình Hamilton (Định lý 2.8) và luôn tồn tại đường đi giữa hai đỉnh phân biệt bất kỳ trong Km, tức ∀i, j ∈ [1, m] ∧ i # j thì (hi, hj) # 0. Suy ra [h1, h2, …, hm-2, hm-1, m, h1] là một chu trình Hamilton trong Km (2). 45 Tương tự, [h’1, h’2, …, h’m-2, h’m-1, m, h’1] cũng là một chu trình Hamilton trong Km (3). Từ (1), (2), (3) ⇒ 2 chu trình trên trùng nhau ⇒ Hm×m = H’m×m Do đó, ở bước B2.5 và B3.2 có: BK×K = B’K×K (4) và mỗi hàng, mỗi cột của ma trận BK×K, B’K×K chỉ có duy nhất một giá trị thuộc *nZ (tức khác 0), các giá trị còn lại đều bằng 0 (Bổ đề 2.2). Ở bước B2.6 và B3.3, có: SK×K = CK×K , vì: SK×K = (sij)K×K = (( ) mod )Cnij K Kb n × =(( ' ) mod )Cnij K Kb n × = (cij)K×K = CK×K ⇒ SK×K , CK×K là ma trận khả nghịch (Định lý 2.6). ⇒ ở bước B3.4, ma trận C’K×K = (c’ij )K×K, với: c’ji = 0 nếu cij = 0 c’ji = (cij )-1 mod n nếu cij ≠ 0 ⇔ ( c’ji × cij ) ≡ 1 mod n là nghịch đảo của ma trận CK×K, tức C’K×K = (CK×K )-1 = (SK×K)-1 (Định lý 2.7) ⇒ ở bước B3.5: X’ = D1.C’ mod n = D1.C-1 mod n = (X.S)S-1 mod n = X nên ở bước B3.6, nếu Client kiểm tra thấy x’1 # nC thì chứng tỏ D1 đã bị thay đổi hoặc bị giả mạo trên đường truyền. Ngược lại, D1 chưa bị thay đổi hay giả mạo. Mặt khác, ở bước B3.7 và B4.1 có: D’K×K = S’K×K , vì: D’K×K = (d’ij )K×K = (( ' ) mod )Snij K Kb n × =(( ) mod )Snij K Kb n × = (s’ij)K×K = S’K×K ⇒ ở bước B4.2, ma trận S” = (s”ij )K×K , với: s”ji = 0 nếu s’ij = 0 s”ji = (s’ij )-1 mod n nếu s’ij ≠ 0 ⇔ ( s”ji × s’ij ) ≡ 1 mod n là nghịch đảo của ma trận S’K×K, tức S”K×K = (S’K×K)-1 = (D’K×K)-1 (Định lý 2.7) ⇒ ở bước B4.3: X” = D2.S” mod n = (X’.D’)D’-1 mod n = X Nên ở bước B4.4, nếu Server kiểm tra thấy X” # X’ thì chứng tỏ D2 đã bị thay đổi hoặc bị giả mạo trên đường truyền. Ngược lại, D2 chưa bị thay đổi hay giả mạo. Ngoài ra, do xi mod m # xj mod m với ∀ i # j ∈ [1, K] nên ở Bước 5 ta cũng có ui # uj với ∀ i # j ∈ [1, K]. 46 Tóm lại, nếu ở bước B3.6 và B4.4, Client và Server kiểm tra không phát hiện thấy sự khác biệt giữa X’, X và X”, X thì quá trình chứng thực được thực hiện thành công. Ngược lại, Client hoặc Server phát hiện bên kia là giả mạo thì lập tức ngắt kết nối. 3.2.2. Tính khả thi Giao thức được xây dựng như trên ngoài việc đảm bảo tín đúng đắn của thuật toán còn có khả năng chống lại đượ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à người trung gian (man- in-the-middle attack). - Đối với tấn công lặp lại: Giả sử kẻ tấn công có thể nghe trộm hoặc chặn được các thông điệp gửi trên đường truyền như ma trận D1, D2, số nguyên tố nC ở các phiên chứng thực trước của Client và Server. Khi thực hiện tấn công bằng phương pháp này, kẻ tấn công phải gửi lại những thông điệp trên cho Client và Server. Tuy nhiên trong mỗi phiên chứng thực, Client và Server đều sinh mới ngẫu nhiên các giá trị nC, nS và giả sử n’C, n’S có trùng với các giá trị phát sinh lần trước nhưng do giá trị của tập U luôn được cập nhật sau mỗi lần chứng thực thành công nên ma trận D’1, D’2 chắc chắn sẽ khác với ma trận D1, D2 trước đó. Vì vậy, Client và Server sẽ dễ dàng nhận ra được kẻ tấn công và ngắt kết nối. - Đối với tấn công vét cạn: Để thực hiện được phương pháp này, kẻ tấn công phải tìm ra được chu trình Hamilton mà Client và Server sử dụng trong quá trình chứng thực cũng như tập ngẫu nhiên U, ma trận B. Với đồ thị đủ có hướng Km có m đỉnh, ta có m! chu trình Hamilton phân biệt nhau (Định lý 2.9). Do ma trận B được sinh dựa vào các giá trị của tập U và chu trình Hamilton H. Mà U ⊆ V, |U| = K, |V| = m nên sẽ có )!(! ! KmK mC Km −= tập U khác nhau. Vì vậy, số ma trận B có thể là ! Kmm C× . 47 Với m càng lớn thì số chu trình Hamilton và ma trận B sẽ rất lớn. Chẳng hạn, m = 20, K = 10 ta có: m! = 20! = 2.432.902.008.176.640.000 chu trình Hamilton. ! Kmm C× = 1020!20 C× = 449.493.243.422.683.299.840.000 ma trận B. Giả sử với việc kiểm tra thử - sai 1 chu trình Hamilton và 1 ma trận B hết 1μs thì phải mất khoảng 77.146 năm để vét cạn hết chu trình Hamilton và 14.253.337.247 năm để vét cạn hết ma trận B. Do đó, việc dùng thuật toán vét cạn để tìm ra đúng chu trình Hamilton được sinh bởi Client, Server và ma trận B sẽ vô cùng khó khăn. Cho nên có thể nói giao thức chống được kiểu tấn công bằng vét cạn. - Tấn công người trung gian: Giả sử ở bước B1.1, kẻ tấn công chặn và lấy được số nguyên tố nC, thay thế bằng số nguyên tố nM rồi gửi cho Server. Trong Bước 2, Server sẽ dựa vào nM, nS, ma trận B để tính ma trận D1 và gửi cho kẻ tấn công. Kẻ tấn công gửi D1 cho Client và Client giải mã D1 sẽ phát hiện D1 bị giả mạo ở bước B3.6. Tương tự, giả sử kẻ tấn công chặn và lấy được ma trận D2 từ Client ở bước B3.8, sửa D2 thành D’2 và gửi cho Server. Server giải mã D’2 và dễ dàng phát hiện ra kẻ tấn công ở bước B4.4. Vì vậy, kẻ tấn công sẽ bị ngắt kết nối bởi Cl