Phương pháp xây dựng tập Slist các logarit có trọng số thấp

Công nghệ thông tin & Cơ sở toán học cho tin học 
Đ. V. Sơn, N. T. Sơn, P. Q. Hoàng, “Phương pháp xây dựng logarit có trọng số thấp.” 148 
PHƯƠNG PHÁP XÂY DỰNG TẬP Slist CÁC LOGARIT 
CÓ TRỌNG SỐ THẤP 
 Đặng Vũ Sơn1, Nguyễn Thanh Sơn1,*, Phạm Quốc Hoàng2 
Tóm tắt: Bài báo này trình bày một số phương pháp xây dựng tập Slist các 
logarit có trọng số thấp nhằm giải bài toán logarit rời rạc. Các tác giả trình bày 
thuật toán gốc trong xây dựng tập S, sau đó, đề xuất thêm hai thuật toán mới tại 
mục 3, mục 4; Đồng thời, đánh giá độ phức tạp của hai thuật toán mới so với 
thuật toán gốc ban đầu. 
Từ khóa: Thuật toán tính logarit rời rạc theo kiểu tính sẵn, Tấn công logarit trọng số thấp. 
1. MỞ ĐẦU 
Đối với các hệ mật có độ an toàn dựa trên độ "khó" của bài toán logarit trên nhóm 
cyclic hữu hạn g tồn tại một kiểu tấn công theo kiểu tính sẵn tập với một số giá trị 
ℓ [0,#g) nào đó ([1], [2],[4],[5]). Tập được tính sẵn đó được ký hiệu là Slist 
Slist = {(b,ℓ): b = gℓ}. 
Việc tính logarit rời rạc lúc này, chuyển thành việc tra bảng Slist. Khi này, với mỗi b 
g, ta có thể hy vọng tính được loggb theo thuật toán sau: 
Thuật toán 1. (tìm logarit đã được tính sẵn) 
Input: a g. 
Output: ℓ = loggb khi (b,ℓ) Slist và "Failure" trong trường hợp ngược lại. 
1 (b,ℓ)  First(Slist); 
2 while ((b,ℓ) Null) do { 
if (b==a) return ℓ; 
(b,ℓ)  Next((b,ℓ),Slist); 
} 
3 return "Failure". 
ở trên các hàm First(.) và Next(.,.) được định nghĩa như sau: 
First(S) 
Input: S là một tập hợp. 
Output: Phần tử đầu tiên trong S nếu có. Ngược lại trả về Null. 
Next(x,S) 
Input: x, S trong đó S là một tập hợp còn x S. 
Output: Phần tử đứng ngay sau x trong S nếu còn, ngược lại trả về Null. 
Ví dụ. 
Trường hợp 
Slist = {(b,ℓ): b = gℓ, ℓ B} 
thường là B không lớn thì thuật toán 1 còn được gọi là thuật toán "tấn công các logarit giá 
trị thấp". 
Trường hợp 
Slist = {(b,ℓ): b = gℓ, weight(ℓ) k, len(ℓ) m } (1.1) 
thường là k không lớn với weight(ℓ) là số các bít 1 trong biểu diễn nhị phân của ℓ, và 
được gọi là trọng số của ℓ, thì thuật toán 1 còn được gọi là thuật toán "tấn công các logarit 
trọng số thấp". 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 149
Tấn công các logarit trọng số thấp sẽ có độ phức tạp tính toán ít hơn, bởi vì với các số 
mũ trọng số thấp, việc thực hiện phép mũ hóa theo thuật toán nhân và bình phương có lặp 
sẽ tốn ít thời gian hơn. Do đó, việc lập tập tính sẵn Slist cũng tốn ít thời gian hơn. 
Rõ ràng các loại tấn công tìm logarit rời rạc dựa trên một tập các logarit rời rạc đã được 
tính sẵn thì việc xây dựng tập Slist chiếm hầu hết chi phí, do đó, mọi cải tiến nhằm giảm 
được chi phí trong công đoạn này là quan trọng nhất. Trong bài báo này, chúng tôi xét đến 
thuật toán tấn công các logarit trọng số thấp, cụ thể đưa ra được hai thuật toán mới để xây 
dựng tập Slist. Dùng thước đo là số phép toán nhóm cần thiết để xây dựng tập Slist của thuật 
toán, ký hiệu là Cost. Tại phần 2 chúng tôi đã chỉ ra rằng Cost của thuật toán mới thứ nhất, 
ký hiệu Cost1(k,m), không đến 
2
1k 
 Cost của thuật toán gốc, ký hiệu Cost0(k,m) tức là 
Cost0(k,m) 
1
2
k 
Cost1(k,m) (1.2) 
ở trên m= log2#g . 
Thuật toán mới thứ hai trình bày tại mục 4 là một chuyển thể của phương pháp baby-
steps, giant-steps do Daniel Shanks đưa ra từ năm 1969 [3] cho phép tách tập Slist thành hai 
phần Sbaby và Sgiant theo công thức 
Slist = Sbaby Sgiant (1.3) 
Độ phức tạp của thuật toán 2 được ký hiệu là Cost2(k,m). Việc đánh giá độ phức tạp 
của thuật toán 2 được thực hiện ở mục 4.2.2. 
Có một số công trình trên thế giới có liên quan đến chủ đề của bài báo này. Trong công 
trình [6], [7] việc lập tập Slist được thực hiện một cách trực tiếp, mà không có việc tách bit 
như trong thuật toán 1 được đề xuất trong bài báo này. Trong công trình [8] dựa trên việc 
phân tích số mũ 1 2 3x x x x , với ix là các số có trọng số thấp, sau đó tìm x. Với việc tách 
1 bit nhờ hàm Div(x) tập Slist sẽ được tích lũy một cách tuần tự theo trọng số tăng dần, việc 
này giúp giảm độ phức tạp tính toán cho thuật toán 1 được đề xuất. Sau đó, thuật toán 2 
được đề xuất dựa trên phương pháp baby-steps, giant-steps và thuật toán 1. 
2. PHƯƠNG PHÁP TRUYỀN THỐNG XÂY DỰNG TẬP Slist 
2.1. Thuật toán gốc 
Tìm các logarit có trọng số thấp (không quá k) theo phương pháp truyền thống được 
thực hiện theo thuật toán sau. 
Thuật toán 0 
Input: k, g trong đó k là một số nguyên dương còn # g là số m-bits, tập S là tập các số ℓ 
có trọng số weight(ℓ) k , độ dài của ℓ theo bit len(ℓ ) m và được sắp theo thứ tự tăng 
dần. 
Output: Slist = {(b,ℓ): b = gℓ, ℓ S }. 
1 Slist  {(1,0)}; 
2 Với mỗi ℓ S, ℓ tăng dần thực hiện { 
b  gℓ; 
Slist  Slist  {(b,ℓ)}; 
} 
3 return Slist. 
2.2. Phân tích thuật toán 0 
Công nghệ thông tin & Cơ sở toán học cho tin học 
Đ. V. Sơn, N. T. Sơn, P. Q. Hoàng, “Phương pháp xây dựng logarit có trọng số thấp.” 150 
Mệnh đề 1. Số phép toán nhóm của thuật toán 0 được đánh giá theo công thức sau: 
Cost0(k,m) 
1
1
2
k
w
m
w
k
C
 (2.1) 
Chứng minh: 
Biết rằng có đúng L = 
k
0w
w
mC giá trị ℓ thỏa mãn weight (ℓ) k, len(ℓ ) m . Để tính 
gℓ người ta sẽ tính sẵn các giá trị 2 4 8 2, , ,...,
m
g g g g rồi lưu lại, mỗi lần dùng thì tra bảng. 
Vì vậy, mỗi lần tính lg chỉ cần weight(ℓ)-1 phép toán nhân. Suy ra độ phức tạp tính toán 
của thuật toán gốc là: 
Cost0(k,m)= w
w 1
(w 1)
k
mC
  (2.2) 
Ta có, cho các số , , ,x y a b sao cho ,y x b a , dễ dàng suy ra bất đẳng thức sau: 
( )( )
2
x y a b
xa yb
 (2.3) 
Với giả thiết 
2
m
k ta có wmC sẽ tăng theo giá trị của w với (1,..., k)w . 
 w
w 1
(w 1)
k
mC
  = 1 20. 1. ... ( 1) km m mC C k C 
= 1 2 1(0. ( 1) ) (1. ( 2) ) ...k km m m mC k C C k C
Áp dụng bất đẳng thức (2.3) ta thu được: 
w
w 1
(w 1)
k
mC
  1 2 1
1 1
( ) ( ) ...
2 2
k k
m m m m
k k
C C C C 
w
w 1
(w 1)
k
mC
  w
w 1
1
2
k
m
k
C
  (2.4) 
Và đây là điều cần chứng minh.  
3. THUẬT TOÁN MỚI XÂY DỰNG TẬP Slist 
3.1. Thuật toán 
Thuật toán xây dựng tập Slist đưa ra ở đây được trình bày như việc tính hàm 3 biến đầu 
vào MakeSlist(g,m,k) được thực hiện như sau. Ý tưởng của thuật toán 1 là tách số mũ ℓ 
thành hai thành phần ℓ1, ℓ2 sao cho weight(ℓ1)=1, weight(ℓ2)=weight(ℓ)-1 và ℓ= 
ℓ1+ℓ2, việc này dễ dàng thực hiện bằng việc tách 1 bit cao nhất bên trái khỏi ℓ. Các tập 
số mũ có trọng số thấp sẽ được xây dựng từ S1, và tập mới tính được sẽ bao trùm tập trước 
đó. Việc phân tích cụ thể thuật toán 1 được trình bày ở mục 3.2. 
3.1.1. Thuật toán tính hàm MakeSlist(g,m,k) 
Thuật toán 1. 
Input: k, g trong đó, k là một số nguyên dương còn # g là số m-bits. 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 151
Output: Slist = {(b,ℓ): b = gℓ, weight(ℓ) k, len(ℓ ) m }. 
1 Sindex[w]  {ℓ: ℓ [0, # g ) and weight(ℓ) = w} with 2 w k; 
2 Slist  {(1,0)}; 
3 ℓ  1; 
4 b  g; 
5 S1 {(b,ℓ)}; 
6 while (ℓ<# g ) do { 
 6.1 b  b*b; //Phép * ở đây là phép toán nhóm. 
6.2 ℓ  2*ℓ; //Phép * ở đây là phép nhân thông thường. 
6.3 S1  S1{(b,ℓ)}; 
} 
7 Snew  S1; 
8 Slist  Slist  Snew; 
9 for w from 2 to k do { 
9.1 Sold  Snew; 
9.2 Snew  {}; 
9.3 ℓ  Fist(Sindex[w]); 
9.4 while (ℓ Null) { 
9.4.1 (ℓ1,ℓ2)  Div(ℓ); 
9.4.2 (b1,ℓ1)  Search((.,ℓ1),S1); 
9.4.3 (b2,ℓ2)  Search((.,ℓ2),Sold); 
9.4.4 b  b1*b2; //* là phép toán nhóm 
9.4.5 Snew  Snew{(b,ℓ)}; 
9.4.6 ℓ  Next(ℓ,Sindex[w]); 
} 
9.5 Slist  Slist  Snew;} 
10 return Slist. 
3.1.2. Định nghĩa một số hàm sử dụng trong thuật toán 
Search((x,.),S); 
Input: S là một tập hợp các cặp phần tử (a,b), x thuộc về tập các phần tử thứ nhất 
của S. 
Output: (x,b) trong S. 
Search((.,x),S); 
Input: S là một tập hợp các cặp phần tử (a,b), x thuộc về tập các phần tử thứ hai 
của S. 
Output: (a,x) trong S. 
Div(x): 
Input: x [0, 2m). 
Output: (x1,x2) [0, 2m) [0, 2m) thỏa mãn weight(x1) = 1, weight(x1) + 
weight(x2) = weight(x) và x = x1 + x2. 
3.2. Phân tích thuật toán 1 
Trước hết, ta chứng tỏ tính đúng đắn của thuật toán 1. 
Công nghệ thông tin & Cơ sở toán học cho tin học 
Đ. V. Sơn, N. T. Sơn, P. Q. Hoàng, “Phương pháp xây dựng logarit có trọng số thấp.” 152 
Kết quả 2. Tập Slist tại đầu ra của thuật toán chứa tất cả các cặp (b,ℓ) với weight(ℓ) k. 
Nói một cách khác thì tập này chính là tập cần xây dựng. 
Chứng minh: 
Sau bước 2 thì Slist chứa cặp (1,0) tức là tập cần lập ứng với k=0. Các bước từ 3 đến 6 
chính là tạo tập S1 chứa toàn bộ các cặp (b,ℓ) với weight(ℓ)=1, do đó, Slist sau bước 8 sẽ 
chứa các cặp (b,ℓ) với weight(ℓ) 1. 
Giả sử quy nạp rằng tập Snew trước bước 9.1 của vòng lặp thứ w chứa tất cả các cặp 
(b,ℓ) với weight(ℓ) = w 1 (điều này đã đúng với w=2), ta sẽ chứng tỏ tập này sau bước 
9.4 sẽ chứa tất cả các cặp (b,ℓ) với weight(ℓ) = w. Quả vậy, từ định nghĩa hàm Div(x) nên 
cặp (ℓ1,ℓ2) thu được trong bước 9.4.1 thỏa mãn: 
 weight(ℓ1) = 1 nên (b,ℓ1) trong bước 9.4.2 sẽ khác Null. (3.1) 
weight(ℓ1) + weight(ℓ2) = weight(ℓ) hay weight(ℓ2) = w 1. (3.2) 
ℓ1+ℓ2 =ℓ. (3.3) 
Như đã chỉ ra ở trên tập S1 chứa toàn bộ các cặp (b,ℓ) với weight(ℓ)=1 nên với (3.1) 
cặp (b1,ℓ1), do đó, tìm được trong 9.4.2 sẽ khác "Failure" điều này có nghĩa 
b1 = 1g (3.4) 
Từ 9.1 ta có Sold chính là Snew trước bước này nên theo giả thiết quy nạp tập này chứa 
tất cả các cặp (b,ℓ) với weight(ℓ) = w 1, cùng với (3.2) nên cặp (b2,ℓ2) do đó tìm được 
trong 9.4.3 sẽ khác "Failure" điều này có nghĩa 
b2 = 2g (3.5) 
Từ (3.4) và (3.5) nên giá trị b trong bước 9.4.4 sẽ là: 
b = b1*b2
)5.3(&)4.3(
 1g * 2g 
= 21g  
)3.3(
 gℓ. (3.6) 
Trong vòng lặp này duyệt toàn bộ các giá trị ℓ với weight(ℓ)=w nên Snew tính được 
trong 9.4.5 sẽ chứa tất cả các cặp (b,ℓ) với weight(ℓ) = w và đây là điều cần chứng minh. 
Điều trên cho thấy Slist sau bước 9.5 sẽ chứa tất cả các cặp (b,ℓ) với weight(ℓ) w và vì thế 
sau bước 9 Slist chính là tập cần xây dựng. 
Do mỗi lần tính b = gℓ trong thuật toán 1 (bước 9.4.4) chỉ cần đúng 1 phép toán nhóm 
nên ta có kết quả sau. 
Kết quả 3. Số phép toán nhóm tối đa của thuật toán 1, ký hiệu Cost1(k,m), được đánh giá 
theo công thức sau 
Cost1(k,m)= 
k
1w
w
mC . (3.7) 
Từ (2.1) và (3.7) ta thu được hệ quả sau đây: 
Hệ quả 4. Cost0(k,m) 
1
2
k 
Cost1(k,m). 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 153
4. PHƯƠNG PHÁP BABY-STEPS, GIANT-STEPS 
TÌM LOGARIT CÓ TRỌNG SỐ THẤP 
4.1. Thuật toán 
Trong phần này, chúng tôi đưa ra một mô tả của thuật toán như sau. Thuật toán 2 dựa 
vào phương pháp baby-steps, giant-steps tách ℓ=2n ℓ1+ ℓ2 với / 2n m , sau đó xây 
dựng các tập Sbaby và Sgiant. Sau đó, thuật toán sẽ tìm va chạm trong tập Sbaby. Việc chứng 
minh tính đúng đắn của thuật toán được làm rõ trong mục 4.2.1. 
Thuật toán 2. (tính logarit trọng số nhỏ theo phương pháp baby-steps, giant-steps) 
Input: a g, k, m với #g là số m-bits. 
Output: ℓ = logga nếu tìm được. Ngược lại trả về "Failure". 
1 n  m/2 ; 
2 Sbaby  MakeSlist(g,n,k); 
3 g1  
n2g ; 
4 Sgiant  MakeSlist(g1,n,k); 
5 (b1,ℓ1)  First(Sgiant); 
6 while ((b1,ℓ1) Null) do { 
6.1 b  a*b1; 
6.2 (b,ℓ2)  Search((b,.),Sbaby); 
6.3 if ((b,ℓ2) "Failure") then return (2nℓ1+ℓ2); 
6.4 (b1,ℓ1)  Next((b1,ℓ1),Sgiant); 
}. 
4.2. Đánh giá thuật toán 2 
4.2.1. Khả năng tìm được các logarit trọng số thấp của thuật toán 2 
Kết quả 5. Với mọi a = gℓ thỏa mãn các điều kiện sau 
ℓ = 2nℓ1+ ℓ2 (4.1) 
 weight(ℓi) k và ℓi<2n (i=1,2) (4.2) 
Thì thuật toán 2 luôn tìm được ℓ. 
Chứng minh: Theo định nghĩa hàm MakeSlist(g1,n,k) đưa ra trong phần 2 thì Sbaby gồm 
các cặp (b,ℓ) trong đó weight(ℓ) k, ℓ<2n và b=gℓ còn Sgiant gồm các cặp (b,ℓ) trong đó 
weight(ℓ) k, ℓ<2n và b=g1ℓ =

 n2g . 
Từ (4.2) thì luôn tồn tại cặp (b2,ℓ2) Sbaby và cặp (b1,ℓ1) Sgiant tức là 
 b2 = gℓ2 còn b1 = g1ℓ1 = 
1
2ng

do đó, b=a*b1=gℓ*
1
2ng

 =gℓ2=b2 
nên, Search((b,.),Sbaby)=(b2,ℓ2) "Failure" 
Điều kiện trong 6.3 xảy ra và ta tìm được ℓ=logga. 
Công nghệ thông tin & Cơ sở toán học cho tin học 
Đ. V. Sơn, N. T. Sơn, P. Q. Hoàng, “Phương pháp xây dựng logarit có trọng số thấp.” 154 
Chú ý rằng từ hai điều kiện (4.1) và (4.2) về ℓ trong kết quả 5 ta có: 
 weight(ℓ) = weight(ℓ1) + weight(ℓ2) (4.3) 
điều này có nghĩa thuật toán 2 có thể tìm được tất cả các logarit với trọng số không quá k, 
thậm chí có thể tìm được cả logarit với trọng số lên đến 2k. Chẳng hạn số các logarit trọng 
số 2k có thể tìm được theo thuật toán 2 là 2knC trên tổng số k2n2C . 
4.2.2. Đánh giá Cost2 của thuật toán 
Theo công thức (3.7) trong kết quả 3 thì số phép toán nhóm cần thực hiện tại các bước 
2 và 4 của thuật toán 2 đều là 
k
1w
w
nC . Bước 3 của thuật toán này cần đến một phép tìm 
phần tử ngược trong nhóm, biết rằng công thức chung cho mọi nhóm là a ℓ = a#g ℓ nên số 
phép toán nhóm cần cho phép toán này là không quá 4 n. Phần tìm logarit của thuật toán 
thực hiện tối đa 
k
1w
w
nC vòng trong bước 6 mà mỗi vòng cần đúng một phép toán nhóm 
tại bước 6.1, do đó, ta có: 
Cost2(k,2n) 
k
1w
w
n n4C3 (4.5) 
5. KẾT LUẬN 
Bài báo đã đề xuất 2 thuật toán mới và đưa ra đánh giá độ phức tạp tính toán của các 
thuật toán này. Sau khi đánh giá ta thấy thuật toán 1 có độ phức tạp ít hơn so với thuật toán 
truyền thống, thuật toán đề xuất thứ 2 có thể tìm các logarit trọng số lên đến 2k. Tuy 
nhiên, thuật toán 2 tốn bộ nhớ lưu trữ, vì vậy, nhóm sẽ nghiên cứu cải tiến thuật toán 2 
bằng cách sử dụng hàm băm mật mã. Hướng nghiên cứu tiếp theo của nhóm sẽ sử dụng 
hàm băm để tiết kiệm bộ nhớ lưu trữ dựa trên kết quả [6]. 
TÀI LIỆU THAM KHẢO 
[1]. V. Miller.Use of elliptic curves in cryptography. In H. Williams, editor, Advances in 
Cryptology, Proc. Eurocrypt '85, volume 218 of Lecture Notes in Computer Csience, 
pages 417-426, Springer-Verlag, 1985. 
[2]. A. Odlyzko. Discrete logarithms in finite fields and their cryptographyc significance. 
In Advances in Cryptology, Proc. Eurocrypt '84, volume 209 of Lecture Notes in 
Computer Csience, pages 224-313, Springer-Verlag, 1985. 
[3]. D. Shanks, Class number, a theory of factorization, and general. In 1969 Number 
Theory Institue, Stony Brook, N. Y., volume 20 of Proc. Sympos. Pure Math., pages 
415-440. Amer. Math. Soc., 1971. 
[4]. S. Kim, J. H. Cheon, Parameterized splitting systems for the discrete logarithm, IEEE 
transactions on Information Theory, 2009. 
[5]. A. May, I. Ozerov A generic algorithm for small weight discrete logarithm in 
composite groups, 2014. 
[6]. B. Kacsmar, S. Plosker, R. Henry, Computing Low-weght discrete logarithms, 24th 
Annual Conference on Selected Areas in Cryptography (SAC 2017). 
[7]. D.R. Stinson Some baby-step giant-step algorithms for the low Hamming weight 
discrete logarithm problem, 2001. 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 155
[8]. Jung Hee Chenon, Hong TaeKim, Analysis of Low Hamming weight products, 
Discrete applied mathematics, 2008. 
ABSTRACT 
A BUIDING METHOD OF SET Slist FOR LOW WEIGHT LOGARITS 
In this paper, some methods construction set Slist, consist low-weight logarithm 
for solve discrete logarithm problem are described. Original algorithm construction 
set Slist is described, then two new algorithms in section 3, 4 are proposed; 
Complexity of new algorithms is evaluated. The proposed algorithm uses much 
memory. In the future, method using hash function for reducing storage memory, 
based on [6] will be researched. 
Keywords: Algorithm solve discrete logarithm, Solve low-weight discrete logarithm. 
Nhận bài ngày 11 tháng 07 năm 2017 
Hoàn thiện ngày 03 tháng 08 năm 2017 
Chấp nhận đăng ngày 20 tháng 12 năm 2017 
Địa chỉ: 1Ban Cơ yếu chính phủ; 
 2Học viện Kỹ thuật Mật mã, Ban Cơ yếu chính phủ. 
 *Email:nguyenthanhson@nacis.gov.vn.