2
$\begingroup$

I am implementing a ECDH using Curve25519 to communicate two system. One system have library that use for weierstrass curve only, it can define with domain parameter like p, a, b, G_x, G_y. I have read and find that Curve25519 can converse to weierstrass, I can find that converse domain paramerter for Curve25519 here (https://tools.ietf.org/id/draft-ietf-lwig-curve-representations-02.html). After that, I need converse point from Curve25519 to weierstrass, I find the mapping is (u,v) -> (x, y) = (u + A/3, v) but I do not understand that. Example with base point of Curve25519, (u, v) = (0x9, 0x20ae19a1b8a086b4e01edd2c7748d14c923d4d7e6d7c61b229e9c5a27eced3d9), after converse in weierstrass, base point is (0x2aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaad245a, 0x20ae19a1b8a086b4e01edd2c7748d14c923d4d7e6d7c61b229e9c5a27eced3d9), with A = 486662, B = 1. That seem not correct with mapping, so is that operator devision is not normal division. What exactly I need to converse point in form Curve25519 to weierstrass curve, thank you.

$\endgroup$
1
2
$\begingroup$

I'm not sure what is your question, I'm assuming you are not understanding why the mapping gives that particular result...

In ECC, all computations are carried out in a finite field. For Curve25519, all computations are done modulo $p = 2^{255}-19$.

To compute $u + A/3$, the division by three is actually $A$ multiplied by the inverse of $3$ modulo $p$. This inverse is the value that, when multiplied by 3, given 1 modulo $p$. This inverse is 0x5555555555555555555555555555555555555555555555555555555555555549; you can check that if you multiply this by $3$ and compute the remainder of the division by $p$ it will give $1$. Carring out the rest of the computation (always reducing modulo $p$) will give the expected result 0x2aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaad245a.

The modular inverse can be computed using the extended Euclidean algorithm or using Euler's theorem (which is computing the exponentiation by $p-2$).

$\endgroup$
0
$\begingroup$

I am implementing a ECDH using Curve25519 to communicate two system. One system have library that use for weierstrass curve only, ...

Curve25519 is the underlaying curve designed for X25519 Diffie-Hellman function (details see RFC 7748), it's designed to be more easily to implement correctly than Weierstrass curves.

Curve25519 and secp256r1 (or any other SECG curves) are NOT designed to interoperate with each other, if you don't have support for one of them, use the other; or if both are missing what the other have, use finite-field Diffie-Hellman key exchange.

$\endgroup$
5
  • 1
    $\begingroup$ Yes, they are not designed to interact with each other however as I mentioned the weiertrass curve implement can use with all domain parameter and I find Curve25519 parameter when perform in weierstrass curve. So in theory, I can use the weierstrass parameter to perform Curve25519 operation right? I try to reuse that implement, is that possible? $\endgroup$
    – Tien Pham
    Dec 26 '19 at 7:04
  • $\begingroup$ It's possible, but no established software can do that at the moment. Most well-written libraries and programs are designed to work on pre-determined curves such as secp256r1, secp384r1, and secp521r1, they can't work on random curves you throw at them. Also, you can post a message to the author on Facebook ask about the motivation for drafting the document, the name is at the end of the draft you linked in the question, I doubt it achieves something non-trivially meaningful. $\endgroup$
    – DannyNiu
    Dec 26 '19 at 7:49
  • $\begingroup$ Yeah, I try something to test that. Thank for your answer. $\endgroup$
    – Tien Pham
    Dec 26 '19 at 7:53
  • $\begingroup$ There are some general-purpose libraries and hardware accelerators which can carry out ECC computations given the Weierstrass curve parameters, so it makes sense in those cases. $\endgroup$
    – Conrado
    Jan 25 '20 at 16:52
  • $\begingroup$ OpenSSL (except RedHat-nobbled builds) and Java (both the 'standard' Sun/Oracle/Open provider and the BouncyCastle provider) support arbitrary Weierstrass curves. 'Well-written' may be de gustibus, but those are indisputably established. $\endgroup$ Jan 27 '20 at 7:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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