PHƯƠNG PHÁP XÂY DỰNG THUẬT TOÁN 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ố.
Nội dung trích xuất từ tài liệu:
PHƯƠNG PHÁP XÂY DỰNG THUẬT TOÁN CHỮ KÝ SỐ DỰA TRÊN MỘT DẠNG BÀI TOÁN KHÓ MỚI Hội thảo lần thứ III: Một số vấn đề chọn lọc về an toàn an ninh thông tin – Đà Nẵng, 07/12/2018 Phương pháp xây dựng thuật toán chữ ký số dựa trên một dạng bài toán khó mới A construction method of digital signature algorithms based on a new hard problem Lưu Hồng Dũng Nguyễn Đức Thụy Khoa CNTT Khoa CNTT Học Viện KTQS CĐ Kinh tế - Kỹ thuật Hà Nội, Việt Nam Tp.HCM, Việt Nam e-mail: luuhongdung@gmail.com e-mail: thuyphulam2013@gmail.com Abstract— Bài báo đề xuất một phương pháp xây đó, nếu có một giải thuật thời gian đa thức cho bài dựng thuật toán chữ ký số dựa trên tính khó của toán này (DLP) thì tính an toàn của các thuật toán sẽ bài toán logarit rời rạc kết hợp khai căn trên Zp. bị phá vỡ hoàn toàn. Nâng cao độ an toàn cho các Đây là một dạng bài toán khó mới, lần đầu được thuật toán chữ ký số dựa trên tính khó của việc giải đề xuất và ứng dụng để xây dựng các thuật toán đồng thời 2 bài toán khó là một hướng tiếp cận đang chữ ký số. Từ phương pháp được đề xuất có thể nhận được nhiều sự quan tâm của các nhà nghiên xây dựng một lớp thuật toán chữ ký số có độ an cứu, trong [3 – 10] các tác giả đã đề xuất một số toàn cao cho các ứng dụng trong thực tế. 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 Keywords: Digital signature; Digital signature này, cũng với mục đích nâng cao độ an toàn cho các algorithm; Digital Signature Schema; Discrete logarithm problem. thuậ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ó I. ĐẶT VẤN ĐỀ của việc giải một bài toán khó mới, ở đây được gọi Trong [1,2] đề xuất một phương pháp xây dựng là bài toán logarit rời rạc kết hợp khai căn trên Zp. thuật toán chữ ký số dựa trên tính khó của việc giải Đây là một dạng bài toán khó lần đầu được đề xuất bài toán logarit rời rạc trên Zp. Ưu điểm của phương và ứng dụng cho việc xây dựng thuật toán chữ ký số pháp mới đề xuất là từ đó có thể triển khai một lớp và có nhiều triển vọng tạo ra các thuật toán có độ an thuật toán chữ ký số cho các ứng dụng khác nhau. toàn cao cho các ứng dụng thực tế. Tuy nhiên, độ an toàn của các thuật toán chữ ký được xây dựng theo phương pháp này chỉ được đảm bảo bởi độ khó của việc giải bài toán logarit rời rạc - DLP (Discrete Logarithm Problem) trên Zp. Do 1 Hội thảo lần thứ III: Một số vấn đề chọn lọc về an toàn an ninh thông tin – Đà Nẵng, 07/12/2018 II. BÀI TOÁN KHÓ MỚI VÀ PHƯƠNG PHÁP 3) Bài toán logarit rời rạc kết hợp khai căn trên XÂY DỰNG THUẬT TOÁN CHỮ KÝ SỐ trường Zp Bài toán logarit rời rạc kết hợp khai căn trên A. Một số bài toán khó ứng dụng trong mật mã và trường Zp (Bài toán DLRP) được đề xuất ở đây có bài toán logarit rời rạc kết hợp khai căn trên Zp thể phát biểu như sau: 1) Bài toán logarit rời rạc trên Zp Bài toán DLRP: Với mỗi số nguyên dương Bài toán logarit rời rạc trên Zp là cơ sở xây y ∈ Z *p , hãy tìm các số x1 và x2 thỏa mãn phương dựng hệ mật khóa công khai ElGamal [11]. Bài toán trình sau: 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ố (x1 )x 2 mod p = y * nguyên dương y ∈ Zp , hãy tìm x thỏa mãn phương Trường hợp x1 là hằng số thì DLRP trở thành trình: DLP, còn nếu x2 là 1 số nguyên tố (hằng số) và thỏa g x mod p = y mãn điều kiện theo [12]: p = N × ( x2 )S + 1 , với: N là Giải thuật cho bài toán DLP có thể được viết một số nguyên chẵn và S ≥ 2, thì DLRP sẽ trở thành như một thuật toán tính hàm DLP(.) với biến đầu FRP. Dễ thấy rằng, việc giải được DLRP là khó hơn vào là y còn giá trị hàm là nghiệm x của phương cả DLP và FRP. Ngay cả khi có các giải thuật thời trình: gian đa thức cho DLP và FRP thì cũng không c ...