0
$\begingroup$

Mike Hamburg proposed the Ed448-Goldilocks curve and submitted a software implementation for it to the SUPERCOP project.

Below you can see that MH picked a generator (or base point) that has a y-coordinate equal to 19.

Why was this generator chosen?

(I would guess that points with y=0..18 are somehow not suitable and that y=19 is the first good point -- could someone confirm this?)

Confusingly, there are two other generators specified in MH's iacr eprint: one generator is from the original version of the paper, and the second is from an updated version. Both versions can be downloaded here. Those generators do not appear in the SUPERCOP sources.

$ cd supercop-20220506/crypto_sign/ed448goldilocks/64
$ grep -A 13 base_point magic.c
const struct affine_t goldilocks_base_point = {
#ifdef USE_NEON_PERM
    {{ 0xaed939f,0xc59d070,0xf0de840,0x5f065c3, 0xf4ba0c7,0xdf73324,0xc170033,0x3a6a26a,
       0x4c63d96,0x4609845,0xf3932d9,0x1b4faff, 0x6147eaa,0xa2692ff,0x9cecfa9,0x297ea0e
    }},
#else
    {{ U58LE(0xf0de840aed939f), U58LE(0xc170033f4ba0c7),
       U58LE(0xf3932d94c63d96), U58LE(0x9cecfa96147eaa),
       U58LE(0x5f065c3c59d070), U58LE(0x3a6a26adf73324),
       U58LE(0x1b4faff4609845), U58LE(0x297ea0ea2692ff)
    }},
#endif
    {{ 19 }}
};

Note that the SUPERCOP software appears to be an early version of MH's libdecaf library. However, the SUPERCOP package is somewhat easier to navigate since all relevant source files are together in one directory.

Improve this question
$\endgroup$
3
  • $\begingroup$ RFC 7748 Appendix A covers the generation algorithm for the parameters typically used here and may be illustrative for your particular question. $\endgroup$
    – bk2204
    Aug 18, 2022 at 1:40
  • $\begingroup$ Thanks for the pointer to RFC 7748. The method there for selecting a generator uses the Montgomery form, v^2 = u^3 + A*u^2 + u. It starts with u=1, computes v (if possible), and then checks if (u,v) has the desired properties; if not, then u is incremented and we try again. This process explains how the generators for Ed25519 and Ed448 in RFC 8032 were derived, but it does not explain the magic values in the SUPERCOP software. $\endgroup$
    – user61836
    Aug 19, 2022 at 2:24
  • $\begingroup$ If I could edit my previous comment, then I would change "Ed25519" to "edwards25519" and "Ed448" to "edwards448" since I was referring to the curves. Ed25519 and Ed448 refer to EdDSA variants. $\endgroup$
    – user61836
    Sep 9, 2022 at 18:47

1 Answer 1

Reset to default
0
$\begingroup$

My guess was correct. The point (Gx, 19) in the SUPERCOP package is a point with minimal y-coordinate such that

  1. it is on the curve edwards448 (i.e. on x^2+y^2 = 1 + dx^2y^2 with d=-39081), and
  2. it has large prime order (i.e. equal to 2^448 - 0x8335dc16...bb0d)

I was able to verify this by adapting the python code given in RFC 8032.

The next such point has y=21.

I'm not sure if there was a reason the search was done on the y-coordinate rather than the x-coordinate.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.