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 trên Zp

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 việc giải một hệ phương trình phi tuyến trên Zp. Đây là một dạng bài toán khó mới chưa có phương pháp giả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:
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 trên ZpCông nghệ thông tin 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 TRÊN Zp Lưu Xuân Văn1*, Đoàn Văn Hòa2, Lưu Hồng Dũng3 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 việc giải một hệ phương trình phi tuyến trên Zp. Đây là một dạng bài toán khó mới chưa có phương pháp giả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: Chữ ký số; Thuật toán ký số; Lược đồ ký số; Logarith rời rạc. 1. ĐẶT VẤN ĐỀ Nâng cao độ an toàn cho các thuật toán chữ ký số dựa trên tính khó của việcgiải đồng thời 2 bài toán khó là một hướng tiếp cận đang nhận được nhiều sự quantâm của các nhà nghiên cứu, trong [1 – 11] các tác giả đã đề xuất một số thuật toánchữ 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. Trongbài báo này, cũng với mục đích nâng cao độ an toàn cho các 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 [12] trên cơ sở tính khócủa việc giải một hệ phương trình phi tuyế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ển vọ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 TÍNH KHÓ GIẢI CỦA HỆ PHƯƠNG TRÌNH PHI TUYẾN TRÊN Zp2.1. 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 giải hệ phương trình phi tuyến trên trường Zp được đề xuất ở đây làmột dạng bài toán khó mới, bài toán này có thể phát biểu như sau: Với mỗi cặp số nguyên dương  y1 , y2   Z *p , hãy tìm các số x1 và x2 thỏa mãnhệ phương trình sau:  x1 x1 . x2 mod p  y1   x2 x1 . x2 mod p  y 2 Về mặt hình thức, nếu x1 là hằng số còn x2 là biến cần tìm thì bài toán trên sẽtrở thành bài toán logarit rời rạc trên Zp - DLP (Discrete Logarithm Problem). Tuynhiên, ở đây x1 cũng là ẩn số như x2 , vì thế các giải thuật cho DLP không thể ápdụng với bài toán này. Tương tự, nếu x2 là hằng số và x1 là biến thì bài toán trênlại trở thành bài toán khai căn trên Zp - RP (Root Problem) [12]. Song ở đây x2cũng là biến cần tìm, do vậy các giải thuật cho RP cũng không áp dụng được đốivới bài toán mới đề xuất. Trong toán học, bài toán trên thực chất là một hệ phươngtrình phi tuyến và thuộc lớp các bài toán chưa có cách giải, các giải thuật cho DLPvà RP hiện tại là không áp dụng được với bài toán này. Điều đó cho thấy bài toánmới đề xuất ở đây có mức độ khó cao hơn DLP và RP.104 L. X. Văn, Đ. V. Hòa, L. H. Dũng, “Xây dựng lược đồ chữ ký số … phi tuyến trên Zp.”Nghiên cứu khoa học công nghệ2.2. Xây dựng lược đồ chữ ký dựa trên tính khó của bài toán mới đề xuất2.2.1. Thuật toán sinh khóa Ở lược đồ chữ ký mới đề xuất, bài toán trên được sử dụng để hình thành cặpkhóa bí mật và công khai của đối tượng ký. Trong đó, p là tham số hệ thống (thamsố miền) do nhà cung cấp dịch vụ tạo ra, ở đây p là số nguyên tố cần phải đượcchọn sao cho việc giải bài toán logarit rời rạc là khó. Cặp ( x1 , x2 ) là khóa bí mậtvà ( y1 , y2 ) là các khóa công khai tương ứng của mỗi đối tượng ký trong hệ thống.Để tạo khóa ( x1 , x2 ) mỗi thực thể ký cần tạo trước số nguyên tố q thỏa mãn: q|(p- p 11) và một cặp số ( ,  )  Z *p . Khóa bí mật x1 được tạo theo: x1   q mod p . p 1 Khóa bí mật x2 được tạo theo: x2   q mod p . Sau đó, các khóa công khai được tạo ra từ ( x1 , x2 ) theo: x .x x .x y1   x1  1 2 mod p , y2   x2  1 2 mod p (1) Chú ý rằng tham số q cũng được sử dụng với vai trò của một khóa bí mật tươngtự như x1 và x2 trong thuật toán ký. Thuật toán sinh khóa có thể được mô tả lại như trên Thuật toán 1 sau đây: Thuật toán 1. Thuật toán sinh khóa Input: p - số nguyên tố, lq - độ dài (tính theo bit) của số nguyên tố q. Output: q, x1, x2, y. [B1] generate q: len(q) = lq, q|(p-1) [B2] select (α,  ): 1   ,   p [B3] x1    p 1 / q mod p , x2    p 1 / q mod p [B4] if (( x1 =1) or ( x2 =1)) then goto [B2] [B5] y1   x1 x .x mod p , y2  x2 x . x mod p 1 2 1 2 [B6] return {q, x1, x2, y1, y2} Chú thích: - len(.) là ...