Re: [TLS] STRAW POLL: Size of the Minimum FF DHE group

[Manuel Pégourié-Gonnard <[e-mail]>]

On 05/11/2014 03:19, Watson Ladd wrote:
> On Tue, Nov 4, 2014 at 5:23 PM, Viktor Dukhovni <[e-mail]> wrote:
>> Basically, what's the expected ratio of DH-per-second between the
>> two proposed field sizes, and between the 2048-bit group and $F_p$
>> with $q = (p-1)/2$ and $p$ a 2048-bit Sophie-Germain prime.  Is
>> the "new" 2432 as fast or faster than the "old" 2048?
> 
> Slower, by a quadratic factor assuming standard algorithms for bignum
> arithmetic. No acceleration of either is possible, and for good
> reason: SNFS uses the same characteristics as we would use to optimize
> arithmetic.
> 
Unless I'm mistaken, if textbook multiplication is used, it's rather cubic:
multiplication is quadratic, and the length of the exponent, which is roughly
the number of multiplications, is linear in the size of the group.

Which gives a 67% performance penalty for 2432 compared to 2048

Now, for this size, Karatsuba is probably the best multiplication algorithm,
which is about n^1.58, so a total of n^2.58 for exponentiation, which gives a
performance penalty of 58% with this algorithm.

Manuel.