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

Bài viết 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.
Nội dung trích xuất từ tài liệu:
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 LLLNghiên cứu khoa học công nghệ MỘT SỐ TẤN CÔNG LÊN LƯỢC ĐỒ CHỮ KÝ SỐ GOSTR 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 , < / hoặc , > / − . 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ôngbố, thuật toán LLL ngay lập tức được xem như một trong những thuật toán quantrọ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áytính và lý thuyết số. Một trong những ứng dụng đầu tiên của thuật toán LLL trongmậ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ênbả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ìnhnghiên cứu tấn công lên DSA, ECDSA dựa trên thuật toán LLL như [1], [7]. Cáctấ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 khicác khóa ký của chữ ký thỏa mãn một điều kiện nào đó. Trong khi đó, GOST R34.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áctấ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ậycó 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óaký 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ấncô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ốTạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 95 Công nghệ thông tinMagma với các tham số được lấy trong [4]. Kết quả thực nghiệm cho thấy, các tấncô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ưởngchung 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ốicù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óaký 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 n  1 , (b1, b 2 ,  , bn ) là một cơ sở của n . Lưới n chiềuL 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ácvéctơ cơ sở nàyvới hệ số nguyên. Tức là, L có thể được biểu diễn như sau:  n   L  b1  b 2    bn    ai bi a1, a 2 , , an    (1)   i 1     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ếtbi  (bi1, bi 2 ,  , bin ) , thành lập một ma trận X  (bij ) . Định thức của lưới L trongcơ sở (b1, b 2 ,  , bn ) được định nghĩa là det L  det X . Ký hiệu (b1* , b*2 ,  , bn* ) làcác véctơ thu được sau khi trực giao hóa Gram-Schmidt (b1, b 2 ,  , bn ) . Định thứccủ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ủamộ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 ( v1, v ...