Re: [Uta] updated I-Ds

[Watson Ladd <[e-mail]>]

On Feb 25, 2014 12:55 PM, "Daniel Kahn Gillmor" <[e-mail]>
wrote:
>
> On 02/13/2014 02:51 PM, Watson Ladd wrote:
> > Currently a 530 bit prime can be done effectively with 3 core years of
sieving.
>
> do you mean "a 530 bit composite can be factored…" here?

No, I mean that a discrete logarithm in G_m modulo a 530 bit prime can be
computed in 3 core years of work.

This is different from RSA, but closely related. I looked up the record on
Wikipedia.
>
> the CADO-NFS team reports roughly 6 core-years for RSA-155, a 512-bit
> number:
>
>  http://cado-nfs.gforge.inria.fr/#feat
>
> so that's in the same ballpark.  But:
>
> > This implies that a 1024 bit prime will take approximately 10.5 core
years,
> > and 2048 bits 15 core years.
>
> These are alarmingly short estimates, given the parallelizability of GNFS.
>
> Recent work (also with CADO-NFS):
>
>   http://maths-people.anu.edu.au/~bai/paper/rsa704.pdf
>
> suggests 12 core years for polynomial selection for RSA-704, and 500 CPU
> years for sieving.
>
> Can you explain your estimate of 10.5 core years for RSA-1024 or 15 core
> years for RSA-2048?

I redid the arithmetic and it looks like I was off/made a typo. Take
L(n)=c*e^{(log n)^a*(loglog n)^(1-a)} with a 1/3, figure out the constant,
and plug in the lengths.

Redoing it I get 8000 core years for DH modulo a 1024 bit prime and about 4
billion core years for 2048 bit prime.

The point is DHE with the 1024 bit prime is much weaker than other
algorithms being considered.
Sincerely,
Watson Ladd
>
> Regards,
>
>         --dkg
>