Re: Factoring one of many RSA moduli
- From: pubkeybreaker <pubkeybreaker@xxxxxxx>
- Date: Mon, 23 Feb 2009 06:50:26 -0800 (PST)
On Feb 22, 4:08 pm, Francois Grieu <fgr...@xxxxxxxxx> wrote:
Assume we have m RSA moduli nj of b-bit, generated in
such a way that each nj has unknown factorisation into
pj*qj, where pj and qj are random primes with
2^(b/2-1/2) < pj < qj < 2^(b/2) [1]
We may assume 512 <= b <= 2048 and m>1000.
Is there an algorithm that can be expected to factor at
least one of the nj with less work than factoring n0
using GNFS?
How does the expected effort scale with m ?
TIA,
Francois Grieu
Note [1]: Established RSA key generation standard ANSI X9.31
do this, with more criteria on the factors.
[Reposted with typo fixes]
It is possible to factor two numbers via NFS in less time
than it does to factor each one separately. But the costs in memory
go way up.
Suppose you want to factor N1 and N2. Each one is factored
using two polynomials: f1(x) and g1(x) for the 1st number, and
f2(x) and g2(x) for the second.
It is possible, however, by modifying g1 and g2 to allow f1 to
equal f2. In other words, we let the rational side polynomial be the
same for each.
Now instead of having to sieve over 4 different polynomials, looking
for
smooth norms, we only have to sieve 3.
.
- Follow-Ups:
- Re: Factoring one of many RSA moduli
- From: Francois Grieu
- Re: Factoring one of many RSA moduli
- References:
- Factoring one of many RSA moduli
- From: Francois Grieu
- Factoring one of many RSA moduli
- Prev by Date: Re: Primitive polynomials
- Next by Date: Re: Factoring one of many RSA moduli
- Previous by thread: Re: Factoring one of many RSA moduli
- Next by thread: Re: Factoring one of many RSA moduli
- Index(es):
Relevant Pages
|
