Factorization and malleability of RSA modules, and counting points on\n elliptic curves modulo N

2019/11/25 by Luís Dieulefait, Dieulefait, Luis, Jorge Jiménez Urroz +1
Computer Science · Mathematics · #Algebraic Geometry and Number Theory #Coding theory and cryptography #Cryptography and Data Security #Cryptography and Residue Arithmetic #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Number Theory (math.NT)

paper · pdf · doi:10.48550/arxiv.1911.11004

openalex publication_date 2019/11/25 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28

Abstract

In this paper we address two different problems related with the\nfactorization of an RSA module N. First we can show that factoring is\nequivalent in deterministic polynomial time to counting points on a pair of\ntwisted Elliptic curves modulo N. Also we settle the malleability of factoring\nan RSA module, as described in [9], using the number of points of a single\nelliptic curve modulo N, and Coppersmith's algorithm.\n

Citations

• Small primitive roots and malleability of RSA moduli
• A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks

Related

• Factoring Numbers with elliptic curves
• Decomposition of RSA modulus applying even order elliptic curves
• On oracle factoring of integers
• Small primitive roots and malleability of RSA moduli
• ECM And The Elliott-Halberstam Conjecture For Quadratic Fields