decoding a Ed25519 key per RFC8032

Question

RFC8032 Edwards-Curve Digital Signature Algorithm (EdDSA) 5.1.3 Decoding states the following:

Decoding a point, given as a 32-octet string, is a little more
complicated.

1. First, interpret the string as an integer in little-endian representation. Bit 255 of this number is the least significant bit of the x-coordinate and denote this value x_0. The y-coordinate is recovered simply by clearing this bit. If the resulting value is >= p, decoding fails.

My questions are...

1. 32 octets is 256 bits. I'm assuming the index of the first bit is 0 instead of 1, which would make 255 the last bit. So why not say that it's the last bit instead of the 255'th bit?

2. Quoting the previous section, "To form the encoding of the point, copy the least significant bit of the x-coordinate to the most significant bit of the final octet.". So to encode we set the most significant bit and to decode we look at the least significant bit? So we're not looking at the same bit? That doesn't make a lot of sense to me.

3. When you interpret the string as an integer I'm assuming you're supposed to interpret it in two's compliment? eg. where if the first bit is 1 then you assume that the number is negative? The RFC isn't at all clear imho..

Answer 1

I'm assuming the index of the first bit is 0 instead of 1, which would make 255 the last bit.

Yes. That's made clear by example at the end of section 2, showing bits numbered starting from 0. In this RFC the i'th bit really is the (i+1)^th bit when numbering things the way America does with floor levels and the way many others standards number bits. I accommodate diversity rather than fight it, that's coward but makes life easier.

---

When you interpret the string as an integer I'm assuming you're supposed to interpret it in two's compliment?

Sign comes after the decoding to integer. That same section 2 states that integers are non-negative and have a non-signed representation, and section 3.1 states how "negative" elements of GF(p) are encoded:

The encoding of GF(p) is used to define "negative" elements of GF(p): specifically, x is negative if the (b-1)-bit encoding of x is lexicographically larger than the (b-1)-bit encoding of -x.

My brain hurts parsing that: if $x$ is negative then the $(b-1)$-bit encoding of $x$ (which the statement seems to try to define) is undefined yet, making the definition at best self-referential, at worst preposterous. I get that "lexicographically" combined with little-endian implies that low-order bit matters most in the comparison made.

The Ed25519 paper has something on the tune of that part of the standard, with $\mathbf F_q$ where the standard has GF(p), followed by the helpful

If $q$ is an odd prime and the encoding is the little-endian representation of $\{0,1,\dots,q-1\}$ then the negative elements of $\mathbf F_q$ are $\{1,3,\dots,q-2\}$.

---

An element $x\pmod p$ of GF(p) is defined to be negative if and only if $((x\bmod p)\bmod 2)=1$ where the two-arguments operator $\bmod$ (recognizable by not having an opening parenthesis immediately on its left) produces non-negative integers less than its second argument; and that quantity $((x\bmod p)\bmod 2)$ is what's stored as a spare bit.

Thus in the question's quote and what follows, the first $(b-1)$ bits of the $b$-bit representation of point $(x,y)$ on the curve are $y$, little-endian, considered a non-negative integer; and the last bit (the high-order bit of the last byte) defines the sign of $x$. The method stated is enough to fully recover $y$ then $x$ as elements of GF(p), and thus the point.