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

Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 37, 06 - 2015 103
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ố được 
sử 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ện 
nay 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ên 
cứ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ết 
bị 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ấ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 và một 
số 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ẠC 
2.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 logarit 
rời rạc - DLP (Discrete Logarithm Problem) trên trường ZP hay còn gọi là bài toán 
),( gpDLP đượ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: 
 ypg x mod (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ể được 
viết như một thuật toán tính hàm (.)),( gpDLP 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): 
)(),( yDLPx gp 
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ốc 
và tính toàn vẹn thông tin cho các thông điệp dữ liệu, bài toán ),( gpDLP là khó theo nghĩa 
khô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(1 px , tính và công khai tham số: 
 pgy x mod (1.2) 
Chú ý: 
(i) Bài toán ),( gpDLP 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 ),( gpDLP đều khó, chẳng hạn những 
pgy x mod 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 )(),( yDLP gp đề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. 
Công nghệ thông tin & Khoa học máy tính 
N.§. Thụy, H.N.Quang, L.H.Dũng,“Phát triển lược đồ chữ ký  logarit rời rạc.” 104 
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ời 
gian đ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ải 
củ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 ứng 
dụ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ành 
phần tương tự như DSA trong chuẩn chữ k ý số của Mỹ (DSS) [4] hay GOST R34.10-94 
củ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ình 
thà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*: phg
qp mod/)1( , với: ph 1 (2.1) 
2. Tính khóa công khai: pgy x mod (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: qx 1 . 
 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: qk 1 . Tính giá trị r theo công thức: 
 pgr k mod (2.3) 
2. Thành phần thứ nhất e của chữ k ý được chọn theo một trong hai dạng: 
 qre mod (2.4) 
hoặc: 
 qrMfe mod),(1 (2.5) 
3. Thành phần thứ hai s của chữ k ý được hình thành theo một trong các dạng 
sau: 
 qrMfxrMfks mod)],(.),(.[ 3
1
2 
 (2.6) 
 hoặc: 
 qrMfxrMfks mod)],(.),(.[ 132
 (2.7) 
 Chú thích: 
(i) M: thông điệp dữ liệu cần k ý. 
(ii) (e,s): chữ ký lên M của đối tượng sở hữu {x,y}. 
(iii) ),(),,(),,( 321 rMfrMfrMf : là các hàm của M, r và thỏa mãn điều 
kiện: 
 qrMfrMfrMf ),(),,(),,(1 321 
 Phương pháp kiểm tra chữ ký 
Dữ liệu vào: p, q, g, y, M, (e,s). 
Kết quả: Khẳng định (e,s) là chữ k ý hợp lệ ((e,s) = true) hay (e,s) là giả 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 37, 06 - 2015 105
 mạo và/hoặc M không còn toàn vẹn ((e,s) = false). 
Các bước thực hiện: 
1. Tính giá trị u: 
 pygu rMfrMfrMfs mod),().,(),(. 322 (2.8), nếu s được tính theo (2.6) 
 hoặc: 
 pygu rMfsrMfs mod),(.),(. 32 (2.9), nếu s được tính theo (2.7) 
2. Tính giá trị v: 
 quv mod (2.10), nếu e được tính theo (2.4) 
 hoặc: 
 quMfv mod),(1 (2.11), nếu e được tính theo (2.5) 
3. Kiểm tra nếu: v = e (2.12), thì: (e,s) = true, ngược lại: (e,s) = false. 
 Tính đúng đắn của lược đồ dạng tổng quát 
Điều cần chứng minh ở đây là: nếu tham số và khóa được hình thành theo (2.1) và 
(2.2), chữ k ý được hình thành theo các công thức từ (2.3) đến (2.7), còn kiểm tra chữ 
k ý được thực hiện theo (2.8) đến (2.11) thì điều kiện chỉ ra bởi (2.12) sẽ được thỏa 
mãn. 
Bổ đề 1.1: 
Cho p và q là 2 số nguyên tố với q là ước số của (p-1), h là một số nguyên dương 
nhỏ hơn p. Nếu: phg qp mod/1( thì: 1mod pg q . 
Chứng minh: 
Ta có: 
 phpphpg pqqpq modmod)mod(mod )1(/)1( 
Theo định l ý Fermat thì: 
 1mod)1( ph p 
Vì vậy: 
 1mod pg q