Re: [Cfrg] Curve selection revisited

[Robert Ransom <[e-mail]>]

On 7/30/14, Andrey Jivsov <[e-mail]> wrote:
> On 07/29/2014 04:14 AM, Robert Ransom wrote:

>> Do you see any benefit of p = 2^256 - 189 over p = 2^255 - 19 that you
>> believe offsets the costs of switching to a different coordinate
>> field?
>
> They are :
> * aesthetics
> * it happened that square root of  p = 2^255 - 19 requires
> multiplication by a sqrt(-1) in half the cases when decompression is
> involved.
>
> Both are tolerable from aesthetics point of view IMO if we (effectively)
> standardize on p = 2^255 - 19. p = 2^255 - 19's slightly higher
> performance than 2^256 - 189 should balance *sqrt(-1) out.

What do you mean by “aesthetics”?  (My aesthetic sense may have been
warped by seeing how these fields are implemented -- 2^255-19 and
2^414-17 are quite pretty to me.)

As for the slightly more annoying square-root algorithm modulo
2^255-19, (a) that's *much* better than the P-224 field (already
IETF-approved as a TLS NamedCurve), and (b) that's better than having
a trade-off between using the a=-1 formulas (and saving 1M per scalar
limb in Edwards form) and having a complete formula available for
arbitrary points.  I think it's unfortunate that 2^414-17 is a 3mod4
field rather than a 5mod8 field.


> ( Compare this with 2^414-17, which won't be trivial to match with other
> algorithms. )

What do you mean by “match with other algorithms”?

If you're referring to ‘security level’:

* Stream-cipher keys are found by brute-force preimage search;
discrete logarithms in strong EC groups are computed by brute-force
collision search on the function m*P + n*Q.  The preimage-search
attack on a stream cipher can attack multiple target keys at the same
time at no extra cost, and its probability of finding any of the
target keys is linear in the number of operations performed.  The
discrete-logarithm attack targets a single key at a time (and cannot
find the first of multiple targets at reduced cost), and its
probability of finding the target key increases slower than linearly.
(See Dr. Bernstein's bruteforce paper for the engineering details of
preimage search, then see his ecc2k130 paper for the details of
discrete logarithms, though that paper targets a curve with
automorphisms.)  Thus, a curve group ‘at the n-bit security level’
should always be used with a stream cipher whose key is longer than n
bits.

* The only reason that people use AES keys shorter than 256 bits is
that NSA chose a cipher which uses more rounds (and is thus slower)
for longer keys.  If AES-256 ran at the same speed as AES-128,
everyone would rightly use 256-bit keys, regardless of the difficulty
of breaking the public-key algorithm used with it.


Robert Ransom