Luận án Nghiên cứu phát triển một số lược đồ chữ ký số và ứng dụng trong việc thiết kế giao thức trao đổi khóa

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ TRIỆU QUANG PHONG NGHIÊN CỨU PHÁT TRIỂN MỘT SỐ LƢỢC ĐỒ CHỮ KÝ SỐ VÀ ỨNG DỤNG TRONG VIỆC THIẾT KẾ GIAO THỨC TRAO ĐỔI KHÓA LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội – 2023 BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ TRIỆU QUANG PHONG NGHIÊN CỨU PHÁT TRIỂN MỘT SỐ LƢỢC ĐỒ CHỮ KÝ SỐ VÀ ỨNG DỤNG TRONG VIỆC THIẾT KẾ GIAO THỨC TRAO ĐỔI KHÓA Ngành: Cơ sở toán học cho tin học Mã số: 9 46 01 10 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƢỜI HƢỚNG DẪN KHOA HỌC: 1. TS Trần Duy Lai 2. TS Vũ Quốc Thành Hà Nội – 2023 i LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Những nội dung, số liệu và kết quả được trình bày trong luận án là hoàn toàn trung thực và chưa được ai công bố trong bất kỳ công trình nào khác, các dữ liệu tham khảo được trích dẫn đầy đủ. Hà Nội, ngày tháng 03 năm 2023 Tác giả luận án Triệu Quang Phong ii LỜI CẢM ƠN Luận án này được thực hiện tại Viện Khoa học và Công nghệ quân sự - Bộ Quốc phòng. Lời đầu tiên, nghiên cứu sinh xin bày tỏ lòng biết ơn sâu sắc tới Tiến sĩ Trần Duy Lai, Tiến sĩ Vũ Quốc Thành, các thầy đã tận tình giúp đỡ định hướng, tr. bị cho nghiên cứu sinh phương pháp nghiên cứu, kinh nghiệm, kiến thức khoa học và kiểm tra, đánh giá các kết quả nghiên cứu của nghiên cứu sinh. Xin chân thành cảm ơn Ban Giám đốc Viện Khoa học và Công nghệ quân sự, Thủ trưởng Phòng Đào tạo, Viện Công nghệ thông tin là cơ sở đào tạo và đơn vị quản lý đã tạo mọi điều kiện, hỗ trợ, giúp đỡ nghiên cứu sinh trong quá trình học tập, nghiên cứu và hoàn thành luận án. Nghiên cứu sinh bày tỏ lòng biết ơn chân thành tới các thầy cô giáo, các nhà khoa học của Viện Khoa học và Công nghệ quân sự, Viện Công nghệ thông tin – Viện KHCN QS, Học viện Kỹ Thuật mật mã; các đồng nghiệp tại Phân viện Khoa học mật mã – Viện KHCN mật mã – Ban Cơ yếu Chính phủ, đã có các góp ý quý báu cho Nghiên cứu sinh trong quá trình thực hiện luận án này. Cuối cùng xin bày tỏ lời cảm ơn đến gia đình, bạn bè của Nghiên cứu sinh đã luôn động viên, chia sẻ, ủng hộ và giúp đỡ Nghiên cứu sinh vượt qua khó khăn để đạt được những kết quả nghiên cứu trong luận án này. Tác giả luận án Triệu Quang Phong iii MỤC LỤC Tr. DANH MỤC CÁC KÝ HIỆU................................................................................... vi DANH MỤC CÁC CHỮ VIẾT TẮT ...................................................................... vii DANH MỤC CÁC BẢNG ........................................................................................ ix DANH MỤC CÁC HÌNH ........................................................................................... x MỞ ĐẦU.. ............................................................................................................... 1 Chương 1. KHÁI QUÁT CHUNG VỀ CHỮ KÝ SỐ VÀ GIAO THỨC TRAO ĐỔI KHÓA........... ...................................................................................................... 6 1.1. Một số khái niệm cơ sở liên quan ........................................................................ 6 1.1.1. Lược đồ chữ ký số tổng quát ............................................................................. 6 1.1.2. Các khái niệm an toàn cho chữ ký số ................................................................ 7 1.1.3. Một số thuộc tính an toàn đáng mong đợi của giao thức trao đổi khóa ............ 9 1.2. Đánh giá về vấn đề bước lặp .............................................................................. 10 1.2.1. Lược đồ ECDSA ............................................................................................. 10 1.2.2. Lược đồ chữ ký GOST R 34.10-2012 ............................................................. 13 1.3. Đánh giá về vấn đề chữ ký kép và tính dễ uốn .................................................. 16 1.3.1. Chữ ký kép và tính dễ uốn đối với ECDSA .................................................... 16 1.3.2. Đánh giá vấn đề chữ ký kép và tính dễ uốn đối với GOST R 34.10-2012 ..... 18 1.4. Các mô hình an toàn cho lược đồ chữ ký số ...................................................... 19 1.4.1. Mô hình bộ tiên tri ngẫu nhiên ........................................................................ 20 1.4.2. Mô hình nhóm tổng quát ................................................................................. 21 1.4.3. Mô hình với thiết bị bảo vệ ............................................................................. 21 1.4.4. Mô hình bộ tiên tri ngẫu nhiên song ánh ........................................................ 22 1.5. Lược đồ chữ ký số dạng TEGTSS ..................................................................... 23 1.6. Khảo sát một số giao thức trao đổi khóa dựa trên chữ ký số ............................. 26 1.6.1. Giao thức STS cơ bản ..................................................................................... 26 1.6.2. Giao thức STS-MAC ....................................................................................... 27 1.6.3. Giao thức ISO-STS-MAC ............................................................................... 32 iv 1.6.4. Họ giao thức SIGMA ..................................................................................... 33 1.7. Mô hình an toàn cho giao thức trao đổi khóa .................................................... 35 1.7.1. Mô hình với đối tác được định rõ trước ......................................................... 35 1.7.2. Mô hình với đối tác được định rõ sau ............................................................ 42 1.8. Đánh giá chung về hướng nghiên cứu ............................................................... 43 1.9. Kết luận Chương 1 ............................................................................................ 46 Chương 2. ĐỀ XUẤT LƯỢC ĐỒ CHỮ KÝ SỐ AN TOÀN .................................. 48 2.1. Lược đồ chữ ký dạng ECTEGTSS .................................................................... 48 2.2. Đề xuất biến thể của lược đồ chữ ký GOST R 34.10-2012 .............................. 53 2.2.1. Lược đồ chữ ký số GOST-I ............................................................................ 53 2.2.2. Lược đồ chữ ký số GOST-II .......................................................................... 57 2.2.3. Đánh giá hiệu năng của GOST-I và GOST-II ................................................ 59 2.3. Đề xuất lược đồ chữ ký bó an toàn ................................................................... 62 2.3.1. Chữ ký bó dựa trên cây băm Merkle .............................................................. 62 2.3.2. Lược đồ chữ ký bó an toàn SBS-01 ............................................................... 69 2.3.3. Lược đồ chữ ký bó an toàn SBS-02 ............................................................... 72 2.4. Kết luận Chương 2 ............................................................................................ 75 Chương 3. ĐỀ XUẤT GIAO THỨC TRAO ĐỔI KHÓA AN TOÀN DỰA TRÊN CHỮ KÝ SỐ. ............................................................................................ 77 3.1. Độ an toàn của giao thức SIGMA ..................................................................... 79 3.2. Giao thức trao đổi khóa M-SIGMA .................................................................. 87 3.2.1. Tính chất P1 của M-SIGMA .......................................................................... 88 3.2.2. Tính chất P2 của M-SIGMA .......................................................................... 89 3.3. Giao thức trao đổi khóa M1-SIGMA .............................................................. 103 3.3.1. Tính chất P1 của M1-SIGMA ...................................................................... 103 3.3.2. Tính chất P2 của M1-SIGMA ...................................................................... 105 3.4. Phiên bản elliptic hóa của các giao thức đề xuất............................................. 109 3.4.1. Xem xét cài đặt các đề xuất trên nhóm điểm đường cong elliptic ............... 109 3.4.2. Xem xét cài đặt hiệu quả trên nhóm điểm đường cong elliptic ................... 110 v 3.4.3. Áp dụng cài đặt hiệu quả trên nhóm điểm đường cong elliptic .................... 115 3.5. Thảo luận về ý nghĩa của các đề xuất .............................................................. 117 3.6. Kết luận Chương 3 ........................................................................................... 119 KẾT LUẬN.. ........................................................................................................... 120 DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ ........................ 121 TÀI LIỆU THAM KHẢO ....................................................................................... 122 PHỤ LỤC. ............................................................................................................ P1 vi DANH MỤC CÁC KÝ HIỆU ̂ ̂ Ký hiệu một thực thể, hoặc định danh của thực thể đó Ký hiệu các kẻ tấn công (hoặc bên đối kháng) Ký hiệu việc kiểm tra có bằng hay không ̂ Chứng chỉ khóa công khai của thực thể ̂ mà có chứa ̂ Cofactor – phần phụ đại số được tính bởi công thức ( ) ̂ Khóa ký (khóa bí mật) của một thực thể ̂ ( ) Đường cong elliptic được định nghĩa trên trường ( ) Số điểm thuộc đường cong ( ) Trường hữu hạn có đặc số , với là số nguyên tố Hàm chuyển để dẫn xuất thành phần chữ ký trong thuật toán ký Phần tử có cấp của nhóm Các hàm băm được sử dụng Bên khởi tạo Bên phúc đáp Thuật toán sinh khóa Khóa phiên chung được tính ra trong quá trình trao đổi giữa hai bên tham gia Khóa cho hàm MAC Khóa cho hàm mã hóa Số nguyên tố (lớn) thỏa mãn ( ) Điểm tại vô cùng của đường cong elliptic ( ) Điểm cơ sở thuộc đường cong ( ) có cấp bằng Số nguyên tố (lớn) Ký hiệu cho khóa công khai ̂ Khóa công khai của một thực thể ̂ Số nguyên tố (lớn) thỏa mãn ( ) vii ( ) Chữ ký, trong đó là thành phần thứ nhất của chữ ký và là thành phần thứ hai của chữ ký ̂( ) Chữ ký của thực thể ̂ trên thông điệp Ký hiệu cho khóa ký bí mật Ký hiệu phiên hoặc định danh của phiên Tương ứng là hoành độ và tung độ của một điểm ( ) * + Thuật toán xác minh chữ ký số ( ) Hàm lấy đầu vào là điểm ( ) * + và trả về Ký hiệu lấy ngẫu nhiên đều một phần tử thuộc tập * + Hàm mã hóa với khóa ( ) Hàm trích xuất một chuỗi con từ phần tử thứ đến phần tử thứ của một chuỗi đầu vào DANH MỤC CÁC CHỮ VIẾT TẮT AK Thỏa thuận khóa có xác thực (Authenticated Key agreement) AKC Thỏa thuận khóa có xác thực kèm theo tính chất chứng nhận khóa (Authenticated Key agreement with key Comfimation) AKE Ký hiệu độ an toàn cho các giao thức trao đổi khóa có xác thực AM Mô hình các liên kết không có xác thực (Authenticated-links Model) CK Mô hình an toàn Canetti-Krawczyk Biến thể của mô hình CK cho việc đánh giá giao thức HMQV CMA Tấn công lựa chọn thông điệp (Chosen Message Attack) DSA Chuẩn chữ ký số của Mỹ dựa trên bài toán logarit rời rạc DSKS Tính chất lựa chọn khóa chữ ký kép (Duplicate Signature Key Selection) ECDSA Chuẩn chữ ký số của Mỹ dựa trên nhóm điểm đường cong elliptic ECTEGTSS Phiên bản trên đường cong elliptic của TEGTSS EUF Tính không thể giả mạo tồn tại (Existential UnForgeability) viii EUF-CMA Tính không thể giả mạo tồn tại trước tấn công lựa chọn thông điệp thích nghi EUF-NMA Tính không thể giả mạo tồn tại trước tấn công không sử dụng thông điệp GOST R 34. 10-2012 Chuẩn chữ ký số của Liên Bang Nga dựa trên nhóm điểm đường cong elliptic GOST-I Biến thể đầu tiên của GOST R 34.10-2012 được đề xuất trong luận án GOST-II Biến thể thứ hai của GOST R 34.10-2012 được đề xuất trong luận án KCI Mạo danh thỏa hiệp khóa (Key Compromise Impersonation) MAC Mã xác thực thông điệp (Message Authenticated Code) MT Bộ xác thực truyền thông điệp (Message Transmission) M-SIGMA Biến thể đầu tiên của giao thức SIGMA được đề xuất trong luận án M1-SIGMA Biến thể thứ hai của giao thức SIGMA được đề xuất trong luận án NMA Tấn công không sử dụng thông điệp (No-Message Attack) PFS Độ an toàn về phía trước (Perfect Forward Screcy) RSA Chuẩn chữ ký số của Mỹ dựa trên bài toán phân tích số SBS-01 Chữ ký bó an toàn loại 1 được đề xuất trong luận án SBS-02 Chữ ký bó an toàn loại 2 được đề xuất trong luận án SIGMA Giao thức trao đổi khóa dựa trên cơ chế “SIGn-and-MAc” SIGMA-I Biến thể của giao thức SIGMA bảo vệ định danh của bên khởi tạo trước tấn công chủ động SIGMA-R Biến thể của giao thức SIGMA bảo vệ định danh của bên phúc đáp trước tấn công chủ động TEGTSS Các lược đồ đáng tin cậy kiểu El Gamal (Trusted El Gamal Type Signature Scheme) UKS Chia sẻ khóa nhưng không rõ đối tác (Unknown Key-Share) UM Mô hình các liên kết không có xác thực (Unauthenticated-links Model) ix DANH MỤC CÁC BẢNG Tr. Bảng 1.1. Kết quả khảo sát bước lặp trên một số lược đồ chữ ký số. ....................... 15 Bảng 1.2. Các tính chất an toàn được xem xét trên họ giao thức STS. .................... 33 Bảng 2.1. So sánh lý thuyết GOST-I, GOST-II với GOST R 34.10-2012. .............. 60 Bảng 2.2. Kết quả thực nghiệm GOST-I, GOST-II và GOST R 34.10-2012. .......... 60 Bảng 2.3. So Sánh thực nghiệm giữa một số lược đồ chữ ký bó với phiên bản thường của chúng ...................................................................................................... 67 Bảng 2.4. Xem xét hiệu năng của SBS-01 và SBS-02. ............................................. 75 Bảng 3.1. So sánh hiệu năng giữa SIGMA, M-SIGMA và M1-SIGMA ................ 110 x DANH MỤC CÁC HÌNH Tr. Hình 1.1. Giao thức trao đổi khóa Diffie-Hellman cơ bản ...................................... 26 Hình 1.2. Giao thức STS cơ bản .............................................................................. 27 Hình 1.3. Tấn công UKS thay đổi khóa công khai trên STS-ENC .......................... 27 Hình 1.4. Giao thức STS-MAC ................................................................................ 28 Hình 1.5. Biến thể 2 của STS-MAC......................................................................... 29 Hình 1.6. Giao thức ISO-STS-MAC ........................................................................ 33 Hình 1.7. Giao thức SIGMA cơ bản ........................................................................ 34 Hình 1.8. Bộ xác thực MT - .............................................................................. 38 Hình 1.9. Giao thức HMQV. .................................................................................... 39 Hình 1.10. Giao thức KEA+. .................................................................................... 40 Hình 2.1. Minh họa một cây Merkle cho việc lưu trữ dữ liệu. ................................ 63 Hình 2.2. Quy trình ký bó cho tập gồm 04 dữ liệu dựa trên cây băm Merkle. ........ 66 Hình 2.3. Quy trình xác minh chữ ký bó dựa trên cây băm Merkle ........................ 67 Hình 2.4. Minh họa việc lựa chọn thích nghi thông điệp trong trường hợp ký bó với 4 thông điệp ........................................................................................................ 68 Hình 3.1. Biến thể MAC dưới chữ ký của Giao thức SIGMA cơ bản ..................... 77 Hình 3.2. Giao thức M-SIGMA ............................................................................... 87 Hình 3.3. Giao thức M1-SIGMA ........................................................................... 103 Hình 3.4. Giao thức M-SIGMA trên nhóm điểm đường cong elliptic ................... 109 Hình 3.5. Giao thức M1-SIGMA trên nhóm điểm đường cong elliptic ................. 110 Hình 3.6. Giao thức Lemograss-3 gốc. .................................................................. 111 Hình 3.7. Giao thức Lemograss-3 được chuẩn hóa ................................................ 112 Hình 3.8. Tấn công giao thức Lemograss-3 được chuẩn hóa................................. 112 Hình 3.9. Cài đặt sửa đổi cho giao thức Lemograss-3 được chuẩn hóa ................. 115 1 MỞ ĐẦU 1. Tính cấp thiết của đề tài luận án Trong thời đại hiện nay, sự tiến bộ và phát triển của công nghệ thông tin mang lại cho chúng ta nhiều phương thức liên lạc mà không bị giới hạn bởi khoảng cách địa lý, bao gồm gọi thoại, video call, email Trong đó, xu thế liên lạc thông qua mạng Internet đang dần trở nên phổ biến và ưa thích do sự tiện lợi và chi phí thấp. Tuy nhiên, mạng Internet chưa bao giờ được xem là một kênh liên lạc an toàn, và nó luôn tiềm ẩn nhiều rủi ro. Do đó, cần có các giải pháp mật mã cho phép các bên trao đổi thông tin bí mật và có xác thực. Việc trao đổi thông tin một cách bí mật và hiệu quả giữa các bên có thể được đảm bảo bởi các lược đồ mã hóa khóa đối xứng. Tuy nhiên, phương thức này lại yêu cầu các bên phải chia sẻ một khóa bí mật chung để thực hiện cả chức năng mã hóa lẫn giải mã. Đối với các bên cách xa nhau về mặt địa lý và chỉ có thể liên lạc với nhau qua các kênh như mạng internet, việc thiết lập các khóa bí mật chung sẽ được thực hiện thông qua các giao thức trao đổi khóa (hay thỏa thuận khóa). Các giao thức trao đổi khóa hiện nay đa phần được thiết kế dựa trên một cơ chế khá nổi tiếng, đó là trao đổi khóa Diffie-Hellman. Tuy nhiên, để đảm bảo các giao thức trao đổi khóa dựa trên cơ chế này hoạt động một cách an toàn, chúng cần được bổ sung thêm các phương thức xác thực. Ở đó, chữ ký số được xem là một giải pháp có tính khả thi. Hơn nữa, các giao thức trao đổi khóa có xác thực dựa trên chữ ký số cũng là thành phần chính trong một số giao thức bảo mật qua mạng internet như Ipsec, SSL, TLS. Do đó, việc triển khai hướng nghiên cứu về các giao thức trao đổi khóa có xác thực dựa trên chữ ký là hết sức cần thiết. Bên cạnh vai trò quan trọng kể trên trong các giao thức trao đổi khóa, “chữ ký số” kể từ khi được giới thiệu bởi Diffie-Hellman vào năm 1976 đã trở thành một chủ đề thu hút được nhiều sự quan tâm và được sử dụng trong nhiều ứng dụng phổ biến hiện nay như blockchain, bỏ phiếu điện tử e-voting, xác thực giao dịch điện tử, Cho đến nay, đã có nhiều dạng chữ ký số đuợc phát triển và chuẩn hóa bởi nhiều quốc gia trên thế giới. Đáng kể nhất trong số đó là chuẩn đồ chữ ký số 2 ECDSA (của Mỹ) và GOST R 34.10-2012 (của Liên bang Nga). Điểm chung của chúng đều thuộc lớp các lược đồ kiểu El Gamal mà dựa trên bài toán logarit rời rạc. Đối với các lược đồ chữ ký số (cũng như giao thức trao đổi khóa) nói riêng, và các nguyên thủy mật mã nói chung để có thể được sử dụng trong các ứng dụng bảo mật, yêu cầu cơ bản đầu tiên được đặt ra là nó phải “an toàn”. Trong đó, “an toàn chứng minh được” trong các mô hình lý thuyết, mà dựa trên các lập luận toán học, là cơ cở để đảm bảo rằng một lược đồ/giao thức mật mã có tính logic và chắc chắn trong thiết kế. Điều này có thể được hiểu là với các thành phần “tốt” thì một lược đồ/giao thức mật mã sẽ là “tốt” nếu như nó được chỉ ra là “an toàn chứng minh được”. Phương thức chứng minh độ an toàn kể trên thường tuân theo phép suy dẫn (phản chứng) mà chỉ ra rằng nếu lược đồ/giao thức là kém an toàn thì ít nhất một trong số các thành phần cấu thành nên nó là “không đủ tốt” như giả thiết ban đầu. Một ví dụ cho thấy tầm quan trọng của an toàn chứng minh được chính là trường hợp của lược đồ chữ ký số El Gamal, luợc đồ này ban đầu được khẳng định là an toàn dựa trên bài toán logarit rời rạc, tuy nhiên thực tế là nó có thể bị giả mạo theo cách mà không cần vi phạm độ khó của bài toán cơ sở. Trên thế giới, “an toàn chứng minh được” là một hướng nghiên cứu rất được quan tâm, tuy nhiên chủ đề này chưa được khai thác nhiều ở các cô