Re: [Cfrg] ECC mod 8^91+5
Thomas Garcia <tgarcia.3141@gmail.com> Wed, 02 August 2017 07:52 UTC
Return-Path: <tgarcia.3141@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 5D37D126BF3 for <cfrg@ietfa.amsl.com>; Wed, 2 Aug 2017 00:52:11 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.448
X-Spam-Level:
X-Spam-Status: No, score=-2.448 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
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 NwJiu1fOOlmC for <cfrg@ietfa.amsl.com>; Wed, 2 Aug 2017 00:52:08 -0700 (PDT)
Received: from mail-lf0-x234.google.com (mail-lf0-x234.google.com [IPv6:2a00:1450:4010:c07::234]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 079F01288B8 for <cfrg@irtf.org>; Wed, 2 Aug 2017 00:52:07 -0700 (PDT)
Received: by mail-lf0-x234.google.com with SMTP id d17so16520973lfe.0 for <cfrg@irtf.org>; Wed, 02 Aug 2017 00:52:07 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=OryFn5vO1Rx1MluFGkCe16QEzjlXwAs8jn+ez8esigs=; b=NBKuCAFVK56SSONZNp13LWZqkFEmitMyi5W0kEfFqp6LS872Eqcf3BIr4DzWkn9Tpm Tc/fNrHPTC9oA1l80c1aH8GiCAwZlbaarqoxvcaQHg/5dbV16wFomjAKKcsp9bn9Xn7T ttzXFiulFFpqDi6ZzKoOkMVk0IQB5Vx5Fa3S2h3Npc3pHgq5InBh4Bf+mDznIySANWJ0 jIUbCWviaNns1dcRQw/cDU+jaMAyQd6SWRU+4aVac5sF84xZdfoJRbZJhz7a4kprHaJw FBF7V7F6qzx8W487Iy4wLhk8mCAsdkDTxf5ghmD5HvfylFvoN/t1S3pI1DUgKfMPycOq kmBA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=OryFn5vO1Rx1MluFGkCe16QEzjlXwAs8jn+ez8esigs=; b=rRQ9+jAPtruMZ81noqTFqgVpgFHy+hkavovz1avSuJxG8XTJbz6ORalb//MvL87iTM Sa8/2xGd4I1sHjyf+SamHrzXIuM/sNoq86LJsv3NqZr1YY3CkF8DYD0/dZPLPvHZf/F3 CtE4XhWmuaVYWd4TRTdPDwk2amiLlLM5bikgj6dtiAPFSCL9e60mEl71DVEOaMc7286H ZSHvXIANqcX9pgoEVLexLCzLZdMvOF8WPa4rKuqizytZYowBS4h4ZwsADxuNbjL4qsqf KBdJkp0jzP7rn9vgK6gRrf7qexgUxYBPA/bRr8pu5sQ3lIlN8rsy8HPnRdVaBi+l2GrP 3yNQ==
X-Gm-Message-State: AIVw112iJhSftNWix9zzYHAS/T1VypSTGyLWfWqOzQhbXIrt+YOc3Eji lHr6KDWoL2PIKLPsgnCKRxYQM4o2tg==
X-Received: by 10.25.228.206 with SMTP id x75mr6450255lfi.94.1501660326035; Wed, 02 Aug 2017 00:52:06 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.25.22.40 with HTTP; Wed, 2 Aug 2017 00:52:05 -0700 (PDT)
In-Reply-To: <810C31990B57ED40B2062BA10D43FBF501B7969D@XMB116CNC.rim.net>
References: <810C31990B57ED40B2062BA10D43FBF501B181DA@XMB116CNC.rim.net> <810C31990B57ED40B2062BA10D43FBF501B7969D@XMB116CNC.rim.net>
From: Thomas Garcia <tgarcia.3141@gmail.com>
Date: Wed, 02 Aug 2017 08:52:05 +0100
Message-ID: <CAFTSWvf3-rpVG+GWh81an400dOwcwrZ=yRAjh1Bt7kkfvPJdRg@mail.gmail.com>
To: Dan Brown <danibrown@blackberry.com>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="94eb2c0c91664e85020555c08a42"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/d8PCHxU_g8vEyHHkJ8mLoaW3CXg>
Subject: Re: [Cfrg] ECC mod 8^91+5
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 02 Aug 2017 07:52:11 -0000
Hi Dan, The transformation you proposed (x->iu, y->(-i/2)^(1/2)v) does indeed define an isomorphism between the curve (2y^2=x^3+x) and the curve (v^2=u^3-u), modulo p=8^91+5. As this transformation is defined over GF(p), it preserves the group of points modulo p. Thomas G. On Tue, Aug 1, 2017 at 10:22 PM, Dan Brown <danibrown@blackberry.com> wrote: > Hi CFRG, > > A minor addition to this topic. > > In my first email on this topic, and in my recent IETF 99 presentation, I > mentioned that the proposed special curve 2y^2=x^3+x was similar to curves > proposed in Miller's 1985 paper introducing of ECC. > > I went back and worked out some more details about this similarity (just > some basic elliptic curve math). > > To prepare, note that there exists a field element i in GF(8^91+5) with > i^2=-1. > > Putting x=iu and y=(-i/2)^(1/2)v defines a map to curve with equation > v^2=u^3-u. I believe (99% sure) that this map is an isomorphism (of > GF(8^91+5)-rational points). This equation has the same form as Miller's > proposed equation y^2 = x^3 - ax, with a=1. > > However, Miller does suggest that value a should not be a perfect square, > which rules out a=1 above. > > I believe (50% sure) that Miller made this non-square a recommendation > merely to help keep the group cofactor down (by ensuring a unique point of > order 2, namely (0,0)). > > By contrast 2y^2=x^3+x, has a subgroup of order 8. (With points O, (0,0), > (i,0), (-i,0), (1,1), (1,-1), (-1,i), (-1,-i).) A subgroup of order 4 (or > 8) is nowadays considered (arguably) an advantage, because of various > Edwards curves (but I am only 10% sure, since I haven't looked at this in a > while, please correct me this is wrong). > > So, the special curve 2y^2=x^3+x is isomorphic to a curve with an even > more compact representation: y^2=x^3-x. > > Despite the more compact equation, the original form 2y^2=x^3+x is > slightly preferable because it is already in the convenient Montgomery > form, so I plan to use the original in the ID. (But if somebody knows how > to do the Montgomery ladder math equally as efficient on a Miller curve > y^2=x^3-x, then I'm all ears :) > > Best regards, > > Dan > > -----Original Message----- > From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of Dan Brown > Sent: Tuesday, May 16, 2017 1:36 PM > To: cfrg@irtf.org > Subject: [Cfrg] ECC mod 8^91+5 > > Hi all, > > I'm considering writing an I-D on doing ECC over the field of size > 8^91+5 (=2^273+5), > because it: > - is written in just 6 symbols (=low Kolmogorov complexity, heuristically > minimizing threat of NOBUS-trapdoor), > - has easy and fast inversion, Legendre symbols, and square roots, > - has efficient arithmetic using at most five 64-bit words (use base 2^55), > - is at least 2^(256-epsilon), > - is (probably) prime, so not an extension field (has no subfields for > descent-type attacks on ECDLP). > Other fields can improve on some of these properties, but might worsen the > others. > > For ECC with this field, I am also considering the special curve > 2y^2=x^3+x, > because it: > - is written in just 10 symbols (similar gains to 6-symbol field), > - has Montgomery form (and easily converts to Weierstrass), > - has efficient endomorphism (so it is a GLV curve), > - is similar to curves already suggested by Miller in 1985 (well-aged), > - is similar to sect256k1 already used in bitcoin (incentivized), > - has an small enough cofactor 72 (over field size 8^91+5), > - avoids the main ECDLP attacks: Pohlig-Hellman, Menezes-Okamoto-Vanstone, > etc., > - is similar to the special curves of Koblitz-Menezes [ia.cr/2008/390, > Sec 11.1, Example 5] resisting a speculative attack. > The motivation for this special curve largely matches the motivation for > the special field. > > The curve's risks are at least: > - CM (endomorphism) makes it potentially weak (after 32 years of being > safe) (note exactly opposing Koblitz-Menezes rationale), > - its small coefficients are weak for some unpublished reason (continuing > trend of weak small-coefficients, y^2=x^3 (singular), supersingular, etc. > being weak), > - weak twist order (so, it requires a static ECDH Montgomery ladder to use > public key validation), > - weak Cheon resistance (but this is an attack with many queries, much > computation, and faulty or no KDF). > - den Boer or Maurer-Wolf reductions are not tight as possible, so perhaps > it has a big gap between DHP and DLP Other curves (over this field) can > reduce these risks, but may also lose some of the benefits. > > Overall, E(GF(8^91+5)):2y^2=x^3+x might offer competitive efficiency with > fairly reasonable security (for 128-bit symmetric keys). It is only an > incremental change over other standard ECC curves, not anything too radical. > > I'd be happy to hear what CFRG thinks, or if the CFRG would welcome such > an I-D as a CFRG work item. I hope to have this topic presented briefly at > an upcoming CFRG meeting. > > Best regards, > > Dan Brown > > > > > _______________________________________________ > Cfrg mailing list > Cfrg@irtf.org > https://www.irtf.org/mailman/listinfo/cfrg > > _______________________________________________ > Cfrg mailing list > Cfrg@irtf.org > https://www.irtf.org/mailman/listinfo/cfrg >
- [Cfrg] ECC mod 8^91+5 Dan Brown
- Re: [Cfrg] ECC mod 8^91+5 David Jacobson
- Re: [Cfrg] ECC mod 8^91+5 Dan Brown
- Re: [Cfrg] ECC mod 8^91+5 Dan Brown
- Re: [Cfrg] ECC mod 8^91+5 Thomas Garcia
- Re: [Cfrg] ECC mod 8^91+5 Ilari Liusvaara
- Re: [Cfrg] ECC mod 8^91+5 Dan Brown
- Re: [Cfrg] ECC mod 8^91+5 Dan Brown
- Re: [Cfrg] ECC mod 8^91+5 Ilari Liusvaara
- Re: [Cfrg] ECC mod 8^91+5 D. J. Bernstein
- Re: [Cfrg] ECC mod 8^91+5 Samuel Neves
- Re: [Cfrg] ECC mod 8^91+5 D. J. Bernstein
- Re: [Cfrg] ECC mod 8^91+5 Dan Brown
- Re: [Cfrg] ECC mod 8^91+5 Dan Brown
- Re: [Cfrg] ECC mod 8^91+5 Paterson, Kenny
- Re: [Cfrg] ECC mod 8^91+5 Hanno Böck
- Re: [Cfrg] ECC mod 8^91+5 Salz, Rich
- Re: [Cfrg] ECC mod 8^91+5 Stephen Farrell
- Re: [Cfrg] ECC mod 8^91+5 Dan Brown