Re: [Cfrg] Consensus and a way forward

["Paterson, Kenny" <[e-mail]>]

Hi Watson,

On 27/11/2014 05:26, "Watson Ladd" <[e-mail]> wrote:

>On Wed, Nov 26, 2014 at 8:25 PM, Benjamin Black <[e-mail]> wrote:
>> All,
>>
>> Over the past couple of weeks we have been working with Adam Langley to
>>see
>> if we could find a compromise with which we could all live. I'm pleased
>>to
>> say we have been successful in accommodating our respective performance
>>and
>> trustworthy generation concerns, and I hope the resulting proposal will
>>be
>> attractive to others, as well. The generation procedure is document in a
>> draft I've just posted that can be found at
>> http://www.ietf.org/id/draft-black-rpgecc-00.txt .
>
>This document doesn't address the most important questions:
>
>1: What goes on the wire for ECDH? Montgomery points, points native to
>each curve formula, or Weierstrass points?
>2: How are signatures computed?
>3: Clear bits, multiply by cofactors, or check group membership?
>4: Point compression or no point compression?

These things would all follow in due course, if the proposal were
acceptable to CFRG.

Anyway, as far as I can see, none of these is very hard, given the many
discussion we've had on the list and the education I've thereby received.
Here's some suggestions that we can come back to later (once we've agreed
whether we want to go down this route or not):

1. Points in Montgomery form for ECDH (remember, we are at liberty to
specify new point formats on the wire for these curves for TLS).
2. Using EC-DSA (oh yes!).
3. Multiply by co-factors, as per the EC-DSA standards, IIRC; plus
whatever Montgomery form needs (please feel free to re-inform me).
4. Not relevant for EC-DSA signatures; for Montgomery form, x-coordindate
only would be best, right?

Cheers

Kenny


>
>Given that generators are recorded for a prime order subgroup, it
>would seem that we are checking group membership, which will lead to
>the check being omitted and resultant, albeit minor, security issues.
>
>>
>> The simplest summary is that we have combined the prime preferred by
>>Adam
>> and others at the 128-bit security level with the rigid parameter
>>generation
>> we view as essential for producing the most trustworthy curves. We have
>>used
>> the generation procedure to produce a new twisted Edwards curve based on
>> 2^255 - 19 and a new Edwards curve based on 2^384 - 317. These new
>>curves
>> are given as test vectors in the draft, and are also given below.
>
>Why 2^384-317 and not 2^383-31 or 2^389-21? This choice of prime
>really pinches the allowable radixes for carry-free multiplication
>reduction, and thus hurts efficiency, more than the 2^255-19 vs
>2^256-189 decision at the lower security level. Far from being a
>simultaneous accommodation of the performance concerns and the
>generation concerns, this is clearly horse trading, with performance
>being given the choice of the 255 bit prime, and a similar improvement
>not happening at the 384 bit prime.
>
>>
>> These 2 curves are sufficient for meeting the request from TLS.
>>However, if
>> there is strong interest in a 3rd curve for the 256-bit security level,
>>the
>> generation procedure gives the same curve with p =2^521 - 1 as several
>>teams
>> produced.
>
>Sincerely,
>Watson Ladd
>>
>>
>> b
>>
>> --
>>
>> 2^255 - 19
>>
>>    p = 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
>>          FFFFFFFFFFED
>>    d = 0x15E93
>>    r = 0x2000000000000000000000000000000016241E6093B2CE59B6B9
>>          8FD8849FAF35
>> x(P) = 0x3B7C1D83A0EF56F1355A0B5471E42537C26115EDE4C948391714
>>          C0F582AA22E2
>> y(P) = 0x775BE0DEC362A16E78EFFE0FF4E35DA7E17B31DC1611475CB4BE
>>          1DA9A3E5A819
>>    h = 0x4
>>
>>
>> 2^384 - 317
>>
>>      p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
>>            FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEC3
>>      d = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
>>            FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD19F
>>      r = 0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE2471A1
>>            CB46BE1CF61E4555AAB35C87920B9DCC4E6A3897D
>>   x(P) = 0x61B111FB45A9266CC0B6A2129AE55DB5B30BF446E5BE4C005763FFA
>>            8F33163406FF292B16545941350D540E46C206BDE
>>   y(P) = 0x82983E67B9A6EEB08738B1A423B10DD716AD8274F1425F56830F98F
>>            7F645964B0072B0F946EC48DC9D8D03E1F0729392
>>      h = 0x4
>>
>>
>> _______________________________________________
>> Cfrg mailing list
>> [e-mail]
>> http://www.irtf.org/mailman/listinfo/cfrg
>>
>
>
>
>-- 
>"Those who would give up Essential Liberty to purchase a little
>Temporary Safety deserve neither  Liberty nor Safety."
>-- Benjamin Franklin
>
>_______________________________________________
>Cfrg mailing list
>[e-mail]
>http://www.irtf.org/mailman/listinfo/cfrg