A note on the analysis of Herrmann-May lattices for small exponent RSA

被引：0

作者：

Kalam, Abul ^{[1
]}

Karmakar, Sudeshna ^{[1
]}

Sarkar, Santanu ^{[1
]}

机构：

[1] Indian Inst Technol Madras, Dept Math, Chennai 600036, Tamil Nadu, India

来源：

SCIENTIFIC REPORTS | 2025年 / 15卷 / 01期

关键词：

Lattice basis reduction; LLL; Linearization; Small exponent RSA; Herrmann-May lattice; CRYPTANALYSIS; LINEARIZATION; BOUNDS;

D O I：

10.1038/s41598-025-10019-9

中图分类号：

O [数理科学和化学]; P [天文学、地球科学]; Q [生物科学]; N [自然科学总论];

学科分类号：

07 ; 0710 ; 09 ;

摘要：

At PKC 2010, Herrmann and May introduced a lattice-based method using unravelled linearization to achieve the theoretical bound d < N1-1/root 2 for small RSA exponents. In this paper, we identify an error in their asymptotic analysis, revising the bound to d < N-0.292256, which is strictly lower than the Boneh-Durfee bound N1-1/root 2 . This error persisted for over 15 years. We also refine the Herrmann-May lattice construction, achieving the Boneh-Durfee bound while significantly reducing the Herrmann-May lattice's dimension.

引用

页数：9

共 12 条

[1] Cryptanalysis of RSA with private key d less than N0.292 [J].

Boneh, D ;

Durfee, G .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2000, 46 (04) :1339-1349

[2] Small solutions to polynomial equations, and low exponent RSA vulnerabilities [J].

Coppersmith, D .

JOURNAL OF CRYPTOLOGY, 1997, 10 (04) :233-260

[3] A Note on the Bivariate Coppersmith Theorem [J].

Coron, Jean-Sebastien ;

Kirichenko, Alexey ;

Tibouchi, Mehdi .

JOURNAL OF CRYPTOLOGY, 2013, 26 (02) :246-250

[4]

Herrmann M, 2010, LECT NOTES COMPUT SC, V6056, P53

[5]

Herrmann M, 2009, LECT NOTES COMPUT SC, V5912, P487, DOI 10.1007/978-3-642-10366-7_29

[6] An Information Fusion approach based on prime numbers coming from RSA algorithm and Fractals for secure coding [J].

Iovane, G. ;

Amorosia, A. ;

Benedetto, E. ;

Lamponi, G. .

JOURNAL OF DISCRETE MATHEMATICAL SCIENCES & CRYPTOGRAPHY, 2015, 18 (05) :455-479

[7] A Modified Technique for Reliable Image Encryption Method using Merkle-Hellman Cryptosystem and Rsa Algorithm [J].

Lokeshwari, G. ;

Susarla, Sreevidya ;

Kumar, S. Udaya .

JOURNAL OF DISCRETE MATHEMATICAL SCIENCES & CRYPTOGRAPHY, 2015, 18 (03) :293-300

[8]

RIVEST RL, 1978, COMMUN ACM, V21, P120, DOI [10.1145/359340.359342, 10.1145/357980.358017]

[9] Fast Practical Lattice Reduction Through Iterated Compression [J].

Ryan, Keegan ;

Heninger, Nadia .

ADVANCES IN CRYPTOLOGY - CRYPTO 2023, PT III, 2023, 14083 :3-36

[10] Partial key exposure attacks on RSA: Achieving the Boneh-Durfee bound [J].

Takayasu, Atsushi ;

Kunihiro, Noboru .

THEORETICAL COMPUTER SCIENCE, 2019, 761 :51-77

← 1 2 →