Một số tấn công lên lược đồ chữ ký số GOST R 34.10-2012 dựa trên thuật toán rút gọn cơ sở lưới LLL

Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 95
MỘT SỐ TẤN CÔNG LÊN LƯỢC ĐỒ CHỮ KÝ SỐ GOST 
R 34.10-2012 DỰA TRÊN THUẬT TOÁN RÚT GỌN CƠ SỞ LƯỚI LLL 
Khúc Xuân Thành1*, Nguyễn Duy Anh2, Nguyễn Bùi Cương1 
Tóm tắt: Trong bài báo này, chúng tôi trình bày hai tấn công khôi phục khóa ký 
dài hạn và khóa ký tức thời  trong lược đồ chữ ký số GOST R 34.10-2012 dựa trên 
thuật toán rút gọn cơ sở lưới LLL. Các tấn công này được dựa trên cách tiếp cận 
trong các tấn công lên lược đồ chữ ký số DSA và ECDSA [1], [7]. Cụ thể, trong tấn 
công dựa trên [1], chúng tôi chỉ ra rằng nếu các khóa ký thỏa mãn ,  < / 
hoặc ,  >  − / thì tấn công này có thể khôi phục lại các khóa này. Tấn công 
dựa trên [7], có thể khôi phục được các khóa ký nếu ,  
 − /. Các tấn công này đã được chúng tôi cài đặt thực nghiệm sử dụng phần 
mềm tính toán đại số Magma. 
Từ khóa: Mật mã, Lưới, Lược đồ chữ ký số, Thuật toán LLL, GOST R 34.10-2012. 
1. MỞ ĐẦU 
Khía cạnh tính toán của hình học của các số đã có một cuộc cách mạng nhờ 
thuật toán rút gọn cơ sở lưới do ba nhà toán học Arjen Lenstra, Hendrik Lenstra, 
László Lovász tìm ra năm 1982 [6] (được viết tắt là LLL). Ngay sau khi được công 
bố, thuật toán LLL ngay lập tức được xem như một trong những thuật toán quan 
trọng nhất của thế kỷ 20 bởi vì những ứng dụng của nó trong mật mã, đại số máy 
tính và lý thuyết số. Một trong những ứng dụng đầu tiên của thuật toán LLL trong 
mật mã là phá vỡ hệ mật Merkle–Hellman. Sau đó, một loạt các tấn công lên RSA 
[2], DSA [1], ECDSA [7] đã được phát triển dựa trên thuật toán LLL. 
Các nghiên cứu liên quan. Lược đồ DSA và ECDSA [5] được biết đến như phiên 
bản lược đồ chữ ký số của Mỹ. Gần đây, trên thế giới nổi lên một số công trình 
nghiên cứu tấn công lên DSA, ECDSA dựa trên thuật toán LLL như [1], [7]. Các 
tấn công này đem lại khả năng thành công cao và thời gian thực hiện rất ngắn khi 
các khóa ký của chữ ký thỏa mãn một điều kiện nào đó. Trong khi đó, GOST R 
34.10-2012 [4] thì được biết đến như phiên bản lược đồ chữ ký số của Nga và hiện 
đang được nghiên cứu tìm hiểu tại Việt Nam thì chưa có nghiên cứu nào với các 
tấn công dạng này. Do đó, nhằm tránh các tấn công trên để không có các khóa ký 
“yếu” trong chữ ký, câu hỏi cần thiết phải được đạt ra là liệu các tấn công như vậy 
có thể xảy ra trên lược đồ chữ ký số GOST R 34.10-2012? 
Đóng góp của chúng tôi. Dựa trên các tấn công trong [1] và [7] lên lược đồ chữ 
ký số DSA và ECDSA, chúng tôi xây dựng hai phiên bản tấn công khôi phục khóa 
ký lên lược đồ chữ ký số GOST R 34.10-2012. Cụ thể, đối với lược đồ chữ ký số 
GOST R 34.10-2012, tấn công 1dựa trên [1] chỉ ra rằng nếu khóa ký dài hạn  và 
khóa ký tức thời  thỏa mãn || <

√
 (ở đây,  là cấp của điểm cơ sở trong 
chữ ký, với  ∈ [1, ],kí hiệu  =  nếu  ≤


, ngược lại  =  − ) thì kẻ tấn 
công có thể khôi phục lại các khóa ký này. Tấn công 2 dựa trên [7] chỉ ra rằng kẻ 
tấn công có thể khôi phục được  và  khi ||  

<

√
. Hai tấn công này đã 
được chúng tôi thực hiện cài đặt thực nghiệm sử dụng phần mềm tính toán đại số 
Công nghệ thông tin 
K. X. Thành, N. D. Anh, N. B. Cương, “Một số tấn công lên lược đồ  cơ sở lưới LLL.” 96 
Magma với các tham số được lấy trong [4]. Kết quả thực nghiệm cho thấy, các tấn 
công này có thể khôi phục các khóa ký trong thời gian rất ngắn. 
Bố cục bài báo. Sau mục Mở đầu, Mục 2 trình bày một số khái niệm cơ sở của lý 
thuyết lưới và lược đồ chữ ký số GOST R 34.10-2012. Mục 3 trình bày ý tưởng 
chung cho việc xây dựng các tấn công lên lược đồ chữ ký số GOST R 34.10-2012. 
Hai tấn công cụ thể lên GOST R 34.10-2012 được trình bày trong Mục 4. Cuối 
cùng, Mục 5 đưa ra một số kết quả thực nghiệm và khuyến cáo khi sinh các khóa 
ký cho lược đồ chữ ký số GOST R 34.10-2012. 
2. MỘT SỐ KHÁI NIỆM CƠ SỞ 
 2.1. Lưới 
Trước tiên, chúng tôi nhắc lại định nghĩa của lưới. 
Định nghĩa 1. ([3]) Cho 1n , 
1 2
( , , , )
n
b b b là một cơ sở của n . Lưới n chiều
L với cơ sở 
1 2
( , , , )
n
b b b là tập hợp gồm tất cả các tổ hợp tuyến tính của các 
véctơ cơ sở nàyvới hệ số nguyên. Tức là, L có thể được biểu diễn như sau: 
1 2 1 2
1
, , ,
n
n i i n
i
L a a a a
  
 
b b b b     (1) 
Các véctơ 
1 2
( , , , )
n
b b b được gọi là cơ sở của lưới. Với mỗi 1 i n , viết 
1 2
b ( , , , )
i i i in
b b b  , thành lập một ma trận ( )
ij
X b . Định thức của lưới L trong 
cơ sở 
1 2
( , , , )
n
b b b được định nghĩa là det detL X . Ký hiệu 
1 2
* * *( , , , )
n
b b b là 
các véctơ thu được sau khi trực giao hóa Gram-Schmidt 
1 2
( , , , )
n
b b b . Định thức 
của lưới không phụ thuộc cách chọn cơ sở. Thuật toán LLL [6] đưa ra một cơ sở 
mới “tốt hơn” theo nghĩa gồm các véctơ ngắn hơn. Sau đây là một số tính chất của 
một cơ sở mới thu được sau khi ápdụng thuật toán LLL. 
Khẳng định 2. ([3]) Cho L là một lưới được căng bởi 
1 2
( , , , )
n
v v v . Áp dụng 
thuật toán rút gọn cơ sở LLL vào lưới L ta thu được một cơ sở mới 
1 2
( , , , )
n
b b b , 
được gọi là cở sở LLL-rút gọn, thỏa mãn hai điều kiện sau đây: 
1, 
2
1 2
b b
b
*
*
i j
ij
j


 với mọi1 j i n . 
2, 
1 1 1
3
4
* * *
,i i i i i

 b b b với mọi 2 i n , ở đây, b b*
i j
 là tích vô hướng của 
véctơ b
i
 và *
j
b . 
Chứng minh. Xem [3], Trang 71. ∎ 
Tính chất 3. ([3])Nếu 
1 2
( , , , )
n
b b b là một cơ sở LLL-rút gọn của lưới L trong 
n thì ta có: 
1, 
1 4 1
1
2b
( )
(det ) .
n n
L
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 97
2, 
1 1
12 4
2 1
2
( )
( )
det .
n
n
L
  
b b 
Chứng minh. Xem [3], Trang 59. ∎ 
2.2. Lược đồ chữ ký số GOST R 34.10-2012 
Lược đồ GOST R 34.10-2012 [4] được xem là chuẩn chữ ký số của Nga. Lược 
đồ này sử dụng một đường cong elliptic E trên 
p
 và một điểm ( )
p
P E  có cấp 
là một số nguyên tố  (256 bít hoặc 512 bít). Lược đồ gồm ba thuật toán chính: 
1, Thuật toán sinh khóa cho người ký: 
 Chọn a ngẫu nhiên đều trong 1 1[ , , ]q  là khóa ký dài hạn. 
 Tính Q aP là khóa công khai 
2, Thuật toán ký của người ký trên thông điệp m : 
 Chọn k ngẫu nhiên đều trong 1 1[ , , ]q  là khóa ký tức thời. 
 Tính ( , )kP x y , lấy (mod )r x q nếu 0r thì chọn lại k . 
 Tính ( )h m , ở đây h là một hàm băm ánh xạ thông điệp tới 1 1{ , , }q  . 
 Tính ( ( ) ) (mod )s kh m ar q , nếu 0s thì chọn lại k . 
3, Thuật toán xác minh chữ ký ( , )r s trên thông điệp m : 
 Xác minh ,r s có thuộc 1 1[ , ]q hay không. 
 Tính 1( ) (mod )w h m q 
 Tính 
1
(mod )u sw q và 
2
(mod )u rw q . 
 Tính 
1 2
( , )
R R
R x y u P u Q 
 Chữ ký được chấp nhận chỉ khi (mod )
R
r x q . 
Tính đúng đắn của thuật toán. Ta có, 
1 1 1
1 2 1 2
( , ) ( ) ( ( ) ( ) ) .
R R
R x y u P u Q u u a P h m s arh m P kP 
3. Ý TƯỞNG CHUNG CỦA TẤN CÔNG 
Ý tưởng chính của các tấn công lên lược đồ chữ ký số GOST R 34.10-2012 dựa 
trên lý thuyết lưới là đi tìm khóa a và k (với ( ), , ,h m r s q đã biết) thông qua việc 
giải phương trình đồng dư: 
 ( ( ) ) (mod )s kh m ar q . (2) 
Từ phương trình (2), các tấn công sử dụng hai các biến đổi chính sau: 
Cách 1. Nhân cả hai vế của (2) với 1r , ta có: 
1 1 0( ( ) ) (mod )a k h m r sr q . 
Đặt 1 1( ) (mod ), (mod )A h m r q B sr q . Khi đó, cặp ( , )k a nghiệm của đa 
thức 0( , ) (mod )f x y y Ax B q . 
Cách 2. Nhân cả hai vế của (2) với 1k và 1r , ta có: 
1 1 1 1 0( ) ( ) (mod )ak r s k h m r q . 
Công nghệ thông tin 
K. X. Thành, N. D. Anh, N. B. Cương, “Một số tấn công lên lược đồ  cơ sở lưới LLL.” 98 
Đặt 1 1(mod ), ( ) (mod )A sr q B h m r q . Khi đó, cặp 1( , )k a là nghiệm của 
phương trình đồng dư 0( , ) (mod )f x y xy Ax B q . 
Với bất kỳ cách biến đổi nào, ta đều phải tìm nghiệm của một phương trình 
đồng dư ( , )f x y trên vành modulo , và đây là một công việc khó. Tuy nhiên, ta lại 
có những công cụ hữu hiệu để tìm nghiệm của phương trình trên vành số nguyên. 
Do vậy, ta sẽ tìm cách chuyển việc tìm nghiệm trên vành modulo q về tìm nghiệm 
trên vành số nguyên. Bổ đề Howgrave-Graham [2] dưới đây cho ta một ý tưởng 
một cách chuyển như vậy. 
Cho 
,
,
( , ) i j
i j
i j
h x y h x y  với ,i jh  . Khi đó, gọi “chuẩn của ( , )h x y ” là đại 
lượng được ký hiệu là ( , )h x y và được xác định theo công thức 
2
,
,
( , ) : .
i j
i j
h x y h  
Bổ đề 4. (Howgrave-Graham, [2])Cho đa thức 
,
,
( , ) [ , ]i j
i j
i j
h x y h x y x y   là tổng 
của n đơn thức. Lấy ,X Y là các số nguyên dươngvà các số nguyên 
0 0
,x y sao cho 
0 0
,x X y Y . Khi đó, nếu 
1, 
0 0
0( , ) (mod )h x y q 
2, ( , )h xX yY q n , 
thì 
0 0
0( , )h x y trên vành số nguyên. 
Chứng minh. Xem [2] Trg. 4-5. ∎ 
Bổ đề chỉ ra rằng ta cần tìm các đa thức có nghiệm chung với ( , )f x y và đa thức 
này có các hệ số đủ nhỏ đề chuẩn của nó cũng đủ nhỏ. Cụ thể, ta tìm các đa thức 
chuyển như sau: Đặt 
0
x k theo biến đổi Cách 1 (hoặc 1
0
x k theo biến đổi 
Cách 2) và 
0
y a . Cho n là một số nguyên dương nào đó (trong từng tấn công sẽ 
định nghĩa cụ thể). Sinh các đa thức 1( , ) ( , , )
i
f x y i n  mà cũng nhận 
0 0
( , )x y là 
nghiệm trên vành modulo q . Sinh lưới  chiềuL từ các hàng của ma trận I trong 
đó các hàng của I là các hệ số của đa thức 1( , ) ( , , )
i
f xX yY i n  . Áp dụng thuật 
toán rút gọn cơ sở LLL vào lưới L ta thu được cơ sở mới 
1 2
b b b( , , , )
n
 . Do thuật 
toán LLL sử dụng các phép toán biến đổi tuyến tính nguyên nên 
0 0
0 1( , ) (mod ) ( , , )
i
g x y q i n  . Ngoài ra, qua thuật toán LLL ta còn thu được 
cận trên của 
1
b . Nếu cận trên này nhỏ hơn q n thì 
1 0 0
0( , )g x y trên  . Toàn 
bộ cách thực hiện có thể được mô tả qua Sơ đồ 1. 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 99
0 0 0 0
0 0
1 1 1
1
2
0
0
0
0
LLL H-G
b
b
( , ) (mod ), ,
Sinh ( , ) (mod )
( , ) ( , )
( , )
( , )
( , ) ( , )
i
n n n
f x y q x X y Y
f x y q
f xX yY g xX yY
g x y
I I
g x y
f xX yY g xX yY


   
 
Sơ đồ 1. Cách thức chung trong thực hiện các tấn công. 
Tấn công 2 dựa trên [7] đã đưa ra một phương pháp tìm nghiệm của 
1
0( , )g x y 
trên  nếu đa thức 
1
( , )g x y có dạng 
1
( , )g x y xy Ax B và dựa trên giả thiết 
biết phân tích thừa số nguyên tố của B . Tuy vậy, không phải lúc nào 
1
( , )g x y cũng 
có dạng như vậy. Do đó, ta cần thêm một đa thức 
2
0( , )g x y trên  để thu được 
hệ hai phương trình hai ẩn số. Hệ này có thể giải bằng cách tính kết thức để thu 
được một đa thức một biến theo  hoặc. Sau đó, áp dụng các phương pháp tìm 
nghiệm của đa thức một biến để tìm  hoặc . Đây cũng là cách thức thực hiện Tấn 
công 1 dựa trên [1]. 
4. CÁC TẤN CÔNG LÊN GOST R 34.10-2012 
4.1. Tấn công 1 
Tấn công này dựa trên cách tiếp cận của Blake [1]. Từ phương trình đồng dư 
(2) thực hiện biến đổi theo Cách 1, ta có ( , ) (mod )f x y y Ax B q nhận ( , )k a 
là nghiệm. Xét các đa thức 
1 2
( , ) , ( , )f x y q f x y qx và 
3
( , ) ( , )f x y f x y . Dễ thấy 
0 1 2 3( , ) (mod ) ( , , )
i
f k a q i . Xây dựng lưới L được căng các véctơ hàng của ma 
trận I , ở đó, ma trận  có các hàng lần lượt hệ số của đa thức 
1 2
( , ) , ( , )f xX yX q f xX yY qXx và 
3
( , )f xX yY Yy AXx B . Do các hàng của 
ma trận I là  -độc lập tuyến tính nên lưới có số chiều bằng 3n . Áp dụng thuật 
toán LLL vào lưới L ta thu được một cơ sở rút gọn của lưới, ký hiệu là
1 2 3
b b b( , , ) . 
0 1 2
3 4 5
6 7 8
0 0
0 0
q C C C
I qX LLL C C C
B AX Y C C C
 
Khi đó, ta có định thức của lưới L là 2det detL I q XY . Đặt 
0 0 1 1 2 2
, ,C C X C Y   ,
3 3
,C 
4 4
C X và 
5 5
C Y nên ta có 
 1 0 1 2 2 3 4 5b b, , , , ,X Y X Y      . Đặt các đa thức 1 0 1 2( , ) ,g x y x y   và 
2 3 4 5
( , )g x y x y   . Do 
1
( , )g xX yY và 
2
( , )g xX yY là các tổ hợp tuyến tính 
nguyên của 1 2 3( , ) ( , , )
i
f xX yY i nên các đa thức 
1 2
( , ), ( , )g x y g x y cũng nhận ( , )k a 
Công nghệ thông tin 
K. X. Thành, N. D. Anh, N. B. Cương, “Một số tấn công lên lược đồ  cơ sở lưới LLL.” 100 
là nghiệm trên vành modulo . Do đó, các đa thức 
1 2
( , ), ( , )g x y g x y thỏa mãn điều 
kiện đầu tiên của Bổ đề 4. Bây giờ, ta cần xác minh điều kiện để các đa thức 
1 2
( , ), ( , )g x y g x y thỏa mãn điều kiện hai của Bổ đề 4. Ta có,
1 1
b ( , )g xX yY và 
2 2
b ( , )g xX yY . Theo Tính chất 3, 
1 32
1
2b ( )q XY . Do đó, để 
1
( , )g x y thỏa 
mãn các điều kiện hai của Bổ đề 4, ta cần 
1 322 3( )q XY q hay 6 6XY q . 
Tuy nhiên, đây chỉ là điều kiện cho đa thức 
1
( , )g x y . Ta cần tìm điều kiện cho 
đa thức 
2
( , )g x y , tức cần điều kiện để 
2
3b q . Theo Tính chất 3, ta có 
11 4 1 2
2 1
2b b(det )L
  . Do đó, ta cần 
11 4 1 2
1
2 3b(det )L q
 hay 
1
3 2b XY . Do vậy, nếu 6 6XY q và 
1
3 2b XY thì 
0 1 2( , ) , ( , )
i
g k a i trên  . Đặt 
3
( )r y là kết thức của đa thức 
1
( , )g x y và 
2
( , )g x y 
theo biến x . Khi đó, ta thu được 
3
( )r y là một đa thức một biến theo biến y . Sử 
dụng các phương pháp tìm nghiệm của đa thức một biến như phương pháp dãy 
Sturm hay phương pháp Newton ta có thể tìm được nghiệm y của 
3
( )r y . Nếu tồn 
tại 
0
y sao cho 
0
y P Q thì 
0
a y . Mặt khác, nếu 0a thì lấy a a ngược lại thì 
lấy .a a q 
Từ các lập luận trên, ta có suy ra khẳng định sau đây: 
Khẳng định 5. Đối với lược đồ chữ ký số GOST R 34.10-2012, giả sử tồn tại ,X Y
là các số nguyên dươngsao cho ,k X a Y và 6 6XY q . Cho L là một 
lưới được định nghĩa bởi ma trận I như ở trên. Khi đó, nếu véctơ ngắn nhất của cơ 
sở LLL-rút gọn có độ dài lớn hơn hoặc bằng 3 2XY thì Tấn công 1 được mô tả 
dưới đây có thể tìm được khóa ký dài hạn a trong lược đồ chữ ký số. 
Tấn công 1 
Đầu vào: Các giá trị đã biết gồm( ( ), , )h m r s . 
Đầu ra: Khóa ký dài hạn hoặc tấn công không thực hiện được. 
Bước 1. Tính 1( ) (mod )A h m r q và 1 (mod )B sr q . 
Bước 2. Xây dựng lưới L được sinh từ 0 0 0 0( , , ),( , , )q qX và ( , , )B AX Y . Sử dụng 
thuật toán LLL, tìm cơ sở LLL-rút gọn của lưới L . 
Bước 3. Tính 
0 0 1 1 2 2
, ,C C X C Y   , 
3 3 4 4
, ,C C X  
5 5
C Y . 
Bước 4. Xây dựng đa thức 
1 2
( , ), ( , )g x y g x y tương ứng là véctơ đầu tiên và véctơ 
thứ hai của cơ sở LLL-rút gọn. Cụ thể, 
1 0 1 2
( , )g x y x y   và 
2 3 4 5
( , )g x y x y   . 
Bước 5. Tính 
3
( )r y là kết thức của đa thức 
1
( , )g x y và 
2
( , )g x y theo biến x . 
Bước 6. Tìm nghiệm của đa thức một biến 
3
( )r y . 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 101
Bước 7. Nếu tồn tại y sao cho yP Q thì trả ra đầu ra a y . Nếu 0a thì 
lấy a a , ngược lại thì lấy a a q . Trường hợp khác trả ra “Tấn công không 
tìm được khóa a ”. 
Nhận xét 6. Chọn các số nguyên dương ,  sao cho  +  < log(/6√6). Đặt 
 = 2,  = 2. Khi đó, theo Khẳng định 5, nếu ta chọn các khóa ký ,  thỏa 
mãn  < , || <  thì tấn công trên có thể khôi phục lại các khóa ký này. Do 
đó, để tránh tấn công này, ta có thể chọn  > /, || > /, tương 
đương/ < ,  <  − /. 
4.2. Tấn công 2 
Tấn công này dựa trên cách tiếp cận trong [7]. Cụ thể, trong [7] đưa ra một 
cách giải cho các phương trình conic có dạng ( , )r x y Dxy Ax B , ở đây 
, ,D A B . Nhờ vậy, ta có thể xây dựng tấn công chỉ cần một đa thức từ 
véctơ đầu tiên của cơ sở LLL-rút gọn. Cụ thể, thuật toán giải phương trình 
( , )r x y như sau. 
Thuật toán giải phương trình ConicDxy Ax B 
Đầu vào: Phương trình 0( , )r x y và phân tích thừa số nguyên tố của B . 
Đầu ra: Cặp 2( , )x y  với 0( , )r x y . 
Bước 1. Tính tập ( )D B gồm tất cả các ước của B . 
Bước 2. Với mỗi ( )x D B tính ( )y B x A D . 
Bước 3. Nếu y  thì trả cặp ( , )x y . Nếu không trả ra không tìm được nghiệm. 
Tính đúng đắn của thuật toán: Giả sử 2( , )x y  là nghiệm của 0( , )r x y . Khi đó, 
( )x Dy A B . Suy ra x B hay B x , ở đây   . Đơn giản hóa phương 
trình, ta thu được 0Dy A  . Do đó, ( ) ( )y A D B x A D . Nếu 
y  thì ta có ( , )x y là nghiệm của 0( , )r x y ∎ 
Từ phương trình đồng dư (2), thực hiện biến đổi theo Cách 2 ta có, 
( , ) (mod )f x y xy Ax B q nhận 1,k a là nghiệm. Xét các đa thức 
1 2
( , ) , ( , )f x y q f x y qx và 
3
( , ) ( , )f x y f x y . Dễ thấy các đa thức này cũng nhận 
1( , )k a là nghiệm trên vành modulo q . Xây dựng lưới L được căng các véctơ 
hàng của ma trận J , ở đó, J có các hàng lần lượt hệ số của đa thức 
1 2
( , ) , ( , )f xX yX q f xX yY qYx và 
3
( , )f xX yY XYxy AYx B . Do các hàng 
của J là  -độc lập tuyến tính nên lưới có số chiều bằng 3n . Áp dụng thuật 
toán LLL vào lưới L ta thu được một cơ sở rút gọn của lưới, ký hiệu là 
1 2 3
b b b( , , ) . 
0 1 2
3 4 5
6 7 8
0 0
0 0
q C C C
J qX LLL C C C
B AX XY C C C
 
Công nghệ thông tin 
K. X. Thành, N. D. Anh, N. B. Cương, “Một số tấn công lên lược đồ  cơ sở lưới LLL.” 102 
Ta có, 2 2det detL I q X Y . Đặt 
0 0 1 1 2 2
, ,C C X C XY   . Ta có 
 1 0 1 2b , ,X XY   . Đặt đa thức 1 0 1 2( , )g x y x xy   . Do 1( , )g xX yY là các 
tổ hợp tuyến tính nguyên của 1 2 3( , ), , ,
i
f xX yY i nên 11 0( , ) (mod )g k a q
 . Do 
vậy, đa thức 
1
( , )g x y thỏa mãn điều kiện đầu tiên của Bổ đề 4. Bây giờ ta cần xác 
minh điều kiện để các đa thức 
1
( , )g x y thỏa mãn điều kiện hai của Bổ đề 4. Theo 
Tính chất 3, ta có 1 32 2
1
2b ( )q X Y . Do đó, để 
1
( , )g x y thỏa mãn ta cần 
1 32 22 3( )q X Y q hay 2 6 6X Y q . Khi đó, ta có 
1 1
3b ( , )g xX yY q . 
Thật vậy, nếu 
2
0 thì 
1 0 1 1
,qt qXt  với 
0 1
,t t  và 
1
2 3bq q 
(vô lý). Suy ra, 
2
0 và 
1 1
3b ( , )g xX yY q . Theo Bổ đề 4, 11 0,g k a 
trên  . Áp dụng thuật toán giải phương trình conic cho 
1
( , )g x y ta thu được a và 
1k (Do  = ℎ() nên việc phân tích thừa số nguyên tố của  hoàn toàn có 
thể thực hiện được). Từ các lập luận trên, ta suy ta khẳng định sau đây. 
Khẳng định 7. Đối với lược đồ chữ ký sốGOST R 34.10-2012, giả sử tồn tại ,X Y
là các số nguyên dương sao cho 1 ,k X a Y và 2 6 6X Y q thì Tấn công 2 
dưới đây có thể tìm được khóa ký dài hạn a trong lược đồ chữ ký. 
Tấn công 2 
Đầu vào: Các giá trị đã biết gồm( ( ), , )h m r s . 
Đầu ra: Khóa ký dài hạn a hoặc tấn công không thực hiện được. 
Bước 1. Tính 1 (mod )A sr q và 1( ) (mod )B h m r q . 
Bước 2. Xây dựng lưới L được sinh từ 0 0 0 0( , , ), ( , , )q qX và ( , , )B AX XY . Sử 
dụng thuật toán LLL, tìm cơ sở LLL-rút gọn của lưới L . 
Bước 3. Tính
0 0 1 1 2 2
, ,C C X C XY   . 
Bước 4. Xây dựng đa thức 
1
( , )g x y từ véctơ đầu tiên của cơ sở LLL-rút gọn. Cụ 
thể, 
1 0 1 2
( , )g x y x xy   . 
Bước 4. Sử dụng thuật toán giải phương trình conic, tính tập S gồm các nghiệm 
( , )x y của đa thức 
1
0( , )g x y . 
Bước 5. Nếu tồn tại 
0 0
( , )x y S và 
0
y P Q thì trả ra 
0
a y . Nếu 0a thì lấy 
a a , ngược lại thì lấy a a q . Trường hợp khác, trả ra “Tấn công không 
tìm được khóa a ”. 
Nhận xét 7. Chọn các số nguyên dương ,  sao cho 2 +  < log(/6√6). Đặt 
 = 2,  = 2. Khi đó, theo Khẳng định 7, nếu ta chọn các khóa ký ,  thỏa 
mãn    < , || <  thì tấn công trên có thể khôi phục lại các khóa ký này. Do 
đó, để tránh tấn công này, ta có thể chọn    > /, || > /, tương đương 
/ < ,  <  − /. 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 103
5. CÁC KẾT QUẢ THỰC NGHIỆM 
Chúng tôi đã cài đặt thực nghiệm các Tấn công 1 và 2 sử dụng phần mềm tính 
toán đại số Magma được cài đặt trên máy tính có năng lực tính toán CPU Intel 
Core i7-6700 3.4 Ghz, 8Gb Ram. Mã nguồn cài đặt trên Magma cho các tấn công 
lên GOST R 34.10-2012 được chúng tôi đạt trong[8]. Các tham số sử dụng trong 
lược đồ chữ ký số GOST R 34.10-2012 được lấy trong Ví dụ 7 của [4]. Cụ thể,  là 
một số nguyên tố có kích thước 256 bít: 
 = 57896044618658097711785492504343953926 
634992332820282019728792003956564821041 
Đường cong elliptic ( )
p
E  được định nghĩa bởi 
:  =  + 7 + 3308876546767276905765904595650931995 
942111794451039583252968842033849580414 
Cấp của điểm cơ sở 
 ≔ 5789604461865809771178549250434395392 
7082934583725450622380973592137631069619 
Tấn 
công 
Kích thước 
của (bít) 
Kích thước 
của  (bít) 
Kích thước 
của (bít) 
Kích thước 
của   (bít) 
Thời gian 
(giây) 
Tấn 
công 1 
256 126 126 0,23 
Tấn 
công 2 
256 80 256 80 1,79 
Qua các kết quả thực nghiệm, chúng tôi thấy rằng điều kiện về véctơ ngắn nhất 
thường luôn được thỏa mãn, đồng thời thời gian thực hiện tấn công khôi phục lại 
được khóa ký là rất ngắn. Do đó, để tránh các tấn công dạng này trên lược đồ 
GOST R 34.10-2012, chúng tôi khuyến cáo cần chọn các khóa ký tức thời và khóa 
ký dài hạn thỏa mãn / < , , ,  <  − /. 
6. KẾT LUẬN 
Trong bài báo này, chúng tôi đã trình bày hai tấn công khôi phục khóa ký lên 
lược đồ chữ ký số GOST R 34.10-2012. Tấn công 1 đã chỉ ra rằng nếu khóa  và  
thỏa mãn || < /6√6 thì tấn công có thể tìm lại được các khóa này. Tấn công 
2 chỉ ra có thể tìm được khóa  và  nếu||  

< /6√6. Các thuật toán tấn 
công này đã được cài đặt tính toán thực hành trên phần mềm tính toán đại số 
Magma với các tham số trong chuẩn GOST R 34.10-2012. 
TÀI LIỆU THAM KHẢO 
[1].Ian F Blake and Theodoulos Garefalakis, “On the security of the digital 
signature algorithm”. Designs, Codes and Cryptography, Vol. 26, No. 1 
(2002), pp. 87–96. 
[2]. Dan Boneh and Glenn Durfee. “Cryptanalysis of rsa with private key 
d less than n/sup 0.292”. IEEE transactions on Information Theory, 
Vol 46, No. 4 (2000), pp. 1339–1349. 
Công nghệ thông tin 
K. X. Thành, N. D. Anh, N. B. Cương, “Một số tấn công lên lược đồ  cơ sở lưới LLL.” 104 
[3]. Murray R Bremner, “Lattice basis reduction: an introduction to the 
LLL algorithm and its applications”. CRC Press (2011). 
[4]. Vasily Dolmatov and Alexey Degtyarev,“Gost R 34.10-2012: Digitalsignature 
algorithm”, (2013). 
[5]. PUB FIPS. 186-4, “Federal information processing standards publication. 
digital signature standard (dss)”.Information TechnologyLaboratory, National 
Institute of Standards and Technology (NIST), Gaithersburg, MD (2013), pp. 
20899–8900. 
[6]. Arjen Klaas Lenstra, Hendrik Willem Lenstra, and László Lovász. 
“Factoring polynomials with rational coefficients”. Mathematische Annalen, 
Vol 261, No. 4 (1982), pp. 515–534. 
[7]. D. Poulakis,“Some lattice attacks on dsa and ecdsa”. Applicable Algebra in 
Engineering,Communication andComputing,Vol 22,No. 5 (2011), pp. 347–
358. 
[8]. https://github.com/khucxuanthanh/Attack-on-GOST-R-34.10-2012- 
ABSTRACT 
SOME ATTACKS ON THE DIGITAL SIGNAURTE SCHEME GOST R 34.10-
2012 BASED ON LATTICE REDUCTION ALGOTHRIM LLL 
In this paper, two attacks to recover the long-term key  and the 
ephemeral key  in the digital signature GOST R 34.10-2012 based on the 
LLL algorithm are introduced. These attacks are based on approaches in the 
attacks on DSA and ECDSA [1], [7]. Specifically, it is showed that if the 
signature keys ,  which satisfies ,   − /then they 
can be retrieved by the attack which based on [1]. The attack that based on 
[7] can be recovered the key ,  if ,  < / or,  < /. These 
attacks have been tested by us on the Magma Algebra software. 
Keywords: Cryptography, Lattice, Digital signature algorithm, LLL algorithm, GOST R 34.10-2012. 
Nhận bài ngày 16 tháng 8 năm 2017 
Hoàn thiện ngày 26 tháng 11 năm 2017 
Chấp nhận đăng ngày 28 tháng 11 năm 2017 
Địa chỉ: 1 Viện Khoa học-Công nghệ Mật mã, Ban cơ yếu Chính phủ; 
 2 Đại học Khoa học Tự nhiên Hà Nội. 
 *Email: khucxuanthanh@gmail.com.