Subject: [Cfrg] DJB's python script

From: Watson Ladd <[email-masked]>
Date: Tue, 21 Jul 2015 06:26:52 -0700

Dear all,
DJB has complained on Twitter about this link not going through, and I
don't see it, so I'll post it instead.

http://ed25519.cr.yp.to/cfrg/signatures.py

This demonstrates how similar most of the schemes are, and is a
reference implementation. He does mention some unclear choices: I hope
we can clear that up by Wednesday for all schemes.
Sincerely,
Watson Ladd

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 21 Jul 2015 16:36:16 +0300

> we can clear that up by Wednesday for all schemes.

Looks like my spec wasn't clear enough, it specifies "unsigned LEB128"
as lengths. Which is that "low 7 bits are little endian number, MSB
is set for all except last octet" (not 128-bit little-endian number).

I.e. something like:
input v: Integer
s = ""
while v > 128
	s = s + octet(128 + v % 128)
	v = v / 128;
end
s = s + octet(v)
return s

-Ilari

---

From: "Salz, Rich" <[email-masked]>
Date: Tue, 21 Jul 2015 13:39:21 +0000

> This demonstrates how similar most of the schemes are, and is a reference
> implementation.

This is really useful.  And an impressive feat of refactoring :)

---

From: Dan Brown <[email-masked]>
Date: Tue, 21 Jul 2015 14:06:35 +0000

Thanks for providing this link.

Some of the details in my ECDSA_CFRG proposal were described yesterday, and
weren't yet incorporated into the python script as of this morning.  So, I
can suggest some corresponding updates to script, if it helps.

For now, I'll just note that the function f _does not_ hash (as described in
python script).  Rather, it a point to a scalar integer multiplier, via a
byte string (and perhaps restricting to one coordinate).  This f is what
ECDSA does when it computes r from R, as r = f(R) = field_to_int(x-coord(R))
mod n.

The python script uses Curve25519.  If we're not aiming to support a generic
ECDSA verifier, then I would suggest f(P) to be decodeint(encodepoint(P)).
If one wants to retrofit to a generic ECDSA, then one needs to use the f
above for ECDSA and also select some Weierstrass representation for
Curve25519, which generally seems to an unpopular approach.

On the brief notation "f": I've used (and so did Neven, Smart, and
Warinschi):
http://eprint.iacr.org/2002/026 (also published in DCC)
http://eprint.iacr.org/2008/286 (no refereed publication)
Advances in ECC (London Math Society) chapter 2
http://www.neven.org/papers/schnorr.pdf
http://eprint.iacr.org/2015/169
http://eprint.iacr.org/2015/509

By the way, all these papers discuss math security arguments for signatures,
although they do not address implementation security.

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of Watson Ladd
> Sent: Tuesday, July 21, 2015 9:27 AM
> To: [email-masked]
> Subject: [Cfrg] DJB's python script
> 
> Dear all,
don't
> see it, so I'll post it instead.
> 
> implementation. He does mention some unclear choices: I hope we can clear
> that up by Wednesday for all schemes.
> Sincerely,
> Watson Ladd
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg