The better bound of private key in RSA with unbalanced primes

Hyun Soo Hong; Ho Kyu Lee; Hyang Sook Lee; Hee Jung Lee

doi:10.1016/S0096-3003(02)00198-4

The better bound of private key in RSA with unbalanced primes

Hyun Soo Hong, Ho Kyu Lee, Hyang Sook Lee, Hee Jung Lee

Department of Mathematics

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

6 Scopus citations

Abstract

At Asiacrypt '99, Sun, Yang and Laih proposed three different schemes of RSA cryptosystem to avoid all known attacks including Boneh-Durfee attack. One year after, Durfee and Nguyen attacked two out of these three schemes based on Coppersmith's lattice technique for finding small roots to trivariate modular polynomial equations. The bounds of private key for the first and third schemes were much improved, but the bound of the second scheme was not good enough. Our result improves Durfee and Nguyen's bound of the private exponent d from N^0.483 to N^0.486 for the second scheme. This implies the system is insecure if the private exponent d<N^0.486.

Original language	English
Pages (from-to)	351-362
Number of pages	12
Journal	Applied Mathematics and Computation
Volume	139
Issue number	2-3
DOIs	https://doi.org/10.1016/S0096-3003(02)00198-4
State	Published - 15 Jul 2003

Keywords

Coppersmith's technique
Geometrically progressive matrices
Lattice reduction
Multivariate modular equations
RSA attack

Access to Document

10.1016/S0096-3003(02)00198-4

Cite this

@article{d5e2bd5425a14aee8a03bee4e295e772,

title = "The better bound of private key in RSA with unbalanced primes",

abstract = "At Asiacrypt '99, Sun, Yang and Laih proposed three different schemes of RSA cryptosystem to avoid all known attacks including Boneh-Durfee attack. One year after, Durfee and Nguyen attacked two out of these three schemes based on Coppersmith's lattice technique for finding small roots to trivariate modular polynomial equations. The bounds of private key for the first and third schemes were much improved, but the bound of the second scheme was not good enough. Our result improves Durfee and Nguyen's bound of the private exponent d from N0.483 to N0.486 for the second scheme. This implies the system is insecure if the private exponent d0.486.",

keywords = "Coppersmith's technique, Geometrically progressive matrices, Lattice reduction, Multivariate modular equations, RSA attack",

author = "Hong, {Hyun Soo} and Lee, {Ho Kyu} and Lee, {Hyang Sook} and Lee, {Hee Jung}",

year = "2003",

month = jul,

day = "15",

doi = "10.1016/S0096-3003(02)00198-4",

language = "English",

volume = "139",

pages = "351--362",

journal = "Applied Mathematics and Computation",

issn = "0096-3003",

publisher = "Elsevier Inc.",

number = "2-3",

}

TY - JOUR

T1 - The better bound of private key in RSA with unbalanced primes

AU - Hong, Hyun Soo

AU - Lee, Ho Kyu

AU - Lee, Hyang Sook

AU - Lee, Hee Jung

PY - 2003/7/15

Y1 - 2003/7/15

N2 - At Asiacrypt '99, Sun, Yang and Laih proposed three different schemes of RSA cryptosystem to avoid all known attacks including Boneh-Durfee attack. One year after, Durfee and Nguyen attacked two out of these three schemes based on Coppersmith's lattice technique for finding small roots to trivariate modular polynomial equations. The bounds of private key for the first and third schemes were much improved, but the bound of the second scheme was not good enough. Our result improves Durfee and Nguyen's bound of the private exponent d from N0.483 to N0.486 for the second scheme. This implies the system is insecure if the private exponent d0.486.

AB - At Asiacrypt '99, Sun, Yang and Laih proposed three different schemes of RSA cryptosystem to avoid all known attacks including Boneh-Durfee attack. One year after, Durfee and Nguyen attacked two out of these three schemes based on Coppersmith's lattice technique for finding small roots to trivariate modular polynomial equations. The bounds of private key for the first and third schemes were much improved, but the bound of the second scheme was not good enough. Our result improves Durfee and Nguyen's bound of the private exponent d from N0.483 to N0.486 for the second scheme. This implies the system is insecure if the private exponent d0.486.

KW - Coppersmith's technique

KW - Geometrically progressive matrices

KW - Lattice reduction

KW - Multivariate modular equations

KW - RSA attack

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

U2 - 10.1016/S0096-3003(02)00198-4

DO - 10.1016/S0096-3003(02)00198-4

M3 - Article

AN - SCOPUS:0037448163

SN - 0096-3003

VL - 139

SP - 351

EP - 362

JO - Applied Mathematics and Computation

JF - Applied Mathematics and Computation

IS - 2-3

ER -

The better bound of private key in RSA with unbalanced primes

Abstract

Keywords

Access to Document

Fingerprint

Cite this