Cryptanalysis of large RSA exponent by using the LLL algorithm

Chien Yuan Chen; Cheng-Yuan Ku; David C. Yen

doi:10.1016/j.amc.2004.10.082

Cryptanalysis of large RSA exponent by using the LLL algorithm

Chien Yuan Chen, Cheng-Yuan Ku^*, David C. Yen

^*Corresponding author for this work

Institute of Information Management

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

The study of paper "Cryptanalysis of RSA with Private Key d less than N^0.292' [IEEE Trans. Information Theory, 46 (2000) 1339], which Boneh and Durfee published in IEEE Transactions on Information Theory in July 2000, supported that when d < N^0.292, the RSA system can be cracked by using the LLL algorithm. In this paper, we find ways to utilize the LLL algorithm to break the RSA system even when the value of d is large. According to the proposed cryptanalysis, if d satisfies |λ - d| < N ^0.25, the RSA system will be possible to be resolved computationally.

Original language	English
Pages (from-to)	516-525
Number of pages	10
Journal	Applied Mathematics and Computation
Volume	169
Issue number	1
DOIs	https://doi.org/10.1016/j.amc.2004.10.082
State	Published - 1 Oct 2005

Keywords

Cryptanalysis
LLL algorithm
Public key encryption
RSA exponent
RSA system

Access to Document

10.1016/j.amc.2004.10.082

Cite this

@article{a82b1fd1bc6a45208f66c5142d45e9ce,

title = "Cryptanalysis of large RSA exponent by using the LLL algorithm",

abstract = "The study of paper {"}Cryptanalysis of RSA with Private Key d less than N0.292' [IEEE Trans. Information Theory, 46 (2000) 1339], which Boneh and Durfee published in IEEE Transactions on Information Theory in July 2000, supported that when d < N0.292, the RSA system can be cracked by using the LLL algorithm. In this paper, we find ways to utilize the LLL algorithm to break the RSA system even when the value of d is large. According to the proposed cryptanalysis, if d satisfies |λ - d| < N 0.25, the RSA system will be possible to be resolved computationally.",

keywords = "Cryptanalysis, LLL algorithm, Public key encryption, RSA exponent, RSA system",

author = "Chen, {Chien Yuan} and Cheng-Yuan Ku and Yen, {David C.}",

year = "2005",

month = oct,

day = "1",

doi = "10.1016/j.amc.2004.10.082",

language = "English",

volume = "169",

pages = "516--525",

journal = "Applied Mathematics and Computation",

issn = "0096-3003",

publisher = "Elsevier Inc.",

number = "1",

}

TY - JOUR

T1 - Cryptanalysis of large RSA exponent by using the LLL algorithm

AU - Chen, Chien Yuan

AU - Ku, Cheng-Yuan

AU - Yen, David C.

PY - 2005/10/1

Y1 - 2005/10/1

N2 - The study of paper "Cryptanalysis of RSA with Private Key d less than N0.292' [IEEE Trans. Information Theory, 46 (2000) 1339], which Boneh and Durfee published in IEEE Transactions on Information Theory in July 2000, supported that when d < N0.292, the RSA system can be cracked by using the LLL algorithm. In this paper, we find ways to utilize the LLL algorithm to break the RSA system even when the value of d is large. According to the proposed cryptanalysis, if d satisfies |λ - d| < N 0.25, the RSA system will be possible to be resolved computationally.

AB - The study of paper "Cryptanalysis of RSA with Private Key d less than N0.292' [IEEE Trans. Information Theory, 46 (2000) 1339], which Boneh and Durfee published in IEEE Transactions on Information Theory in July 2000, supported that when d < N0.292, the RSA system can be cracked by using the LLL algorithm. In this paper, we find ways to utilize the LLL algorithm to break the RSA system even when the value of d is large. According to the proposed cryptanalysis, if d satisfies |λ - d| < N 0.25, the RSA system will be possible to be resolved computationally.

KW - Cryptanalysis

KW - LLL algorithm

KW - Public key encryption

KW - RSA exponent

KW - RSA system

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

U2 - 10.1016/j.amc.2004.10.082

DO - 10.1016/j.amc.2004.10.082

M3 - Article

AN - SCOPUS:27144543667

SN - 0096-3003

VL - 169

SP - 516

EP - 525

JO - Applied Mathematics and Computation

JF - Applied Mathematics and Computation

IS - 1

ER -

Cryptanalysis of large RSA exponent by using the LLL algorithm

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this