Phát triển lược đồ chữ ký số trên bài toán logarit rời rạc

Bài báo đề xuất phương pháp xây dựng lược đồ chữ ký số dựa trên tính khó giải của bài toán logarit rời rạc. Từ dạng lược đồ tổng quát được xây dựng, một số lược đồ chữ ký đã được đề xuất cho các ứng dụng trong thực tế.
Nội dung trích xuất từ tài liệu:
Phát triển lược đồ chữ ký số trên bài toán logarit rời rạcNghiên cứu khoa học công nghệ PHÁT TRIỂN LƯỢC ĐỒ CHỮ KÝ SỐ TRÊN BÀI TOÁN LOGARIT RỜI RẠC Nguyễn Đức Thụy1*, Hồ Nhật Quang2, Lưu Hồng Dũng2 Tóm tắt: Bài báo đề xuất phương pháp xây dựng lược đồ chữ ký số dựa trên tính khó giải của bài toán logarit rời rạc. Từ dạng lược đồ tổng quát được xây dựng, một số lược đồ chữ ký đã được đề xuất cho các ứng dụng trong thực tế.Từ khoá: Digital Signature, Digital Signature Schema, Discrete logarit problem. 1. MỞ ĐẦU Trong các giao dịch điện tử (Chính phủ điện tử, Thương mại điện tử,…), chữ ký số đượcsử dụng nhằm đáp ứng yêu cầu chứng thực về nguồn gốc và tính toàn vẹn của thông tin. Hiệnnay chữ ký số đã được ứng dụng rộng rãi trong các lĩnh vực Chính phủ điện tử, Thương mạiđiện tử,… trên thế giới cũng như đã bước đầu được triển khai ở Việt Nam. Do đó, việc nghiêncứu - phát triển các lược đồ chữ ký số mới cho mục đích thiết kế - chế tạo các sản phẩm, thiếtbị an toàn và bảo mật thông tin trong nước luôn là vấn đề cần thiết được đặt ra. Bài báo đề xuấtphươ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 và mộtsố lược đồ chữ ký số được phát triển theo phương pháp chung này. 2. XÂY DỰNG LƯỢC ĐỒ CHỮ KÝ DỰA TRÊN BÀI TOÁN LOGARIT RỜI RẠC2.1. Bài toán logarit rời rạc Cho p là một số nguyên tố và g là phần tử sinh của nhóm ZP*. Khi đó bài toán logaritrời rạc - DLP (Discrete Logarithm Problem) trên trường ZP hay còn gọi là bài toán DLP( p , g ) được phát biểu như sau:Bài toán DLP(p,g): Với mỗi số nguyên dương y ℤp*, hãy tìm x thỏa mãn phương trình sau: g x mod p  y (1.1) Giải thuật cho bài toán logarit rời rạc với các tham số {p, g} công khai có thể đượcviết như một thuật toán tính hàm DLP( p , g ) (.) 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( p , g ) ( y ) Trong một hệ thống giao dịch điện tử ứng dụng chứng thực số để xác thực nguồn gốcvà tính toàn vẹn thông tin cho các thông điệp dữ liệu, bài toán DLP( p , g ) là khó theo nghĩakhông thể thực hiện được trong thời gian thực. Ở đó, 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.2) Chú ý: (i) Bài toán DLP( p , g ) là khó theo nghĩa không thể thực hiện được trong thời gian thực,tuy nhiên không phải với mọi yZP* thì việc tính DLP( p , g ) đều khó, chẳng hạn nhữngy  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 giá trị của khóa mật x phảiđược lựa chọn sao cho việc tính DLP( p , g ) ( y ) đều khó. (ii) Với lựa chọn x như trên thì không có ai ngoài U biết được giá trị x, vì vậy việc biếtđược x đủ để xác thực đó là U.Tạp chí Nghiên cứu KH&CN quân sự, Số 37, 06 - 2015 103 Công nghệ thông tin & Khoa học máy tính Hiện tại, bài toán trên vẫn được coi là bài toán khó [1,2] do chưa có giải thuật thờigian đa thức cho nó và hệ mật ElGamal [3] là một chứng minh thực tế cho tính khó giảicủa bài toán này.2.2. Xây dựng lược đồ dạng tổng quát Lược đồ dạng tổng quát được sử dụng để phát triển các lược đồ chữ ký số cho các ứngdụng thực tế. Lược đồ dạng tổng quát đề xuất ở đây được xây dựng trên cơ sở tính khógiải của bài toán logarit rời rạc và được thiết kế theo dạng lược đồ sinh chữ ký 2 thànhphần tương tự như DSA trong chuẩn chữ ký số của Mỹ (DSS) [4] hay GOST R34.10-94của Liên bang Nga [5], bao gồm các phương pháp hình thành tham số, phương pháp hìnhthành và kiểm tra chữ ký được chỉ ra dưới đây.  Phương pháp hình thành tham số và khóa Dữ liệu vào: p, q , x . Kết quả: g, y, H(.). Các bước thực hiện: 1. Tính phần tử sinh g của Zp*: g  h ( p 1) / q mod p , với: 1  h  p (2.1) 2. Tính khóa công khai: y  g  x mod p (2.2) 3. Chọn hàm băm H: {0,1}* → Zq ; Chú thích: (i) p, q: 2 số nguyên tố thỏa mãn q|(p-1). (ii) x: khóa bí mật của đối tượng ký thỏa mãn: 1  x  q .  Phương pháp hình thành chữ ký Dữ liệu vào: p, q, g, x, M. Kết quả: (e,s). Các bước thực hiện: 1. Chọn giá trị k thỏa mãn: 1  k  q . Tính giá trị r theo công thức: r  g k mod p (2.3) 2. Thành phần thứ nhất e của chữ ký được chọn t ...