Subject: [Cfrg] draft-irtf-cfrg-spake2 edwards25519 M/N values

From: Greg Hudson <[email-masked]>
Date: Thu, 30 Nov 2017 13:19:13 -0500

I would like to see M/N values for edwards25519 added to
draft-irtf-cfrg-spake2.  This addition requires minor adjustments to the
text and Python code.  Combined with my suggestions from
https://www.ietf.org/mail-archive/web/cfrg/current/msg09370.html the
introductory text for the section should read:

   For each curve in the table below, we construct a string using the
   curve OID from [RFC5480] or its name, combined with the needed
   constant, for instance "1.3.132.0.35 point generation seed (M)" for
   P-512.  This string is turned into a series of blocks by hashing with
   SHA256, and hashing that output again to generate the next 32 bytes,
   and so on.  This pattern is repeated for each group and value, with
   the string modified appropriately.

   A byte string of length equal to that of an encoded group element is
   constructed by concatenating as many blocks as are required, starting
   from the first block, and truncating to the desired length.  The byte
   string is then formatted as required for the group.  In the case of
   Weierstrass curves, this means setting the first byte to 0x02 or 0x03
   depending on the low-order bit.  For [RFC7748] curves this means
   taking all the bytes as the representation of the group element.  The
   byte string is then interpreted as an element in the group.  If this
   interpretation yields a valid group element with the correct order
   (p), the byte string is the output.  Otherwise, the initial hash
   block is discarded and the process is repeated until a valid element
   is found.

The new M and N points are:

   For edwards25519:

   M =
   d048032c6ea0b6d697ddc2e86bda85a33adac920f1bf18e1b0c6d166a5cecdaf
   seed: edwards25519 point generation seed (M)

   N =
   d3bfb518f44f3430f29d0c92af503865a1ed3281dc69b35dd868ba85f886c4ab
   seed: edwards25519 point generation seed (N)

I would also like the draft to list the seed string for each point, as
included above.

The Python code should read:

   def canon_pointstr(s):
       return chr(ord(s[0]) & 1 | 2) + s[1:]

   def iterated_hash(seed, n):
       h = seed
       for i in xrange(n):
           h = SHA256.new(h).digest()
       return h

   def bighash(seed, start, sz):
       n = -(-sz // 32)
       hashes = [iterated_hash(seed, i) for i in xrange(start, start + n)]
       return ''.join(hashes)[:sz]

   def gen_point(seed, ec, order, need_canonicalization):
       for i in xrange(1, 1000):
           pointstr = bighash(seed, i, ec.nbytes_point())
           if need_canonicalization:
               pointstr = canon_pointstr(pointstr)
           try:
               p = ec.decode_point(pointstr)
               if p != ec.identity() and ec.mul(p, order) == ec.identity():
                   return pointstr, i
           except Exception:
               pass

(I will submit a pull request to Ben's github repository for the draft
with all of this.)