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ành

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.