Subject: [Cfrg] A2 versus A^2 and BB verus AA

From: Paul Lambert <[email-masked]>
Date: Sat, 10 Jan 2015 11:15:36 -0800

In reviewing and trying to implement curve25519 from:
   draft-josefsson-tls-curve25519-06,
   draft-agl-cfrgcurve-00
   and http://www.hyperelliptic.org/EFD/g1p/auto-montgom-xz.html

I¹ve noticed a possible error in draft-josefsson-tls-curve25519-06:

A  = X2 + Z2
               AA = A2           <‹ should be A^2
               B  = X2 - Z2
               BB = B2           <‹‹ should be B^2
               E  = AA - BB
               C  = X3 + Z3
               D  = X3 - Z3
               DA = D * A
               CB = C * B
               X5 = (DA + CB)^2
               Z5 = X1 * (DA - CB)^2
               X4 = AA * BB
               Z4 = E * (BB + a24 * E)    <‹‹‹‹‹ correctly uses ŒBB¹

This looks like a cut-and-paste error.  The Œ^2¹ is a superscript in the
EFD definitions.

In draft-agl-cfrgcurve-00 it appears that the ŒAA¹ term  is not consistent
with the josefsson text or the EFD that both use BB

A = x_2 + z_2
    AA = A^2
    B = x_2 - z_2
    BB = B^2
    E = AA - BB
    C = x_3 + z_3
    D = x_3 - z_3
    DA = D * A
    CB = C * B
    x_3 = (DA + CB)^2
    z_3 = x_1 * (DA - CB)^2
    x_2 = AA * BB
    z_2 = E * (AA + a24 * E)    <‹‹‹‹‹‹  versus E*(BB+a24*E)

Is this a typo? Š here¹s the EFD version for reference

A = X2+Z2
      AA = A^2
      B = X2-Z2
      BB = B^2
      E = AA-BB
      C = X3+Z3
      D = X3-Z3
      DA = D*A
      CB = C*B
      X5 = (DA+CB)^2
      Z5 = X1*(DA-CB)^2
      X4 = AA*BB
      Z4 = E*(BB+a24*E)             <‹‹‹‹‹  also uses ŒBB'

Hummm Š maybe it works anyway since AA and BB both have z2^2 term Š.
 Z4 = 4*x2*z2*(x2^2+A*x2*z2+z2^2))

Ether way it would be nice to match the EFD and the TLS definition

Paul

---

From: Adam Langley <[email-masked]>
Date: Sat, 10 Jan 2015 11:29:25 -0800

> with the josefsson text or the EFD that both use BB

Whether it works out or not, it's good to match EFD. I've updated the
draft in GitHub to match, thanks!

Cheers

AGL

-- 
Adam Langley [email-masked] https://www.imperialviolet.org

---

From: Samuel Neves <[email-masked]>
Date: Sat, 10 Jan 2015 20:38:28 +0000

> draft in GitHub to match, thanks!

It is not a typo: the formulas present in the draft are taken from Appendix B of the Curve25519 paper, where as the
formulas in EFD are taken from the 1987 Montgomery paper.

These formulas also differ in the particular a24 constant used: Curve25519 uses (A - 2)/4 = 121665, whereas Montgomery
uses (A + 2)/4 = 121666. Your fix is missing this second adjustment, if it is to match Montgomery's formulas.

Best regards,
Samuel Neves

---

From: Tanja Lange <[email-masked]>
Date: Sat, 10 Jan 2015 21:42:27 +0100

> draft in GitHub to match, thanks!
This is not a typo, it is using a different (better) definition
of the curve constant which is what the implementations use.

	Tanja

---

From: Adam Langley <[email-masked]>
Date: Sat, 10 Jan 2015 13:09:52 -0800

> of the curve constant which is what the implementations use.

Thanks both. I've replaced that change with a TODO to note why the
formula will differ from EFD.

Cheers

AGL

---

From: Tanja Lange <[email-masked]>
Date: Sat, 10 Jan 2015 22:29:27 +0100

> formula will differ from EFD.
Easier option: we'll add the set of formulas to the EFD. Should do that
anyways. Will happen some time after Wednesday.
	Tanja

---

From: Samuel Neves <[email-masked]>
Date: Sat, 10 Jan 2015 21:31:13 +0000

> of the curve constant which is what the implementations use.

Not trying to turn this into another pointless discussion, but the choice of a24 seems 50/50 in actual implementations.
From the current SUPERCOP version:

 - amd64-51: 121666
 - amd64-64: 121666
 - athlon: 121665
 - costigan-schwabe: 121666
 - donna: 121665
 - donna_c64: 121665
 - neon2: 121666
 - ref: 121665
 - ref10: 121666

All of these were written by experts. What makes 121665 better?

Best regards,
Samuel Neves

---

From: Tanja Lange <[email-masked]>
Date: Sat, 10 Jan 2015 23:07:15 +0100

> All of these were written by experts. What makes 121665 better?
Sorry, ignore the "(better)" part. I was thinking about the 
refence implementations being written with these formulas following
the Curve25519 paper but stand corrected.
	Tanja