0
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – nsayer
    Commented Feb 23, 2023 at 19:43

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.