Re: [Cfrg] RFC 6090 correctness

Tanja Lange <tanja@hyperelliptic.org> Sun, 16 March 2014 00:28 UTC

Return-Path: <tanja@hyperelliptic.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 ACF191A02B5 for <cfrg@ietfa.amsl.com>; Sat, 15 Mar 2014 17:28:17 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.6
X-Spam-Level:
X-Spam-Status: No, score=-2.6 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7] 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 U1zEPFUvNJWd for <cfrg@ietfa.amsl.com>; Sat, 15 Mar 2014 17:28:16 -0700 (PDT)
Received: from mace.cs.uic.edu (mace.cs.uic.edu [131.193.32.224]) by ietfa.amsl.com (Postfix) with SMTP id E405E1A02B0 for <cfrg@irtf.org>; Sat, 15 Mar 2014 17:28:15 -0700 (PDT)
Received: (qmail 28252 invoked from network); 16 Mar 2014 00:28:09 -0000
Received: from pcdhz005.win.tue.nl (HELO hyperelliptic.org) (131.155.71.33) by mace.cs.uic.edu with SMTP; 16 Mar 2014 00:28:09 -0000
Received: (qmail 3903 invoked by uid 1000); 16 Mar 2014 00:28:06 -0000
Date: Sun, 16 Mar 2014 01:28:06 +0100
From: Tanja Lange <tanja@hyperelliptic.org>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Message-ID: <20140316002806.GL5925@cph.win.tue.nl>
References: <CACsn0ck+8Rhxc1_4bp9za7n+Pe5Oan755CoxBs1ZnPFuruG6OQ@mail.gmail.com> <CACsn0ckXVPtkDiyNUNTTj+oTzVeLBqOr9-tijDRc_2C5mn0_jA@mail.gmail.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <CACsn0ckXVPtkDiyNUNTTj+oTzVeLBqOr9-tijDRc_2C5mn0_jA@mail.gmail.com>
User-Agent: Mutt/1.5.11
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/NYrB3hq3QURZPfOSpn1WxA1tyVA
Subject: Re: [Cfrg] RFC 6090 correctness
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: Sun, 16 Mar 2014 00:28:17 -0000

Dear all,
> > It is not obvious to me why the algorithm in appendix F.2 in RFC 6090
> > is correct. Why is u=0, v !=0 prohibited? In particular, given a
> > single y coordinate there are potentially three x coordinates in the
> > field with that y coordinate. When presented with two of these points,
> > the algorithm given then falls through to computing 2*P1, which isn't
> > the right answer.
> 
To phrase it stronger than Watson: The algorithm is wrong. It merges the
cases of adding (x1,y1) to (x2,y1) into the case of doubling (x1,y1).

The correct algorithm needs a different case distinction

if P1=infty
elif P2=infty 
elif P1=-P2
elif P1!=P2
else (which is the P1=P2) case

All the best
	Tanja