3
$\begingroup$

I'm using the Curve25519 code (from http://www.dlbeer.co.nz/oss/c25519.html), and trying to convert from a public signing key (Edwards form) to a public key-exchange key (Montgomery form). There's test code that does that, but it seems to extract the Y coordinate from the secret key, and if I had the secret key I wouldn't need to do this.

I'm a software developer, not a mathematician. I don't see how to go from a packed Ed25519 public key to the unpacked X and Y coordinates required for the conversion.

How can I split a packed Ed25519 public signing key into its X and Y coordinates?

I'm asking for the mathematical explanation and/or references to the functions in that package that will split the packed Ed25519 key into X and Y coordinates.

For reference, I've tried the upp function to unpack the public key, and the ed25519_try_unpack function. Both give the same (incorrect) value.

$\endgroup$
2
  • $\begingroup$ Why do you care about the second coordinate when you want to convert to a montgomery DH key, which is typically x-only? $\endgroup$ Sep 20, 2017 at 17:10
  • $\begingroup$ Hello, @CodesInChaos. I've looked at your implementation as well, but couldn't figure out what I needed to do from it. Anyway, the comment on the morph25519_e2m function is "Convert an Edwards Y to a Montgomery X (Edwards X is not used)". $\endgroup$
    – Head Geek
    Sep 20, 2017 at 20:13

1 Answer 1

4
$\begingroup$

tldr: Public and private points have the same EdDSA serialization formats (notwithstanding external wrappers around the serialized points such as PEM, PKCS#12, OpenSSH, etc.). Therefore, that library's ed25519_try_unpack should be able to be "ab"-used as a decompression algorithm for private points with no issue (especially if the keys' length in octets is the same).


The format in question is a slight variant on the "compressed" format of EC serialization from Standards for Efficient Cryptography 1, §2.3.3.

Compared to the above-linked standard EC point serialization, "Bernstein serialization":

  • Truncates $x$ (the first coordinate) during compression, rather than $y$.

  • Encodes the truncated coordinate trivially during compression. (This contrasts starkly with SEC 1, which maps the truncated coordinate through $0 \mapsto 2 ; 1 \mapsto 3$ before encoding.)

  • Encodes $y$ into 1 fewer bits than would be required to encode ${p}-{1}$; this saves a bit for free given that its highest bit will always be zero.

  • The concatenation of ${Y} \mathbin\Vert {X}$ is done bitwise, without padding each encoded bitstring along octet boundaries. (This allows the previous optimization to save an octet in the case of Ed25519.)

  • It lacks the header byte; compressed format is assumed. The encoded length is always $\lceil{{({{\lceil{\text{log2}{({p})}}\rceil}+{1}})}\div 8}\rceil$. Strings of length $0$ and ${\lceil{{\text{log2}{({p})}} \div 8}\rceil} \times {2}$ are defined as invalid encodings.
    This has the following consequences, both intentional security features for the context of EdDSA:

    • $\mathcal{O}$ (the point-at-infinity) has no representation.

    • Since compressed format is forced, points in $\mathbb{Z}_p^2 \setminus E$ (that is, "points-off-the-curve") have no representation; any attempt to encode such a value will yield the representation of a point in $E$ (*technically, in $E \setminus \mathcal{O}$.)


I'm a software developer, not a mathematician. I don't see how to go from a packed Ed25519 public key to the unpacked X and Y coordinates required for the conversion.

The problem is that the "compressed" serialization simply doesn't contain the whole $x$-coordinate, only its $\text{mod 2}$ parity:

The public key A is an octet encoding of the point $sB$, as follows:

First, encode the $y$ coordinate as a little-endian string of 32 octets. To form the encoding of the point $sB$, copy the least significant bit of the $x$ coordinate to the most significant bit of the final octet. (The most significant bit of the final octet is always $0$.) The result is the public key.

Thankfully, $x$ can be recovered given $y$, the least significant bit of $x$, and knowledge of the curve the point lies on. The demo/illustrative Python script published with the original Ed25519 paper includes a function xrecover that shows how to make this recovery. The authors of IETF RFC 8032, however, recommend a marginally more complicated process (slightly adapted for the format here):

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; denote this value $x_0$. The $y$ coordinate is recovered simply by clearing this bit. If the resulting value is $\geq p$, decoding fails.

To recover the $x$ coordinate, the curve equation implies $x^2 = {({y^2 - 1})}/{({d y^2 + 1})}\text{ mod }p$. The denominator is always non-zero mod $p$. Let $u = y^2 - 1$ and $v = d y^2 + 1$. To compute the square root of $u/v$, the first step is to compute the candidate root $\tilde{x} = {({u/v})}\text{^}{({{({p+3})}/8})}$. This can be done with the following trick, using a single modular exponentiation for both the inversion of $v$ and the square root: $$\tilde{x} = {({u/v})}^{{({p+3})}/8} = u v^3 {({u v^7})}^{{({p-5})}/8} \text{ mod } p$$

Again, there are three cases:

  1. If $v \tilde{x}^2 = u \text{ mod } p$, $\tilde{x}$ is a square root.
  2. If $v \tilde{x}^2 = -u \text{ mod } p$, set $\tilde{x} := 2^{({{({p-1})}/4})}x$, which is a square root.
  3. Otherwise, no square root exists modulo $p$, and decoding fails.

Finally, use the $x_0$ bit to select the right square root: If $\tilde{x} = 0$ and $x_0 = 1$, decoding fails. If $x_0 = \tilde{x} \text{ mod } 2$,set $x := \tilde{x}$; otherwise, set $x := p - \tilde{x}$. Return the decoded point $(x,y)$.


Worked raw example (since I assume you're using a different library after all these years) would be something like this, with code borrowed from the above RFC document:

# constants
P = 2 ** 255 - 19  # Finite field modulus
D = -121665 * pow(121666, -1, P)  # Twisted Edwards curve constant
SQRT_NEG1 = pow(2, (P-1)//4, P)  # Square root of P-1 in the field

def encode_publickey(scaled_B):
    "Serialize point to Bernstein compressed format"
    x, y = scaled_B
    A = bytearray(int.to_bytes(y, 32, 'little'))
    assert (A[-1] & 0x80) == 0
    A[-1] &= (0x80 * bool(x & 1))
    return bytes(A)

def decode_publickey(A):
    "Deserialize point from Bernstein compressed format"
    A = bytearray(A)
    x_0 = int(bool(A[-1] & 0x80))
    A[-1] &= ~(0x80)
    y = int.from_bytes(A, 'little')
    x = _recover_x(y, x_0)
    return x, y

def _recover_x(y, x_0):
    if y >= P:
        raise ValueError
    x2 = ((y*y-1) * pow(D*y*y+1, -1, P)) % P
    if x2 == 0:
        if x_0 != 0:
            raise ValueError
        return 0
    x = pow(x2, (P+3)//8, P)
    if x**2 % P != x2:
        x = x * SQRT_NEG1 % P
        if x**2 % P != x2:
            raise ValueError
    if (x & 1) != x_0:
        x = (-x) % P
    assert (1 + D * x**2 * y**2 + x**2 - y**2) % P == 0  # on curve
    return x
$\endgroup$
5
  • $\begingroup$ Question for actual mathematicians: is this recoverability a property of points on all Edwards curves, only points on twisted Edwards curves, a totally different subset of elliptic curves, all elliptic curves, or was it specially engineered as part of Ed25519's selection? $\endgroup$ Oct 17, 2022 at 16:50
  • $\begingroup$ Yes, this recovery is generally possible for elliptic curves. You're really just solving for the other coordinate using the curve equation, which is just a quadratic or cubic equation. Finding square roots and cube roots in a finite field have known simple methods. $\endgroup$
    – Myria
    Oct 31, 2022 at 19:34
  • $\begingroup$ I don't think that this statement is true: "$\mathcal{O}$ (the point-at-infinity) has no representation.". The byte string 01,00,00,...,00 decodes to x=0 y=1, which is Ed25519's infinity. $\endgroup$
    – Myria
    Oct 19, 2023 at 21:19
  • $\begingroup$ @Myria When I try to import that key, I don't get that point: Crypto.PublicKey.ECC.import_key('-----BEGIN PRIVATE KEY-----\nMC4CAQAwBQYDK2VwBCIEIAEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\n-----END PRIVATE KEY-----') seems to decode to x=0x3b4d073c80188b09594f9e0d6ad03a5e615e62b799660f795905c62b20b55a93, y=0x7cd43b685d06dfe696d6731b4d04b9ad95f08808291c959572dd1ddc0715ccce $\endgroup$ Feb 15 at 22:00
  • $\begingroup$ Ed25519 private keys are random 32 bytes that are hashed using SHA-512, then are used as the scalar for point-multiplying by the base point. It's encoded points that can represent $\mathcal{O}$ as a 01 byte followed by 00 bytes. Try using a public key instead of a private key; Ed25519 public keys are encoded points. $\endgroup$
    – Myria
    Feb 16 at 1:02

Your Answer

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

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