Một phương pháp xây dựng lược đồ chữ ký số dựa trên bài toán logarit rời rạc

Bài viết đề xuất một phương pháp xây dựng lược đồ chữ ký số dựa trên tính khó của bài toán logarit rời rạc. Từ phương pháp được đề xuất có thể triển khai ra các lược đồ chữ ký khác nhau để lựa chọn phù hợp cho các ứng dụng trong thực tế.
Nội dung trích xuất từ tài liệu:
Một phương pháp xây dựng lược đồ chữ ký số dựa trên bài toán logarit rời rạc Kỷ yếu Hội nghị Khoa học Quốc gia lần thứ IX “Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR'9)”; Cần Thơ, ngày 4-5/8/2016 DOI: 10.15625/vap.2016.00055 MỘT PHƯƠNG PHÁP XÂY DỰNG LƯỢC ĐỒ CHỮ KÝ SỐ DỰA TRÊN BÀI TOÁN LOGARIT RỜI RẠC Lưu Hồng Dũng 1, Nguyễn Đức Thụy2, Lê Đình Sơn3, Nguyễn Thị Thu Thủy4 1 Khoa Công nghệ thông tin, Học viện Kỹ thuật Quân sự 2 Khoa Công nghệ thông tin, Cao đẳng Kinh tế - Kỹ thuật Tp. Hồ Chí Minh 3 Phòng SĐH, Học viện Kỹ thuật Quân sự 4 Khoa Cơ bản, Cao đẳng Kinh tế - Kỹ thuật Quảng Nam luuhongdung@gmail.com, thuyphulam2013@gmail.com, sonld2004@gmail.com, thuytoankhcb@gmail.com TÓM TẮT— Bài báo đề xuất một phương pháp xây dựng lược đồ chữ ký số dựa trên tính khó của bài toán logarit rời rạc. Từ phương pháp được đề xuất có thể triển khai ra các lược đồ chữ ký khác nhau để lựa chọn phù hợp cho các ứng dụng trong thực tế. Từ khóa— Chữ ký số, lược đồ chữ ký số, thuật toán chữ ký số, bài toán logarit rời rạc. I. ĐẶT VẤN ĐỀ Lƣợc đồ chữ k‎ý số xây dựng trên bài toán logarit rời rạc lần đầu tiên đƣợc T. ElGamal [1] đề xuất vào năm 1985. Phƣơng pháp xây dựng lƣợc đồ chữ k‎ý của ElGamal đã đƣợc sử dụng trong nhiều lƣợc đồ chữ k‎ý phát triển sau đó, mà quan trọng nhất là lƣợc đồ chữ k‎ý Schnorr [2] với việc cải tiến các tham số hệ thống nhằm cho phép rút gọn độ dài chữ ký và giảm độ phức tạp tính toán trong các thủ tục sinh và kiểm tra chữ ký. Các chuẩn chữ k‎ý số của Hoa Kỳ [3], Nga [4], … đều đƣợc xây dựng trên cơ sở kết hợp phƣơng pháp của ElGamal và Schnorr. Các lƣợc đồ chữ k‎ý này đƣợc gọi chung là họ chữ k‎ý ElGamal. Trong [5] các tác giả đề xuất một phƣơng pháp xây dựng lƣợc đồ chữ k‎ý số đƣợc phát triển từ phƣơng pháp xây dựng của họ chữ k‎ý ElGamal, ƣu điểm của phƣơng pháp đề xuất là có thể phát triển đƣợc nhiều lƣợc đồ chữ k‎ý khác nhau cho các ứng dụng thực tế. Trong bài báo này, nhóm tác giả tiếp tục đề xuất một phƣơng pháp xây dựng lƣợc đồ chữ k‎ý số dựa trên tính khó của bài toán logarit rời rạc, tuy nhiên phƣơng pháp đề xuất ở đây có nguyên tắc thiết kế hoàn toàn khác với phƣơng pháp xây dựng của họ chữ k‎ý ElGamal. Tƣơng tự [5], ƣu điểm của phƣơng pháp mới đề xuất ở đây là từ đó có thể phát triển đƣợc nhiều lƣợc đồ chữ ký khác nhau để lựa chọn phù hợp với yêu cầu của các ứng dụng trong thực tế. Hiện tại, chƣa có các kết quả nghiên cứu tƣơng tự đƣợc công bố ở trong và ngoài nƣớc. II. XÂY DỰNG LƯỢC ĐỒ CHỮ KÝ SỐ TRÊN BÀI TOÁN LOGARIT RỜI RẠC A. Phương pháp xây dựng lược đồ chữ ký trên bài toán logarit rời rạc 1. Bài toán logarit rời rạc Cho p là số nguyên tố, g là phần tử sinh của nhóm ℤp*. Khi đó bài toán logarit rời rạc trên trƣờng hữu hạn nguyên tố DLP(p,g) đƣợc phát biểu nhƣ sau: Bài toán DLP(g,p) : Với mỗi số nguyên dƣơng y ℤp*, hãy tìm x thỏa mãn phƣơng trình: g x mod p  y (1.1) Giải thuật cho bài toán DLP(g,p) có thể đƣợc viết nhƣ một thuật toán tính hàm DLP(g,p)(.) 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 (1.1): x  DLP( g , p ) ( y) (1.2) Dạng lƣợc đồ chữ ký xây dựng theo phƣơng pháp mới đề xuất ở đây cho phép các thực thể k‎ý trong cùng một hệ thống có thể dùng chung bộ tham số {g, p}, trong đó mỗi thành viên U của hệ thống tự chọn cho mình khóa bí mật x thỏa mãn: 1< x < (p-1), tính và công khai tham số: y  g x mod p (1.3) Chú ý: (i) Mặc dù bài toán DLP(g,p) là khó, tuy nhiên không phải với mọi yℤp* thì việc tính DLP(g,p) (y) đều khó, chẳng hạn những y  g x mod p , với x không đủ lớn thì bằng cách duyệt dần x = 1, 2, ... cho đến khi tìm đƣợc nghiệm của (1.2) ta sẽ tìm đƣợc khóa bí mật x, do đó các tham số mật x phải đƣợc lựa chọn sao cho việc tính DLP(g,p) (y) đều khó. (ii) Với lựa chọn x nêu trên, chỉ có ngƣời ký U biết đƣợc giá trị x, vì vậy việc biết đƣợc x đủ để xác thực đó là U. 454 MỘT PHƢƠNG PHÁP XÂY DỰNG LƢỢC ĐỒ CHỮ KÝ SỐ TRÊN BÀI TOÁN LOGARIT RỜI RẠC B. Xây dựng lược đồ chữ ký số trên bài toán DLP(p,g) Dạng lƣợc đồ mới đề xuất ở đây xây dựng dựa trên tính khó giải của bài toán DLP(g,p) và đƣợc thiết kế theo dạng lƣợc đồ sinh chữ ký 2 thành phần tƣơng tự nhƣ DSA trong chuẩn chữ k‎ý số DSS (Digital Signature Standard) của Hoa Kỳ [3] hay GOST R34.10-94 [4] của Liên bang Nga. Giả sử rằng khóa bí mật của ngƣời k‎ý là x đƣợc chọn ngẫu nhiên trong khoảng (1, p) và khóa công khai tƣơng ứng y đƣợc hình thành từ x theo (1.3): y  g x mod p Ở đây p là số nguyên tố đƣợc chọn sao cho việc giải bài toán DLP(g,p) (y) là khó, g là phần tử sinh của nhóm ℤp* có bậc là q, với q|(p-1). Giả sử (r,v) là chữ k‎ý lên bản tin M, u là 1 giá trị: 1 < u < q và r đƣợc tính từ u theo công thức: r  g u mod p (1.4) và v là một giá trị đƣợc tính từ s theo công thức: v  g s mod p (1.5) Cũng giả thiết rằng phƣơng trình kiểm tra của lƣợc đồ có dạng: ...