Hi Panos:
There seems to be some misunderstanding regarding computational
complexities here (here: Special Number field Sieve (SNFS) vs. General
Number Field Sieve (NFS)).
With the General Number Field Sieve, the complexity is conjectured to be
LN[c,a], where
a= 1/3 and c = (64/9)^{1/3}+o(1) and where
LN[c,a]:=exp(c (log N)^a (log(log(N))^{1-a}).
With the Special Number Field Sieve, the conjectured complexity is
LN[c,a], where
a= 1/3 and c = (32/9)^{1/3}+o(1).
Note that if one ignores the o(1) term, then the asymptotic running time
using the GNFS with N is about the same time required with the SNFS and
N^2.
The paper you quoted exploits some potentially hidden structure in the
method for producing N that results in being able to use the SNFS rather
than the GNFS (thereby, explaining the relatively low running time). The
paper's premises were already known in the '90s, where the only thing
the paper added was using the best sieving methods known to the authors
in 2016. The paper does not apply to parameters that were not concocted
in a special way: to my knowledge, there are no results that would show
otherwise.
(There are some other complexity results, with a=1/3 and c somewhere in
between [(32/9)^{1/3}, (64/9)^{1/3}] as well, see, e.g., [1], which
results in some scaling along [N,N^2] interval.)
Conclusion: your reference to the paper is misleading regarding
state-of-the-art. {I do concur that elliptic curves outperform RSA, but
that is another matter entirely.}
Rene
[1] DLP - the Number Field Sieve for Integers of Low Weight (Oliver
Schirokauer, Math.Comp., 2010)
On 2/9/2017 12:37 PM, Derek Atkins wrote:
Hi,
On Thu, February 9, 2017 12:20 pm, Panos Kampanakis (pkampana) wrote:
About factoring 1024-bits,
https://hal.inria.fr/hal-01376934/file/paper.pdf shows that a special
1024-bit p was factored in 2 months. Also it explains that it is possible
to factor some primes used on the internet today. Going to 1024 gives a
false sense of security. Endorsing it in a standard to be used for some
years down the road makes me uncomfortable. 256-bit ECDSA or EdDSA are
more sufficient with good performance compared to RSA1024.
Please do not mix up 1024-bit Diffie-Hellman and 1024-bit RSA. They are
different mechanisms and depend on different underlying math. Everything
you say above is about DH, which just does not apply when we're discussing
RSA. You cannot "Factor a Prime"; by definition a prime's factors are 1
and itself (e.g. 11).
Yes, it is possible to create a DH-prime that allows easy solutions to the
discrete-log problem. And yes, it's easy to create an RSA key that's
easily factored. However, factoring a "good" 1024-bit RSA key is not "2
months" of effort. c.f. https://en.wikipedia.org/wiki/RSA_numbers for a
list of numbers and references to their factoring efforts over the years.
Yes, 256-bit ECC is more secure than 1024-bit RSA (128-bit security vs
80-bit security). I cannot comment on the performance difference; I've
been focusing on WalnutDSA which verifies orders of magnitude faster than
either RSA or ECDSA.
-derek
--
email: [email protected] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363
_______________________________________________
Ace mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/ace
