Tóm tắt Luận án Tiến sĩ Toán học: Đề xuất xây dựng lược đồ chữ ký số dựa trên bài toán khai căn và logarit rời rạc

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:27

Thêm vào BST

Báo xấu

9
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tóm tắt Luận án Tiến sĩ Toán học "Đề xuất xây dựng lược đồ chữ ký số dựa trên bài toán khai căn và logarit rời rạc" được nghiên cứu với mục tiêu là: Đề xuất dạng bài toán khó mới dựa trên việc kết hợp 2 dạng bài toán khó cơ sở: bài toán khai căn và bài toán logarit rời rạc; Đề xuất phương pháp xây dựng lược đồ CKS dựa trên dạng bài toán khai căn kết hợp logarit rời rạc; Đánh giá, thử nghiệm một số lược đồ chữ ký số đã đề xuất.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận án Tiến sĩ Toán học: Đề xuất xây dựng lược đồ chữ ký số dựa trên bài toán khai căn và logarit rời rạc

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Ự LƯU XUÂN VĂN ĐỀ XUẤT XÂY DỰNG LƯỢC ĐỒ CHỮ KÝ SỐ DỰA TRÊN BÀI TOÁN KHAI CĂN VÀ LOGARIT RỜI RẠC TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội – 2023
CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI VIỆN KH-CN QUÂN SỰ, BỘ QUỐC PHÒNG Người hướng dẫn khoa học: 1. TS Lưu Hồng Dũng 2. TS Đoàn Văn Hòa Phản biện 1: PGS, TS Lê Mỹ Tú Học viện Kỹ thuật mật mã Phản biện 2: PGS, TS Đỗ Trung Tuấn Đại học Khoa học tự nhiên, ĐHQG Hà Nội Phản biện 3: TS Thái Trung Kiên Viện Khoa học và Công nghệ quân sự Luận án được bảo vệ trước Hội đồng đánh giá luận án tiến sĩ cấp Viện, họp tại Viện Khoa học và Công nghệ quân sự Vào hồi . . . giờ . . . ngày . . . tháng . . . năm 2023. Có thể tìm hiểu luận án tại: - Thư viện Viện Khoa học và Công nghệ quân sự; - Thư viện Quốc gia Việt Nam.
1 MỞ ĐẦU 1. Tính cấp thiết của đề tài luận án Cuộc cách mạng công nghiệp lần thứ 4 đang diễn ra trên toàn thế giới mang tới cho mọi người dân những tiến bộ mới, nhiều tiện ích và dịch vụ mới. Môi trường làm việc này mang đến nhiều cơ hội nhưng cũng nảy sinh rất nhiều vấn đề về an ninh, bảo mật, an toàn thông tin. Kỹ thuật mật mã hiện nay đã được ứng dụng rộng rãi trong các lĩnh vực như Chính phủ điện tử, thương mại điện tử,. . . hay trong các hệ thống viễn thông. Trước bối cảnh đó, nhiệm vụ đặt ra cho ngành an toàn và bảo mật thông tin là phải nghiên cứu, xây dựng riêng những hệ mã hóa mới đáp ứng được mục tiêu, yêu cầu về an toàn, bảo mật thông tin, và ứng dụng hiệu quả trong lĩnh vực quốc phòng an ninh. Xuất phát từ thực tiễn nêu trên, luận án thực hiện nghiên cứu đề tài “Đề xuất xây dựng lược đồ chữ ký số dựa trên bài toán khai căn và logarit rời rạc” với mong muốn có những đóng góp vào sự phát triển khoa học và công nghệ trong lĩnh vực an toàn và bảo mật thông tin của nước ta nói chung và trong lĩnh vực quốc phòng an ninh nói riêng. 2. Mục tiêu nghiên cứu Mục tiêu chính của luận án là đề xuất phương pháp xây dựng lược đồ chữ ký số (CKS) an toàn dựa trên việc kết hợp một số bài toán khó. Các mục tiêu cụ thể như sau: - Đề xuất dạng bài toán khó mới dựa trên việc kết hợp 2 dạng bài toán khó cơ sở: bài toán khai căn và bài toán logarit rời rạc. - Đề xuất phương pháp xây dựng lược đồ CKS dựa trên dạng bài toán khai căn kết hợp logarit rời rạc. - Đánh giá, thử nghiệm một số lược đồ chữ ký số đã đề xuất. 3. Đối tượng và phạm vi nghiên cứu - Đối tượng nghiên cứu: Lược đồ chữ ký số và những thuật toán, bài toán cơ sở để xây dựng lược đồ chữ ký số. - Phạm vi nghiên cứu: + Nghiên cứu cơ sở lý thuyết một số bài toán trong lý thuyết số trên trường số hữu hạn. + Cách thức hình thành khóa và tham số hệ thống của một số chuẩn CKS (DSS, GOST), đặc biệt là các dạng lược đồ CKS 2 thành phần.
2 + Phát triển lược đồ CKS dựa trên tính khó giải của việc kết hợp các bài toán khó. 4. Nội dung nghiên cứu Nội dung nghiên cứu hướng đến của luận án là: - Cơ sở toán học của hệ mật khóa công khai, các lược đồ CKS. - Nguyên lý xây dựng và một số hệ mật khoá công khai ứng dụng xây dựng các lược đồ chữ ký số điển hình như: RSA, ElGamal, Schnorr. - Một số bài toán khó được áp dụng để xây dựng các lược đồ CKS. - Đề xuất giải pháp và lựa chọn phương án thích hợp để xây dựng lược đồ CKS mới và các thuật toán tương ứng có thể áp dụng trong thực tế. - Đánh giá hiệu quả thực hiện của lược đồ CKS mới. 5. Phương pháp nghiên cứu Luận án sử dụng một số phương pháp nghiên cứu: - Phương pháp nghiên cứu lý thuyết, cụ thể tham khảo các công trình, báo cáo khoa học, tài liệu đã công bố về lĩnh vực mật mã và chữ ký số. - Phương pháp nghiên cứu thực tiễn, phân tích và tổng hợp các kết quả đã có để từ đó rút ra vấn đề cần giải quyết, hướng nghiên cứu của luận án. 6. Ý nghĩa khoa học và thực tiễn của luận án - Ý nghĩa khoa học: Luận án đề xuất dạng kết hợp bài toán khó mới, có thể được áp dụng làm bài toán cơ sở để xây dựng lược đồ chữ ký số an toàn, là bài toán kết hợp tính khó giải của một số bài toán khó cơ bản. Tính khoa học, chính xác, an toàn của các lược đồ được xác định rõ ràng. Ngoài ra, luận án có thể sử dụng làm tài liệu tham khảo để tiếp tục đi sâu nghiên cứu xây dựng, phát triển các lược đồ chữ ký số an toàn. - Ý nghĩa thực tiễn: Phương pháp xây dựng lược đồ chữ ký số được đề xuất có thể được xây dựng, điều chỉnh, phát triển thành nhiều lược đồ chữ ký số khác nhau trong thực tế, với các thuật toán tạo chữ ký số, xác thực chữ ký số khác nhau, sử dụng các khóa có độ dài thấp hơn nhưng vẫn đảm bảo được mức độ an toàn. 7. Bố cục của luận án Ngoài các phần Mở đầu, Kết luận, và Danh mục các công trình khoa học đã công bố, luận án được bố cục 04 chương nội dung. Nội dung cơ bản của từng chương cụ thể như sau: - Chương 1: Tổng quan về chữ ký số và định hướng nghiên cứu của luận án. Nội dung của chương là một số lý thuyết toán học cơ bản thường được
3 sử dụng trong việc xây dựng, phát triển các hệ mật mã khóa công khai. Tóm tắt một số nghiên cứu liên quan đến việc phát triển các lược đồ chữ ký số trong và ngoài nước, những vấn đề tồn tại của những nghiên cứu trước và định hướng nghiên cứu của đề tài luận án. - Chương 2: Xây dựng lược đồ chữ ký số dựa trên tính khó của việc giải hệ phương trình phi tuyến. Nội dung của chương là trình bày một số dạng bài toán khó thường được sử dụng trong quá trình xây dựng các hệ mật mã, các lược đồ CKS. Đề xuất một dạng kết hợp bài toán khó mới, là dạng bài toán mà hiện nay không thể giải quyết trong thời gian đa thức được. Dạng bài toán khó mới này sẽ được sử dụng để xây dựng lược đồ chữ ký số an toàn. - Chương 3: Xây dựng lược đồ chữ ký số dựa trên tính khó giải của bài toán khai căn kết hợp logarit rời rạc. Nội dung của chương là đề xuất dạng kết hợp bài toán khó mới là kết hợp bài toán khai căn kết hợp logarit rời rạc, hiện nay chưa có lời giải hiệu quả để giải quyết; Đề xuất phương pháp xây dựng lược đồ chữ ký số dựa trên dạng bài toán khó này, có thể phát triển, xây dựng thành lớp các lược đồ chữ ký số cụ thể với những thuật toán tạo chữ ký số, xác thực chữ ký số khác nhau. - Chương 4: Xây dựng lược đồ chữ ký số mù dựa trên bài toán khai căn kết hợp logarit rời rạc. Nội dung của chương là đưa ra một số điểm yếu có thể làm lộ danh tính nguồn ký của một số lược đồ chữ ký số mù nếu áp dụng bài toán khó cơ bản và đề xuất một ứng dụng cụ thể có thể đạt được trong việc xây dựng lược đồ chữ ký số mù, dựa trên dạng bài toán khó đã đề xuất ở chương 3. Lược đồ chữ ký số mù này có tác dụng hạn chế việc lộ danh tính nguồn ký của thông điệp. CHƯƠNG 1. TỔNG QUAN VỀ CHỮ KÝ SỐ VÀ ĐỊNH HƯỚNG NGHIÊN CỨU CỦA LUẬN ÁN 1.1. Giới thiệu về chữ ký số 1.1.1. Khái niệm chữ ký số Chữ ký số là một lược đồ toán học để xác minh tính xác thực của một bản tin hoặc một tài liệu số. Một lược đồ CKS thường bao gồm 3 thuật toán: Thuật toán tạo khóa; Thuật toán ký; Thuật toán xác thực chữ ký.
4 1.1.2. Phân loại chữ ký số 1.1.2.1. Phân loại chữ ký số theo đặc trưng kiểm tra chữ ký - Chữ ký số kèm thông điệp (message appendix). - Chữ ký số khôi phục thông điệp (message recovery). 1.1.2.2. Phân loại theo mức an toàn - Chữ ký số “không thể phủ nhận”. - Chữ ký số “một lần”. 1.1.2.3. Phân loại theo ứng dụng đặc trưng - Chữ ký số “mù” (Blind Signature). - Chữ ký số “tập thể” (Group Signature). - Chữ ký số “bội” (Multi-Signature). - Chữ ký số “mù tập thể” (Blind Group Signature). - Chữ ký số “mù bội” (Blind Multi-Signature). - Chữ ký số “ngưỡng” (Threshold Signature). 1.2. Cơ sở hình thành chữ ký số 1.2.1. Mật mã học 1.2.1.1. Khái niệm, chức năng Mật mã học là ngành khoa học nghiên cứu về việc đảm bảo an toàn thông tin. Mật mã học giúp đảm bảo: tính bí mật, tính toàn vẹn, tính xác thực, tính chống chối bỏ. 1.2.1.2. Các thành phần của hệ mật Hệ mật mã là bộ gồm 5 thành phần (P, C, K, E, D) đại diện cho: bản rõ, bản mã, khóa, mã hóa, giải mã. 1.2.1.3. Phân loại Mật mã khóa bí mật (SKC); Mật mã khóa công khai (PKC); Hàm băm. 1.2.1.4. Mật mã khóa công khai PKC sử dụng hai khóa, khi biết thông tin một khóa thì cũng không dễ dàng để xác định khóa kia. Một khóa được sử dụng để mã hóa bản rõ và khóa còn lại được sử dụng để giải mã bản mã. Chữ ký số thường được phát triển từ hệ mật khóa công khai. 1.2.2. Hàm băm 1.2.2.1. Giới thiệu Hàm băm là giải thuật sinh ra các giá trị băm có kích thước cố định tương ứng với khối dữ liệu đầu vào có kích thước tùy ý.
5 1.2.2.2. Chuẩn hàm băm an toàn Chuẩn hàm băm an toàn được NIST công bố: FIPS PUB 180-1 (SHA- 1); FIPS PUB 180-2 (SHA-1, SHA-256, SHA-384, SHA-512); FIPS PUB 180-3 (SHA-224). 1.3. Một số chuẩn chữ ký số 1.3.1. Chuẩn DSS của Mỹ Gồm các phiên bản: FIPS PUB 186 (1994), FIPS PUB 186-1 (năm 1998), FIPS PUB 186-2 (2000), FIPS PUB 186-3 (2009), FIPS PUB 186-4 (2013). 1.3.2. Chuẩn GOST của Liên bang Nga Gồm chuẩn chữ ký số GOST P34.10-94, chuẩn CKS GOST P34.10- 2001, GOST R 34.10-2012 và chuẩn hàm băm GOST R 34.11-2012. 1.4. Một số hướng nghiên cứu phát triển lược đồ chữ ký số 1.4.1. Nâng cao tính hiệu quả Tính hiệu quả của các lược đồ chữ ký số dựa trên các đánh giá sau: - Hiệu quả về mặt không gian: không gian bộ nhớ cần được sử dụng. Trong các lược đồ chữ ký số, bộ nhớ cần thiết được sử dụng cho việc lưu các tham số, sinh khóa, lưu khóa, bản băm, chữ ký. - Hiệu quả về mặt thời gian: thời gian cần thiết để quá trình ký và xác thực chữ ký được thực hiện thành công. 1.4.2. Nâng cao tính an toàn Để đảm bảo sự tin cậy cho những thực thể tham gia giao dịch mạng, và đảm bảo tính tin cậy của quá trình trao đổi thông tin trên mạng, các lược đồ CKS cần phải thực sự an toàn. Sự an toàn này bao gồm: an toàn khóa, an toàn trước các dạng tấn công thông điệp, an toàn tránh giả mạo. 1.5. Hướng nghiên cứu của đề tài luận án Rất nhiều nhà nghiên cứu đã phát triển các lược đồ CKS, tất cả chúng đều có chung một đặc điểm là chỉ dựa vào một bài toán khó không khả thi về mặt tính toán, ví dụ, bài toán logarit rời rạc (DLP) hoặc bài toán phân tích số (IFP), để bảo mật. Tuy nhiên tính khó giải của một số bài toán khó cơ bản có thể giảm đi trong tương lai, vì khả năng đạt được tiến bộ lớn về hiệu quả của các thuật toán giải quyết các bài toán khó hoặc khả năng hoạt động của hệ thống tính toán, đó là một thực tế mà nhiều chuyên gia lo lắng sẽ sớm làm cho các bài toán khó đơn lẻ hiện tại sẽ không còn thực sự an toàn nữa. Điều này đã khiến nhiều tác giả đưa ra các sơ đồ mã khóa công khai
6 hoặc các lược đồ CKS dựa trên nhiều bài toán khó để nâng cao mức độ bảo mật. Tuy nhiên, nhiều lược đồ CKS được đề xuất dựa trên việc kết hợp các bài toán khó đã mắc phải các lỗi bảo mật. Kế thừa từ những nghiên cứu trước đây, luận án dự kiến tiếp tục phát triển, xây dựng một số lược đồ CKS dựa trên tính khó của việc giải đồng thời bài toán khai căn và logarit rời rạc, nhằm nâng cao độ an toàn mà vẫn đảm bảo các yêu cầu của lược đồ CKS. Để đạt được mục tiêu nghiên cứu, luận án nghiên cứu về một số bài toán khó thường được áp dụng và những thuật toán ở thời điểm hiện tại có thể giải quyết những bài toán khó này. Việc nghiên cứu này góp phần xác định được mức độ khó giải của bài toán cơ sở dựa trên việc kết hợp một số dạng bài toán khó đề xuất trong luận án. Từ bài toán cơ sở và đánh giá về tính đúng đắn, tính khó giải của bài toán này, NCS sẽ đề xuất hướng áp dụng để xây dựng lược đồ CKS. 1.6. Kết luận chương 1 Chương 1 của luận án đã thực hiện: - Nghiên cứu tổng quan về CKS, cơ sở hình thành và các thành phần cơ bản của lược đồ CKS, một số chuẩn CKS hiện nay. - Nghiên cứu và trình bày định hướng nghiên cứu phát triển các lược đồ CKS. Đề cập tới nội dung, đánh giá một số kết quả nghiên cứu trên thế giới và tại Việt Nam. - Nghiên cứu, xác định hướng nghiên cứu của đề tài luận án là xây dựng lược đồ CKS an toàn dựa trên việc kết hợp một số bài toán khó. CHƯƠNG 2. XÂY DỰNG LƯỢC ĐỒ CHỮ KÝ SỐ DỰA TRÊN TÍNH KHÓ CỦA VIỆC GIẢI HỆ PHƯƠNG TRÌNH PHI TUYẾN 2.1. Một số bài toán khó ứng dụng trong mật mã 2.1.1. Bài toán phân tích số 2.1.1.1. Mô tả bài toán phân tích số Cho số n ∈ N (N là tập các số tự nhiên), hãy tìm biểu diễn: n = k ei ∗ i=1 pi với ei ∈ N (i = 1, . . . , k) và pi ≥ 1 (i = 1, . . . , k) là các số nguyên tố.
7 2.1.1.2. Tính khó giải của bài toán phân tích số Các thuật toán giải quyết bài toán phân tích số hiện nay được chia thành 2 nhóm thuật toán như sau: Nhóm các thuật toán đặc thù, Nhóm các thuật toán tổng quát. Trong số đó, có 2 phương pháp tốt để giải quyết bài toán này là: - Phương pháp sàng trường số tổng quát (General Number Field Sieve) Đây là một trong số những thuật toán cổ điển hiệu quả nhất được biết đến để phân tích các số nguyên lớn hơn 10100 . Độ phức tạp của thuật toán này để phân tích một số nguyên n (với độ lớn [log2 n] + 1 bits) là: 64 1 64 + o(1) (ln n)1/3(ln ln n)2/3 3 3 exp = Ln , 9 3 9 - Phương pháp phân tích thừa số đường cong elliptic (ECM) Độ phức tạp thời gian tính toán của thuật toán này phụ thuộc vào kích thước của thừa số nguyên tố nhỏ nhất của n và có thể được biểu thị bằng √ 1 √ exp ( 2 + o(1)) ln p ln ln p = Lp , 2 2 trong đó p là nhân tử nhỏ nhất của n. Cho đến nay, bài toán phân tích số cũng không cần đến thời gian hàm mũ để giải nó, nhưng vẫn chưa thể giải được trong thời gian hàm đa thức, và vẫn được coi là một dạng bài toán khó được ứng dụng trong mật mã. 2.1.1.3. Ứng dụng của bài toán trong hệ mã RSA Dựa vào tính khó của bài toán phân tích số, trong mật mã học, bài toán phân tích số được áp dụng nhiều để xây dựng các hệ mật. Dựa trên tính khó của bài toán này, Rivest, Shamir và Adleman đã đề xuất hệ mật khóa công khai RSA. 2.1.2. Bài toán logarit rời rạc 2.1.2.1. Mô tả bài toán logarit rời rạc Cho số nguyên tố p và g là phần tử sinh của G∗ , với y ∈ G∗ , tìm x p p sao cho: g x = y mod p 2.1.2.2. Tính khó giải của bài toán logarit rời rạc Có các thuật toán giải quyết bài toán logarit rời rạc như: Thuật toán Baby-step giant-step, thuật toán Pohlig–Hellman, thuật toán λ của Pol- lard, thuật toán ρ của Pollard đối với bài toán logarit rời rạc, nhóm thuật
8 toán IC (Index Calculus algorithm), thuật toán sàng trường số (Number field sieve), thuật toán sàng hàm số (Function field sieve). Trong đó: - Thuật toán của Pohlig - Hellman có độ phức tạp tính toán là √ O ei(log n + pi ) i - Thuật toán tính chỉ số IC (Index Calculus algorithm) có độ phức tạp tính toán là: √ Ln[1/2, 2 + o(1)] - Một số thuật toán thuộc lớp đường cong elliptic có thể giải quyết bài toán trong thời gian Lq [1/3, c] với c > 0, nhưng đối với trường hợp tổng quát vẫn có độ phức tạp hàm mũ. Như vậy, cho đến nay, bài toán logarit rời rạc vẫn chưa thể giải được trong thời gian hàm đa thức, và vẫn được coi là một dạng bài toán khó. 2.1.2.3. Ứng dụng của bài toán trong hệ mật Elgamal Hệ mật Elgamal được xây dựng dựa trên bài toán logarit rời rạc. 2.1.3. Bài toán khai căn 2.1.3.1. Mô tả bài toán Bài toán khai căn modulo n được phát biểu như sau: Với các số nguyên dương n, k cho trước và a là một số nguyên nguyên tố cùng nhau với n, tìm giá trị x thỏa mãn phương trình đồng dư sau: xk ≡ a (mod n) 2.1.3.2. Tính khó giải của bài toán khai căn Trong một số trường hợp, việc tính toán khai căn là vô cùng đơn giản. Tuy nhiên, trong một số trường hợp khác, việc giải quyết bài toán khai căn modulo n là khó. Độ khó của giải quyết bài toán khai căn modulo n sẽ phụ thuộc vào bài toán phân tích số, và trong một số trường hợp sẽ cần việc giải quyết bài toán logarit rời rạc. 2.1.3.3. Ứng dụng của bài toán khai căn trong hệ mật Rabin Hệ Rabin có một số ưu điểm so với RSA: - Tính an toàn được chứng minh hoàn toàn tương đương với bài toán phân tích số. - Thuật toán sinh mã của Rabin nhanh hơn nhiều so với RSA.
9 2.2. Giải hệ phương trình phi tuyến trên Zp - Một dạng bài toán khó mới Bài toán này được phát biểu như sau: ∗ Với mỗi cặp số nguyên dương (y1 , y2 ) ∈ Zp , hãy tìm các số x1 và x2 thỏa mãn hệ phương trình sau: (x1)x1·x2 ≡ y1 mod p (x2)x1·x2 ≡ y2 mod p Dạng kết hợp bài toán khó mới này thuộc lớp các bài toán chưa có cách giải, các giải thuật cho DLP và IFP hiện tại là không áp dụng hiệu quả được với bài toán mới này, khó giải hơn so với dạng bài toán phân tích số, bài toán khai căn hoặc bài toán logarit rời rạc đơn thuần. Theo nghiên cứu của NCS, chỉ có thể giải hệ phương trình phi tuyến trên bằng cách thử sai, với độ phức tạp tính toán là O(2len(p) ). Đây là độ phức tạp tính toán theo hàm mũ, bất khả thi để có thể thực hiện trong thực tế. 2.3. Phương pháp xây dựng lược đồ chữ ký dựa trên tính khó của bài toán mới đề xuất 2.3.1. Thuật toán sinh khóa Thuật toán sinh khóa có thể được mô tả như Thuật toán 2.1 sau đây: Thuật toán 2.1 Thuật toán sinh khóa Input: p nguyên tố, lq - Độ dài theo bit của q . Output: q, x1 , x2 , y1 , y2 . 1: generate q : len(q) = lq, q|(p − 1) 2: select (α, β) : 1 < α, β < p 3: x1 ← α(p−1)/q mod p, x2 ← β (p−1)/q mod p 4: if ((x1 × x2 mod q = 0) or (gcd(x1 × x2 , p − 1) = 1)) then 5: go to 2 6: end if x ·x mod q 7: y1 = x1 1 2 mod p, y2 = x2 1·x2 mod q mod p x 8: return {p, q, x1 , x2 , y1 , y2 } Trong đó: - q, x1 , x2 là khóa bí mật của người ký (U ). - y1 , y2 là khóa công khai của người ký (U ).
10 2.3.2. Thuật toán ký Thuật toán ký được mô tả bằng Thuật toán 2.2 như sau: Thuật toán 2.2 Thuật toán ký Input: p, q, x1 , x2 , y1 , y2 , M Output: (R, S) 1: E = H(M ) 2: select k : 1 < k < p−1 3: Z ← k x2 mod p −1 −1 (y2 ·y1 +1)−1 4: v← k× (xE 2 × xZ )−x1·y2 1 mod p −1 −1 5: u ← v y2 ·y1 × (xE × xZ )x1 ·y2 mod 2 1 p x2 6: R ← u mod p 7: S ← v x2 mod p 8: if ((R == 1) or (S == 1)) then 9: goto 2 10: end if 11: return (R, S) Trong đó: (R, S) là chữ ký của U lên M . 2.3.3. Thuật toán kiểm tra Thuật toán kiểm tra của lược đồ mới đề xuất được mô tả trong Thuật toán 2.3 như sau: Thuật toán 2.3 Thuật toán kiểm tra Input: p, y1 , y2 , M, R, S Output: T rue\F alse 1: E = H(M ) 2: A ← Ry2 mod p 3: Z ← R × S mod p 4: B ← S y1 × y2 × y1 mod p E Z 5: if (A == B ) then 6: return T rue 7: else 8: return F alse 9: end if 2.3.4. Tính đúng đắn của lược đồ mới đề xuất Tính đúng đắn của thuật toán mới đề xuất đã được chứng minh.
11 2.3.5. Mức độ an toàn của thuật toán được đề xuất Mức độ an toàn của lược đồ mới đề xuất có thể đánh giá qua khả năng chống một số dạng tấn công như: Tấn công khóa bí mật, Tấn công giả mạo chữ ký. 2.4. Kết luận chương 2 Chương 2 của luận án đã thực hiện: - Tổng quan về một số bài toán khó được sử dụng trong việc thiết lập các hệ mật kinh điển. - Đề xuất dạng bài toán khó mới là bài toán giải hệ phương trình phi tuyến trên Zp , đây là dạng kết hợp của 2 bài toán khó cơ bản là bài toán khai căn và bài toán logarit rời rạc. Việc giải dạng bài toán khó mới này đòi hỏi phải giải đồng thời cả 2 dạng bài toán cơ sở trên, mà hiện nay chưa có phương pháp nào có thể thực hiện hiệu quả được. - Đề xuất phương pháp xây dựng lược đồ chữ ký số an toàn dựa trên dạng bài toán khó mới đã đề xuất. Những nghiên cứu về việc mở rộng hoặc kết hợp các bài toán khó cơ bản tạo ra dạng bài toán cơ sở khó hơn có thể áp dụng vào việc xây dựng các lược đồ CKS an toàn hơn và có thể thực hiện được. Những kết quả nghiên cứu đã được công bố ở các công trình [CT1], [CT2], [CT3]. CHƯƠNG 3. XÂY DỰNG LƯỢC ĐỒ CHỮ KÝ SỐ DỰA TRÊN TÍNH KHÓ GIẢI CỦA BÀI TOÁN KHAI CĂN KẾT HỢP LOGARIT RỜI RẠC 3.1. Một dạng bài toán khai căn khó giải 3.1.1. Bài toán khai căn bậc k trên Zp Bài toán khai căn bậc k trên Zp với p là số nguyên tố: Cho p là một số nguyên tố, k ∈ N ∗ , với mỗi số a ∈ Zn hãy tìm x sao cho: ∗ xk = a mod p Nhận xét: Bài toán trên có số nghiệm là 0 hoặc gcd(k, p − 1). 3.1.2. Bài toán khai căn bậc k modulo p = N k s + 1 Theo phần 3.1.1 ở trên, số nghiệm của Bài toán khai căn bậc k mod- ulo p sẽ là 0 (đối với trường hợp rất đặc biệt khi a ≡ 0 mod p) hoặc
12 s gcd(k, p − 1). Với p = N k + 1, chúng ta có: gcd(k, p − 1) = gcd(k, N k s) = k Như vậy, với p = N k s + 1, bài toán khai căn bậc k modulo p sẽ có k nghiệm. Tuy nhiên, việc giải quyết bài toán này cũng không đơn giản, tính khó của việc giải quyết bài toán khai căn bậc k modulo p = N k s +1 đã được trình bày. 3.2. Bài toán khai căn mở rộng và bài toán khai căn kết hợp logarit rời rạc 3.2.1. Bài toán khai căn mở rộng Bài toán khai căn mở rộng được phát biểu như sau: Cho p là một số nguyên tố lớn có dạng p = N k s + 1, b ∈ N ∗ , gcd(b, p − 1) = k , với số a ∈ Zp hãy tìm x sao cho: xb = a mod p Tuy nhiên, vì bài toán khai căn bậc k modulo p với p = N k s + 1 là khó, vì vậy, bài toán khai căn mở rộng này cũng là bài toán khó, thậm chí, nó còn khó hơn nhiều so với bài toán trên, vì còn phải giải xb1 = X mod p để tìm ra giá trị x thỏa mãn. 3.2.2. Bài toán khai căn kết hợp logarit rời rạc 3.2.2.1. Dạng thứ nhất - ERP Cho p là một số nguyên tố lớn có dạng p = N k s + 1, a, b ∈ N ∗ , gcd(b, p − 1).k , hãy tìm x sao cho: . . ax = xb mod p Dạng bài toán khó mới này khó giải hơn so với dạng bài toán logarit rời rạc và khai căn đơn thuần. Vì vậy, nó hoàn toàn có thể được sử dụng để xây dựng các lược đồ CKS trong thực tế. 3.2.2.2. Dạng thứ hai - RDLP ∗ Cho p là số nguyên tố lớn, với số nguyên dương y ∈ Zp cho trước, hãy tìm các số x1 và x2 thỏa mãn: y = (x1)x2 mod p Trường hợp x1 là hằng số thì bài toán trở thành bài toán Logarit rời rạc DLP, còn nếu x2 là hằng số và gcd(x2 , φ(p)) = 1 thì đây là dạng
13 bài toán khai căn. Việc giải được RDLP là khó hơn cả RP và DLP. Dạng bài toán khó mới này hoàn toàn có thể được sử dụng để xây dựng các thuật toán mã hóa và giải mã khóa công khai trong thực tế. 3.2.2.3. Dạng thứ ba ∗ Cho p là số nguyên tố lớn, với số nguyên dương y ∈ Zp cho trước, ∗ hãy tìm số x ∈ Zp thỏa mãn: y = xx mod p Các phương pháp giải quyết bài toán DLP đã biết hiện nay cũng không thể sử dụng để giải quyết bài toán khai căn kết hợp logarit rời rạc dạng thứ ba này được. Như vậy, việc giải quyết bài toán này là khó hơn nhiều so với các bài toán khai căn và logarit rời rạc. Nhờ đó, chúng ta có thể tạo ra các khóa công khai sử dụng trong các lược đồ CKS. 3.3. Phương pháp xây dựng lược đồ chữ ký số tổng quát dựa trên tính khó giải bài toán khai căn kết hợp bài toán logarit rời rạc 3.3.1. Lược đồ chữ ký dựa trên tính khó của bài toán khai căn kết hợp bài toán logarit rời rạc 3.3.1.1. Thuật toán sinh khóa Quá trình sinh tham số và khóa được mô tả như trong Thuật toán 3.1: Thuật toán 3.1 Thuật toán sinh khóa Input: lp, lq - Độ dài theo bit của p, q . Output: p, q, t, x, y . 1: generate p: len(p) = lp 2: select t: te | (p − 1), e ≥ 2 3: generate q : len(q) = lq , q|(p − 1) 4: select α : α ∈ (1, p) 5: x ← α(p−1)/q mod p 6: if ((x = 1) or (x mod q = 0)) then 7: go to 4 8: end if 9: y ← xx mod p 10: return {p, q, t, x, y}
14 3.3.1.2. Thuật toán ký Quá trình ký số sẽ được thực hiện theo Thuật toán 3.2 như sau: Thuật toán 3.2 Thuật toán ký Input: p, q, x, y, M . Output: (R, S). 1: E = Hash(M ) 2: select β : β ∈ (1, p), k ← β (p−1)/q mod p 3: Z ← k x mod p −1 −Z.E −1 (E −1·y+1) 4: v ← k×x mod p 5: u ← k × v −1 mod p 6: R ← ux mod p 7: S ← v x mod p 8: if ((R == 1) or (S == 1)) then 9: go to 2 10: end if 11: return (R, S) Trong đó: (R, S) là chữ ký của thông điệp M . 3.3.1.3. Thuật toán xác thực chữ ký Quá trình xác thực chữ ký số được mô tả theo Thuật toán 3.3 như sau: Thuật toán 3.3 Thuật toán xác thực chữ ký Input: p, y, M, R, S . Output: T rue/F alse. 1: E ← Hash(M ) 2: A ← RE mod p 3: Z ← R × S mod p 4: B ← S y × yZ 5: if (A == B) then 6: return T rue 7: else 8: return F alse 9: end if 3.3.1.4. Tính đúng đắn của lược đồ Tính đúng đắn của lược đồ đã được chứng minh
15 3.3.1.5. Đánh giá mức độ an toàn của lược đồ Lược đồ CKS có khả năng chống lại một số dạng tấn công như: an toàn trước việc tấn công vào khóa bí mật, an toàn trước việc tấn công vào thuật toán ký, an toàn trước việc tấn công vào thuật toán xác thực. 3.3.2. Lược đồ tổng quát dựa trên tính khó giải bài toán khai căn kết hợp logarit rời rạc 3.3.2.1. Phương pháp hình thành tham số và khóa Phương pháp sinh tham số và khóa được mô tả trong Thuật toán 3.4: Thuật toán 3.4 Thuật toán sinh tham số và sinh khóa Input: lp, lq - độ dài theo bit của các số nguyên tố p, q . Output: (p, q, x, y) 1: generate p, q : len(p) = lp, len(q) = lq, q|(p − 1) 2: select α: α ∈ (1, p) 3: x ← α(p−1)/q mod p 4: if ((x = 1) or (x mod q = 0)) then 5: go to 2 6: end if 7: y ← xx mod p 8: return (p, q, x, y) Trong đó: x, y là khóa bí mật, khóa công khai tương ứng. 3.3.2.2. Phương pháp xây dựng thuật toán ký Thuật toán ký được mô tả như sau: Thuật toán 3.5 Thuật toán ký Input: (p, q, x, y, M ). Output: (R, S). 1: select β : 1 < β < p 2: k ← β (p−1)/q mod p 3: Z ← k x mod p 4: e1 ← H(Z||M ), e2 ← H(Z||y), e3 ← H(Z||y||M ) −1 −1 5: u ← k (e1+e2) ·e2 × x(e1+e2) ·e3 mod p 6: v ← k × u−1 mod p 7: R ← ux mod p 8: S ← v x mod p 9: return (R, S)
16 Trong đó: (R, S) là chữ ký số của M . 3.3.2.3. Thuật toán kiểm tra chữ ký Thuật toán kiểm tra của lược đồ được mô tả như sau: Thuật toán 3.6 Thuật toán kiểm tra chữ ký Input: p, y, M, R, S. Output: T rue/F alse. 1: Z ← R × S mod p 2: e1 ← H(Z||M ), e2 ← H(Z||y), e3 ← H(Z||y||M ) 3: A ← Re1 mod p 4: B ← S e2 × y e3 mod p 5: if (A == B) then 6: return T rue 7: else 8: return F alse 9: end if 3.3.2.4. Tính đúng đắn của lược đồ Tính đúng đắn của lược đồ đã được chứng minh. 3.3.2.5. Mức độ an toàn của lược đồ Lược đồ CKS an toàn trước việc tấn công vào khóa, an toàn trước việc tấn công vào thuật toán ký, an toàn trước việc tấn công giả mạo. 3.3.2.6. Hiệu quả thực hiện của lược đồ So sánh chi phí thực hiện của lược đồ mới đề xuất cho thấy hiệu quả thực hiện của lược đồ đề xuất thấp hơn các lược đồ DSA và GOST R34- 10.94 khoảng 2 – 3 lần. Đây chính là chi phí phải trả cho việc nâng cao độ an toàn của lược đồ CKS. 3.3.3. Một số lược đồ chữ ký số được phát triển từ lược đồ tổng quát 3.3.3.1. Lược đồ chữ ký số DVH01 3.3.3.2. Lược đồ chữ ký số DVH02 3.4. Kết luận chương 3 Chương 3 của luận án đã nghiên cứu sâu về bài toán khai căn. Trong một số trường hợp, việc giải quyết bài toán khai căn lại có độ phức tạp lớn hơn so với giải quyết bài toán DLP. Từ bài toán khai căn là cơ sở, luận án đã trình bày một số dạng bài toán khó khác, gọi chung là bài toán khai căn kết hợp logarit rời rạc.
17 Việc giải quyết bài toán khai căn kết hợp logarit rời rạc đòi hỏi phải giải quyết 2 bài toán này đồng thời. Dạng kết hợp bài toán khó mới này không thể giải quyết được tại thời điểm hiện nay. Nghiên cứu và đề xuất phương pháp xây dựng lược đồ CKS dựa trên tính khó giải của bài toán khai căn kết hợp bài toán logarit rời rạc. Những kết quả nghiên cứu đạt được đã được công bố tại các công trình [CT4] và [CT5]. CHƯƠNG 4. XÂY DỰNG LƯỢC ĐỒ CHỮ KÝ SỐ MÙ DỰA TRÊN BÀI TOÁN KHAI CĂN KẾT HỢP LOGARIT RỜI RẠC 4.1. Chữ ký số mù và điểm yếu của một số lược đồ chữ ký số mù 4.1.1. Chữ ký số mù Chữ ký số mù được đề xuất bởi D. Chaum vào năm 1983, đây là một loại CKS được sử dụng để xác thực tính toàn vẹn của một bản tin điện tử và danh tính của người ký, nhưng không cho phép xác thực nguồn gốc thực sự của bản tin được ký. Tuy nhiên, một số lược đồ trên là không có khả năng chống lại kiểu tấn công làm lộ nguồn gốc của bản tin được ký, vì thế khả năng ứng dụng của các lược đồ này trong thực tế là rất hạn chế. 4.1.2. Tấn công lược đồ chữ ký số mù DSA cải tiến 4.1.2.1. Lược đồ chữ ký số DSA cải tiến 4.1.2.2. Lược đồ chữ ký số mù DSA Từ lược đồ chữ ký DSA cải tiến, nhóm tác giả Jan L. Camenisch, Jean-Marc Piveteau, Markus A. Stadler đề xuất một lược đồ CKS mù với thủ tục hình thành tham số hệ thống bao gồm một số nguyên tố p, q , ∗ q là ước của (p − 1) và phần tử sinh g ∈ Zp có bậc là q . Người ký có khóa bí mật x ∈ Zq và khóa công khai tương ứng là y = g x mod p. 4.1.2.3. Tấn công làm lộ nguồn gốc bản tin được ký Để tấn công làm lộ nguồn gốc bản tin được ký M , người ký A cần lưu trữ giá trị các tham số (R′ , m′ , s′ ) và IDB ở mỗi lần ký. A có thể xác định được danh tính của B bằng Thuật toán 4.1 như sau:
18 Thuật toán 4.1 Thuật toán xác định danh tính B ′ Input: (M, r, s), {(Ri , m′i , s′i , IDBi )|i = 0, 1, 2, . . . , N } Output: IDBi 1: m ← H(M ), i = 0 2: ′ select: (Ri , m′i , s′i , IDBi ) 3: α ← m′i × m−1 × r × R′−1 mod q 4: β ← m−1 × (s − s′i × r × R′−1) mod q ′ 5: R ← (Ri)α × g β mod p 6: r∗ ← R mod q 7: if (r∗ ̸= r) then 8: i←i+1 9: goto 2 10: end if 11: return IDBi Lược đồ chữ ký số mù DSA sẽ không an toàn xét theo khía cạnh chống tấn công làm lộ nguồn gốc bản tin nếu số lượng bản tin được ký không đủ lớn. 4.1.3. Tấn công lược đồ chữ ký số mù Nyberg-Rueppel 4.1.3.1. Lược đồ chữ ký số Nyberg-Rueppel 4.1.3.2. Lược đồ chữ ký số mù Nyberg-Rueppel Cũng nhóm tác giả Jan L. Camenisch, Jean-Marc Piveteau, Markus A. Stadler đã đề xuất một lược đồ CKS mù được phát triển từ lược đồ chữ ký Nyberg-Rueppel. 4.1.3.3. Tấn công làm lộ nguồn gốc bản tin được ký Để tấn công làm lộ nguồn gốc bản tin được ký M , người ký A cần lưu trữ giá trị các tham số (r′ , m′ , s′ ) và IDB ở mỗi lần ký. Từ đó, A có thể xác định được danh tính của B bằng Thuật toán 4.2 như sau: Thuật toán 4.2 Thuật toán tấn công lộ nguồn gốc bản tin ký Input: (M, r, s), {(Ri , m′i , s′i , IDBi )|i = 0, 1, 2, . . . , N } ′ Output: IDBi 1: m ← H(M ), i = 0 2: select: (ri , m′ , s′ , IDBi ) ′ i i 3: β ← r × (m′ )−1 mod q i