Re: [Cfrg] ECC mod 8^91+5

"D. J. Bernstein" <djb@cr.yp.to> Wed, 02 August 2017 15:25 UTC

Return-Path: <djb-dsn2-1406711340.7506@cr.yp.to>
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 0550113214A for <cfrg@ietfa.amsl.com>; Wed, 2 Aug 2017 08:25:08 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.898
X-Spam-Level:
X-Spam-Status: No, score=-1.898 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, UNPARSEABLE_RELAY=0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=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 cUT0F2NDWkv8 for <cfrg@ietfa.amsl.com>; Wed, 2 Aug 2017 08:25:06 -0700 (PDT)
Received: from salsa.cs.uic.edu (salsa.cs.uic.edu [131.193.32.108]) by ietfa.amsl.com (Postfix) with SMTP id D29D9132145 for <cfrg@irtf.org>; Wed, 2 Aug 2017 08:24:35 -0700 (PDT)
Received: (qmail 10367 invoked by uid 1010); 2 Aug 2017 15:24:33 -0000
Received: from unknown (unknown) by unknown with QMTP; 2 Aug 2017 15:24:33 -0000
Received: (qmail 8451 invoked by uid 1000); 2 Aug 2017 15:24:30 -0000
Date: 2 Aug 2017 15:24:30 -0000
Message-ID: <20170802152430.8449.qmail@cr.yp.to>
From: "D. J. Bernstein" <djb@cr.yp.to>
To: cfrg@irtf.org
Mail-Followup-To: cfrg@irtf.org
In-Reply-To: <20170802081237.k6pcmldfso4dkgeq@LK-Perkele-VII>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/4jtGpn7oDKxZWzlJChLxvRJl-UU>
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 15:25:08 -0000

Ilari Liusvaara writes:
> Unfortunately there is another related problem: The theorem that says
> that folded Montgomery ladder always works assumes that there is
> unique point of order 2.

The theorem in the Curve25519 paper assumed a unique point of order 2,
but this turned out to be unnecessary. See Theorem 4.5 in

   https://cr.yp.to/papers.html#montladder

and in particular the proofs of the underlying DBL and DADD theorems via
the Edwards addition law. The paper also gives proofs from the
historical Weierstrass perspective.

The completeness issue is more problematic outside the ladder context:

   * The fast complete Edwards formulas don't apply to this curve: the
     curve doesn't have a unique point of order 2.

   * The fast complete Hessian formulas also don't apply to this curve:
     the curve doesn't have a unique point of order 3.

   * The formulas from https://cr.yp.to/talks/2009.07.17/slides.pdf and
     https://eprint.iacr.org/2015/1060 do apply but don't meet the
     SafeCurves requirements of speed and simplicity ("implementations
     of scalar multiplication for the same curve cannot be much faster"
     and "reasonably fast implementations of scalar multiplication for
     the same curve cannot be much more concise"), so implementors are
     pressured to use incomplete formulas instead.

---Dan