The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Pour RSA, May a montré une équivalence temporelle polynomiale déterministe du calcul d à l'affacturage N(=pq). D'autre part, Takagi a montré une variante du RSA telle que l'algorithme de décryptage est plus rapide que le RSA standard, où N=prq tout en ed=1 module(p-1)(q-1). Dans cet article, nous montrons qu’une équivalence temporelle polynomiale déterministe est également valable dans cette variante. La matrice des coefficients T auquel l'algorithme LLL est appliqué n'est plus triangulaire inférieur, et nous développons donc une nouvelle technique pour surmonter ce problème.
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.
Copier
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
Copier
@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},}
Copier
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 -