IETF Logo Mail Archive

Re: [Cfrg] New names for draft-ladd-safecurves

Mike Hamburg <mike@shiftleft.org> Tue, 21 January 2014 05:41 UTC

Return-Path: <mike@shiftleft.org>
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 D96C81A003C for <cfrg@ietfa.amsl.com>; Mon, 20 Jan 2014 21:41:43 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.556
X-Spam-Level: *
X-Spam-Status: No, score=1.556 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_ORG=0.611, HOST_MISMATCH_NET=0.311, RDNS_DYNAMIC=0.982, 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 wmh6e5FDcF9C for <cfrg@ietfa.amsl.com>; Mon, 20 Jan 2014 21:41:42 -0800 (PST)
Received: from aspartame.shiftleft.org (199-116-74-157-v301.PUBLIC.monkeybrains.net [199.116.74.157]) by ietfa.amsl.com (Postfix) with ESMTP id ADEBC1A0036 for <cfrg@irtf.org>; Mon, 20 Jan 2014 21:41:42 -0800 (PST)
Received: from [192.168.1.129] (unknown [192.168.1.1]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 60E5F3AA04; Mon, 20 Jan 2014 21:39:36 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1390282776; bh=l1muQ/l/pOq/05stgoHAs94EyMq57jH+uEP6HYh0wdA=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=DJVX1FM6fNapmvRt7JLUDIa1Lf3HO1wG+tRLYV4rEGLwrLjBDN0mRq5QLZjs3vtVA y+1pe2RvhRjBYEF4BAFtPO1Cfa22g7QhbPmShfFKUkdBa43az8XYVNpoDDFZbC8LH8 a56+OO/SfRKee99AkW9ejmFz/BOBE8EXa8zYlhg4=
Content-Type: text/plain; charset="us-ascii"
Mime-Version: 1.0 (Mac OS X Mail 7.1 \(1827\))
From: Mike Hamburg <mike@shiftleft.org>
In-Reply-To: <CABqy+sqb_CcSpg5g_N1TD1JcSktjtRE7Yj-aMjWpSN18Zuk6-Q@mail.gmail.com>
Date: Mon, 20 Jan 2014 21:41:39 -0800
Content-Transfer-Encoding: quoted-printable
Message-Id: <1BDA9C49-6458-4005-9682-B8CEEA5C9257@shiftleft.org>
References: <CACsn0ck02mnETBUfuyJjLV9K8Yuiki8_-RG0tVszL8BDhkK27w@mail.gmail.com> <6489F7D3-BF54-416F-94BE-64FD1CFCCB1E@callas.org> <CACsn0cn0938BHMs7uFJYeB_q2VcGQULcF8fzc7KR67A_+mqzLw@mail.gmail.com> <264676DC-14DA-432E-81AB-CD0D852307A4@shiftleft.org> <CABqy+sr1zc-T-F3D_VOoz2B9GNZPsAxi=HeMoe=DwG5EJq8AuA@mail.gmail.com> <CACsn0ckg3Pna2bd9RPZnDGWa=GSaLGykkdqPwg3bat0+p2ZGcA@mail.gmail.com> <CABqy+sqb_CcSpg5g_N1TD1JcSktjtRE7Yj-aMjWpSN18Zuk6-Q@mail.gmail.com>
To: Robert Ransom <rransom.8774@gmail.com>
X-Mailer: Apple Mail (2.1827)
Cc: "cfrg@irtf.org" <cfrg@irtf.org>, Jon Callas <jon@callas.org>
Subject: Re: [Cfrg] New names for draft-ladd-safecurves
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: Tue, 21 Jan 2014 05:41:44 -0000

On Jan 20, 2014, at 9:06 PM, Robert Ransom <rransom.8774@gmail.com> wrote:
> I would suggest using the Montgomery-form x coordinate with the sign
> bit of the Edwards-form x coordinate.  (In fact, I *did* suggest that:
> <http://www.ietf.org/mail-archive/web/cfrg/current/msg03868.html>
> <http://www.ietf.org/mail-archive/web/cfrg/current/msg03870.html>)

Amusingly, if you say that "sign" is "Jacobi symbol" (when p==3 mod 4), the two are the same for q-torsion points.  But either way, the difference is a couple of field muls vs a slightly messier spec.

> And yes, the Brier-Joye formulas to recover Montgomery-form y after
> the Montgomery ladder would be faster than Brauer's algorithm on
> Edwards-form points for variable-base single-scalar multiplication.


Is this still true for large curves?  I don't think it's true asymptotically, and if people switch from inverse-by-exp to inverse-by-blind-and-EGCD, then you lose your free square root and the tradeoff might happen before 521 bits.  You might get your freebie back again if you spec that sign is Jacobi symbol and use a blind EGCD inverse-and-Jacobi-symbol, but again this only works for p==3 mod 4.

Cheers,
-- Mike

v2.23.0 | Report a Bug | By Email