1. NCCU Academic Hub
  2. Publications
  3. College of Informatics
  4. Proceedings
  5. Item

Publications-Proceedings

Article View/Open

Publication Export

Google ScholarTM

NCCU Library

Citation Infomation

Related Publications in TAIR

題名 Cryptanalysis of exhaustive search on attacking RSA
作者 Wu, M.-E.;Tso, R.;Sun, H.-M.
左瑞麟
貢獻者 資科系
關鍵詞 Computational environments; Exhaustive search; Lattice basis reduction; Lattice reduction; LLL algorithm; Most significant bit; Partial key exposure; RSA; RSA moduli; Artificial intelligence; Network security
日期 2012
上傳時間 17-Apr-2015 11:39:48 (UTC+8)
摘要 In RSA equation: ed = k·φ(N) + 1, we may guess on partial bits of d or p + q by doing an exhaustive search to further extend the security boundary of d. In this paper, we discuss the following question: Does guessing on p + q bring more benefit than guessing on d? We provide the detailed analysis on this problem by using the lattice reduction technique. Our analysis shows that leaking partial most significant bits (MSBs) of p + q in RSA risks more than leaking partial MSBs of d. This result inspires us to further extend the boundary of the Boneh-Durfee attack to N0.284+Δ, where "Δ" is contributed by the capability of exhaustive search. Assume that doing an exhaustive search for 64 bits is feasible in the current computational environment, the boundary of the Boneh-Durfee attack should be raised to d < N0.328 for an 1024-bit RSA modulus. This is a 37 bits improvement over Boneh and Durfee`s boundary. © 2012 Springer-Verlag.
關聯 Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)，Volume 7645 LNCS, 373-379
資料類型 conference
DOI http://dx.doi.org/10.1007/978-3-642-34601-9_28
dc.contributor 資科系
dc.creator (作者) Wu, M.-E.;Tso, R.;Sun, H.-M.
dc.creator (作者) 左瑞麟zh_TW
dc.date (日期) 2012
dc.date.accessioned 17-Apr-2015 11:39:48 (UTC+8)-
dc.date.available 17-Apr-2015 11:39:48 (UTC+8)-
dc.date.issued (上傳時間) 17-Apr-2015 11:39:48 (UTC+8)-
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/74659-
dc.description.abstract (摘要) In RSA equation: ed = k·φ(N) + 1, we may guess on partial bits of d or p + q by doing an exhaustive search to further extend the security boundary of d. In this paper, we discuss the following question: Does guessing on p + q bring more benefit than guessing on d? We provide the detailed analysis on this problem by using the lattice reduction technique. Our analysis shows that leaking partial most significant bits (MSBs) of p + q in RSA risks more than leaking partial MSBs of d. This result inspires us to further extend the boundary of the Boneh-Durfee attack to N0.284+Δ, where "Δ" is contributed by the capability of exhaustive search. Assume that doing an exhaustive search for 64 bits is feasible in the current computational environment, the boundary of the Boneh-Durfee attack should be raised to d < N0.328 for an 1024-bit RSA modulus. This is a 37 bits improvement over Boneh and Durfee`s boundary. © 2012 Springer-Verlag.
dc.format.extent 176 bytes-
dc.format.mimetype text/html-
dc.relation (關聯) Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)，Volume 7645 LNCS, 373-379
dc.subject (關鍵詞) Computational environments; Exhaustive search; Lattice basis reduction; Lattice reduction; LLL algorithm; Most significant bit; Partial key exposure; RSA; RSA moduli; Artificial intelligence; Network security
dc.title (題名) Cryptanalysis of exhaustive search on attacking RSA
dc.type (資料類型) conferenceen
dc.identifier.doi (DOI) 10.1007/978-3-642-34601-9_28
dc.doi.uri (DOI) http://dx.doi.org/10.1007/978-3-642-34601-9_28