IEICE TRANSACTIONS on Fundamentals
Deterministic Polynomial Time Equivalence between Factoring and Key-Recovery Attack on Takagi's RSA
Summary :
For RSA, May showed a deterministic polynomial time equivalence of computing d to factoring N(=pq). On the other hand, Takagi showed a variant of RSA such that the decryption algorithm is faster than the standard RSA, where N=prq while ed=1 mod(p-1)(q-1). In this paper, we show that a deterministic polynomial time equivalence also holds in this variant. The coefficient matrix T to which LLL algorithm is applied is no longer lower triangular, and hence we develop a new technique to overcome this problem.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E91-A No.9 pp.2356-2364
- Publication Date
- 2008/09/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1093/ietfec/e91-a.9.2356
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Noboru KUNIHIRO, Kaoru KUROSAWA, "Deterministic Polynomial Time Equivalence between Factoring and Key-Recovery Attack on Takagi's RSA" in IEICE TRANSACTIONS on Fundamentals,
vol. E91-A, no. 9, pp. 2356-2364, September 2008, doi: 10.1093/ietfec/e91-a.9.2356.
Abstract: For RSA, May showed a deterministic polynomial time equivalence of computing d to factoring N(=pq). On the other hand, Takagi showed a variant of RSA such that the decryption algorithm is faster than the standard RSA, where N=prq while ed=1 mod(p-1)(q-1). In this paper, we show that a deterministic polynomial time equivalence also holds in this variant. The coefficient matrix T to which LLL algorithm is applied is no longer lower triangular, and hence we develop a new technique to overcome this problem.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e91-a.9.2356/_p
Copy
@ARTICLE{e91-a_9_2356,
author={Noboru KUNIHIRO, Kaoru KUROSAWA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Deterministic Polynomial Time Equivalence between Factoring and Key-Recovery Attack on Takagi's RSA},
year={2008},
volume={E91-A},
number={9},
pages={2356-2364},
abstract={For RSA, May showed a deterministic polynomial time equivalence of computing d to factoring N(=pq). On the other hand, Takagi showed a variant of RSA such that the decryption algorithm is faster than the standard RSA, where N=prq while ed=1 mod(p-1)(q-1). In this paper, we show that a deterministic polynomial time equivalence also holds in this variant. The coefficient matrix T to which LLL algorithm is applied is no longer lower triangular, and hence we develop a new technique to overcome this problem.},
keywords={},
doi={10.1093/ietfec/e91-a.9.2356},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - Deterministic Polynomial Time Equivalence between Factoring and Key-Recovery Attack on Takagi's RSA
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2356
EP - 2364
AU - Noboru KUNIHIRO
AU - Kaoru KUROSAWA
PY - 2008
DO - 10.1093/ietfec/e91-a.9.2356
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E91-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2008
AB - For RSA, May showed a deterministic polynomial time equivalence of computing d to factoring N(=pq). On the other hand, Takagi showed a variant of RSA such that the decryption algorithm is faster than the standard RSA, where N=prq while ed=1 mod(p-1)(q-1). In this paper, we show that a deterministic polynomial time equivalence also holds in this variant. The coefficient matrix T to which LLL algorithm is applied is no longer lower triangular, and hence we develop a new technique to overcome this problem.
ER -
English
