Why does Ed25519 scalar multiplication allow values larger than the subgroup order?

Question

The GeScalarMultBase function is documented like so. From the way it is documented we see that it expects a little-endian value and has a precondition that constrains the range it accepts.

// GeScalarMultBase computes h = a*B, where
//   a = a[0]+256*a[1]+...+256^31 a[31]
//   B is the Ed25519 base point (x,4/5) with x positive.
//
// Preconditions:
//   a[31] <= 127
func GeScalarMultBase(h *ExtendedGroupElement, a *[32]byte) {

My understanding of elliptic curves has me thinking that the range of accepted values for scalar point multiplication should be in [0, subgroup_order]. While it could accept larger values since $(n+x)G = xG \pmod n$ it would be wasteful computationally so I'd expect the function to constrain it to the subgroup order or always mod it before using it.

In Ed25519 the order constants are defined like so:

curve_order 2**255 - 19
subgroup_order 2**252 + 27742317777372353535851937790883648493

Comparing these to what that method documentation says:

# hex in little-endian
curve_order: 0xdefffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7
subgroup_order: 0xde3d5fc5a13621856dc97f2aed9fed4100000000000000000000000000000001
GeScalarMulBase states: a[31] <= 127 (0xf7)
curve_order[31]: 0xf7 (127)
subgroup_order[31]: 0x01 (16)

Since we are working in little-endian, byte 31 is the most significant byte and we see from the documentation that the function enforces it is less than 127, which maps to the curve order.

This seems to indicate it accepts values in the range of [0, curve_order] instead of my expectation of [0, subgroup_order].

Is my understanding of what's happening accurate? If so, is there a particular reason this allows values larger than the subgroup order?

Answer 1

My understanding of elliptic curves has me thinking that the range of accepted values for scalar point multiplication should be in [0, group_order].

Actually, that's not the case - the point multiplication $xG$ is well-defined for all integer values of $x$.

While it could accept larger values since $(n+x)G=xG$, it would be wasteful computationally so I'd expect the function to constrain it to the group order or always mod it before using it.

Well, cryptographically that would be valid, however that would allow a further "optimization" that Dan wanted to avoid allowing to well-meaning implementors.

If someone were to implement the point multiplication $xG$ in the straight-forward manner (where $x$ is a number between $0$ and $n$), they might notice that, some of the time, $x$ was fewer than 252 bits - in that case, they might be tempted to skip those iterations of the point multiplication logic (and so speed things up slightly). That might sound like a nice optimization, however that introduces a (small) timing leak (as the time taken depends on secret data), and Dan really wants to avoid any such leakage.

By ensuring that $x$ is a number between $2^{254}$ and $2^{254}+n$ (and thus is a fixed number of bits), any such optimization is far less straight-forward (and so far less likely to occur to our well-meaning implementator)