Name
Abstract | ||
|---|---|---|
Let N = pq be an RSA modulus, i.e. the product of two large unknown primes of equal bit-size. In the X 9.31-1997 standard for public key cryptography, Section 4.1.2, there are a number of recommendations for the generation of the primes of an RSA modulus. Among them, the ratio of the primes shall not be close to the ratio of small integers. In this paper, we show that if the public exponent e satisfies an equation eX *** (N *** (ap + bq ))Y = Z with suitably small integers X , Y , Z , where $\frac{a}{b}$ is an unknown convergent of the continued fraction expansion of $\frac{q}{p}$, then N can be factored efficiently. In addition, we show that the number of such exponents is at least $N^{\frac{3}{4}-\varepsilon}$ where *** is arbitrarily small for large N . |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-02384-2_7 | AFRICACRYPT |
Keywords | Field | DocType |
continued fraction expansion,unknown convergent,equal bit-size,large unknown prime,public key cryptography,large n,suitably small integers x,public exponent e,rsa modulus,small integer,satisfiability,continued fraction,factorization,cryptanalysis | Integer,Discrete mathematics,Continued fraction,Exponent,Cryptanalysis,Factorization,Public-key cryptography,Mathematics | Conference |
Volume | ISSN | Citations |
5580 | 0302-9743 | 1 |
PageRank | References | Authors |
0.36 | 9 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Abderrahmane Nitaj | 1 | 72 | 15.00 |