Xây dựng lược đồ chữ ký số dựa trên một dạng bài toán khó mới

Bài viết đề xuất một phương pháp xây dựng thuật toán chữ ký số dựa trên tính khó của bài toán logarit rời rạc kết hợp khai căn trên Zp. Đây là một dạng bài toán khó mới, lần đầu được đề xuất và ứng dụng để xây dựng các thuật toán chữ ký số. Từ phương pháp được đề xuất có thể xây dựng một lớp thuật toán chữ ký số có độ an toàn cao cho các ứng dụng trong thực tế.
Nội dung trích xuất từ tài liệu:
Xây dựng lược đồ chữ ký số dựa trên một dạng bài toán khó mớiCông nghệ thông tin XÂY DỰNG LƯỢC ĐỒ CHỮ KÝ SỐ DỰA TRÊN MỘT DẠNG BÀI TOÁN KHÓ MỚI Nguyễn Đức Thụy1, Lưu Hồng Dũng2* Tóm tắt: Bài báo đề xuất một phương pháp xây dựng thuật toán chữ ký số dựa trên tính khó của bài toán logarit rời rạc kết hợp khai căn trên Zp. Đây là một dạng bài toán khó mới, lần đầu được đề xuất và ứng dụng để xây dựng các thuật toán chữ ký số. Từ phương pháp được đề xuất có thể xây dựng một lớp thuật toán chữ ký số có độ an toàn cao cho các ứng dụng trong thực tế.Từ khóa: Digital signature; Digital signature algorithm; Digital Signature Schema; Discrete logarithmproblem. 1. ĐẶT VẤN ĐỀ Trong [1,2] đề xuất một phương pháp xây dựng thuật toán chữ ký số dựa trêntính khó của việc giải bài toán logarit rời rạc trên Zp. Ưu điểm của phương phápmới đề xuất là từ đó có thể triển khai một lớp thuật toán chữ ký số cho các ứngdụng khác nhau. Tuy nhiên, độ an toàn của các thuật toán chữ ký được xây dựngtheo phương pháp này chỉ được đảm bảo bởi độ khó của việc giải bài toán logaritrời rạc - DLP (Discrete Logarithm Problem) trên Zp. Do đó, nếu có một giải thuậtthời gian đa thức cho bài toán này (DLP) thì tính an toàn của các thuật toán sẽ bịphá vỡ hoàn toàn. Nâng cao độ an toàn cho các thuật toán chữ ký số dựa trên tínhkhó của việc giải đồng thời 2 bài toán khó là một hướng tiếp cận đang nhận đượcnhiều sự quan tâm của các nhà nghiên cứu, trong [3 – 10] các tác giả đã đề xuấtmột số thuật toán chữ ký xây dựng trên đồng thời hai bài toán phân tích số vàlogarit rời rạc. Trong bài báo này, cũng với mục đích nâng cao độ an toàn cho cácthuật toán chữ ký số, nhóm tác giả tiếp tục phát triển phương pháp đề xuất trong[1,2] trên cơ sở tính khó của việc giải một bài toán khó mới, ở đây được gọi là bàitoán logarit rời rạc kết hợp khai căn trên Zp. Đây là một dạng bài toán khó lần đầuđược đề xuất và ứng dụng cho việc xây dựng thuật toán chữ ký số và có nhiều triểnvọng tạo ra các thuật toán có độ an toàn cao cho các ứng dụng thực tế.2. XÂY DỰNG LƯỢC ĐỒ CHỮ KÝ SỐ DỰA TRÊN BÀI TOÁN LOGARIT RỜI RẠC KẾT HỢP KHAI CĂN TRÊN Zp2.1. Một số bài toán khó ứng dụng trong mật mã và bài toán logarit rời rạc kết hợp khai căn trên Zp2.1.1. Bài toán logarit rời rạc trên Zp Bài toán logarit rời rạc trên Zp là cơ sở xây dựng hệ mật khóa công khaiElGamal [11]. Bài toán có thể được phát biểu như sau: Cho p là số nguyên tố, g làphần tử sinh của nhóm Zp*. Với mỗi số nguyên dương y  Zp*, hãy tìm x thỏa mãnphương trình: g x mod p  y174 N. Đ. Thụy, L. H. Dũng, “Xây dựng lược đồ chữ ký số … bài toán khó mới.”Nghiên cứu khoa học công nghệ Giải thuật cho bài toán DLP có thể được viết như một thuật toán tính hàmDLP(.) với biến đầu vào là y còn giá trị hàm là nghiệm x của phương trình: x  DLP( y )Ở hệ mật ElGamal, bài toán logarit rời rạc được sử dụng với vai trò hàm một chiềutrong việc hình thành khóa của các thực thể trong cùng hệ thống với bộ tham số{p,g} dùng chung.2.1.2. Bài toán khai căn trên Zp Bài toán khai căn (FRP) trên Zp có thể được phát biểu như sau: Cho p là sốnguyên tố, với mỗi số nguyên dương y  Zp*, hãy tìm x thỏa mãn phương trình: x k mod p  y Trong [12], tác giả N.A. Moldovyan đã chứng minh bài toán khai căn trên làkhó nếu thỏa mãn: p  N .k S  1 Ở đây: N là một số nguyên chẵn, k là một số nguyên tố và S ≥ 2. Ngoài ra, p vàk còn phải có kích thước thỏa mãn: |p| ≥ 1024 bit và: |k| ≥ 160 bit. 2.1.3. Bài toán logarit rời rạc kết hợp khai căn trên trường ZpBài toán logarit rời rạc kết hợp khai căn trên trường Zp (Bài toán DLRP) được đềxuất ở đây có thể phát biểu như sau: Bài toán DLRP: Với mỗi số nguyên dương y  Z *p , hãy tìm các số x1 và x2thỏa mãn phương trình sau: x1 x 2 mod p  y Trường hợp x1 là hằng số thì DLRP trở thành DLP, còn nếu x2 là 1 số nguyêntố (hằng số) và thỏa mãn điều kiện theo [12]: p  N  x2 S  1 , với: N là một sốnguyên chẵn và S ≥ 2, thì DLRP sẽ trở thành FRP. Dễ thấy rằng, việc giải đượcDLRP là khó hơn cả DLP và FRP. Ngay cả khi có các giải thuật thời gian đa thứccho DLP và FRP thì cũng không có nghĩa là sẽ giải được DLRP.2.2. Xây dựng lược đồ chữ ký dựa trên tính khó của bài toán DLRP2.2.1. Thuật toán sinh khóa Ở phương pháp xây dựng thuật toán chữ ký mới đề xuất, DLRP được sử dụngđể hình thành cặp khóa bí mật và công khai của đối tượng ký. Trong đó, p là thamsố hệ thống (tham số miền) do nhà cung cấp dịch vụ tạo ra, ở đây p là số nguyên tốcần phải được chọn sao cho việc giải bài toán DLP là khó. Cặp (x1, x2) là khóa bímật và y là kh ...