Deterministic Polynomial Time Equivalence between Factoring and Key-Recovery Attack on Takagi's RSA
スポンサーリンク
概要
- 論文の詳細を見る
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.
- 2008-09-01
著者
-
KUNIHIRO Noboru
University of Electro-Communica-tions
-
KUROSAWA Kaoru
Ibaraki University
-
Kurosawa Kaoru
Ibaraki Univ. Hitachi‐shi Jpn
関連論文
- New RSA-Based (Selectively) Convertible Undeniable Signature Schemes
- Extended Password Recovery Attacks against APOP, SIP, and Digest Authentication
- Extension of Secret Handshake Protocols with Multiple Groups in Monotone Condition
- Cryptanalysis of Two MD5-Based Authentication Protocols : APOP and NMAC
- Extended Password Recovery Attacks against APOP, SIP, and Digest Authentication
- New Message Differences for Collision Attacks on MD4 and MD5
- Improved Collision Attacks on MD4 and MD5(Hash Functions,Cryptography and Information Security)
- Deterministic Polynomial Time Equivalence between Factoring and Key-Recovery Attack on Takagi's RSA
- New RSA-Based (Selectively) Convertible Undeniable Signature Schemes
- Tag-KEM from Set Partial Domain One-Way Permutations
- Small Secret Key Attack on a Takagi's Variant of RSA
- Security of the Five-Round KASUMI Type Permutation
- Improved Collision Search for Hash Functions : New Advanced Message Modification
- Small Secret CRT-Exponent Attacks on Takagi's RSA
- Near-Collision Attacks on MD4 : Applied to MD4-Based Protocols
- Between Hashed DH and Computational DH : Compact Encryption from Weaker Assumption
- Exact Analyses of Computational Time for Factoring in Quantum Computers(Public Key Cryptography)(Cryptography and Information Security)
- How to Construct Super-Pseudorandom Permutations with Short Keys(Symmetric Cryptography,Cryptography and Information Security)
- An Electronic Voting Protocol Preserving Voter's Privacy(Applications of Information Security Techniques)
- Solving Generalized Small Inverse Problems
- How to Shorten a Ciphertext of Reproducible Key Encapsulation Mechanisms in the Random Oracle Model
- Undeniable and Unpretendable Signatures