Luận án Nghiên cứu phát triển giao thức trao đổi khóa an toàn

i gian của phép tính nghịch đảo modulo. + 𝑇𝐶𝑅𝑇 là độ phức tạp thời gian của phép tính đồng dư Trung Hoa. Bảng 2.1 so sánh độ phức tạp tính toán của hai lược đồ mới đề xuất và hai lược đồ của Ismail [26] [27]. Bảng 2.1. So sánh độ phức tạp thời gian Độ phức tạp thời gian (lược đồ thứ nhất) Độ phức tạp thời gian (lược đồ thứ hai) Độ phức tạp thời gian [26] Độ phức tạp thời gian [27] Sinh khóa 𝑻𝑬𝑿𝑷 𝑻𝑬𝑿𝑷 + 𝑻𝑰𝑵𝑽 𝑻𝑬𝑿𝑷 + 𝑻𝑰𝑵𝑽 𝑻𝑬𝑿𝑷 + 𝑻𝑰𝑵𝑽 Sinh chữ ký 𝑻𝑬𝑿𝑷 + 𝑻𝑴𝑼𝑳 +𝑻𝑪𝑹𝑻 + 𝑻𝑯 𝟐𝑻𝑬𝑿𝑷 + 𝑻𝑴𝑼𝑳 +𝑻𝑯 5𝑇𝐸𝑋𝑃 +3𝑇𝑀𝑈𝐿 + 𝑇𝐻 𝑇𝐸𝑋𝑃 + 3𝑇𝑀𝑈𝐿 +𝑇𝐻 Xác thực chữ ký 𝟑𝑻𝑬𝑿𝑷 + 𝑻𝑴𝑼𝑳 +𝑻𝑯 𝟑𝑻𝑬𝑿𝑷 + 𝑻𝑴𝑼𝑳 +𝑻𝑯 𝟓𝑻𝑬𝑿𝑷 +𝟐𝑻𝑴𝑼𝑳 + 𝑻𝑯 𝟒𝑻𝑬𝑿𝑷 +𝟐𝑻𝑴𝑼𝑳 + 𝑻𝑯 2.2. Phát triển giao thức trao đổi khóa có xác thực dựa trên hai bài toán khó Như đã trình bày, giao thức trao đổi khóa công khai Diffie–Hellman (DHKE) không đảm bảo xác thực giữa hai bên tham gia giao thức [64]. Từ thực tế này, đã xuất hiện hướng nghiên cứu mới nhằm phát triển các giao thức trao đổi khóa dựa trên sự tích hợp giao thức DHKE và lược đồ chữ ký số. Giao thức được đề xuất theo hướng này kết hợp được các ưu điểm của DHKE và lược đồ chữ ký số khi triển khai ứng dụng trong thực tiễn. Định nghĩa 2: Một giao thức trao đổi khóa được gọi là an toàn dựa trên hai bài toán khó HP1 và HP2 nếu việc tìm được khóa thỏa thuận theo giao thức và việc giả mạo để thực hiện này với người trong hệ thống đều cần phải giải đồng thời hai bài toán nói trên. 53 2.2.1. Một số phát triển giao thức trao đổi khóa an toàn Giao thức trao đổi khóa của Arazi: Năm 1993, Arazi là người đầu tiên phát triển giao thức trao đổi khóa theo hướng tích hợp giao thức DHKE với lược đồ chữ ký số DSA [7]. Giao thức này dùng các khóa công khai chỉ sử dụng một lần (one–time), còn gọi là khóa công khai ngắn hạn (ephemeral) cho giao thức DHKE. Ngoài ra, các khóa công khai ngắn hạn được ký bằng cách sử dụng lược đồ chữ ký số DSA để xác thực các khóa này. Mô tả giao thức: Các tham số công khai (𝑝, 𝑞, 𝑔) được xác định như cách thiết lập tham số hệ thống của lược đồ chữ ký số DSA [2]. Cặp khóa bí mật/công khai của A là (𝑥𝐴, 𝑦𝐴) và cặp khóa tương ứng của B là (𝑥𝐵, 𝑦𝐵) (Hình 2.1). Hình 2.1. Giao thức trao đổi khóa Arazi 54 Để tiết kiệm băng thông, giao thức Arazi có thể được thay đổi bằng cách A và B trao đổi (𝑟𝐴, 𝑠𝐴) và (𝑟𝐵, 𝑠𝐵) thay vì trao đổi (𝑅𝐴, 𝑠𝐴) và (𝑅𝐵, 𝑠𝐵). Đánh giá giao thức: Năm 1994, Nyberg và Rueppel chỉ ra rằng giao thức của Arazi không có thuộc tính về sự an toàn dựa trên khóa đã biết [30]. Các khóa bí mật ngắn hạn được chia sẻ có thể được tính từ khóa bí mật dài hạn và các thông tin không bí mật khác. Một số sửa đổi của L. Harn trên giao thức trao đổi khóa Arazi: Năm 1995, L. Harn và các cộng sự đề xuất sửa đổi giao thức trao đổi khóa của Arazi [33]. Thay vì phân phối một khóa công khai đơn lẻ trong mỗi phiên giao tiếp, nhóm L. Harn đề xuất phân phối nhiều khóa công khai trong mỗi phiên [34]. Mô tả giao thức: Các thông tin công khai sẽ được thỏa thuận bởi các bên tham gia giao thức như sau: - 𝑝 là một số nguyên tố lớn thỏa mãn 2511 < 𝑝 < 2512 - 𝑞 là một ước số nguyên tố của 𝑝 − 1 thỏa mãn 2159 < 𝑝 < 2160 - Chọn 𝑔 = 𝛼(𝑝−1)/𝑞 𝑚𝑜𝑑 𝑝, với 𝑔 ∈ 𝑍𝑝 ∗ thỏa mãn: 1 < 𝑔 < 𝑝 và 𝑔𝑞 𝑚𝑜𝑑 𝑝 = 1, ở đây 𝛼 ∈ 𝑍𝑝 ∗ . - 𝑥𝑖 là khóa bí mật của người dùng 𝑖, thỏa mãn 2 159 < 𝑥𝑖 < 2 160 - 𝑦𝑖 là khóa công khai tương ứng của người dùng 𝑖, 𝑦𝑖 = 𝑔 𝑥𝑖 𝑚𝑜𝑑 𝑝 - 𝐻 là một hàm băm an toàn (SHA–1) đưa ra bởi NIST. Trong đó (𝑝, 𝑞, 𝑔, 𝑦𝑖) là các giá trị công khai và 𝑥𝑖 là khóa bí mật. Harn giả sử rằng A muốn chia sẻ ba khóa phiên bí mật với B. Giao thức của Harn hoạt động như mô tả trong Hình 2.2. 55 Hình 2.2. Giao thức trao đổi khóa L. Harn Đánh giá độ an toàn của giao thức: Harn đánh giá độ an toàn của giao thức trên theo cách thức tấn công dựa trên khóa đã biết (known–key attack) mà Nyberg và Rueppel đã đưa ra. Chúng ta đã biết, kết thúc giao thức trên thu được ba khóa bí mật được chia sẻ giữa A và B như sau: + 𝐾𝐴𝐵1 = 𝑚𝐵1 𝑣1 𝑚𝑜𝑑 𝑝 + 𝐾𝐴𝐵2 = 𝑚𝐵2 𝑣2 𝑚𝑜𝑑 𝑝 + 𝐾𝐴𝐵3 = 𝑚𝐵1 𝑣2 𝑚𝑜𝑑 𝑝 Trong đó: 𝑣1 + 𝑣2 = 𝑠𝐴 −1[𝐻(𝑚𝐴1||𝑚𝐴2)] + 𝑥𝐴𝑟𝐴 𝑚𝑜𝑑 𝑞 (2.1) 𝑤1 + 𝑤2 = 𝑠𝐵 −1[𝐻(𝑚𝐵1|| 𝑚𝐵2)] + 𝑥𝐵𝑟𝐵 𝑚𝑜𝑑 𝑞 (2.2) 56 Nhân hai vế của hai phương trình (2.1) và (2.2) ta có phương trình sau: 𝑣1𝑤1 + 𝑣1𝑤2 + 𝑣2𝑤1 + 𝑣2𝑤2 = 𝑠𝐴 −1𝑠𝐵 −1[𝐻(𝑚𝐴1, 𝑚𝐴2) 𝐻(𝑚𝐵1, 𝑚𝐵2) + 𝐻(𝑚𝐴1, 𝑚𝐴2)𝑥𝐵𝑟𝐵 + 𝐻(𝑚𝐵1, 𝑚𝐵2)𝑥𝐴𝑟𝐴 +𝑥𝐴𝑟𝐴𝑥𝐵𝑟𝐵] 𝑚𝑜𝑑 𝑞 (2.3) Nhân hai vế của phương trình (2.3) với 𝑠𝐴𝑠𝐵, sau đó nâng lũy thừa với hệ số 𝑔, số mũ là hai vế của phương trình thu được, ta được phương trình sau: (𝐾𝐴𝐵1𝐾𝐴𝐵2𝐾𝐴𝐵3𝑔 𝑣1𝑤2)𝑠𝐴𝑠𝐵 = 𝑔𝐻(𝑚𝐴1,𝑚𝐴2)𝐻(𝑚𝐵1,𝑚𝐵2) 𝑦𝐵 𝐻(𝑚𝐴1,𝑚𝐴2)𝑟𝐵𝑦𝐴 𝐻(𝑚𝐵1,𝑚𝐵2)𝑟𝐴(𝑔𝑥𝐴𝑥𝐵)𝑟𝐴𝑟𝐵 𝑚𝑜𝑑 𝑝 (2.4) Xem xét dưới góc độ tấn công dựa trên khóa đã biết, do 𝑔𝑣1𝑤2 không bao giờ được dùng làm khóa phiên bí mật, tất cả các tham số trong (2.4) đều được biết công khai hoặc được gửi giữa các bên tham gia giao thức ngoại trừ 𝑔𝑣1𝑤2 và 𝑔𝑥𝐴𝑥𝐵 nên dù đối phương có biết được các khóa 𝐾𝐴𝐵1, 𝐾𝐴𝐵2, 𝐾𝐴𝐵3 trong một phiên truyền thông thì cũng không thể tính được các khóa này trong các phiên khác. Vì vậy, phương pháp tấn công dựa trên khóa đã biết không thể thực hiện thành công trong giao thức của L. Harn. Giao thức này cho phép trao đổi 𝑛 cặp khóa công khai giữa hai bên tham gia giao thức và xác lập được (𝑛2 − 1) khóa phiên bí mật. Ngoài ra, nó cung cấp thêm tính chất an toàn là chống lại tấn công dựa trên khóa đã biết. Giao thức trao đổi khóa Phan: Năm 2005, Phan đã chỉ ra rằng giao thức của Harn không thể cung cấp hai tính chất về chuẩn bảo mật mà các giao thức cần có đó là an toàn phía trước (forward secrecy) và làm mới khóa (key freshness) [52]. Không có tính chất an toàn về phía trước: Trong giao thức của Harn, khóa phiên theo hướng từ A tới B được tính bởi A như sau: 𝐾𝐴𝐵 = 𝑦𝐵 𝑣 𝑚𝑜𝑑 𝑝 (= 𝑔𝑥𝐵𝑣 𝑚𝑜𝑑 𝑝) (2.5) Trong khi đó nó được tính bởi B như sau: 57 𝐾𝐵𝐴 = 𝑚𝐴 𝑥𝐵 𝑚𝑜𝑑 𝑝 (= 𝑔𝑥𝐵𝑣 𝑚𝑜𝑑 𝑝) (2.6) Vì vậy, khi khóa riêng dài hạn 𝑥𝐵 của B bị lộ thì người tấn công có thể dễ dàng tính được bất kỳ khóa phiên 𝐾𝐴𝐵 nào đã được thành lập trước đó bởi phương trình (2.5). Điều tương tự cũng sẽ xảy ra với 𝐾𝐵𝐴 khi 𝑥𝐴 bị lộ. Không có tính chất làm mới khóa: Trong các giao thức của Harn, A tính 𝐾𝐴𝐵 thông qua (2.6), cho thấy 𝐾𝐴𝐵 phụ thuộc vào khóa công khai 𝑦𝐵 (A luôn biết khóa này) của B và một giá trị bí mật ngẫu nhiên 𝑣 (được lựa chọn bởi A). Vì vậy, A có thể quyết định rằng 𝐾𝐴𝐵 phải bằng một giá trị đã được định trước. B cũng có thể làm điều tương tự với 𝐾𝐵𝐴 như A. Phan đưa ra cải tiến của mình trên giao thức của Harn để giao thức có thể cung cấp hai tính chất nói trên (an toàn phía trước và làm mới khóa). Mô tả giao thức: Giao thức của Phan được mô tả trong Hình 2.3. Hình 2.3. Giao thức trao đổi khóa Phan 58 Đánh giá giao thức: Thứ nhất, dễ dàng nhận thấy giao thức của Phan đảm bảo giữ nguyên các ưu điểm của giao thức của Harn do các khóa phiên đều được xác nhận vì có trong phương trình ký. Thứ hai, trong giao thức trao đổi khóa của Phan ta có khóa phiên theo hướng từ A tới B được tính bởi A như sau: 𝐾𝐴𝐵 = (𝑚𝐴) 𝑥𝐵𝑤 𝑚𝑜𝑑 𝑝 (= 𝑔𝑥𝐵𝑣𝑤 𝑚𝑜𝑑 𝑝)(= 𝑦𝐵 𝑣𝑤 𝑚𝑜𝑑 𝑝) (2.7) Trong khi đó nó được tính bởi B như sau: 𝐾𝐴𝐵 = (𝑛𝐵) 𝑣 𝑚𝑜𝑑 𝑝 (= 𝑔𝑥𝐵𝑣𝑤 𝑚𝑜𝑑 𝑝) (2.8) Căn cứ vào (2.7) và (2.8) ta nhận thấy dù 𝐾𝐴𝐵 có được tính theo cách nào đi chăng nữa thì nếu khóa riêng dài hạn 𝑥𝐵 của B bị lộ, người tấn công cũng không thể tính được khóa phiên 𝐾𝐴𝐵 vì 𝐾𝐴𝐵 còn phụ thuộc vào các khóa bí mật ngắn hạn của A và B. Tương tự với 𝐾𝐵𝐴 khi 𝑥𝐴 bị lộ. Do đó, giao thức trao đổi khóa của Phan cung cấp tính chất an toàn phía trước. Thứ ba, trong giao thức này A tính 𝐾𝐴𝐵 thông qua (2.7) cho thấy 𝐾𝐴𝐵 không những phụ thuộc vào khóa công khai 𝑦𝐵 (A luôn biết khóa này) của B và một giá trị bí mật ngẫu nhiên 𝑣 (được lựa chọn bởi A) mà còn phụ thuộc vào giá trị bí mật ngẫu nhiên 𝑤 (được lựa chọn bởi B). Vì vậy, A không thể định trước được 𝐾𝐴𝐵. Tương tự B cũng không thể định trước được 𝐾𝐵𝐴. Tóm lại cả A và B đều không thể định trước được các khóa phiên được đàm phán giữa hai bên. Do đó, giao thức trao đổi khóa Phan cung cấp tính chất làm mới khóa. Tuy nhiên, trong giao thức trao đổi khóa Phan ta có: 𝐾𝐵𝐴 = 𝑔 𝑥𝐴𝑣𝑤 𝑚𝑜𝑑 𝑝 (2.9) Suy ra: 𝐾𝐴𝐵 𝑥𝐴 = 𝐾𝐵𝐴 𝑥𝐵 𝑚𝑜𝑑 𝑝 (2.10) Rõ ràng có một mối quan hệ hiện (explicit relation) giữa hai khóa phiên được đàm phán giữa hai bên, 𝐾𝐴𝐵 và 𝐾𝐵𝐴. Mối quan hệ này có thể gây ra một 59 số lỗ hổng trong tương lai. Ví dụ, khi các khóa riêng dài hạn 𝑥𝐴 và 𝑥𝐵 bị tổn thương đồng thời, người tấn công có thể tính toán 𝐾𝐴𝐵 từ 𝐾𝐵𝐴 và ngược lại. Mặc dù không có cuộc tấn công nào tồn tại trên giao thức ngay bây giờ nhưng các giao thức sẽ an toàn hơn nếu không có mối quan hệ rõ ràng giữa hai khóa phiên được thỏa thuận. Giao thức trao đổi khóa Jie Liu và Jianhua Li: Năm 2010, hai tác giả Jie Liu và Jianhua Li [38] đã đề xuất một cải tiến tốt hơn, an toàn hơn bằng cách khắc phục nhược điểm mối quan hệ hiện trong giao thức trao đổi khóa Phan [52]. Mô tả giao thức: Giao thức của Jie Liu và Jianhua Li hoạt động như Hình 2.4. Hình 2.4. Giao thức trao đổi khóa của Jie Liu và Jianhua Li Đánh giá giao thức: Cải thiện của giao thức này đó là có thêm hai số nguyên ngẫu nhiên tạm thời so với giao thức trao đổi khóa của Phan (trong giao thức của Phan thì mỗi 60 bên tham gia giao thức chọn một số nguyên ngẫu nhiên còn trong giao thức Liu & Li mỗi bên chọn hai số nguyên ngẫu nhiên). Giao thức này vẫn cung cấp được tính an toàn của giao thức của Phan. Cụ thể đó là nó có thể cung cấp cả hai tính chất chất an toàn phía trước và làm mới khóa. Các khóa phiên trong giao thức cải tiến này được kết hợp bởi các số nguyên ngẫu nhiên khác nhau như được chỉ ra trong (2.11) và (2.12) cho nên không có bất kỳ mối quan hệ hiện nào giữa 𝐾𝐴𝐵 và 𝐾𝐵𝐴. Do đó, giao thức cải tiến này khắc phục được nhược điểm mối quan hệ hiện giữa hai khóa phiên được thỏa thuận giữa hai bên. Chính vì lẽ đó nó an toàn hơn so với giao thức trao đổi khóa Phan. Độ phức tạp tính toán của giao thức này tương đương với giao thức trao đổi khóa của Phan. Việc thêm hai số nguyên ngẫu nhiên tạm thời làm cho độ phức tạp của giao thức tăng lên nhưng nó làm cho giao thức an toàn hơn. Tuy nhiên, qua (2.11) và (2.12), ta thấy giao thức của Jie Liu và Jianhua Li không cung cấp tính chất an toàn: chống lại tấn công lộ khóa phiên. Như vậy, bắt đầu từ Arazi là người đầu tiên đề xuất kết hợp chữ ký số nhằm cung cấp khả năng xác thực cho giao thức trao đổi khóa, đã có nhiều đề xuất, cải tiến nhằm nâng cao tính bảo mật của các giao thức trao đổi khóa an toàn. Tuy nhiên, có thể thấy, các giao thức này đều chỉ dựa trên một bài toán khó. Vì vậy, Luận án này sẽ phát triển giao thức trao đổi khóa an toàn dựa trên hai bài toán khó nhằm khắc phục những điểm yếu đã phân tích ở trên. 2.2.2. Mô tả giao thức DH–MM–KE Các tham số miền (𝑝𝐴, 𝑝𝐵 , 𝑛𝐴, 𝑛𝐵) được định nghĩa như lược đồ chữ ký số thứ hai trong phần 2.1. 𝐾𝐴𝐵 = 𝑔 𝑥𝐵𝑣1𝑤1 𝑚𝑜𝑑 𝑝 (= 𝑦𝐵 𝑣1𝑤1 𝑚𝑜𝑑 𝑝) (2.11) 𝐾𝐵𝐴 = 𝑔 𝑥𝐴𝑣2𝑤2 𝑚𝑜𝑑 𝑝 (= 𝑦𝐴 𝑣2𝑤2 𝑚𝑜𝑑 𝑝) (2.12) 61 Với người gửi A: 𝑝𝐴 = 2𝑛𝐴 + 1, trong đó 𝑛𝐴 = 𝑞𝐴 ′ 𝑞𝐴, 𝑞𝐴 ′ và 𝑞𝐴 là các số nguyên tố lớn với kích thước ít nhất là 1024 bit. Các tham số khóa của người A, khóa công khai (𝑒𝐴, 𝑦𝐴) và khóa bí mật (𝑥𝐴, 𝑑𝐴). Với người nhận B: 𝑝𝐵 = 2𝑛𝐵 + 1, trong đó 𝑛𝐵 = 𝑞𝐵 ′ 𝑞𝐵, 𝑞𝐵 ′ và 𝑞𝐵 là các số nguyên tố lớn với kích thước ít nhất là 1024 bit. Các tham số khóa của người B, khóa công khai (𝑒𝐵, 𝑦𝐵) và khóa bí mật (𝑥𝐵, 𝑑𝐵). Thủ tục chọn tham số cho từng bên được thực hiện theo Thủ tục 2.1: Thủ tục 2.1. Chọn tham số Input: độ dài bit (length) của tham số Output: các tham số q, q1, n, p, x, y, e, d, g Function GenerateParameter() q := RandomPrime(length);//sinh số nguyên tố ngẫu nhiên có độ dài bit là length q1 := RandomPrime(length);//sinh số nguyên tố ngẫu nhiên có độ dài bit là length n := q * q1; p := n * 2 + 1; //tìm p while true do if p is prime then break else q := RandomPrime(); q1 := RandomPrime(); n := q * q1; p := n * 2 + 1; end if end while //tìm g while true do 62 tmp := RandomInteger(); g := (tmp pow ((p - 1) / q)) mod p; if g > 1 then break else tmp := RandomInteger(); end if end while phiN := (q - 1) * (q1 - 1); x := RandomInteger(1, p – 1);//sinh số tự nhiên ngẫu nhiên trong khoảng [1, p-1] e := RandomInteger(1, n - 1); y := (g pow x) mod p; //tìm e while gcd(e, phiN) != 1 do e := RandomInteger(1, n - 1); end while d := e multiple_inverse_mod phiN; return (q, q1, n, p, x, y, e, d, g); end function Tính toán giá trị 𝑔 như là một phần tử sinh trong 𝑍𝑝𝐴 ∗ và 𝑍𝑝𝐵 ∗ . Với một xác suất cụ thể (xấp xỉ 1/4), giá trị ngẫu nhiên cho 𝑔 là một phần tử sinh trong 𝑍𝑝𝐴 ∗ và 𝑍𝑝𝐵 ∗ . Chính vì thế có thể thử nhiều giá trị của 𝑔 để xem nó có phải là phần tử sinh trong cả hai nhóm trên không. Ký hiệu {𝑝𝐴} = {0, 1, , 𝑝𝐴 − 1} và {𝑝𝐵} = {0, 1, , 𝑝𝐵 − 1}. Tìm tập 𝑝 = 𝑝𝐴 ∩ 𝑝𝐵. Từ đó, giá trị 𝑔 cũng là phần tử sinh của 𝑍𝑝 ∗ . Chọn 𝑛 chung: nếu 𝑛𝐴 < 𝑛𝐵, 𝑛 = 𝑛𝐴, nếu không, 𝑛 = 𝑛𝐵. Tham số chung 𝑝 được tính theo Thủ tục 2.2: 63 Thủ tục 2.2. Chọn tham số chung Input: p_A và p_B của hai bên A và B Output: tham số p chung Function FindCommonParameter () p := RandomPrime(); if p_A < p_B then p := p_A; else p := p_B; end if return p; end function Giả định rằng A muốn chia sẻ khóa phiên bí mật với B. Vậy thì: 1) A thực hiện như sau: - Lựa chọn 𝑘𝐴 ∈𝑅 [1, 𝑛 − 1]. - Tính 𝑅𝐴1 = 𝑔 𝑘𝐴 𝑚𝑜𝑑 𝑝 và 𝑅𝐴2 = 𝑔 𝑥𝐴 𝑚𝑜𝑑 𝑝 - Gửi cặp (𝑅𝐴1, 𝑅𝐴2) cho B. 2) B thực hiện như sau: - Chọn 𝑍 ∈𝑅 [1, 𝑛 − 1]. - Tính 𝑤 = 𝑍𝑒𝐴 𝑚𝑜𝑑 𝑛 - Chọn 𝑘𝐵 ∈𝑅 [1, 𝑛 − 1]. - Tính 𝑇𝐵 = (𝑅𝐴2 𝑥𝐵𝑅𝐴1 𝑘𝐵) 𝑚𝑜𝑑 𝑝 = 𝑔𝑥𝐴𝑥𝐵+𝑘𝐴𝑘𝐵 𝑚𝑜𝑑 𝑝. - Tính toán khóa bí mật được chia sẻ 𝐾𝐵𝐴 = 𝐻(𝑍||𝑇𝐵) - Tính 𝑅𝐵1 = 𝑔 𝑘𝐵 𝑚𝑜𝑑 𝑝 và 𝑅𝐵2 = 𝑔 𝑥𝐵 𝑚𝑜𝑑 𝑝 - Tính 𝐸𝐵 = 𝐻(𝑍||𝐾𝐵𝐴||𝑅𝐴1||𝑅𝐵1||𝑅𝐴2||𝑅𝐵2) và 𝑆𝐵 = (𝑘𝐵 − 𝑥𝐵𝐸𝐵) 𝑑𝐵 𝑚𝑜𝑑 𝑛 - Gửi lại các giá trị (𝑤, 𝑅𝐵1 , 𝑅𝐵2 , 𝐸𝐵, 𝑆𝐵) cho người A. 64 3) A sau đó tiếp tục thực hiện như sau: - Tính 𝑍 = 𝑤𝑑𝐴 𝑚𝑜𝑑 𝑛 - Tính 𝑇𝐴 = (𝑅𝐵2 𝑥𝐴𝑅𝐵1 𝑘𝐴) 𝑚𝑜𝑑 𝑝 = 𝑔𝑥𝐵𝑥𝐴+𝑘𝐵𝑘𝐴 𝑚𝑜𝑑 𝑝 - Tính khóa bí mật chia sẻ 𝐾𝐴𝐵 = 𝐻(𝑍||𝑇𝐴) - Xác thực (𝐸𝐵, 𝑆𝐵) - Tính 𝐸𝐴 = 𝐻(𝑍||𝐾𝐴𝐵||𝑅𝐴1||𝑅𝐵1||𝑅𝐴2||𝑅𝐵2) - Tính 𝑆𝐴 = (𝑘𝐴 − 𝑥𝐴𝐸𝐴) 𝑑𝐴 𝑚𝑜𝑑 𝑛 - Gửi (𝐸𝐴, 𝑆𝐴) cho B. 4) B thực hiện: - Xác thực (𝐸𝐴, 𝑆𝐴). Giao thức DH-MM-KE được mô tả hoạt động trên Hình 2.5. Hình 2.5. Giao thức DH–MM–KE 65 Tính đúng đắn của giao thức: Ta có: 𝑇𝐴 = (𝑅𝐵2 𝑥𝐴𝑅𝐵1 𝑘𝐴) 𝑚𝑜𝑑 𝑝 = 𝑔𝑥𝐵𝑥𝐴+𝑘𝐵𝑘𝐴 𝑚𝑜𝑑 𝑝 = 𝑇𝐵 => 𝐾𝐴𝐵 = 𝐻(𝑍||𝑇𝐴) = 𝐻(𝑍||𝑇𝐵) = 𝐾𝐵𝐴 2.2.3. Đánh giá giao thức 2.2.3.1. Độ an toàn của giao thức Tính chất 2.1: Giao thức DH–MM–KE đảm bảo tính chất an toàn đầy đủ về phía trước (Perfect Forward Secrecy). Chứng minh: Ta cần chứng minh nếu khóa bí mật dài hạn của A và B bị lộ thì các khóa phiên 𝐾𝐴𝐵 và 𝐾𝐵𝐴 được tạo ra trước đó vẫn không bị ảnh hưởng. Khóa phiên theo hướng từ A tới B được A tính như sau: 𝐾𝐴𝐵 = 𝐻(𝑍||𝑇𝐴) = 𝐻(𝑍||𝑔 𝑥𝐵𝑥𝐴+𝑘𝐵𝑘𝐴 𝑚𝑜𝑑 𝑝) (2.13) Còn B tính như sau: 𝐾𝐵𝐴 = 𝐻(𝑍||𝑇𝐵) = 𝐻(𝑍||𝑔 𝑥𝐴𝑥𝐵+𝑘𝐴𝑘𝐵 𝑚𝑜𝑑 𝑝) (2.14) 𝐾𝐴𝐵 và 𝐾𝐵𝐴 phụ thuộc vào giá trị ngẫu nhiên 𝑘𝐴 và 𝑘𝐵 Do đó, khi một khóa dài hạn (𝑥𝐴, 𝑑𝐴), (𝑥𝐵 , 𝑑𝐵) của A và B bị lộ, người tấn công không thể tính bất kỳ khóa phiên đã sử dụng 𝐾𝐴𝐵 và 𝐾𝐵𝐴 bằng (2.13) và (2.14). Do đó, giao thức này đảm bảo tính an toàn đầy đủ về phía trước. Tính chất 2.2: Giao thức DH–MM–KE thỏa mãn tính chất khóa độc lập. Chứng minh: Trong giao thức DH–MM–KE, A và B tính như sau: 𝐾𝐴𝐵 = 𝐻(𝑍||𝑔 𝑥𝐵𝑥𝐴+𝑘𝐵𝑘𝐴𝑚𝑜𝑑 𝑝) và 𝐾𝐵𝐴 = 𝐻(𝑍||𝑔 𝑥𝐴𝑥𝐵+𝑘𝐴𝑘𝐵𝑚𝑜𝑑 𝑝) Các khóa phiên đều phụ thuộc vào khóa bí mật (𝑥𝐴, 𝑥𝐵) và số ngẫu nhiên (𝑘𝐴, 𝑘𝐵). Điều này có nghĩa là các khóa phiên được tính độc lập. Tính chất 2.3: Giao thức DH–MM–KE an toàn với tấn công SSR (session-state reveal). Chứng minh: Ta cần chứng minh nếu người tấn công thu được các trạng thái trung gian trong quá trình thực hiện giao thức cũng không thể tính được khóa bí mật chia sẻ. 66 Theo công thức (2.13) và (2.14), khóa phiên 𝐾𝐴𝐵 và 𝐾𝐵𝐴 phụ thuộc vào khóa bí mật (𝑥𝐴, 𝑥𝐵) của A và B. Do đó, khi các số ngẫu nhiên 𝑘𝐴 và 𝑘𝐵 hoặc các thành phần trung gian khác bị lộ, người tấn công cũng không thể tính được khóa phiên vì không tính được 𝑇𝐴 (𝑇𝐵). Do đó, giao thức DH–MM–KE an toàn với tấn công SSR. Tính chất 2.4: Giao thức DH–MM–KE an toàn trước tấn công giả mạo khóa thỏa thuận (key compromise impersonation – KCI). Chứng minh: Giao thức này sử dụng một quá trình xác thực chung giữa A và B. Do đó, quá trình xác thực sẽ thất bại nếu người tấn công hoạt động và không đồng thời biết về 𝑘𝐴 và (𝑥𝐴, 𝑑𝐴) hoặc 𝑘𝐵 và (𝑥𝐵, 𝑑𝐵). Do đó, cách duy nhất của người tấn công là tính trực tiếp khóa phiên, giả sử người tấn công biết khóa bí mật dài hạn của A (𝑥𝐴, 𝑑𝐴) và khóa phiên tạm thời của B (𝑘𝐵), vì khóa phiên là 𝐾𝐴𝐵 = 𝐻(𝑍||𝑔 𝑥𝐵𝑥𝐴+𝑘𝐵𝑘𝐴 𝑚𝑜𝑑 𝑝) và người tấn công có thể tính 𝑍. Tuy nhiên, trong trường hợp này, người tấn công vẫn không thể tính được 𝑔𝑥𝐵𝑥𝐴+𝑘𝐵𝑘𝐴. Do đó, giao thức DH–MM–KE an toàn trước tấn công giả mạo khóa thỏa thuận KCI. Tính chất 2.5: Giao thức DH–MM–KE an toàn trước tấn công không biết khóa chia sẻ (unknown key-share). Chứng minh: Việc xác nhận khóa có thể ngăn chặn tấn công không biết khóa chia sẻ. B xác nhận với A rằng đã nhận được khóa chia sẻ bí mật 𝐾𝐵𝐴 bằng việc kí khóa này cùng với (𝑍, 𝑅𝐴1, 𝑅𝐵1, 𝑅𝐴2, 𝑅𝐵2). Vì khóa bí mật chia sẻ 𝐾𝐵𝐴 là một hàm băm một chiều của các số ngẫu nhiên (𝑅𝐴1, 𝑅𝐴2) của A, A tin rằng nội dung tin nhắn không bị lặp và biết rằng nó thực sự là từ phía B. 67 B cũng làm những điều tương tự với 𝐾𝐴𝐵 giống như A. Tính chất 2.6: Giao thức DH–MM–KE an toàn dựa trên hai bài toán khó. Chứng minh: Ta cần chứng minh để phá giải giao thức DH–MM–KE, người tấn công phải giải quyết đồng thời hai bài toán khó. Trong giao thức DH–MM–KE, A và B tính khóa chia sẻ 𝐾𝐴𝐵 và 𝐾𝐵𝐴 theo công thức (2.13) và (2.14). Các giá trị này phụ thuộc vào (𝑍, 𝑇𝐴 hoặc 𝑇𝐵). Để tính 𝑍, người tấn công phải tính được 𝑑, muốn tính được giá trị của 𝑑 thì lại cần tìm được (𝑛) mà muốn tìm được (𝑛) thì lại cần phải giải tiếp bài toán phân tích 𝑛 thành thừa số nguyên tố. Để tính 𝑇𝐴 (hoặc 𝑇𝐵) người tấn công phải tính được giá trị của (𝑥𝐴, 𝑘𝐴) hoặc (𝑥𝐵, 𝑘𝐵). Ta có: (𝑅𝐴1 = 𝑔 𝑘𝐴 𝑚𝑜𝑑 𝑝 và 𝑅𝐴2 = 𝑔 𝑥𝐴 𝑚𝑜𝑑 𝑝) và (𝑅𝐵1 = 𝑔 𝑘𝐵 𝑚𝑜𝑑 𝑝 và 𝑅𝐵2 = 𝑔 𝑥𝐵 𝑚𝑜𝑑 𝑝). Do đó, để tính được (𝑥𝐴, 𝑘𝐴) hoặc (𝑥𝐵, 𝑘𝐵), người tấn công phải giải bài toán logarithm rời rạc. Như vậy, giao thức DH–MM–KE an toàn dựa trên hai bài toán khó. 2.2.3.2. Độ phức tạp của giao thức Độ phức tạp thời gian của giao thức DH–MM–KE được trình bày trong Bảng 2.2. Bảng 2.2. Độ phức tạp thời gian của giao thức DH–MM–KE Giai đoạn Độ phức tạp thời gian 1 2𝑇𝐸𝑋𝑃 2 6𝑇𝐸𝑋𝑃 + 2𝑇𝑀𝑈𝐿 + 𝑇𝐻 3 7𝑇𝐸𝑋𝑃 + 3𝑇𝑀𝑈𝐿 + 2𝑇𝐻 4 3𝑇𝐸𝑋𝑃 + 𝑇𝑀𝑈𝐿 + 𝑇𝐻 Tổng 18𝑇𝐸𝑋𝑃 + 6𝑇𝑀𝑈𝐿 + 4𝑇𝐻 68 2.3. Kết luận chương 2 Chương 2 nghiên cứu về các lược đồ chữ ký số dựa trên hai bài toán khó trước đây. Các lược đồ này có một nhược điểm là chỉ cần giải một trong hai bài toàn khó là có thể phá được toàn bộ lược đồ. Do đó, Luận án đã đề xuất hai lược đồ chữ ký số mới nhằm khắc phục nhược điểm này. Các lược đồ được đề xuất có hai ưu điểm nổi bật. Thứ nhất, chúng được phát triển từ một số lược đồ chữ ký số mà tính bảo mật và hiệu quả đã được chứng minh, nên được thừa hưởng những đặc tính từ các lược đồ này. Thứ hai, sự an toàn của các lược đồ được đề xuất dựa trên hai bài toán khó. Vì vậy, nó vẫn là an toàn ngay cả khi có một thuật toán hiệu quả để giải một trong hai bài toán khó. Do đó, các lược đồ được đề xuất là phù hợp cho các ứng dụng đòi hỏi mức an ninh cao trong hệ thống hạn chế về nguồn lực. Tiếp theo, Luận án nghiên cứu, phân tích các giao thức trao đổi khóa an toàn có tích hợp chữ ký số đã được công bố. Các giao thức này vẫn còn tồn tại các nhược điểm về tính an toàn và chỉ dựa trên một bài toán khó. Do vậy, dựa trên cơ sở lược đồ chữ ký số mới đề xuất, Luận án đã xây dựng giao thức trao đổi khóa mới, tích hợp chữ ký số và dựa trên hai bài toán khó, nhằm khắc phục những nhược điểm của các giao thức trước đây, đồng thời nâng cao tính bảo mật của giao thức. Kết quả nghiên cứu đạt được trong chương này là cơ sở để tiếp tục nghiên cứu chuyên sâu hơn và tiến tới đề xuất xây dựng các giao thức ký và mã hóa đồng thời, ký và mã hóa đồng thời có thể chối từ. 69 Chương III: PHÁT TRIỂN GIAO THỨC KÝ VÀ MÃ HÓA ĐỒNG THỜI DỰA TRÊN HAI BÀI TOÁN KHÓ Nội dung chính của chương này: Dựa trên cơ sở kết quả nghiên cứu của chương 2, trong chương này Luận án đề xuất một giao thức ký và mã hóa đồng thời (DH–MM–SC) và một giao thức ký và mã hóa đồng thời có thể chối từ (DH–MM–DSC). Các giao thức này đều dựa trên việc tích hợp chữ ký số và kết hợp hai bài toán khó. Tiếp theo, Luận án chứng minh tính đúng đắn, khả năng bảo mật và tính hiệu quả của các giao thức mới đề xuất. 3.1. Giao thức ký và mã hóa đồng thời Hiện nay, an toàn thông tin đã trở thành một khía cạnh quan trọng trong tất cả các lĩnh vực truyền thông. Khi gửi một thông điệp tới cho một cá nhân trên một kênh không an toàn (như Internet), ta cần phải đảm bảo tính bí mật, toàn vẹn của thông điệp, có thể xác thực người gửi và người gửi không thể chối bỏ thông điệp đã gửi. Trước đây, mật mã học chỉ đơn thuần bảo đảm tính bí mật của thông điệp, ngăn chặn người khác đọc được khi không có những thông tin bí mật. Trong thời hiện đại, mật mã học đã được mở rộng phạm vi, không chỉ đảm bảo tính bí mật của truyền thông mà còn cung cấp khả năng kiểm tra tính toàn vẹn của thông điệp, xác thực người gửi/người nhận,.... Hiện nay, mật mã có hai dạng chính là hệ mật khóa bí mật và hệ mật khóa công khai. Với hệ mật khóa bí mật, hai bên tham gia sẽ thỏa thuận một giá trị khóa chung và giữ bí mật khóa này với bên ngoài. Truyền khóa trong môi trường không an toàn trở thành vấn đề quan trọng trong việc đảm bảo tính an toàn của hệ mật. Trong hệ mật khóa công khai, mỗi bên tham gia sẽ có một cặp khóa bí mật/khóa công khai, khi mã hóa, người gửi sẽ dùng khóa công khai để mã hóa, người nhận sẽ dùng khóa bí mật để giải mã. Với phương pháp này, ta không cần quan tâm đến việc giữ bí mật khóa trên môi trường công cộng. Tuy nhiên, nhược điểm của hệ mật khóa công khai là khối lượng tính toán lớn hơn nhiều so với hệ mật khóa 70 bí mật. Để xác thực thông điệp, người gửi cần phải ký lên đó trước khi gửi nó tới người nhận. Để làm được việc này, người gửi có thể sử dụng các lược đồ chữ ký số như RSA, Rabin, Schnorr, DSA,... Tính bảo mật của thông điệp và khả năng xác thực là những vấn đề quan trọng trong truyền thông trên Internet. Trước đây, mã hóa và chữ ký số là những phương thức quan trọng nhưng riêng rẽ và không có liên kết [27], [66] trong các hệ thống mã hóa. Trong hệ mã khóa công khai, phương pháp truyền thống là ký lên thông điệp rồi mã hóa nó và gửi tới cho người nhận. Người nhận sẽ giải mã thông điệp rồi xác thực nó. Đây là phương pháp ký rồi mã hóa (signature-then-encryption). Nhược điểm lớn nhất của phương pháp này là việc tạo chữ ký và mã hóa làm tăng độ phức tạp của giao thức và làm tăng kích thước của thông điệp ban đầu. Từ đó, nhiều phương pháp được đưa ra để kết hợp các bước này vào một phép tính duy nhất. Phương pháp này gọi là ký và mã hóa đồng thời (signcryption). Một giao thức ký và mã hóa đồng thời cung cấp tính bảo mật của cả mã hóa và chữ ký số: bảo mật, toàn vẹn, không thể chỉnh sửa và chống chối từ. 3.1.1. Phương pháp ký rồi mã hóa Để gửi một thông điệp bí mật đi và đảm bảo nó không bị chỉnh sửa, người gửi sẽ thực hiện các bước sau: - Ký lên thông điệp sử dụng lược đồ chữ ký số (RSA, DSA, Rabin,...). - Mã hóa thông điệp và c