Score:0

EC: Can you derive Y from X for a public key?

vn flag

I'm reading through the EDHOC draft spec and they talk about passing just the X portion of the (ephemeral) public key across in message 1. I've only ever heard of EC public keys (in this case the curve is P-256, if it matters) having both an X and a Y. The implication is, I guess, that you can derive the Y from the X? Is this true? If so, how?

Score:2
my flag

The implication is, I guess, that you can derive the Y from the X? Is this true?

Well, for each valid $X$ value, there are two possible values for $Y$; it is easy to recover both.

And, for Diffie Hellman, it happens that we don't care which $Y$ value we pick (as the ultimate shared secret doesn't depend on which one); hence we can arbitrarily pick one.

If so, how?

Well, the underlying relation for P256 is:

$$Y^2 \equiv X^3 + aX + b \pmod p$$

(for constants $a, b, p$). Given that we know $X$, we can plug in that value and compute $X^3 + aX + b \bmod p$; that gives us the value of $Y^2$ (modulo $p$). And so, the only thing left to do is perform a modular square root.

And, that turns out to be easy; because $p \equiv 3 \bmod 4$, a modular square root value by perform by raising the value to the power $(p+1)/4$; hence one of the possible $Y$ values is:

$$Y = (X^3 + aX + b)^{(p+1)/4} \bmod p$$

(and, in case you're curious, the other value is $-Y = p-Y$)

One last warning: just because the above formula gives you a $Y$ value doesn't mean that $X$ is a valid coordinate - some (about half) of the $X$ values are illegal, and injecting such a value may lead to an attack. Fortunately, it is easy to check: take the $X, Y$ values you get and plug them into the relation $Y^2 = X^3 + aX + b \pmod p$ - if the two sides don't agree (modulo $p$), then the original $X$ value was illegal, and you can treat it as such.

nsayer avatar
vn flag
Thanks. I think posting here was a tactical error. I need to know how to do this in Java, and your theoretical answer is correct, but it is not what I need. That's my fault, though, and I thank you for the answer.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.