Re: [Cfrg] Review of ECC topics
Watson Ladd <watsonbladd@gmail.com> Sat, 01 March 2014 04:37 UTC
Return-Path: <watsonbladd@gmail.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 674551A02DF for <cfrg@ietfa.amsl.com>; Fri, 28 Feb 2014 20:37:02 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.7
X-Spam-Level: *
X-Spam-Status: No, score=1.7 tagged_above=-999 required=5 tests=[BAYES_05=-0.5, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, MANGLED_OFF=2.3, SPF_PASS=-0.001] autolearn=no
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 jky8rg2Omwju for <cfrg@ietfa.amsl.com>; Fri, 28 Feb 2014 20:37:00 -0800 (PST)
Received: from mail-yk0-x229.google.com (mail-yk0-x229.google.com [IPv6:2607:f8b0:4002:c07::229]) by ietfa.amsl.com (Postfix) with ESMTP id A98E81A02D9 for <cfrg@irtf.org>; Fri, 28 Feb 2014 20:37:00 -0800 (PST)
Received: by mail-yk0-f169.google.com with SMTP id 142so4493123ykq.0 for <cfrg@irtf.org>; Fri, 28 Feb 2014 20:36:58 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=wtWmzKYiR9GTLsPfMyzBn43/QNop+ZcNLJC9ZI+Hvlc=; b=PIXEWlx7sLKWFLJzioX+6NchlPiu75yndc4KqJzz1VqrGtzaQwQGgkBaCgkO7zKs3f /Xy1baqR6wllHiLm6WEKMTXz38ZueNHXV17z9E69XCIufBfTKIA1MJwxbDeWt/IDm+LA XW+6tkivmqLcS51CEn3LE6rIJehWNkGEH3tt0yR4quTPBX+7Sl1/aVi2ahQxNupMOf98 vXQOarGcdX8po5D+CRo2aadWp4mv/La4Hf376VllaEPq7dn7zQS/eZ0J0oyXQNQ+hZbX SB3K29yUM1Db1MMHm1noUyZjybhvsTn8FrR/x+/xdpWnokYLs1GW5IbbFDDfxv7tkt5q nFKg==
MIME-Version: 1.0
X-Received: by 10.236.101.227 with SMTP id b63mr6301852yhg.37.1393648618311; Fri, 28 Feb 2014 20:36:58 -0800 (PST)
Received: by 10.170.92.85 with HTTP; Fri, 28 Feb 2014 20:36:58 -0800 (PST)
In-Reply-To: <CABqy+soS=t3riOZkDnJ5jMApJfWv95So34DdFona5JXERAws_w@mail.gmail.com>
References: <CABqy+soS=t3riOZkDnJ5jMApJfWv95So34DdFona5JXERAws_w@mail.gmail.com>
Date: Fri, 28 Feb 2014 20:36:58 -0800
Message-ID: <CACsn0cnEXGrF-icsVMSp0x+RbhYXaU59FEnq+sBCxenGMgEDJw@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Robert Ransom <rransom.8774@gmail.com>
Content-Type: text/plain; charset="UTF-8"
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/StVxbkDuL3BYmCQ7CpAAP4r4h4w
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Review of ECC topics
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: Sat, 01 Mar 2014 04:37:02 -0000
Some notes, from the concrete to the abstract: I do not see what the grade school definition of polynomial has to offer above the one recorded below. Furthermore, polynomial addition and multiplication are defined so as to make F[x] a commutative ring: it is not the case that one can show that the results hold without defining the multiplication and addition. Vector space is mentioned but is never defined. Despite desiring to avoid algebraic geometry, the world "multiplicity" is used without explanation. The parenthetical is an explanation only for the initiate or the credulous. Furthermore, to avoid algebraic geometry in explaining elliptic curves is to evade the nature of the subject. I strongly question the comprehensibility of any such attempt in the final reckoning. An algebraic curve is not the zero set of f(x,y) in some affine plane: the field must be algebraically closed for the classical definition, and in the modern definition that only is the F_p rational points. In particular one runs into the issue of x^p+y^p=0 over F_p, which is not the same curve as x+y=0. Not every morphism is given by a single polynomial, but rather a rule assigning to every open set a polynomial in a compatible manner. This matters because the addition morphism on a curve in short Weierstrass form is not given by a single polynomial, hence the need for complete addition laws in the first place. (I will temporarily leave aside the issue of defining the product to define the addition law as a morphism). Your definition of isogeny differs from that of Silverman, the standard text in this area. In particular your first condition is somewhat mystifying to me: it is not part of the definition of Silverman, and so I am concerned the there might actually be a difference between them that is material. I have not thought about this hard enough to be sure either way. But in one case it is unnecessary, and in the other it is wrong. Lastly, intuition does not come from definitions and quoted results. It comes from examples. Perhaps "convey the definitions of a few critical concepts" would better fit the goals here. Sincerely, Watson On Fri, Feb 28, 2014 at 7:41 PM, Robert Ransom <rransom.8774@gmail.com> wrote: > See attached for a document reviewing the background in abstract > algebra, number theory, and elliptic curves that I consider necessary > to properly explain the specific design and implementation details of > Montgomery and Edwards curves (including conditions for twist > security, conversion between Montgomery and Edwards forms, conditions > for completeness of the Edwards-form addition law, use of Edwards > forms with a=-1 in fields where -1 is a non-square, and implementation > of simple point formats). > > My main goal is to convey the intuition behind a few critical > mathematical concepts; I'm not trying to teach readers to implement > computations involving e.g. algebraic extension fields or Weierstrass > curves. (Except for the sections on non-squares and square-root > computations, where I can only provide insight without a long > digression for fields in which -1 is a non-square.) > > > I would greatly appreciate any comments, especially from non-experts. > I am particularly interested in whether the sections on polynomial > rings, algebraic extension fields, and maps between curves (and > elliptic curves) are easy to understand. > > > Robert Ransom > > _______________________________________________ > Cfrg mailing list > Cfrg@irtf.org > 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] Review of ECC topics Robert Ransom
- Re: [Cfrg] Review of ECC topics Watson Ladd
- Re: [Cfrg] Review of ECC topics Robert Ransom
- Re: [Cfrg] Review of ECC topics Robert Ransom