Merge pull request #7989 from valeriosetti/issue7754
driver-only ECC: BN.PK testing
diff --git a/ChangeLog.d/improve-doc-on-ecp-curve-optimized-representation.txt b/ChangeLog.d/improve-doc-on-ecp-curve-optimized-representation.txt
new file mode 100644
index 0000000..8fdc588
--- /dev/null
+++ b/ChangeLog.d/improve-doc-on-ecp-curve-optimized-representation.txt
@@ -0,0 +1,3 @@
+Features
+ * The documentation of mbedtls_ecp_group now describes the optimized
+ representation of A for some curves. Fixes #8045.
diff --git a/include/mbedtls/ecp.h b/include/mbedtls/ecp.h
index 0e678a3..a89d4d2 100644
--- a/include/mbedtls/ecp.h
+++ b/include/mbedtls/ecp.h
@@ -197,6 +197,27 @@
* odd prime as mbedtls_ecp_mul() requires an odd number, and
* mbedtls_ecdsa_sign() requires that it is prime for blinding purposes.
*
+ * The default implementation only initializes \p A without setting it to the
+ * authentic value for curves with <code>A = -3</code>(SECP256R1, etc), in which
+ * case you need to load \p A by yourself when using domain parameters directly,
+ * for example:
+ * \code
+ * mbedtls_mpi_init(&A);
+ * mbedtls_ecp_group_init(&grp);
+ * CHECK_RETURN(mbedtls_ecp_group_load(&grp, grp_id));
+ * if (mbedtls_ecp_group_a_is_minus_3(&grp)) {
+ * CHECK_RETURN(mbedtls_mpi_sub_int(&A, &grp.P, 3));
+ * } else {
+ * CHECK_RETURN(mbedtls_mpi_copy(&A, &grp.A));
+ * }
+ *
+ * do_something_with_a(&A);
+ *
+ * cleanup:
+ * mbedtls_mpi_free(&A);
+ * mbedtls_ecp_group_free(&grp);
+ * \endcode
+ *
* For Montgomery curves, we do not store \p A, but <code>(A + 2) / 4</code>,
* which is the quantity used in the formulas. Additionally, \p nbits is
* not the size of \p N but the required size for private keys.
@@ -223,8 +244,11 @@
typedef struct mbedtls_ecp_group {
mbedtls_ecp_group_id id; /*!< An internal group identifier. */
mbedtls_mpi P; /*!< The prime modulus of the base field. */
- mbedtls_mpi A; /*!< For Short Weierstrass: \p A in the equation. For
- Montgomery curves: <code>(A + 2) / 4</code>. */
+ mbedtls_mpi A; /*!< For Short Weierstrass: \p A in the equation. Note that
+ \p A is not set to the authentic value in some cases.
+ Refer to detailed description of ::mbedtls_ecp_group if
+ using domain parameters in the structure.
+ For Montgomery curves: <code>(A + 2) / 4</code>. */
mbedtls_mpi B; /*!< For Short Weierstrass: \p B in the equation.
For Montgomery curves: unused. */
mbedtls_ecp_point G; /*!< The generator of the subgroup used. */
@@ -992,6 +1016,26 @@
#if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED)
/**
+ * \brief This function checks if domain parameter A of the curve is
+ * \c -3.
+ *
+ * \note This function is only defined for short Weierstrass curves.
+ * It may not be included in builds without any short
+ * Weierstrass curve.
+ *
+ * \param grp The ECP group to use.
+ * This must be initialized and have group parameters
+ * set, for example through mbedtls_ecp_group_load().
+ *
+ * \return \c 1 if <code>A = -3</code>.
+ * \return \c 0 Otherwise.
+ */
+static inline int mbedtls_ecp_group_a_is_minus_3(const mbedtls_ecp_group *grp)
+{
+ return grp->A.MBEDTLS_PRIVATE(p) == NULL;
+}
+
+/**
* \brief This function performs multiplication and addition of two
* points by integers: \p R = \p m * \p P + \p n * \p Q
*
diff --git a/library/bignum.c b/library/bignum.c
index f2a8641..f02b1ac 100644
--- a/library/bignum.c
+++ b/library/bignum.c
@@ -258,6 +258,10 @@
return (mbedtls_mpi_uint) 0 - (mbedtls_mpi_uint) z;
}
+/* Convert x to a sign, i.e. to 1, if x is positive, or -1, if x is negative.
+ * This looks awkward but generates smaller code than (x < 0 ? -1 : 1) */
+#define TO_SIGN(x) ((((mbedtls_mpi_uint) x) >> (biL - 1)) * -2 + 1)
+
/*
* Set value from integer
*/
@@ -270,7 +274,7 @@
memset(X->p, 0, X->n * ciL);
X->p[0] = mpi_sint_abs(z);
- X->s = (z < 0) ? -1 : 1;
+ X->s = TO_SIGN(z);
cleanup:
@@ -326,16 +330,35 @@
*/
size_t mbedtls_mpi_lsb(const mbedtls_mpi *X)
{
- size_t i, j, count = 0;
+ size_t i;
MBEDTLS_INTERNAL_VALIDATE_RET(X != NULL, 0);
+#if defined(__has_builtin)
+#if (MBEDTLS_MPI_UINT_MAX == UINT_MAX) && __has_builtin(__builtin_ctz)
+ #define mbedtls_mpi_uint_ctz __builtin_ctz
+#elif (MBEDTLS_MPI_UINT_MAX == ULONG_MAX) && __has_builtin(__builtin_ctzl)
+ #define mbedtls_mpi_uint_ctz __builtin_ctzl
+#elif (MBEDTLS_MPI_UINT_MAX == ULLONG_MAX) && __has_builtin(__builtin_ctzll)
+ #define mbedtls_mpi_uint_ctz __builtin_ctzll
+#endif
+#endif
+
+#if defined(mbedtls_mpi_uint_ctz)
for (i = 0; i < X->n; i++) {
- for (j = 0; j < biL; j++, count++) {
+ if (X->p[i] != 0) {
+ return i * biL + mbedtls_mpi_uint_ctz(X->p[i]);
+ }
+ }
+#else
+ size_t count = 0;
+ for (i = 0; i < X->n; i++) {
+ for (size_t j = 0; j < biL; j++, count++) {
if (((X->p[i] >> j) & 1) != 0) {
return count;
}
}
}
+#endif
return 0;
}
@@ -796,9 +819,8 @@
}
}
- if (i == 0 && j == 0) {
- return 0;
- }
+ /* If i == j == 0, i.e. abs(X) == abs(Y),
+ * we end up returning 0 at the end of the function. */
if (i > j) {
return 1;
@@ -880,7 +902,7 @@
MPI_VALIDATE_RET(X != NULL);
*p = mpi_sint_abs(z);
- Y.s = (z < 0) ? -1 : 1;
+ Y.s = TO_SIGN(z);
Y.n = 1;
Y.p = p;
@@ -1068,7 +1090,7 @@
MPI_VALIDATE_RET(A != NULL);
p[0] = mpi_sint_abs(b);
- B.s = (b < 0) ? -1 : 1;
+ B.s = TO_SIGN(b);
B.n = 1;
B.p = p;
@@ -1086,7 +1108,7 @@
MPI_VALIDATE_RET(A != NULL);
p[0] = mpi_sint_abs(b);
- B.s = (b < 0) ? -1 : 1;
+ B.s = TO_SIGN(b);
B.n = 1;
B.p = p;
@@ -1436,7 +1458,7 @@
MPI_VALIDATE_RET(A != NULL);
p[0] = mpi_sint_abs(b);
- B.s = (b < 0) ? -1 : 1;
+ B.s = TO_SIGN(b);
B.n = 1;
B.p = p;
diff --git a/library/bignum_core.c b/library/bignum_core.c
index 8bf819c..ae0b94a 100644
--- a/library/bignum_core.c
+++ b/library/bignum_core.c
@@ -686,16 +686,16 @@
static size_t exp_mod_get_window_size(size_t Ebits)
{
- size_t wsize = (Ebits > 671) ? 6 : (Ebits > 239) ? 5 :
- (Ebits > 79) ? 4 : 1;
-
-#if (MBEDTLS_MPI_WINDOW_SIZE < 6)
- if (wsize > MBEDTLS_MPI_WINDOW_SIZE) {
- wsize = MBEDTLS_MPI_WINDOW_SIZE;
- }
+#if MBEDTLS_MPI_WINDOW_SIZE >= 6
+ return (Ebits > 671) ? 6 : (Ebits > 239) ? 5 : (Ebits > 79) ? 4 : 1;
+#elif MBEDTLS_MPI_WINDOW_SIZE == 5
+ return (Ebits > 239) ? 5 : (Ebits > 79) ? 4 : 1;
+#elif MBEDTLS_MPI_WINDOW_SIZE > 1
+ return (Ebits > 79) ? MBEDTLS_MPI_WINDOW_SIZE : 1;
+#else
+ (void) Ebits;
+ return 1;
#endif
-
- return wsize;
}
size_t mbedtls_mpi_core_exp_mod_working_limbs(size_t AN_limbs, size_t E_limbs)
diff --git a/library/debug.c b/library/debug.c
index 56bc3f6..0983cb0 100644
--- a/library/debug.c
+++ b/library/debug.c
@@ -144,7 +144,6 @@
debug_send_line(ssl, level, file, line, str);
- idx = 0;
memset(txt, 0, sizeof(txt));
for (i = 0; i < len; i++) {
if (i >= 4096) {
@@ -202,17 +201,54 @@
}
#endif /* MBEDTLS_ECP_LIGHT */
-#if defined(MBEDTLS_BIGNUM_C)
#if defined(MBEDTLS_PK_USE_PSA_EC_DATA)
+static void mbedtls_debug_print_ec_coord(const mbedtls_ssl_context *ssl, int level,
+ const char *file, int line, const char *text,
+ const unsigned char *buf, size_t len)
+{
+ char str[DEBUG_BUF_SIZE];
+ size_t i, idx = 0;
+
+ mbedtls_snprintf(str + idx, sizeof(str) - idx, "value of '%s' (%u bits) is:\n",
+ text, (unsigned int) len * 8);
+
+ debug_send_line(ssl, level, file, line, str);
+
+ for (i = 0; i < len; i++) {
+ if (i >= 4096) {
+ break;
+ }
+
+ if (i % 16 == 0) {
+ if (i > 0) {
+ mbedtls_snprintf(str + idx, sizeof(str) - idx, "\n");
+ debug_send_line(ssl, level, file, line, str);
+
+ idx = 0;
+ }
+ }
+
+ idx += mbedtls_snprintf(str + idx, sizeof(str) - idx, " %02x",
+ (unsigned int) buf[i]);
+ }
+
+ if (len > 0) {
+ for (/* i = i */; i % 16 != 0; i++) {
+ idx += mbedtls_snprintf(str + idx, sizeof(str) - idx, " ");
+ }
+
+ mbedtls_snprintf(str + idx, sizeof(str) - idx, "\n");
+ debug_send_line(ssl, level, file, line, str);
+ }
+}
+
void mbedtls_debug_print_psa_ec(const mbedtls_ssl_context *ssl, int level,
const char *file, int line,
const char *text, const mbedtls_pk_context *pk)
{
char str[DEBUG_BUF_SIZE];
- mbedtls_mpi mpi;
- const uint8_t *mpi_start;
- size_t mpi_len;
- int ret;
+ const uint8_t *coord_start;
+ size_t coord_len;
if (NULL == ssl ||
NULL == ssl->conf ||
@@ -223,32 +259,21 @@
/* For the description of pk->pk_raw content please refer to the description
* psa_export_public_key() function. */
- mpi_len = (pk->pub_raw_len - 1)/2;
+ coord_len = (pk->pub_raw_len - 1)/2;
/* X coordinate */
- mbedtls_mpi_init(&mpi);
- mpi_start = pk->pub_raw + 1;
- ret = mbedtls_mpi_read_binary(&mpi, mpi_start, mpi_len);
- if (ret != 0) {
- return;
- }
+ coord_start = pk->pub_raw + 1;
mbedtls_snprintf(str, sizeof(str), "%s(X)", text);
- mbedtls_debug_print_mpi(ssl, level, file, line, str, &mpi);
- mbedtls_mpi_free(&mpi);
+ mbedtls_debug_print_ec_coord(ssl, level, file, line, str, coord_start, coord_len);
/* Y coordinate */
- mbedtls_mpi_init(&mpi);
- mpi_start = mpi_start + mpi_len;
- ret = mbedtls_mpi_read_binary(&mpi, mpi_start, mpi_len);
- if (ret != 0) {
- return;
- }
+ coord_start = coord_start + coord_len;
mbedtls_snprintf(str, sizeof(str), "%s(Y)", text);
- mbedtls_debug_print_mpi(ssl, level, file, line, str, &mpi);
- mbedtls_mpi_free(&mpi);
+ mbedtls_debug_print_ec_coord(ssl, level, file, line, str, coord_start, coord_len);
}
#endif /* MBEDTLS_PK_USE_PSA_EC_DATA */
+#if defined(MBEDTLS_BIGNUM_C)
void mbedtls_debug_print_mpi(const mbedtls_ssl_context *ssl, int level,
const char *file, int line,
const char *text, const mbedtls_mpi *X)
@@ -324,19 +349,21 @@
mbedtls_snprintf(name, sizeof(name), "%s%s", text, items[i].name);
name[sizeof(name) - 1] = '\0';
+#if defined(MBEDTLS_RSA_C)
if (items[i].type == MBEDTLS_PK_DEBUG_MPI) {
mbedtls_debug_print_mpi(ssl, level, file, line, name, items[i].value);
} else
+#endif /* MBEDTLS_RSA_C */
#if defined(MBEDTLS_ECP_LIGHT)
if (items[i].type == MBEDTLS_PK_DEBUG_ECP) {
mbedtls_debug_print_ecp(ssl, level, file, line, name, items[i].value);
} else
-#endif
+#endif /* MBEDTLS_ECP_LIGHT */
#if defined(MBEDTLS_PK_USE_PSA_EC_DATA)
if (items[i].type == MBEDTLS_PK_DEBUG_PSA_EC) {
mbedtls_debug_print_psa_ec(ssl, level, file, line, name, items[i].value);
} else
-#endif
+#endif /* MBEDTLS_PK_USE_PSA_EC_DATA */
{ debug_send_line(ssl, level, file, line,
"should not happen\n"); }
}
diff --git a/library/ecp.c b/library/ecp.c
index 870773c..f9b6672 100644
--- a/library/ecp.c
+++ b/library/ecp.c
@@ -1255,7 +1255,7 @@
MPI_ECP_SQR(rhs, X);
/* Special case for A = -3 */
- if (grp->A.p == NULL) {
+ if (mbedtls_ecp_group_a_is_minus_3(grp)) {
MPI_ECP_SUB_INT(rhs, rhs, 3);
} else {
MPI_ECP_ADD(rhs, rhs, &grp->A);
@@ -1526,7 +1526,7 @@
int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
/* Special case for A = -3 */
- if (grp->A.p == NULL) {
+ if (mbedtls_ecp_group_a_is_minus_3(grp)) {
/* tmp[0] <- M = 3(X + Z^2)(X - Z^2) */
MPI_ECP_SQR(&tmp[1], &P->Z);
MPI_ECP_ADD(&tmp[2], &P->X, &tmp[1]);