Copy

Naoyuki SHINOHARA, Tetsuya IZU, Noboru KUNIHIRO, "Small Secret CRT-Exponent Attacks on Takagi's RSA" in IEICE TRANSACTIONS on Fundamentals,
vol. E94-A, no. 1, pp. 19-27, January 2011, doi: 10.1587/transfun.E94.A.19.

Abstract: CRT-RSA is a variant of RSA, which uses integers *d*_{p} = *d* mod (*p*-1) and *d*_{q} = *d* mod (*q*-1) (CRT-exponents), where *d*, *p*, *q* are the secret keys of RSA. May proposed a method to obtain the secret key in polynomial time if a CRT-exponent is small, moreover Bleichenbacher and May improved this method. On the other hand, Takagi's RSA is a variant of CRT-RSA, whose public key *N* is of the form *p*^{r}q for a given positive integer *r*. In this paper, we extend the May's method and the Bleichenbacher-May's method to Takagi's RSA, and we show that we obtain *p* in polynomial time if by the extended May's method, and if by the extended Bleichenbacher-May's method, when *d*_{q} is arbitrary small. If *r*=1, these upper bounds conform to May's and Bleichenbacher-May's results respectively. Moreover, we also show that the upper bound of *p*^{r} increase with an increase in *r*. Since these attacks are heuristic algorithms, we provide several experiments which show that we can obtain the secret key in practice.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E94.A.19/_p

Copy

@ARTICLE{e94-a_1_19,

author={Naoyuki SHINOHARA, Tetsuya IZU, Noboru KUNIHIRO, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Small Secret CRT-Exponent Attacks on Takagi's RSA},

year={2011},

volume={E94-A},

number={1},

pages={19-27},

abstract={CRT-RSA is a variant of RSA, which uses integers *d*_{p} = *d* mod (*p*-1) and *d*_{q} = *d* mod (*q*-1) (CRT-exponents), where *d*, *p*, *q* are the secret keys of RSA. May proposed a method to obtain the secret key in polynomial time if a CRT-exponent is small, moreover Bleichenbacher and May improved this method. On the other hand, Takagi's RSA is a variant of CRT-RSA, whose public key *N* is of the form *p*^{r}q for a given positive integer *r*. In this paper, we extend the May's method and the Bleichenbacher-May's method to Takagi's RSA, and we show that we obtain *p* in polynomial time if by the extended May's method, and if by the extended Bleichenbacher-May's method, when *d*_{q} is arbitrary small. If *r*=1, these upper bounds conform to May's and Bleichenbacher-May's results respectively. Moreover, we also show that the upper bound of *p*^{r} increase with an increase in *r*. Since these attacks are heuristic algorithms, we provide several experiments which show that we can obtain the secret key in practice.},

keywords={},

doi={10.1587/transfun.E94.A.19},

ISSN={1745-1337},

month={January},}

Copy

TY - JOUR

TI - Small Secret CRT-Exponent Attacks on Takagi's RSA

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 19

EP - 27

AU - Naoyuki SHINOHARA

AU - Tetsuya IZU

AU - Noboru KUNIHIRO

PY - 2011

DO - 10.1587/transfun.E94.A.19

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E94-A

IS - 1

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - January 2011

AB - CRT-RSA is a variant of RSA, which uses integers *d*_{p} = *d* mod (*p*-1) and *d*_{q} = *d* mod (*q*-1) (CRT-exponents), where *d*, *p*, *q* are the secret keys of RSA. May proposed a method to obtain the secret key in polynomial time if a CRT-exponent is small, moreover Bleichenbacher and May improved this method. On the other hand, Takagi's RSA is a variant of CRT-RSA, whose public key *N* is of the form *p*^{r}q for a given positive integer *r*. In this paper, we extend the May's method and the Bleichenbacher-May's method to Takagi's RSA, and we show that we obtain *p* in polynomial time if by the extended May's method, and if by the extended Bleichenbacher-May's method, when *d*_{q} is arbitrary small. If *r*=1, these upper bounds conform to May's and Bleichenbacher-May's results respectively. Moreover, we also show that the upper bound of *p*^{r} increase with an increase in *r*. Since these attacks are heuristic algorithms, we provide several experiments which show that we can obtain the secret key in practice.

ER -