curve25519: Elligator 2 map_to_curve implementation Signed-off-by: Xiangfei Ding <xfding@google.com> Change-Id: I3cdcb0f6a8f6a2fe754013cee515f0466a6a6964 Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/101148 Reviewed-by: David Benjamin <davidben@google.com> Presubmit-BoringSSL-Verified: boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com <boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com>
diff --git a/build.json b/build.json index 1d991cf..b9a831c 100644 --- a/build.json +++ b/build.json
@@ -837,6 +837,7 @@ "crypto/constant_time_test.cc", "crypto/cpu_arm_linux_test.cc", "crypto/crypto_test.cc", + "crypto/curve25519/curve25519_test.cc", "crypto/curve25519/ed25519_test.cc", "crypto/curve25519/spake25519_test.cc", "crypto/curve25519/x25519_test.cc",
diff --git a/crypto/curve25519/curve25519.cc b/crypto/curve25519/curve25519.cc index 3133633..489c916 100644 --- a/crypto/curve25519/curve25519.cc +++ b/crypto/curve25519/curve25519.cc
@@ -22,6 +22,7 @@ #include <assert.h> #include <string.h> +#include <openssl/digest.h> #include <openssl/mem.h> #include <openssl/rand.h> #include <openssl/sha2.h> @@ -157,6 +158,8 @@ assert_fe(h->v); } +// fe_frombytes takes in a little-endian 255-bit number and decodes it into an +// `fe`. static void fe_frombytes(fe *h, const uint8_t s[32]) { uint8_t s_copy[32]; OPENSSL_memcpy(s_copy, s, 32); @@ -300,6 +303,19 @@ } } +// Replace (f,g) with (g,g) if b == 1; +// replace (f,g) with (f,g) if b == 0. +// +// Preconditions: b in {0,1}. +static void fe_cmov(fe *f, const fe *g, fe_limb_t b) { + b = 0 - b; + for (unsigned i = 0; i < FE_NUM_LIMBS; i++) { + fe_limb_t x = f->v[i] ^ g->v[i]; + x &= b; + f->v[i] ^= x; + } +} + // h = f static void fe_copy(fe *h, const fe *f) { OPENSSL_memmove(h, f, sizeof(fe)); } @@ -374,16 +390,22 @@ // return 0 if f == 0 // return 1 if f != 0 -static int fe_isnonzero(const fe_loose *f) { - fe tight; - fe_carry(&tight, f); +static int fe_isnonzero(const fe *f) { uint8_t s[32]; - fe_tobytes(s, &tight); + fe_tobytes(s, f); static const uint8_t zero[32] = {0}; return CRYPTO_memcmp(s, zero, sizeof(zero)) != 0; } +// return 0 if f == 0 +// return 1 if f != 0 +static int fe_isnonzero(const fe_loose *f) { + fe tight; + fe_carry(&tight, f); + return fe_isnonzero(&tight); +} + // return 1 if f is in {1,3,5,...,q-2} // return 0 if f is in {0,2,4,...,q-1} static int fe_isnegative(const fe *f) { @@ -2155,3 +2177,187 @@ fe_tobytes(out_public_value, &zminusy_inv); CONSTTIME_DECLASSIFY(out_public_value, 32); } + +static void fe_from_limb(fe *h, fe_limb_t val) { + fe_0(h); + h->v[0] = val; + assert_fe(h->v); +} + +// map_to_curve_elligator2 implements the straight-line Elligator 2 mapping +// for Curve25519 from RFC 9380, Appendix G.2.1. +// +// It maps a field element u to a Montgomery point (xn / xd, y / 1) on the curve +// t^2 = s^3 + 486662*s^2 + s. +static void map_to_curve_elligator2(fe *out_xMn, fe *out_xMd, fe *out_yMn, + const fe *u) { + fe one, J_fe, c2_fe; + fe_1(&one); + fe_from_limb(&J_fe, 486662); + // c2 = 2^((p + 3) / 8) mod (2^255 - 19) in little-endian. + constexpr static uint8_t kC2[32] = { + 0xb1, 0xa0, 0x0e, 0x4a, 0x27, 0x1b, 0xee, 0xc4, 0x78, 0xe4, 0x2f, + 0xad, 0x06, 0x18, 0x43, 0x2f, 0xa7, 0xd7, 0xfb, 0x3d, 0x99, 0x00, + 0x4d, 0x2b, 0x0b, 0xdf, 0xc1, 0x4f, 0x80, 0x24, 0x83, 0x2b}; + fe_frombytes(&c2_fe, kC2); + + // 1-2. tv1 = 2 * u^2 + fe tv1; + fe_sq2_tt(&tv1, u); + + // 3. xd = tv1 + 1 + fe_loose xd_loose; + fe_add(&xd_loose, &tv1, &one); + + // 4. x1n = -J + fe_loose x1n_loose; + fe_neg(&x1n_loose, &J_fe); + + // 5. tv2 = xd^2 + fe tv2; + fe_sq_tl(&tv2, &xd_loose); + + // 6. gxd = xd^3 + fe gxd; + fe_mul_ttl(&gxd, &tv2, &xd_loose); + + fe gx1; + { + fe_loose l_tmp; + // 7. gx1 = J * tv1 + fe_mul_ltt(&l_tmp, &J_fe, &tv1); + // 8. gx1 = gx1 * x1n + fe_mul_tll(&gx1, &l_tmp, &x1n_loose); + // 9. gx1 = gx1 + tv2 + fe_add(&l_tmp, &gx1, &tv2); + // 10. gx1 = gx1 * x1n + fe_mul_tll(&gx1, &l_tmp, &x1n_loose); + } + + fe tv3; + // 11. tv3 = gxd^2 + fe_sq_tt(&tv3, &gxd); + // 12. tv2 = tv3^2 + fe_sq_tt(&tv2, &tv3); + // 13. tv3 = tv3 * gxd + fe_mul_ttt(&tv3, &tv3, &gxd); + // 14. tv3 = tv3 * gx1 + fe_mul_ttt(&tv3, &tv3, &gx1); + // 15. tv2 = tv2 * tv3 + fe_mul_ttt(&tv2, &tv2, &tv3); + + // 16. y11 = tv2^c4 = (gx1 * gxd^7)^((p - 5) / 8) + fe y11; + fe_pow22523(&y11, &tv2); + // 17. y11 = y11 * tv3 + fe_mul_ttt(&y11, &y11, &tv3); + + // 18. y12 = y11 * c3 + fe y12; + fe_mul_ttt(&y12, &y11, &sqrtm1); + + // 19. tv2 = y11 ^ 2 + fe_sq_tt(&tv2, &y11); + // 20. tv2 = tv2 * gxd + fe_mul_ttt(&tv2, &tv2, &gxd); + // 21. e1 = tv2 == gx1 + fe_limb_t e1; + { + fe_loose l_tmp; + fe_sub(&l_tmp, &tv2, &gx1); + e1 = 1 - fe_isnonzero(&l_tmp); + } + + // 22. y1 = CMOV(y12, y11, e1) # If g(x1) is square, this is its sqrt + fe y1; + fe_copy(&y1, &y12); + fe_cmov(&y1, &y11, e1); + + // 23. x2n = x1n * tv1 + fe x2n; + fe_mul_ttl(&x2n, &tv1, &x1n_loose); + + // 24. y21 = y11 * u + fe y21; + fe_mul_ttt(&y21, &y11, u); + // 25. y21 = y21 * c2 + fe_mul_ttt(&y21, &y21, &c2_fe); + + // 26. y22 = y21 * c3 + fe y22; + fe_mul_ttt(&y22, &y21, &sqrtm1); + + // 27. gx2 = gx1 * tv1 # g(x2) = gx2 / gxd = 2 * u^2 * g(x1) + fe gx2; + fe_mul_ttt(&gx2, &gx1, &tv1); + + // 28. tv2 = y21^2 + fe_sq_tt(&tv2, &y21); + // 29. tv2 = tv2 * gxd + fe_mul_ttt(&tv2, &tv2, &gxd); + // 30. e2 = tv2 == gx2 + fe_limb_t e2; + { + fe_loose l_tmp; + fe_sub(&l_tmp, &tv2, &gx2); + e2 = 1 - fe_isnonzero(&l_tmp); + } + + // 31. y2 = CMOV(y22, y21, e2) # If g(x2) is square, this is its sqrt + fe y2; + fe_copy(&y2, &y22); + fe_cmov(&y2, &y21, e2); + + // 32. tv2 = y1^2 + fe_sq_tt(&tv2, &y1); + // 33. tv2 = tv2 * gxd + fe_mul_ttt(&tv2, &tv2, &gxd); + // 34. e3 = tv2 == gx1 + fe_limb_t e3; + { + fe_loose l_tmp; + fe_sub(&l_tmp, &tv2, &gx1); + e3 = 1 - fe_isnonzero(&l_tmp); + } + + fe xn, y; + // 35. xn = CMOV(x2n, x1n, e3) # If e3, x = x1, else x = x2 + // or xn = CMOV(x1n, x2n, 1 - e3) + fe_carry(&xn, &x1n_loose); + fe_cmov(&xn, &x2n, 1 - e3); + // 36. y = CMOV(y2, y1, e3) # If e3, y = y1, else y = y2 + fe_copy(&y, &y2); + fe_cmov(&y, &y1, e3); + + // 37. e4 = sgn0(y) == 1 # Fix sign of y + fe_limb_t e4 = fe_isnegative(&y); + fe negy; + { + fe_loose l_tmp; + fe_neg(&l_tmp, &y); + fe_carry(&negy, &l_tmp); + } + // 38. y = CMOV(y, -y, e3 XOR e4) + fe_cmov(&y, &negy, e3 ^ e4); + + // 39. return (xn, xd, y, /* 1 */) + fe_copy(out_xMn, &xn); + fe_carry(out_xMd, &xd_loose); + fe_copy(out_yMn, &y); +} + +void bssl::map_to_curve_curve25519_elligator2(uint8_t out_qx[32], + uint8_t out_qy[32], + const uint8_t u[32]) { + fe u_fe; + fe_frombytes(&u_fe, u); + + fe xMn, xMd, yMn; + map_to_curve_elligator2(&xMn, &xMd, &yMn, &u_fe); + + fe xMd_inv, qx; + fe_invert(&xMd_inv, &xMd); + fe_mul_ttt(&qx, &xMn, &xMd_inv); + fe_tobytes(out_qx, &qx); + fe_tobytes(out_qy, &yMn); +}
diff --git a/crypto/curve25519/curve25519_test.cc b/crypto/curve25519/curve25519_test.cc new file mode 100644 index 0000000..b308162 --- /dev/null +++ b/crypto/curve25519/curve25519_test.cc
@@ -0,0 +1,179 @@ +// Copyright 2026 The BoringSSL Authors +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include <limits.h> +#include <stdint.h> + +#include <gtest/gtest.h> + +#include <openssl/bn.h> +#include <openssl/curve25519.h> +#include <openssl/digest.h> +#include <openssl/mem.h> +#include <openssl/rand.h> + +#include "../test/test_util.h" +#include "internal.h" + +using namespace bssl; + +namespace { + +#if !defined(BORINGSSL_SHARED_LIBRARY) + +TEST(Curve25519Test, MapToCurveElligator2RFC9380) { + struct Elligator2Test { + // RFC 9380 big-endian hex strings + const char *u_hex; + const char *qx_hex; + const char *qy_hex; + }; + + const Elligator2Test kTests[] = { + // RFC 9380, Appendix J.4.1 (curve25519_XMD:SHA-512_ELL2_RO_) + // We include this because we are testing map_to_curve_elligator2 + {"005fe8a7b8fef0a16c105e6cadf5a6740b3365e18692a9c05bfbb4" + "d97f645a6a", + "36b4df0c864c64707cbf6cf36e9ee2c09a6cb93b28313c169be295" + "61bb904f98", + "6cd59d664fb58c66c892883cd0eb792e52055284dac3907dd756b4" + "5d15c3983d"}, + {"1347edbec6a2b5d8c02e058819819bee177077c9d10a4ce165aab0" + "fd0252261a", + "3fa114783a505c0b2b2fbeef0102853c0b494e7757f2a089d0daae" + "7ed9a0db2b", + "76c0fe7fec932aaafb8eefb42d9cbb32eb931158f469ff3050af15" + "cfdbbeff94"}, + {"49bed021c7a3748f09fa8cdfcac044089f7829d3531066ac9e74e0" + "994e05bc7d", + "16b3d86e056b7970fa00165f6f48d90b619ad618791661b7b5e1ec" + "78be10eac1", + "4ab256422d84c5120b278cbdfc4e1facc5baadffeccecf8ee9bf39" + "46106d50ca"}, + {"5c36525b663e63389d886105cee7ed712325d5a97e60e140aba7e2" + "ce5ae851b6", + "7ec29ddbf34539c40adfa98fcb39ec36368f47f30e8f888cc7e86f" + "4d46e0c264", + "10d1abc1cae2d34c06e247f2141ba897657fb39f1080d54f09ce0a" + "f128067c74"}, + {"6412b7485ba26d3d1b6c290a8e1435b2959f03721874939b21782d" + "f17323d160", + "71de3dadfe268872326c35ac512164850860567aea0e7325e6b91a" + "98f86533ad", + "26a08b6e9a18084c56f2147bf515414b9b63f1522e1b6c5649f7d4" + "b0324296ec"}, + {"24c7b46c1c6d9a21d32f5707be1380ab82db1054fde82865d5c9e3" + "d968f287b2", + "5704069021f61e41779e2ba6b932268316d6d2a6f064f997a22fef" + "16d1eaeaca", + "50483c7540f64fb4497619c050f2c7fe55454ec0f0e79870bb4430" + "2e34232210"}, + {"5e123990f11bbb5586613ffabdb58d47f64bb5f2fa115f8ea8df01" + "88e0c9e1b5", + "7a94d45a198fb5daa381f45f2619ab279744efdd8bd8ed587fc5b6" + "5d6cea1df0", + "67d44f85d376e64bb7d713585230cdbfafc8e2676f7568e0b6ee59" + "361116a6e1"}, + {"5e8553eb00438a0bb1e7faa59dec6d8087f9c8011e5fb8ed9df31c" + "b6c0d4ac19", + "30506fb7a32136694abd61b6113770270debe593027a968a01f271" + "e146e60c18", + "7eeee0e706b40c6b5174e551426a67f975ad5a977ee2f01e8e20a6" + "d612458c3b"}, + {"20f481e85da7a3bf60ac0fb11ed1d0558fc6f941b3ac5469aa8b56" + "ec883d6d7d", + "02d606e2699b918ee36f2818f2bc5013e437e673c9f9b9cdc15fd0" + "c5ee913970", + "29e9dc92297231ef211245db9e31767996c5625dfbf92e1c8107ef" + "887365de1e"}, + {"017d57fd257e9a78913999a23b52ca988157a81b09c5442501d07f" + "ed20869465", + "38920e9b988d1ab7449c0fa9a6058192c0c797bb3d42ac34572434" + "1a1aa98745", + "24dcc1be7c4d591d307e89049fd2ed30aae8911245a9d8554bf603" + "2e5aa40d3d"}, + // RFC 9380, Appendix J.4.2 (curve25519_XMD:SHA-512_ELL2_NU_) + {"608d892b641f0328523802a6603427c26e55e6f27e71a91a478148" + "d45b5093cd", + "51125222da5e763d97f3c10fcc92ea6860b9ccbbd2eb1285728f56" + "6721c1e65b", + "343d2204f812d3dfc5304a5808c6c0d81a903a5d228b342442aa3c" + "9ba5520a3d"}, + {"46f5b22494bfeaa7f232cc8d054be68561af50230234d7d1d63d1d" + "9abeca8da5", + "7d56d1e08cb0ccb92baf069c18c49bb5a0dcd927eff8dcf75ca921" + "ef7f3e6eeb", + "404d9a7dc25c9c05c44ab9a94590e7c3fe2dcec74533a0b24b188a" + "5d5dacf429"}, + {"235fe40c443766ce7e18111c33862d66c3b33267efa50d50f9e8e5" + "d252a40aaa", + "3fbe66b9c9883d79e8407150e7c2a1c8680bee496c62fabe4619a7" + "2b3cabe90f", + "08ec476147c9a0a3ff312d303dbbd076abb7551e5fce82b48ab14b" + "433f8d0a7b"}, + {"001e92a544463bda9bd04ddbe3d6eed248f82de32f522669efc5dd" + "ce95f46f5b", + "227e0bb89de700385d19ec40e857db6e6a3e634b1c32962f370d26" + "f84ff19683", + "5f86ff3851d262727326a32c1bf7655a03665830fa7f1b8b1e5a09" + "d85bc66e4a"}, + {"1a68a1af9f663592291af987203393f707305c7bac9c8d63d6a729" + "bdc553dc19", + "3bcd651ee54d5f7b6013898aab251ee8ecc0688166fce6e9548d38" + "472f6bd196", + "1bb36ad9197299f111b4ef21271c41f4b7ecf5543db8bb5931307e" + "bdb2eaa465"}, + }; + + for (const auto &t : kTests) { + std::vector<uint8_t> u_bytes, expected_qx, expected_qy; + ASSERT_TRUE(DecodeHex(&u_bytes, t.u_hex)); + ASSERT_TRUE(DecodeHex(&expected_qx, t.qx_hex)); + ASSERT_TRUE(DecodeHex(&expected_qy, t.qy_hex)); + ASSERT_EQ(u_bytes.size(), 32u); + ASSERT_EQ(expected_qx.size(), 32u); + ASSERT_EQ(expected_qy.size(), 32u); + + // RFC 9380 test vectors encode coordinates in big-endian hex, while + // Curve25519 serializes field elements in little-endian. + std::reverse(u_bytes.begin(), u_bytes.end()); + std::reverse(expected_qx.begin(), expected_qx.end()); + std::reverse(expected_qy.begin(), expected_qy.end()); + + uint8_t qx[32], qy[32]; + map_to_curve_curve25519_elligator2(qx, qy, u_bytes.data()); + EXPECT_EQ(Bytes(qx), Bytes(expected_qx)); + EXPECT_EQ(Bytes(qy), Bytes(expected_qy)); + } +} + +TEST(Curve25519Test, CPaceX25519GeneratorTest) { + // Test vector from draft-irtf-cfrg-cpace-21, Appendix B.1.1 + const uint8_t u_bytes[32] = {0x03, 0x99, 0x80, 0x87, 0xbd, 0xb1, 0xa2, 0x61, + 0x7b, 0xbe, 0x25, 0xef, 0x5a, 0x7c, 0x18, 0xcd, + 0x4f, 0x84, 0xf9, 0x02, 0x32, 0x87, 0x01, 0x79, + 0x09, 0x58, 0x75, 0x5e, 0xe4, 0xae, 0xd1, 0x53}; + const uint8_t expected_g[32] = { + 0xd0, 0x4b, 0xf6, 0xd4, 0x1f, 0x6a, 0x28, 0x96, 0x32, 0xa2, 0xe9, + 0x29, 0xfa, 0x29, 0xbe, 0xbd, 0x51, 0x09, 0x25, 0x12, 0xa7, 0x82, + 0x9f, 0xdd, 0xe7, 0xd3, 0x14, 0xb6, 0x2f, 0x05, 0xa7, 0x3f}; + + uint8_t g[32], v[32]; + map_to_curve_curve25519_elligator2(g, v, u_bytes); + EXPECT_EQ(Bytes(g), Bytes(expected_g)); +} + +#endif + +} // namespace
diff --git a/crypto/curve25519/internal.h b/crypto/curve25519/internal.h index 8e78185..6791b05 100644 --- a/crypto/curve25519/internal.h +++ b/crypto/curve25519/internal.h
@@ -146,6 +146,9 @@ spake2_state_key_generated, }; +void map_to_curve_curve25519_elligator2(uint8_t out_qx[32], uint8_t out_qy[32], + const uint8_t u[32]); + BSSL_NAMESPACE_END struct spake2_ctx_st {
diff --git a/gen/sources.bzl b/gen/sources.bzl index 437a52e..df92c3d 100644 --- a/gen/sources.bzl +++ b/gen/sources.bzl
@@ -764,6 +764,7 @@ "crypto/constant_time_test.cc", "crypto/cpu_arm_linux_test.cc", "crypto/crypto_test.cc", + "crypto/curve25519/curve25519_test.cc", "crypto/curve25519/ed25519_test.cc", "crypto/curve25519/spake25519_test.cc", "crypto/curve25519/x25519_test.cc",
diff --git a/gen/sources.cmake b/gen/sources.cmake index 9d8f10b..bc1f596 100644 --- a/gen/sources.cmake +++ b/gen/sources.cmake
@@ -792,6 +792,7 @@ crypto/constant_time_test.cc crypto/cpu_arm_linux_test.cc crypto/crypto_test.cc + crypto/curve25519/curve25519_test.cc crypto/curve25519/ed25519_test.cc crypto/curve25519/spake25519_test.cc crypto/curve25519/x25519_test.cc
diff --git a/gen/sources.gni b/gen/sources.gni index 475d665..7af3411 100644 --- a/gen/sources.gni +++ b/gen/sources.gni
@@ -764,6 +764,7 @@ "crypto/constant_time_test.cc", "crypto/cpu_arm_linux_test.cc", "crypto/crypto_test.cc", + "crypto/curve25519/curve25519_test.cc", "crypto/curve25519/ed25519_test.cc", "crypto/curve25519/spake25519_test.cc", "crypto/curve25519/x25519_test.cc",
diff --git a/gen/sources.json b/gen/sources.json index aa87ee5..3e01523 100644 --- a/gen/sources.json +++ b/gen/sources.json
@@ -745,6 +745,7 @@ "crypto/constant_time_test.cc", "crypto/cpu_arm_linux_test.cc", "crypto/crypto_test.cc", + "crypto/curve25519/curve25519_test.cc", "crypto/curve25519/ed25519_test.cc", "crypto/curve25519/spake25519_test.cc", "crypto/curve25519/x25519_test.cc",
diff --git a/gen/sources.mk b/gen/sources.mk index 3bb15fb..a15ade0 100644 --- a/gen/sources.mk +++ b/gen/sources.mk
@@ -751,6 +751,7 @@ crypto/constant_time_test.cc \ crypto/cpu_arm_linux_test.cc \ crypto/crypto_test.cc \ + crypto/curve25519/curve25519_test.cc \ crypto/curve25519/ed25519_test.cc \ crypto/curve25519/spake25519_test.cc \ crypto/curve25519/x25519_test.cc \