Factorization and Malleability of RSA Moduli, and Counting Points on Elliptic Curves Modulo N

Luis V. Dieulefait and Jorge Urroz
Additional contact information
Luis V. Dieulefait: Departament de Matemàtiques i Informàtica, Universitat de Barcelona, Gran Via de les Corts Catalanes 585, 08007 Barcelona, Spain
Jorge Urroz: Departamento de Matemáticas, Universitat Politécnica Catalunya, Edificio C3—Campus Nord UPC, Carrer de Jordi Girona 1-3, 08034 Barcelona, Spain

Mathematics, 2020, vol. 8, issue 12, 1-10

Abstract: In this paper we address two different problems related with the factorization of an RSA (Rivest–Shamir–Adleman cryptosystem) modulus N . First we show that factoring is equivalent, in deterministic polynomial time, to counting points on a pair of twisted Elliptic curves modulo N . The second problem is related with malleability. This notion was introduced in 2006 by Pailler and Villar, and deals with the question of whether or not the factorization of a given number N becomes substantially easier when knowing the factorization of another one N ′ relatively prime to N . Despite the efforts done up to now, a complete answer to this question was unknown. Here we settle the problem affirmatively. To construct a particular N ′ that helps the factorization of N , we use the number of points of a single elliptic curve modulo N . Coppersmith’s algorithm allows us to go from the factors of N ′ to the factors of N in polynomial time.

Keywords: factorization; malleability; elliptic curves; coppersmith algorithm (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/12/2126/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/12/2126/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:12:p:2126-:d:452249

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().