Gửi lúc: 16/01/2018 17:03:50
Bookmark and Share

Analysis of the errors in the recent attacks on DSA and ECDSA using lattice theory

CSKH-01.2017 - (Tóm tắt) Gần đây, trong các tấn công lên lược đồ chữ ký DSA và ECDSA dựa trên lý thuyết lưới đã có các kết quả mới được công bố của Poulakis trong [1, 2] và Draziotis trong [3]. Tuy vậy, trong các bài báo đó vẫn tồn tại một số sai sót trong tính toán bằng số, định nghĩa và tính khả thi của tấn công. Các sai sót này đã được chúng tôi trao đổi lại với chính các tác giả của các bài báo trên và đã nhận được sự công nhận về những nhầm lẫn này. Các kết quả kiểm chứng tính toán đã được chúng tôi thực hiện trên bộ công cụ tính toán đại số MAGMA [4].

Abstract- Recently, in the attacks on DSA and ECDSA which based on the lattice have some new results that are published by Poulakis in [1, 2] and Draziotis in [3]. However, these papers still have some of the errors in the numerical computation examples, the definitions, and the feasibility of the attack. Namely, Poulakis [1] has an error in the numerical computation example. Draziotis [3] incorrectly defines polynomials that construct rows of matrices in the attack. Attack of Poulakis in 2016 [2] is less feasible and the numerical computation example on this paper is incorrect. We discussed with Poulakis and Draziotis about the above errors. They recognized these errors. The computationally verifiable results have made on the MAGMA Algebra Toolkit [4].

Xem toàn bộ bài báo tại đây


  Tài liệu tham khảo

[1] D. Poulakis, "Some lattice attacks on DSA and ECDSA," Applicable Algebra in Engineering, Communication, and Computing, vol. 22, no. 5, pp. 347-358, 2011.

[2] D. Poulakis, "New lattice attacks on DSA schemes," Journal of Mathematical Cryptology, vol. 10, no. 2, pp. 135-144, 2016.

[3] K. A. Draziotis, "DSA lattice attacks based on Coppersmith's method," Information Processing Letters, vol. 116, no. 8, pp. 541-545, 2016.

[4] J. Cannon, W. Bosma, C. Fieker, and A. Steel, "Handbook of MAGMA functions," Edition, vol. 2, 2006.

[5] A. K. Lenstra, H. W. Lenstra, and L. Lovász, "Factoring polynomials with rational coefficients," Mathematische Annalen, vol. 261, no. 4, pp. 515-534, 1982.

[6] A. May, "Using LLL-reduction for solving RSA and factorization problems," in The LLL algorithm: Springer, pp. 315-348, 2009.

[7] D. Boneh and G. Durfee, "Cryptanalysis of RSA with private key d less than N/sup 0.292," IEEE transactions on Information Theory, vol. 46, no. 4, pp. 1339-1349, 2000.

[8] I. F. Blake and T. Garefalakis, "On the security of the digital signature algorithm," Designs, Codes and Cryptography, vol. 26, no. 1, pp. 87-96, 2002.

[9] P. Gallagher, "Digital signature standard (DSS)," Federal Information Processing Standards Publications, volume FIPS, pp. 186-3, 2013.

[10] I. F. Blake, G. Seroussi, and N. Smart, Elliptic curves in cryptography. Cambridge university press, 1999.

[11] K. Draziotis. (2017). DSA lattice attacks based on Coppersmith's method. Available: http://users.auth.gr/drazioti/extension_of_poulakis_11_elsevier.pdf


Khúc Xuân Thành, Nguyễn Duy Anh, Nguyễn Bùi Cương