Re: [Cfrg] Requirements for elliptic curves with a view towards constrained devices

Dan Brown <dbrown@certicom.com> Wed, 19 November 2014 18:21 UTC

Return-Path: <dbrown@certicom.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 4727D1A1B9A for <cfrg@ietfa.amsl.com>; Wed, 19 Nov 2014 10:21:06 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.001
X-Spam-Level:
X-Spam-Status: No, score=-0.001 tagged_above=-999 required=5 tests=[BAYES_40=-0.001] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id HEoe1x5tNO3E for <cfrg@ietfa.amsl.com>; Wed, 19 Nov 2014 10:21:04 -0800 (PST)
Received: from smtp-p01.blackberry.com (smtp-p01.blackberry.com [208.65.78.88]) by ietfa.amsl.com (Postfix) with ESMTP id EE7E21AD428 for <cfrg@irtf.org>; Wed, 19 Nov 2014 10:21:03 -0800 (PST)
Received: from xct105cnc.rim.net ([10.65.161.205]) by mhs211cnc.rim.net with ESMTP/TLS/AES128-SHA; 19 Nov 2014 13:20:58 -0500
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT105CNC.rim.net ([fe80::d13d:b7a2:ae5e:db06%16]) with mapi id 14.03.0174.001; Wed, 19 Nov 2014 13:20:57 -0500
From: Dan Brown <dbrown@certicom.com>
To: "'F.RONDEPIERRE@oberthur.com'" <F.RONDEPIERRE@oberthur.com>, "'cfrg@irtf.org'" <cfrg@irtf.org>
Thread-Topic: [Cfrg] Requirements for elliptic curves with a view towards constrained devices
Thread-Index: AdAEEs5MtREHuut+R2eLj0cfl46SiAAEKXyQ
Date: Wed, 19 Nov 2014 18:20:57 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF5D03C53@XMB116CNC.rim.net>
References: <8FBEB0194016E64D9DF7E7855CD88E0C073A6D@FRPASERV0088.emea.oberthurcs.com>
In-Reply-To: <8FBEB0194016E64D9DF7E7855CD88E0C073A6D@FRPASERV0088.emea.oberthurcs.com>
Accept-Language: en-CA, en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
x-originating-ip: [10.65.160.249]
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg="SHA1"; boundary="----=_NextPart_000_0124_01D003FB.A7EEE3F0"
MIME-Version: 1.0
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/7hUvC1GObt6bVBE9RcLy7RCgg2k
Subject: Re: [Cfrg] Requirements for elliptic curves with a view towards constrained devices
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 19 Nov 2014 18:21:06 -0000


>From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of RONDEPIERRE Franck
>However when performances matters, why not taking Short Weierstrass curves
with a=0? Indeed, in such a case doublings 

Using a=0 seems to result in j=0 and a complex multiplication curve with
discriminant -3, which is arguably a rather special curve, and conjecturally
a greater risk than random j invariant. A complex multiplication
endomorphism by the cube root w of unity is (x,y) -> (wx,7). 

A precedent for an a=0 curve is secp256k1, which has apparently been used in
BitCoin.  In theory, the GLV method can speed-up ECC operations using the
endomorphism above, although I'm not personally aware of the practical gain.

Perhaps others in CFRG may agree that the risk of CM is worth the
performance gain, at least as an option.
 
 (Aside: also, the MOV test will rule half the prime field sizes because
they are supersingular when a=0.)