Subject: [Cfrg] CFRG Curves document fixes

From: Thomas DuBuisson <[email-masked]>
Date: Mon, 11 May 2015 17:37:01 -0700

All,

I have produced an executable (Cryptol) specification of the Turner
draft and now the cfrg-curves document.  In doing so I believe I have
found a bug; the division optimization is only valid for 25519, if I
understand correctly.  The offending text:

```
Return x_2 * (z_2^(p - 2))
```

appears as field division in my reference implementation.

As a matter of full disclosure: my specification "passes the tests" in
that the Curve25519 passes 7.1 and 8.X while 448 passes section 7.1
vectors but not 8.X (ECDH).  I will investigate the failure when time
allows, though if someone wishes to confirm this KAT is correct I
certainly would not object.

I'd be happy to answer any questions about the Cryptol implementation
if that interests folks.

Cheers,
Thomas

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 12 May 2015 08:14:02 +0300

> appears as field division in my reference implementation.

I think the formula above is correct for all GF(p) (except for producing
0 for 0, which is actually desirable to handle z=0 right).

> certainly would not object.

I tried running through KAT with my own implementation:
- [PASS] KAT Curve25519 DHF #1
- [PASS] KAT Curve25519 DHF #2
- [PASS] KAT Curve25519 ECDH Alice public
- [PASS] KAT Curve25519 ECDH Bob public
- [PASS]     Curve25519 ECDH consistancy[1]
- [PASS] KAT Curve25519 ECDH Shared secret
- [PASS] KAT Curve448 DHF #1
- [PASS] KAT Curve448 DHF #2
- [PASS] KAT Curve448 ECDH Alice public
- [PASS] KAT Curve448 ECDH Bob public
- [PASS]     Curve448 ECDH consistancy[1]
- [FAIL] KAT Curve448 ECDH Shared secret

Was that KAT Curve448 ECDH Shared secret the KAT you saw failing?
Any others failed for you?

[1] Where ECDH consistency means the consistency conditions:
- DHF(a, G) = DHF_base(a)
- DHF(b, G) = DHF_base(b)
- DHF(a, B) = DHF(b, A)

(My implementation does have different faster algorithm for standard
basepoint).

-Ilari

---

From: Mike Hamburg <[email-masked]>
Date: Tue, 12 May 2015 10:27:40 -0700

I dunno how I managed to typo this, since I was doing it in SAGE. Do you 
get

07fff4181ac6cc95ec1c16a94a0f74d12da232ce40a77552281d282b
b60c0b56fd2464c335543936521c24403085d59a449a5037514a879d

Cheers,
-- Mike

On 05/11/2015 10:14 PM, Ilari Liusvaara wrote:
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 12 May 2015 20:32:07 +0300

On Tue, May 12, 2015 at 10:27:40AM -0700, Mike Hamburg wrote:
> I dunno how I managed to typo this, since I was doing it in SAGE. Do you get
> 

Matches what I get.

-Ilari

---

From: Thomas DuBuisson <[email-masked]>
Date: Tue, 12 May 2015 10:38:21 -0700

That value for 448 ECDH matches what I get as well.

With respect to field division: div a b == mul a (pow b (p - 2)), this
isn't immediately obvious to me and my implementation disagrees, which
could mean one of many things.  If this is a known fact then feel free
to ignore that "bug", it wouldn't be my first false positive.

Thomas

---

From: Thomas DuBuisson <[email-masked]>
Date: Tue, 12 May 2015 10:53:50 -0700

Ah, one of my primitives was hard-coded for 256 bit words so I now see
the division implementation in the specification is successful.

Sorry for the noise, and I'm happy to see the KAT simply seems to be
wrong according to three separate implementations.

-Thomas

---

From: Mike Hamburg <[email-masked]>
Date: Tue, 12 May 2015 10:58:59 -0700

Yeah, 1/b = b^(|F|-2) for any nonzero b in any finite field F, because 
the multiplicative group of the field has order |F|-1.  By a theorem of 
Legendre (I think?) the order of every element divides the order of the 
group, so that b^(|F|-1) = 1 if b != 0, so b^(|F|-2) = 1/b.

Cheers,
-- Mike

---

From: Michael Hamburg <[email-masked]>
Date: Tue, 12 May 2015 13:08:57 -0700

Dan Brown says: Lagrange, not Legendre.  Thanks.

> On May 12, 2015, at 10:58 AM, Mike Hamburg <[email-masked]> wrote:
> 
> Yeah, 1/b = b^(|F|-2) for any nonzero b in any finite field F, because the multiplicative group of the field has order |F|-1.  By a theorem of Legendre (I think?) the order of every element divides the order of the group, so that b^(|F|-1) = 1 if b != 0, so b^(|F|-2) = 1/b.
> 
> Cheers,
> -- Mike
>