Subject: Re: [Cfrg] Fwd: New Version Notification for draft-mcgrew-fundamental-ecc-03

From: Robert Moskowitz <[email-masked]>
Date: Mon, 07 Jun 2010 09:59:52 -0400

You reference RFC 4753 for P-256, P-384, and P-512 parameters.

Would RFC 5639 be better?  A lot more sizes available?

On 05/21/2010 03:48 PM, David McGrew wrote:
> FYI.  Version 03 makes several corrections and some clarifications.   
> Thanks especially to Alfred Hoenes for a thorough review and the 
> pseudocode in Appendix F.
>
> David
>
> Begin forwarded message:
>
>> From: IETF I-D Submission Tool <[email-masked]>
>> Date: May 21, 2010 12:45:06 PM PDT
>> To: [email-masked]
>> Cc: [email-masked], [email-masked]
>> Subject: New Version Notification for draft-mcgrew-fundamental-ecc-03
>>
>>
>> A new version of I-D, draft-mcgrew-fundamental-ecc-03.txt has been 
>> successfully submitted by David McGrew and posted to the IETF 
>> repository.
>>
>> Filename:     draft-mcgrew-fundamental-ecc
>> Revision:     03
>> Title:         Fundamental Elliptic Curve Cryptography Algorithms
>> Creation_date:     2010-05-21
>> WG ID:         Independent Submission
>> Number_of_pages: 34
>>
>> Abstract:
>> This note describes the fundamental algorithms of Elliptic Curve
>> Cryptography (ECC) as they are defined in some early references.
>> These descriptions may be useful for implementing the fundamental
>> algorithms without using any of the specialized methods that were
>> developed in following years.  Only elliptic curves defined over
>> fields of characteristic greater than three are in scope; these
>> curves are those used in Suite B.
>>
>>
>>
>> The IETF Secretariat.
>>
>>
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Robert Moskowitz <[email-masked]>
Date: Mon, 07 Jun 2010 10:25:58 -0400

On 06/07/2010 10:13 AM, David McGrew wrote:
> Hi Bob,
>
> On Jun 7, 2010, at 6:59 AM, Robert Moskowitz wrote:
>
> I agree that it would be useful to add a reference to RFC 5639, since 
> that specification is expected to work with fECC.   However, that RFC 
> doesn't provide the parameter definitions that are in RFC 4753, so the 
> new reference would be an addition rather than a replacement.  This 
> will be a minor addition that could be thrown in at any time between 
> now and the end of AUTH48.

I did note that parameter values in 4753 did not match those in 5639.  I 
guess there are those that care (like IKEv2 implementers!).  But I 
desire some smaller key sizes, and thus the attraction of 5639.

I missed that you are in AUTH48...

>>> FYI.  Version 03 makes several corrections and some 
>>> clarifications.   Thanks especially to Alfred Hoenes for a thorough 
>>> review and the pseudocode in Appendix F.
>>>
>>> David
>>>
>>> Begin forwarded message:
>>>

---

From: Simon Josefsson <[email-masked]>
Date: Mon, 07 Jun 2010 17:22:22 +0200

Robert Moskowitz <[email-masked]> writes:

> On 06/07/2010 11:00 AM, Simon Josefsson wrote:
>> Further, aren't the RFC 5639 primes chosen to be in a special form for
>> efficient implementation?  It isn't clear to me whether those
>> optimization are patent encumbered or not, and avoiding patented ECC
>> variants appears to be a goal of the draft.
>>    
>
> From 5639:
>
> 6.  Intellectual Property Rights
>
>    The authors have no knowledge about any intellectual property rights
>    that cover the usage of the domain parameters defined herein.
>    However, readers should be aware that implementations based on these
>    domain parameters may require use of inventions covered by patent
>    rights.

D'uh, I meant RFC 4753 of course -- RFC 5639 was explicitly designed to
avoid special forms -- and the 4753 document contains:

   - The groups proposed afford efficiency advantages in software
     applications since the underlying arithmetic is integer arithmetic
     modulo a prime rather than binary field arithmetic.  (Additional
     computational advantages for these groups are presented in [GMN].)

With the reference being

   [GMN]          J. Solinas, Generalized Mersenne Numbers,
                  Combinatorics and Optimization Research Report 99-39,
                  1999.  (http://www.cacr.math.uwaterloo.ca/)

Whether this is a patented optimization or not is beyond me.

/Simon

>
> YMMV, I guess.
>
>> /Simon
>>
>> Robert Moskowitz<[email-masked]>  writes:
>>
>>    
>>>>> From: IETF I-D Submission Tool<[email-masked]>

---

From: Simon Josefsson <[email-masked]>
Date: Mon, 07 Jun 2010 17:00:41 +0200

/Simon

---

From: Paul Hoffman <[email-masked]>
Date: Mon, 7 Jun 2010 08:50:33 -0700

>Would RFC 5639 be better?  A lot more sizes available?

RFC 5639 does not describe the NIST curves: it describes curves of its own devising. They happen to have the same key sizes. Let's not mix the two up.

--Paul Hoffman, Director
--VPN Consortium

---

From: Robert Moskowitz <[email-masked]>
Date: Mon, 07 Jun 2010 11:15:01 -0400

From 5639:

YMMV, I guess.

---

From: David McGrew <[email-masked]>
Date: Mon, 7 Jun 2010 07:31:25 -0700

On Jun 7, 2010, at 7:25 AM, Robert Moskowitz wrote:

>> I agree that it would be useful to add a reference to RFC 5639,  
>> since that specification is expected to work with fECC.   However,  
>> that RFC doesn't provide the parameter definitions that are in RFC  
>> 4753, so the new reference would be an addition rather than a  
>> replacement.  This will be a minor addition that could be thrown in  
>> at any time between now and the end of AUTH48.
>
> I did note that parameter values in 4753 did not match those in  
> 5639.  I guess there are those that care (like IKEv2  
> implementers!).  But I desire some smaller key sizes, and thus the  
> attraction of 5639.
>

I'm not yet, sorry for the confusion; I've requested last call.   What  
I meant to say was that the additional reference is a minor tweak that  
could be accommodated without a new spin of the draft.

David

>>>> clarifications.   Thanks especially to Alfred Hoenes for a  
>>>> thorough review and the pseudocode in Appendix F.
>>>>
>>>> David
>>>>
>>>> Begin forwarded message:
>>>>
>>>>> A new version of I-D, draft-mcgrew-fundamental-ecc-03.txt has  
>>>>> been successfully submitted by David McGrew and posted to the  
>>>>> IETF repository.
>>>>>

---

From: David McGrew <[email-masked]>
Date: Mon, 7 Jun 2010 07:13:48 -0700

Hi Bob,

David

---

From: "Dan Harkins" <[email-masked]>
Date: Mon, 7 Jun 2010 13:13:53 -0700 (PDT)

Hi Simon,

  They are all of the form p mod 4 = 3 and that makes for efficient
point decompression since the square root of x will be x^((p+1)/4) mod p.
The paper discusses this in Appendix C and attributes this optimization
to a paper by D. Lehmer in 1969. So this particular optimization isn't
patent encumbered.

  Dan.