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ệ<br /> <br /> MỘT SỐ TẤN CÔNG LÊN LƯỢC ĐỒ CHỮ KÝ SỐ GOST<br /> R 34.10-2012 DỰA TRÊN THUẬT TOÁN RÚT GỌN CƠ SỞ LƯỚI LLL<br /> Khúc Xuân Thành1*, Nguyễn Duy Anh2, Nguyễn Bùi Cương1<br /> 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ý<br /> 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<br /> 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<br /> trong các tấn công lên lược đồ chữ ký số DSA và ECDSA [1], [7]. Cụ thể, trong tấn<br /> 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 , < /<br /> 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<br /> dựa trên [7], có thể khôi phục được các khóa ký nếu , < / hoặc , ><br /> /<br /> − . 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<br /> mềm tính toán đại số Magma.<br /> Từ khóa: Mật mã, Lưới, Lược đồ chữ ký số, Thuật toán LLL, GOST R 34.10-2012.<br /> <br /> 1. MỞ ĐẦU<br /> 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ờ<br /> thuật toán rút gọn cơ sở lưới do ba nhà toán học Arjen Lenstra, Hendrik Lenstra,<br /> László Lovász tìm ra năm 1982 [6] (được viết tắt là LLL). Ngay sau khi được công<br /> bố, thuật toán LLL ngay lập tức được xem như một trong những thuật toán quan<br /> 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<br /> 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<br /> 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<br /> [2], DSA [1], ECDSA [7] đã được phát triển dựa trên thuật toán LLL.<br /> Các nghiên cứu liên quan. Lược đồ DSA và ECDSA [5] được biết đến như phiên<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> đ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<br /> 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ý<br /> “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<br /> có thể xảy ra trên lược đồ chữ ký số GOST R 34.10-2012?<br /> Đó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ữ<br /> 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<br /> ký lên lược đồ chữ ký số GOST R 34.10-2012. Cụ thể, đối với lược đồ chữ ký số<br /> 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à<br /> khóa ký tức thời thỏa mãn | | < (ở đây, là cấp của điểm cơ sở trong<br /> √<br /> chữ ký, với ∈ [1, ],kí hiệu = nếu ≤ , ngược lại = − ) thì kẻ tấn<br /> 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ẻ<br /> tấn công có thể khôi phục được và khi | | < . Hai tấn công này đã<br /> √<br /> đượ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ố<br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 95<br />  Công nghệ thông tin<br /> <br /> 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<br /> công này có thể khôi phục các khóa ký trong thời gian rất ngắn.<br /> 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ý<br /> thuyết lưới và lược đồ chữ ký số GOST R 34.10-2012. Mục 3 trình bày ý tưởng<br /> 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.<br /> 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<br /> 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<br /> ký cho lược đồ chữ ký số GOST R 34.10-2012.<br /> 2. MỘT SỐ KHÁI NIỆM CƠ SỞ<br /> 2.1. Lưới<br /> Trước tiên, chúng tôi nhắc lại định nghĩa của lưới.<br /> Định nghĩa 1. ([3]) Cho n  1 , (b1, b 2 ,  , bn ) là một cơ sở của n . Lưới n chiều<br /> L với cơ sở (b1, b 2 ,  , bn ) là tập hợp gồm tất cả các tổ hợp tuyến tính của các<br /> véctơ cơ sở nàyvới hệ số nguyên. Tức là, L có thể được biểu diễn như sau:<br /> <br /> n <br /> <br /> L  b1  b 2    bn  <br />  ai bi a1, a 2 , , an  <br />  (1)<br /> <br />  i 1 <br /> <br />  <br /> Các véctơ (b1, b 2 ,  , bn ) được gọi là cơ sở của lưới. Với mỗi 1  i  n , viết<br /> bi  (bi1, bi 2 ,  , bin ) , thành lập một ma trận X  (bij ) . Định thức của lưới L trong<br /> cơ sở (b1, b 2 ,  , bn ) được định nghĩa là det L  det X . Ký hiệu (b1* , b*2 ,  , bn* ) là<br /> các véctơ thu được sau khi trực giao hóa Gram-Schmidt (b1, b 2 ,  , bn ) . Định thức<br /> 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ở<br /> 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<br /> một cơ sở mới thu được sau khi ápdụng thuật toán LLL.<br /> Khẳng định 2. ([3]) Cho L là một lưới được căng bởi ( v1, v 2 ,  , vn ) . Áp dụng<br /> 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 (b1, b 2 ,  , bn ) ,<br /> được gọi là cở sở LLL-rút gọn, thỏa mãn hai điều kiện sau đây:<br /> <br /> bi  b*j<br /> 1, ij  2<br />  1 2 với mọi 1  j  i  n .<br /> *<br /> b j<br /> <br /> <br /> 3 *<br /> 2, bi*  i,i 1bi*1  b với mọi 2  i  n , ở đây, bi  b *j là tích vô hướng của<br /> 4 i 1<br /> véctơ bi và b*j .<br /> Chứng minh. Xem [3], Trang 71. ∎<br /> Tính chất 3. ([3])Nếu (b1, b 2 ,  , bn ) là một cơ sở LLL-rút gọn của lưới L trong<br /> n thì ta có:<br /> (n 1) 4 1n<br /> 1, b1  2 (det L) .<br /> <br /> <br /> <br /> 96 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.”<br /> Nghiên cứu khoa học công nghệ<br /> 1 (n 1)<br /> (n  2 ) 4  1<br /> <br /> 2, b 2  2 det L  b1  .<br /> <br /> Chứng minh. Xem [3], Trang 59. ∎<br /> 2.2. Lược đồ chữ ký số GOST R 34.10-2012<br /> Lược đồ GOST R 34.10-2012 [4] được xem là chuẩn chữ ký số của Nga. Lược<br /> đồ này sử dụng một đường cong elliptic E trên p và một điểm P  E (p ) có cấp<br /> 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:<br /> 1, Thuật toán sinh khóa cho người ký:<br />  Chọn a ngẫu nhiên đều trong [1,  , q  1] là khóa ký dài hạn.<br />  Tính Q  aP là khóa công khai<br /> 2, Thuật toán ký của người ký trên thông điệp m :<br />  Chọn k ngẫu nhiên đều trong [1,  , q  1] là khóa ký tức thời.<br />  Tính kP  (x , y ) , lấy r  x (mod q ) nếu r  0 thì chọn lại k .<br />  Tính h (m ) , ở đây h là một hàm băm ánh xạ thông điệp tới {1,  , q  1} .<br />  Tính s  (kh (m )  ar ) (mod q ) , nếu s  0 thì chọn lại k .<br /> 3, Thuật toán xác minh chữ ký (r , s ) trên thông điệp m :<br />  Xác minh r , s có thuộc [1, q  1] hay không.<br />  Tính w  h(m)1 (mod q )<br />  Tính u1  sw (mod q ) và u 2  rw (mod q ) .<br />  Tính R  (x R , yR )  u1P  u 2Q<br />  Chữ ký được chấp nhận chỉ khi r  x R (mod q ) .<br /> Tính đúng đắn của thuật toán. Ta có,<br /> R  (x R , yR )  u1P  u 2Q  (u1  u 2a )P  (h(m )1s 1  arh(m )1 )P  kP .<br /> <br /> 3. Ý TƯỞNG CHUNG CỦA TẤN CÔNG<br /> Ý 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<br /> 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<br /> giải phương trình đồng dư:<br /> s  (kh(m)  ar ) (mod q) . (2)<br /> Từ phương trình (2), các tấn công sử dụng hai các biến đổi chính sau:<br /> Cách 1. Nhân cả hai vế của (2) với r 1 , ta có:<br /> a  k(h(m)r 1 )  sr 1  0 (mod q ) .<br /> Đặt A  h(m)r 1 (mod q ), B  sr 1 (mod q ) . Khi đó, cặp (k , a ) nghiệm của đa<br /> thức f (x , y )  y  Ax  B  0 (mod q ) .<br /> Cách 2. Nhân cả hai vế của (2) với k 1 và r 1 , ta có:<br /> ak 1  (r 1s )k 1  h (m )r 1  0 (mod q ) .<br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 97<br />  Công nghệ thông tin<br /> <br /> Đặt A  sr 1 (mod q ), B  h(m)r 1 (mod q ) . Khi đó, cặp (k 1, a ) là nghiệm của<br /> phương trình đồng dư f (x , y )  xy  Ax  B  0 (mod q ) .<br /> 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<br /> đồ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<br /> 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.<br /> 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<br /> trên vành số nguyên. Bổ đề Howgrave-Graham [2] dưới đây cho ta một ý tưởng<br /> một cách chuyển như vậy.<br /> Cho h(x , y )   hi, j x i y j với hi, j   . Khi đó, gọi “chuẩn của h(x, y) ” là đại<br /> i, j<br /> <br /> lượng được ký hiệu là h(x , y ) và được xác định theo công thức<br /> <br /> h(x , y ) : h 2<br /> i, j<br /> .<br /> i, j<br /> <br /> <br /> Bổ đề 4. (Howgrave-Graham, [2])Cho đa thức h (x , y )  h i, j<br /> x i y j  [x , y ] là tổng<br /> i, j<br /> <br /> của n đơn thức. Lấy X ,Y là các số nguyên dươngvà các số nguyên x 0 , y 0 sao cho<br /> x 0  X , y 0  Y . Khi đó, nếu<br /> <br /> 1, h(x 0 , y 0 )  0 (mod q )<br /> <br /> 2, h(xX , yY )  q n,<br /> <br /> thì h(x 0 , y 0 )  0 trên vành số nguyên.<br /> Chứng minh. Xem [2] Trg. 4-5. ∎<br /> 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<br /> 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<br /> chuyển như sau: Đặt x 0  k theo biến đổi Cách 1 (hoặc x 0  k 1 theo biến đổi<br /> Cách 2) và y 0  a . Cho n là một số nguyên dương nào đó (trong từng tấn công sẽ<br /> định nghĩa cụ thể ). Sinh các đa thức fi (x , y ) (i  1,  , n ) mà cũng nhận (x 0 , y 0 ) là<br /> nghiệm trên vành modulo q . Sinh lưới chiều L từ các hàng của ma trận I trong<br /> đó các hàng của I là các hệ số của đa thức fi (xX , yY ) (i  1,  , n ) . Áp dụng thuật<br /> toán rút gọn cơ sở LLL vào lưới L ta thu được cơ sở mới (b1, b 2 ,  , bn ) . Do thuật<br /> toán LLL sử dụng các phép toán biến đổi tuyến tính nguyên nên<br /> g i (x 0 , y 0 )  0 (mod q ) (i  1,  , n ) . Ngoài ra, qua thuật toán LLL ta còn thu được<br /> <br /> cận trên của b1 . Nếu cận trên này nhỏ hơn q n thì g1(x 0 , y 0 )  0 trên  . Toàn<br /> bộ cách thực hiện có thể được mô tả qua Sơ đồ 1.<br /> <br /> <br /> <br /> 98 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.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> f (x 0 , y 0 )  0 (mod q ), x 0  X , y 0  Y<br /> <br /> Sinh fi (x 0 , y 0 )  0 (mod q )<br /> <br />  f (xX , yY )  b  g (xX , yY ) <br />  1   1 1  g (x , y )  0<br /> <br /> I     LLL<br />  I     <br /> H-G  1<br />      <br />     <br /> g (x , y )  0<br />  2<br />  fn (xX , yY ) bn  gn (xX , yY )<br /> Sơ đồ 1. Cách thức chung trong thực hiện các tấn công.<br /> Tấn công 2 dựa trên [7] đã đưa ra một phương pháp tìm nghiệm của g1(x , y )  0<br /> trên  nếu đa thức g1(x , y ) có dạng g1(x , y )  xy  Ax  B và dựa trên giả thiết<br /> 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 g1(x , y ) cũng<br /> có dạng như vậy. Do đó, ta cần thêm một đa thức g 2 (x , y )  0 trên  để thu được<br /> 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<br /> đượ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<br /> 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<br /> công 1 dựa trên [1].<br /> 4. CÁC TẤN CÔNG LÊN GOST R 34.10-2012<br /> 4.1. Tấn công 1<br /> 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ư<br /> (2) thực hiện biến đổi theo Cách 1, ta có f (x , y )  y  Ax  B (mod q ) nhận (k , a )<br /> là nghiệm. Xét các đa thức f1(x , y )  q, f2 (x , y )  qx và f3 (x , y )  f (x , y ) . Dễ thấy<br /> fi (k , a )  0 (mod q ) (i  1, 2, 3) . Xây dựng lưới L được căng các véctơ hàng của ma<br /> trận I , ở đó, ma trận có các hàng lần lượt hệ số của đa thức<br /> f1(xX , yX )  q , f2 (xX , yY )  qXx và f3 (xX , yY )  Yy  AXx  B . Do các hàng của<br /> ma trận I là  -độc lập tuyến tính nên lưới có số chiều bằng n  3 . Áp dụng thuật<br /> 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à (b1, b 2 , b 3 ) .<br /> q 0   <br />  0 C 0 C1 C 2 <br />  <br /> I   0 qX 0  LLL <br />  C 3 C 4 C 5 <br />   <br /> C C C <br /> B AX Y   6 7 8<br /> <br /> Khi đó, ta có định thức của lưới L là det L  det I  q 2XY . Đặt<br />  0  C 0 , 1  C 1 X ,  2  C 2 Y ,  3  C 3,  4  C 4 X và  5  C 5 Y nên ta có<br /> b1   0 , 1X ,  2Y , b 2   3 ,  4 X ,  5Y  . Đặt các đa thức g1(x , y )   0  1x   2y, và<br /> g 2 (x , y )   3   4x   5y . Do g1(xX , yY ) và g 2 (xX , yY ) là các tổ hợp tuyến tính<br /> nguyên của fi (xX , yY ) (i  1, 2, 3) nên các đa thức g1(x , y ), g 2 (x , y ) cũng nhận (k , a )<br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 99<br />  Công nghệ thông tin<br /> <br /> là nghiệm trên vành modulo . Do đó, các đa thức g1(x , y ), g 2 (x , y ) thỏa mãn điều<br /> 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<br /> g1(x , y ), g 2 (x , y ) thỏa mãn điều kiện hai của Bổ đề 4. Ta có, b1  g1(xX , yY ) và<br /> 13<br /> b 2  g 2 (xX , yY ) . Theo Tính chất 3, b1  2(q XY ) . Do đó, để g1(x , y ) thỏa<br /> 2<br /> <br /> <br /> 13<br /> mãn các điều kiện hai của Bổ đề 4, ta cần 2(q 2XY ) q 3 hay XY  q 6 6 .<br /> Tuy nhiên, đây chỉ là điều kiện cho đa thức g1(x , y ) . Ta cần tìm điều kiện cho<br /> đa thức g 2 (x , y ) , tức cần điều kiện để b 2  q 3 . Theo Tính chất 3, ta có<br /> 14 1 1 2 14 1 1 2<br /> b 2  2 (det L  b1 ) . Do đó, ta cần 2 (det L  b1 ) q 3 hay<br /> b1  3 2XY . Do vậy, nếu XY  q 6 6 và b1  3 2XY thì<br /> g i (k , a )  0, (i  1, 2) trên  . Đặt r3 (y ) là kết thức của đa thức g1(x , y ) và g 2 (x , y )<br /> theo biến x . Khi đó, ta thu được r3 (y ) là một đa thức một biến theo biến y . Sử<br /> 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<br /> Sturm hay phương pháp Newton ta có thể tìm được nghiệm y của r3 (y ) . Nếu tồn<br /> tại y0 sao cho y 0P  Q thì a  y 0 . Mặt khác, nếu a  0 thì lấy a  a ngược lại thì<br /> lấy a  a  q.<br /> Từ các lập luận trên, ta có suy ra khẳng định sau đây:<br /> 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<br /> là các số nguyên dươngsao cho k  X , a  Y và XY  q 6 6 . Cho L là một<br /> 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ơ<br /> 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ả<br /> dưới đây có thể tìm được khóa ký dài hạn a trong lược đồ chữ ký số.<br /> Tấn công 1<br /> Đầu vào: Các giá trị đã biết gồm (h (m ), r , s ) .<br /> Đầu ra: Khóa ký dài hạn hoặc tấn công không thực hiện được.<br /> Bước 1. Tính A  h(m)r 1 (mod q ) và B  sr 1 (mod q ) .<br /> Bước 2. Xây dựng lưới L được sinh từ (q, 0, 0),(0, qX , 0) và (B, AX ,Y ) . Sử dụng<br /> thuật toán LLL, tìm cơ sở LLL-rút gọn của lưới L .<br /> Bước 3. Tính  0  C 0 , 1  C 1 X ,  2  C 2 Y ,  3  C 3 ,  4  C 4 X ,  5  C 5 Y .<br /> Bước 4. Xây dựng đa thức g1(x , y ), g 2 (x , y ) tương ứng là véctơ đầu tiên và véctơ<br /> thứ hai của cơ sở LLL-rút gọn. Cụ thể, g1(x , y )   0  1x   2y và<br /> g 2 (x , y )   3   4x   5y .<br /> Bước 5. Tính r3 (y ) là kết thức của đa thức g1(x , y ) và g 2 (x , y ) theo biến x .<br /> Bước 6. Tìm nghiệm của đa thức một biến r3 (y ) .<br /> <br /> <br /> 100 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.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> Bước 7. Nếu tồn tại y sao cho yP  Q thì trả ra đầu ra a  y . Nếu a  0 thì<br /> 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<br /> tìm được khóa a ”.<br /> Nhận xét 6. Chọn các số nguyên dương , sao cho + < log ( /6√6). Đặt<br /> = 2 , = 2 . Khi đó, theo Khẳng định 5, nếu ta chọn các khóa ký , thỏa<br /> 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<br /> đó, để tránh tấn công này, ta có thể chọn > / , | | > / , tương<br /> đương / < , < − / .<br /> 4.2. Tấn công 2<br /> 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<br /> cách giải cho các phương trình conic có dạng r (x , y )  Dxy  Ax  B , ở đây<br /> 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ừ<br /> 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<br /> r (x , y ) như sau.<br /> Thuật toán giải phương trình Conic Dxy  Ax  B<br /> Đầu vào: Phương trình r (x , y )  0 và phân tích thừa số nguyên tố của B .<br /> Đầu ra: Cặp (x , y )   2 với r (x , y )  0 .<br /> Bước 1. Tính tập D(B ) gồm tất cả các ước của B .<br /> Bước 2. Với mỗi x  D(B ) tính y  (B x  A) D .<br /> 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.<br /> Tính đúng đắn của thuật toán: Giả sử (x , y )   2 là nghiệm của r (x , y )  0 . Khi đó,<br /> x (Dy  A)  B . Suy ra x B hay B  x , ở đây    . Đơn giản hóa phương<br /> trình, ta thu được Dy  A    0 . Do đó, y  (  A) D  (B x  A) D . Nếu<br /> y   thì ta có (x , y ) là nghiệm của r (x , y )  0 ∎<br /> Từ phương trình đồng dư (2), thực hiện biến đổi theo Cách 2 ta có,<br /> f (x , y )  xy  Ax  B (mod q ) nhận k ,a <br /> 1<br /> là nghiệm. Xét các đa thức<br /> <br /> f1(x , y )  q, f2 (x , y )  qx và f3 (x , y )  f (x , y ) . Dễ thấy các đa thức này cũng nhận<br /> <br /> (k 1, a ) là nghiệm trên vành modulo q . Xây dựng lưới L được căng các véctơ<br /> 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<br /> f1(xX , yX )  q, f2 (xX , yY )  qYx và f3 (xX , yY )  XYxy  AYx  B . Do các hàng<br /> của J là  -độc lập tuyến tính nên lưới có số chiều bằng n  3 . Áp dụng thuật<br /> 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à (b1, b 2 , b 3 ) .<br /> q 0  C C C <br />  0  0 2<br />  C C C <br /> 1<br /> J   0 qX 0  LLL<br />   3 5<br />    4<br /> <br /> B AX XY  C 6 C 7 C 8 <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 101<br />  Công nghệ thông tin<br /> <br /> Ta có, det L  det I  q 2 X 2Y . Đặt  0  C 0 , 1  C 1 X ,  2  C 2 XY . Ta có<br /> b1   0 , 1X ,  2 XY  . Đặt đa thức g1(x , y )   0  1x   2xy . Do g1(xX , yY ) là các<br /> <br /> tổ hợp tuyến tính nguyên của fi (xX , yY ), i  1, 2, 3 nên g1(k 1, a )  0 (mod q ) . Do<br /> vậy, đa thức g1(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<br /> minh điều kiện để các đa thức g1(x , y ) thỏa mãn điều kiện hai của Bổ đề 4. Theo<br /> Tính chất 3, ta có b1  2 (q 2 X 2Y )1 3 . Do đó, để g1(x , y ) thỏa mãn ta cần<br /> 13<br /> 2 (q 2 X 2Y ) q 3 hay X 2Y  q 6 6 . Khi đó, ta có b1  g1 (xX , yY )  q 3.<br /> <br /> Thật vậy, nếu  2  0 thì 1  qt0 , 1  qXt1 với t 0 , t1   và q 2  b1  q 3<br /> <br /> (vô lý). Suy ra,  2  0 và b1  g1(xX , yY )  q <br /> 1<br /> 3 . Theo Bổ đề 4, g1 k , a  0<br /> trên  . Áp dụng thuật toán giải phương trình conic cho g1(x , y ) ta thu được a và<br /> k 1 (Do = ℎ( ) nên việc phân tích thừa số nguyên tố của hoàn toàn có<br /> thể thực hiện được). Từ các lập luận trên, ta suy ta khẳng định sau đây.<br /> 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<br /> là các số nguyên dương sao cho k 1  X , a  Y và X 2Y  q 6 6 thì Tấn công 2<br /> dưới đây có thể tìm được khóa ký dài hạn a trong lược đồ chữ ký.<br /> Tấn công 2<br /> Đầu vào: Các giá trị đã biết gồm (h (m ), r , s ) .<br /> Đầu ra: Khóa ký dài hạn a hoặc tấn công không thực hiện được.<br /> Bước 1. Tính A  sr 1 (mod q ) và B  h(m )r 1(mod q ) .<br /> Bước 2. Xây dựng lưới L được sinh từ (q , 0, 0), (0, qX , 0) và (B , AX , XY ) . Sử<br /> dụng thuật toán LLL, tìm cơ sở LLL-rút gọn của lưới L .<br /> Bước 3. Tính  0  C 0 , 1  C 1 X ,  2  C 2 XY .<br /> Bước 4. Xây dựng đa thức g1(x , y ) từ véctơ đầu tiên của cơ sở LLL-rút gọn. Cụ<br /> thể, g1(x , y )   0  1x   2xy .<br /> 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<br /> (x , y ) của đa thức g1(x , y )  0 .<br /> Bước 5. Nếu tồn tại (x 0 , y 0 )  S và y 0P  Q thì trả ra a  y 0 . Nếu a  0 thì lấy<br /> 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<br /> tìm được khóa a ”.<br /> Nhận xét 7. Chọn các số nguyên dương , sao cho 2 + < log ( /6√6). Đặt<br /> = 2 , = 2 . Khi đó, theo Khẳng định 7, nếu ta chọn các khóa ký , thỏa<br /> 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<br /> đó, để tránh tấn công này, ta có thể chọn > / , | | > / , tương đương<br /> /<br /> < , < − / .<br /> <br /> <br /> <br /> 102 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.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> 5. CÁC KẾT QUẢ THỰC NGHIỆM<br /> 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<br /> 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<br /> Core i7-6700 3.4 Ghz, 8Gb Ram. Mã nguồn cài đặt trên Magma cho các tấn công<br /> lên GOST R 34.10-2012 được chúng tôi đạt trong[8]. Các tham số sử dụng trong<br /> lược đồ chữ ký số GOST R 34.10-2012 được lấy trong Ví dụ 7 của [4]. Cụ thể, là<br /> một số nguyên tố có kích thước 256 bít:<br /> = 57896044618658097711785492504343953926<br /> 634992332820282019728792003956564821041<br /> Đường cong elliptic E (p ) được định nghĩa bởi<br /> : = + 7 + 3308876546767276905765904595650931995<br /> 942111794451039583252968842033849580414<br /> Cấp của điểm cơ sở<br /> ≔ 5789604461865809771178549250434395392<br /> 7082934583725450622380973592137631069619<br /> <br /> Tấn Kích thước Kích thước Kích thước Kích thước Thời gian<br /> công của (bít) của (bít) của (bít) của (bít) (giây)<br /> Tấn<br /> 256 126 126 0,23<br /> công 1<br /> Tấn<br /> 256 80 256 80 1,79<br /> công 2<br /> 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<br /> 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<br /> đượ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 đồ<br /> 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<br /> ký dài hạn thỏa mãn / < , , , < − / .<br /> 6. KẾT LUẬN<br /> 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<br /> lược đồ chữ ký số GOST R 34.10-2012. Tấn công 1 đã chỉ ra rằng nếu khóa và<br /> 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<br /> 2 chỉ ra có thể tìm được khóa và nếu| | < /6√6. Các thuật toán tấn<br /> 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ố<br /> Magma với các tham số trong chuẩn GOST R 34.10-2012.<br /> TÀI LIỆU THAM KHẢO<br /> [1].Ian F Blake and Theodoulos Garefalakis, “On the security of the digital<br /> signature algorithm”. Designs, Codes and Cryptography, Vol. 26, No. 1<br /> (2002), pp. 87–96.<br /> [2]. Dan Boneh and Glenn Durfee. “Cryptanalysis of rsa with private key<br /> d less than n/sup 0.292”. IEEE transactions on Information Theory,<br /> Vol 46, No. 4 (2000), pp. 1339–1349.<br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 103<br />  Công nghệ thông tin<br /> <br /> [3]. Murray R Bremner, “Lattice basis reduction: an introduction to the<br /> LLL algorithm and its applications”. CRC Press (2011).<br /> [4]. Vasily Dolmatov and Alexey Degtyarev,“Gost R 34.10-2012: Digitalsignature<br /> algorithm”, (2013).<br /> [5]. PUB FIPS. 186-4, “Federal information processing standards publication.<br /> digital signature standard (dss)”.Information TechnologyLaboratory, National<br /> Institute of Standards and Technology (NIST), Gaithersburg, MD (2013), pp.<br /> 20899–8900.<br /> [6]. Arjen Klaas Lenstra, Hendrik Willem Lenstra, and László Lovász.<br /> “Factoring polynomials with rational coefficients”. Mathematische Annalen,<br /> Vol 261, No. 4 (1982), pp. 515–534.<br /> [7]. D. Poulakis,“Some lattice attacks on dsa and ecdsa”. Applicable Algebra in<br /> Engineering,Communication andComputing,Vol 22,No. 5 (2011), pp. 347–<br /> 358.<br /> [8]. https://github.com/khucxuanthanh/Attack-on-GOST-R-34.10-2012-<br /> ABSTRACT<br /> SOME ATTACKS ON THE DIGITAL SIGNAURTE SCHEME GOST R 34.10-<br /> 2012 BASED ON LATTICE REDUCTION ALGOTHRIM LLL<br /> In this paper, two attacks to recover the long-term key and the<br /> ephemeral key in the digital signature GOST R 34.10-2012 based on the<br /> LLL algorithm are introduced. These attacks are based on approaches in the<br /> attacks on DSA and ECDSA [1], [7]. Specifically, it is showed that if the<br /> signature keys , which satisfies , < / or , > − / then they<br /> can be retrieved by the attack which based on [1]. The attack that based on<br /> [7] can be recovered the key , if , < / or , < / . These<br /> attacks have been tested by us on the Magma Algebra software.<br /> Keywords: Cryptography, Lattice, Digital signature algorithm, LLL algorithm, GOST R 34.10-2012.<br /> <br /> <br /> Nhận bài ngày 16 tháng 8 năm 2017<br /> Hoàn thiện ngày 26 tháng 11 năm 2017<br /> Chấp nhận đăng ngày 28 tháng 11 năm 2017<br /> Địa chỉ: 1 Viện Khoa học-Công nghệ Mật mã, Ban cơ yếu Chính phủ;<br /> 2<br /> Đại học Khoa học Tự nhiên Hà Nội.<br /> *<br /> Email: khucxuanthanh@gmail.com.<br /> <br /> <br /> <br /> <br /> 104 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.”<br />