Phát triển thuật toán của Danied Shank để giải bài toán Logarit rời rạc trên vành Zn

Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 48, 04 - 2017 129
PHÁT TRIỂN THUẬT TOÁN CỦA DANIED SHANK ĐỂ GIẢI BÀI 
TOÁN LOGARIT RỜI RẠC TRÊN VÀNH Zn 
Lê Văn Tuấn1*, Bùi Thế Truyền2 
Tóm tắt: Bài viết này giới thiệu phương pháp tính logarit rời rạc trên trường 
hữu hạn Zp của Danied Shanks và của Polig-Hellman. Dựa trên phương pháp của 
Danied Shanks, chúng tôi phát triển nó để giải bài toán logarit rời rạc trên vành Zn. 
Kết quả nghiên cứu được ứng dụng vào phân tích độ an toàn của lược đồ chữ ký số 
trên bài toán logarit rời rạc trong vành Zn 
Từ khoá: Vành hữu hạn, Trường hữu hạn, Bài toán logarit rời rạc. 
1. MỞ ĐẦU 
Tương tự bài toán phân tích số nguyên lớn ra thừa số, bài toán logarit rời rạc 
thuộc lớp bài toán khó giải. Hiện nay, một lớp hệ mật khóa công khai và biến thể 
của nó được xây dựng dựa trên độ khó của bài toán này. Tuy nhiên, bài toán logarit 
rời rạc không phải khó giải trong mọi trường hợp. Chính vì thế, các nhà khoa học 
đã lợi dụng những trường hợp không khó của bài toán để xây dựng các thuật toán 
giải bài toán logarit rời rạc. Một thực tế cho thấy, đa số các thuật toán giải bài toán 
logarit rời rạc hiện nay, chỉ áp dụng được trên trường hữu hạn Zp. Trong khi đó, 
một số hệ mã khóa công khai và các biến thể của nó được xây dựng trên cấu trúc 
vành Zn. Với mục tiêu nhằm loại bỏ những mầm mống không an toàn cho các hệ 
mật khoá công khai và các hệ chữ ký số dựa trên độ khó của bài toán logarit rời rạc 
trên vành Zn, trên cơ sở tìm hiểu những thuật toán giải bài toán logarit rời rạc đã 
được công bố trên thế giới[2][3][5] và một số công trình liên quan đến bài toán 
logarit rời rạc trên vành Zn,[1][4][8], chúng tôi phát triển thuật toán Baby step 
Giant Step của Danied Shanks để giải được bài toán logarit rời rạc trên vành Zn. 
Giả sử nhóm cyclic G= là nhóm con của nhóm nhân và cỡ bậc của g là m 
bit. Khi đó bậc của g thuộc đoạn [2m-1,2
m-1] và khoảng tìm giá trị logarit rời rạc 
thuộc đoạn [0,2m-1]. Trong bài viết này, chúng tôi phát triển thuật toán Baby-step 
Giant-step của Danied Shanks để tìm logarit rời rạc trong nửa đoạn [0,2m-1) trên 
vành Zn. Việc tìm logarit rời rạc thuộc đoạn [2
m-1,2m-1] nằm ngoài phạm vi nghiên 
cứu trong bài báo này. Kết quả nghiên cứu là cơ sở để xây dựng tiêu chuẩn tham số 
an toàn [9] cho hệ chữ ký số, hoặc các biến thể của nó dựa vào độ khó của bài toán 
logarit rời rạc trên vành Zn. 
2. CƠ SỞ TOÁN HỌC 
2.1. Một số ký hiệu, định nghĩa và tính chất 
Bitlength(M): Hàm trả về số bít của số nhị phân biểu diễn M. 
#G: Chỉ bậc của nhóm G. 
OrdG(g): Chỉ bậc của phần tử g thuộc tập G. 
Định nghĩa 2.1: Cho G là một nhóm nhân với phần tử đơn vị là 1 và g ∈ G. 
Nếu tồn tại số tự nhiên d sao cho 
 = 1 (2.1) 
thì g được gọi là “có cấp hữu hạn” và giá trị d nhỏ nhất thỏa mãn đẳng thức (2.1) 
được gọi là “cấp của g trong G” và ký hiệu là ord(g) mod G hay .■ 
Công nghệ thông tin & Cơ sở toán học cho tin học 
L.V. Tuấn, B.T. Truyền, “Phát triển thuật toán của Danied Shank rời rạc trên vành Zn.” 130 
Lưu ý. Nếu G là nhóm hữu hạn thì mọi phần tử trong G đều có cấp hữu hạn và 
 luôn là ước bậc của nhóm G, ký hiệu |#G, ngoài ra, nếu số tự nhiên d 
thỏa mãn (2.1) thì cũng là ước của d. 
Định lí 2.1: Cho G= Zn
*(n= pxq), [2m-1,2m-1], 1 k1,k2 2
m-1, thoả 
mãn: 
 gk1=b mod n (2.2) 
và gk2=b mod n (2.3) 
thì k1=k2. 
Chứng minh: Giả sử k1 k2 không giảm tổng quát, giả sử k1>k2, từ (2.2) và (2.3) 
ta có = 1 mod n, khi đó (k1-k2), nghĩa là k1-k2 2
m-1, điều này mẫu 
thuẫn với giả thiết 1 k1,k2 2
m-1■ 
Định lý 2.2 [11]: 
Giả sử Γ...m1m là các số nguyên dương nguyên tố cùng nhau từng đôi một và 
cho Γ...a1a là các số nguyên. Khi đó, hệ r đồng dư thức )i(modmiax (1<=i<=r) 
sẽ có một nghiệm duy nhất theo modulo M= Γ1 m...m được cho theo công thức: 
x= iii
Γ
1i
yMa
 mod M, trong đó và yi= M
-1 mod mi với 1<=i<=r. 
Bổ đề 2.1. Cho nhóm cyclic G= có bậc M, M= RS và k=loggx mod M ta có: 
k= S
g
xlog S mod R
 (2.4)
k= R
g
xlog R mod S (2.5) 
Bổ đề 2.2. Cho G= có bậc M=Rc, i=loggx=i0+i1R+...+ic-1R
c-1 ta có: 
i0=
1
c-1R
log ( )
cR
g
x
. (2.6) 
it= ))xg((log
1tc1t
1t0 RRi...i
g
1-cR
 (t=1,...,c-1). (2.7) 
2.2. Logarit rời rạc và ứng dụng 
Định nghĩa 2.2: Cho G= bậc M, khi đó  G,  duy nhất ZM sao cho 
=g . Giá trị được gọi là logarit rời rạc [10]cơ số g của  và ký hiệu logg. Cho 
trước phần tử g G, khi đó, với mọi  G= việc tìm logg được gọi là bài toán 
logarit rời rạc trên G. 
Định nghĩa 2.3: 
Cho p là số nguyên tố lẻ, G==Z*p , g là phần tử nguyên thuỷ của Z
*
p và  
Z*p. tồn tại duy nhất ,0 p-1 sao cho g
  mod p. Giá trị được gọi là logarit 
rời rạc [10] cơ số g của , ký hiệu là logg. Cho trước phần tử g Z
*
p, khi đó, với 
mọi  Z*p, tìm logg gọi là bài toán logarit rời rạc[10] trên trường Zp. 
Tính chất 2.1: 
log(1.2. . . .k )log1+log 2+ . . + log k(mod p-1). (2.8) 
Tính chất 2.2: 
log
.log(mod p-1) (2.9) 
Ứng dụng 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ố 48, 04 - 2017 131
Một lớp các hệ mã khoá công khai và biến thể quan trọng mà độ an toàn của nó 
dựa trên tính khó giải của bài toán logarit rời rạc, chẳng hạn như hệ mã khóa công 
khai của Elgamal, giao thức trao đổi khóa Diffie-Hellman v.v... Trong phần này, 
bài báo sẽ trình bày ứng dụng bài toán logarit rời rạc trong xây dựng hệ mật khóa 
công khai Elgamal và hệ chữ ký số Elgamal. Giả sử một hệ thống truyền tin sử 
dụng hệ mã khóa công khai Elgamal trên trường Zp để bảo mật thông tin. Khóa của 
hệ mã xây dựng theo các bước như sau: 
Thuật toán 2.1: 
+ Bước 1: Chọn số nguyên tố p đủ lớn sao cho bài toán logarith trong pZ là khó giải. 
+ Bước 2: Chọn *pZα là phần tử nguyên thủy. 
+ Bước 3: Chọn x là số ngẫu nhiên sao cho 1<x<p. 
+ Bước 4: Tính giá trị y thỏa mãn công thức: modxy p 
Khóa bí mật là x, còn khóa công khai là bộ gồm 3 số (y, p, ). 
Để mã hóa bản rõ