Cryptanalysis of short exponent RSA with primes sharing least significant bits

Hung Min Sun; Mu En Wu; Ron Steinfeld; Jian Guo; Huaxiong Wang

doi:10.1007/978-3-540-89641-8_4

Cryptanalysis of short exponent RSA with primes sharing least significant bits

Hung Min Sun^*, Mu En Wu, Ron Steinfeld, Jian Guo, Huaxiong Wang

^*Corresponding author for this work

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

16 Citations (Scopus)

Abstract

LSBS-RSA denotes an RSA system with modulus primes, p and q, sharing a large number of least significant bits. In ISC 2007, Zhao and Qi analyzed the security of short exponent LSBS-RSA. They claimed that short exponent LSBS-RSA is much more vulnerable to the lattice attack than the standard RSA. In this paper, we further raise the security boundary of the Zhao-Qi attack by considering another polynomial. Our improvemet supports the result of analogue Fermat factoring on LSBS-RSA, which claims that p and q cannot share more than least significant bits, where n is the bit-length of pq. In conclusion, it is a trade-off between the number of sharing bits and the security level in LSBS-RSA. One should be more careful when using LSBS-RSA with short exponents.

Original language	English
Title of host publication	Cryptology and Network Security - 7th International Conference, CANS 2008, Proceedings
Editors	Matthew K. Franklin, Lucas Chi Kwong Hui, Duncan S. Wong
Place of Publication	Berlin
Publisher	Springer, Springer Nature
Pages	49-63
Number of pages	15
Volume	5339 LNCS
ISBN (Print)	3540896406, 9783540896401
DOIs	https://doi.org/10.1007/978-3-540-89641-8_4
Publication status	Published - 2008
Event	7th International Conference on Cryptology and Network Security, CANS 2008 - Hong-Kong, China Duration: 2 Dec 2008 → 4 Dec 2008

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5339 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Other

Other	7th International Conference on Cryptology and Network Security, CANS 2008
Country/Territory	China
City	Hong-Kong
Period	2/12/08 → 4/12/08

Access to Document

10.1007/978-3-540-89641-8_4

Cite this

Sun, H. M., Wu, M. E., Steinfeld, R., Guo, J., & Wang, H. (2008). Cryptanalysis of short exponent RSA with primes sharing least significant bits. In M. K. Franklin, L. C. K. Hui, & D. S. Wong (Eds.), Cryptology and Network Security - 7th International Conference, CANS 2008, Proceedings (Vol. 5339 LNCS, pp. 49-63). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5339 LNCS). Springer, Springer Nature. https://doi.org/10.1007/978-3-540-89641-8_4

Sun, Hung Min ; Wu, Mu En ; Steinfeld, Ron et al. / Cryptanalysis of short exponent RSA with primes sharing least significant bits. Cryptology and Network Security - 7th International Conference, CANS 2008, Proceedings. editor / Matthew K. Franklin ; Lucas Chi Kwong Hui ; Duncan S. Wong. Vol. 5339 LNCS Berlin : Springer, Springer Nature, 2008. pp. 49-63 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{81860e2e96924e1bb11b0651fb228937,

title = "Cryptanalysis of short exponent RSA with primes sharing least significant bits",

abstract = "LSBS-RSA denotes an RSA system with modulus primes, p and q, sharing a large number of least significant bits. In ISC 2007, Zhao and Qi analyzed the security of short exponent LSBS-RSA. They claimed that short exponent LSBS-RSA is much more vulnerable to the lattice attack than the standard RSA. In this paper, we further raise the security boundary of the Zhao-Qi attack by considering another polynomial. Our improvemet supports the result of analogue Fermat factoring on LSBS-RSA, which claims that p and q cannot share more than least significant bits, where n is the bit-length of pq. In conclusion, it is a trade-off between the number of sharing bits and the security level in LSBS-RSA. One should be more careful when using LSBS-RSA with short exponents.",

author = "Sun, {Hung Min} and Wu, {Mu En} and Ron Steinfeld and Jian Guo and Huaxiong Wang",

year = "2008",

doi = "10.1007/978-3-540-89641-8_4",

language = "English",

isbn = "3540896406",

volume = "5339 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer, Springer Nature",

pages = "49--63",

editor = "Franklin, {Matthew K.} and Hui, {Lucas Chi Kwong} and Wong, {Duncan S.}",

booktitle = "Cryptology and Network Security - 7th International Conference, CANS 2008, Proceedings",

address = "United States",

note = "7th International Conference on Cryptology and Network Security, CANS 2008 ; Conference date: 02-12-2008 Through 04-12-2008",

}

Sun, HM, Wu, ME, Steinfeld, R, Guo, J & Wang, H 2008, Cryptanalysis of short exponent RSA with primes sharing least significant bits. in MK Franklin, LCK Hui & DS Wong (eds), Cryptology and Network Security - 7th International Conference, CANS 2008, Proceedings. vol. 5339 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5339 LNCS, Springer, Springer Nature, Berlin, pp. 49-63, 7th International Conference on Cryptology and Network Security, CANS 2008, Hong-Kong, China, 2/12/08. https://doi.org/10.1007/978-3-540-89641-8_4

Cryptanalysis of short exponent RSA with primes sharing least significant bits. / Sun, Hung Min; Wu, Mu En; Steinfeld, Ron et al.
Cryptology and Network Security - 7th International Conference, CANS 2008, Proceedings. ed. / Matthew K. Franklin; Lucas Chi Kwong Hui; Duncan S. Wong. Vol. 5339 LNCS Berlin: Springer, Springer Nature, 2008. p. 49-63 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5339 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Cryptanalysis of short exponent RSA with primes sharing least significant bits

AU - Sun, Hung Min

AU - Wu, Mu En

AU - Steinfeld, Ron

AU - Guo, Jian

AU - Wang, Huaxiong

PY - 2008

Y1 - 2008

N2 - LSBS-RSA denotes an RSA system with modulus primes, p and q, sharing a large number of least significant bits. In ISC 2007, Zhao and Qi analyzed the security of short exponent LSBS-RSA. They claimed that short exponent LSBS-RSA is much more vulnerable to the lattice attack than the standard RSA. In this paper, we further raise the security boundary of the Zhao-Qi attack by considering another polynomial. Our improvemet supports the result of analogue Fermat factoring on LSBS-RSA, which claims that p and q cannot share more than least significant bits, where n is the bit-length of pq. In conclusion, it is a trade-off between the number of sharing bits and the security level in LSBS-RSA. One should be more careful when using LSBS-RSA with short exponents.

AB - LSBS-RSA denotes an RSA system with modulus primes, p and q, sharing a large number of least significant bits. In ISC 2007, Zhao and Qi analyzed the security of short exponent LSBS-RSA. They claimed that short exponent LSBS-RSA is much more vulnerable to the lattice attack than the standard RSA. In this paper, we further raise the security boundary of the Zhao-Qi attack by considering another polynomial. Our improvemet supports the result of analogue Fermat factoring on LSBS-RSA, which claims that p and q cannot share more than least significant bits, where n is the bit-length of pq. In conclusion, it is a trade-off between the number of sharing bits and the security level in LSBS-RSA. One should be more careful when using LSBS-RSA with short exponents.

UR - http://www.scopus.com/inward/record.url?scp=58449115732&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-89641-8_4

DO - 10.1007/978-3-540-89641-8_4

M3 - Conference proceeding contribution

AN - SCOPUS:58449115732

SN - 3540896406

SN - 9783540896401

VL - 5339 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 49

EP - 63

BT - Cryptology and Network Security - 7th International Conference, CANS 2008, Proceedings

A2 - Franklin, Matthew K.

A2 - Hui, Lucas Chi Kwong

A2 - Wong, Duncan S.

PB - Springer, Springer Nature

CY - Berlin

T2 - 7th International Conference on Cryptology and Network Security, CANS 2008

Y2 - 2 December 2008 through 4 December 2008

ER -

Sun HM, Wu ME, Steinfeld R, Guo J, Wang H. Cryptanalysis of short exponent RSA with primes sharing least significant bits. In Franklin MK, Hui LCK, Wong DS, editors, Cryptology and Network Security - 7th International Conference, CANS 2008, Proceedings. Vol. 5339 LNCS. Berlin: Springer, Springer Nature. 2008. p. 49-63. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-89641-8_4

Cryptanalysis of short exponent RSA with primes sharing least significant bits

Abstract

Publication series

Other

Access to Document

Other files and links

Fingerprint

Cite this