Subject: [Cfrg] draft-irtf-cfrg-eddsa - Implementation failure for 448

From: Jim Schaad <[email-masked]>
Date: Wed, 20 Jul 2016 14:18:52 +0200

There is a difference between the document and the code for point addition
of 448.  Which is the correct one?

Text in section 5.2.4

    X3 = A*G*(H-C-D)
    Y3 = A*G*(D-C)

Python Code
        tmp.x=zcp*F*((self.x+self.y)*(y.x+y.y)-xcp-ycp)
        tmp.y,tmp.z=zcp*G*(ycp-xcp),F*G

Note that the first uses A*G the section uses A*F in computing the new x
value.

Jim

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 20 Jul 2016 15:49:04 +0300

> Note that the first uses A*G the section uses A*F in computing the new x

Good catch: It should be A*F (as in code). Fixed in Editor's Copy.

-Ilari

---

From: Jim Schaad <[email-masked]>
Date: Wed, 20 Jul 2016 16:38:28 +0200

OK - Another one for you.

H = (X1+X2)*(Y1+Y2)
X3 = A*G*(H-C-D)

Vs code

note that in once case the two X are being added and in the other x and y are being added.

Jim

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]]
> Sent: Wednesday, July 20, 2016 2:49 PM
> To: Jim Schaad <[email-masked]>
> Cc: [email-masked]; [email-masked]
> Subject: Re: draft-irtf-cfrg-eddsa - Implementation failure for 448
> 
> > There is a difference between the document and the code for point
> > addition of 448.  Which is the correct one?
> >
> > Text in section 5.2.4
> >
> >     X3 = A*G*(H-C-D)
> >     Y3 = A*G*(D-C)
> >
> > Python Code
> > Note that the first uses A*G the section uses A*F in computing the new
> > x value.
>

---

From: Watson Ladd <[email-masked]>
Date: Wed, 20 Jul 2016 07:48:59 -0700

Why aren't we using the formulas from EFD?
https://hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html

We know these are right due to a Magma script checking them.

On Wed, Jul 20, 2016 at 7:38 AM, Jim Schaad <[email-masked]> wrote:
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Jim Schaad <[email-masked]>
Date: Wed, 20 Jul 2016 17:07:55 +0200

Maybe because this is an a=-1 curve?  (Guess on my part).

Jim

> From: Watson Ladd [mailto:[email-masked]]
> Sent: Wednesday, July 20, 2016 4:49 PM
> Cc: Ilari Liusvaara <[email-masked]>; [email-masked]; draft-irtf-cfrg-
> [email-masked]
> Subject: Re: [Cfrg] draft-irtf-cfrg-eddsa - Implementation failure for 448
> 
> >> > Note that the first uses A*G the section uses A*F in computing the
> >> > new x value.
> >>

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 20 Jul 2016 18:59:43 +0300

> > note that in once case the two X are being added and in the other x and y are being added.

Got that too.

> We know these are right due to a Magma script checking them.

The formulas supposedly come from EFD. No darn clue why that one
formula pulled one of the terms as H (and did so incorrectly).

The twisted doubling formula in EFD contains a, despite having assumed
a=-1 for some darn reason. There the a=-1 was carried forward in the
draft (note that E, F, G and H flip sign, but end results only contain
two-products of those, so sign flips cancel out).

-Ilari.