Merged support for Curve25519
diff --git a/ChangeLog b/ChangeLog
index 27a6eab..84115d4 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -5,6 +5,7 @@
* EC key generation support in gen_key app
* Support for adhering to client ciphersuite order preference
(POLARSSL_SSL_SRV_RESPECT_CLIENT_PREFERENCE)
+ * Support for Curve25519
Changes
* gen_prime() speedup
@@ -15,6 +16,7 @@
* Split off curves from ecp.c into ecp_curves.c
Bugfix
+ * Fixed bug in mpi_set_bit() on platforms where t_uint is wider than int
* Fixed X.509 hostname comparison (with non-regular characters)
* SSL now gracefully handles missing RNG
* Missing defines / cases for RSA_PSK key exchange
diff --git a/include/polarssl/bignum.h b/include/polarssl/bignum.h
index d98dce9..df17b12 100644
--- a/include/polarssl/bignum.h
+++ b/include/polarssl/bignum.h
@@ -236,11 +236,10 @@
*
* \param X MPI to conditionally assign to
* \param Y Value to be assigned
- * \param assign 1: perform the assignment, 0: leave X untouched
+ * \param assign 1: perform the assignment, 0: keep X's original value
*
* \return 0 if successful,
* POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed,
- * POLARSSL_ERR_MPI_BAD_INPUT_DATA if assing is not 0 or 1
*
* \note This function is equivalent to
* if( assign ) mpi_copy( X, Y );
@@ -252,6 +251,25 @@
int mpi_safe_cond_assign( mpi *X, const mpi *Y, unsigned char assign );
/**
+ * \brief Safe conditional swap X <-> Y if swap is 1
+ *
+ * \param X First mpi value
+ * \param Y Second mpi value
+ * \param assign 1: perform the swap, 0: keep X and Y's original values
+ *
+ * \return 0 if successful,
+ * POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed,
+ *
+ * \note This function is equivalent to
+ * if( assign ) mpi_swap( X, Y );
+ * except that it avoids leaking any information about whether
+ * the assignment was done or not (the above code may leak
+ * information through branch prediction and/or memory access
+ * patterns analysis).
+ */
+int mpi_safe_cond_swap( mpi *X, mpi *Y, unsigned char assign );
+
+/**
* \brief Set value from integer
*
* \param X MPI to set
diff --git a/include/polarssl/config.h b/include/polarssl/config.h
index bdd40af..0b76f08 100644
--- a/include/polarssl/config.h
+++ b/include/polarssl/config.h
@@ -248,6 +248,10 @@
#define POLARSSL_ECP_DP_BP256R1_ENABLED
#define POLARSSL_ECP_DP_BP384R1_ENABLED
#define POLARSSL_ECP_DP_BP512R1_ENABLED
+//#define POLARSSL_ECP_DP_M221_ENABLED // Not implemented yet!
+#define POLARSSL_ECP_DP_M255_ENABLED
+//#define POLARSSL_ECP_DP_M383_ENABLED // Not implemented yet!
+//#define POLARSSL_ECP_DP_M511_ENABLED // Not implemented yet!
/**
* \def POLARSSL_ECP_NIST_OPTIM
diff --git a/include/polarssl/ecp.h b/include/polarssl/ecp.h
index c0f5079..a1a37af 100644
--- a/include/polarssl/ecp.h
+++ b/include/polarssl/ecp.h
@@ -64,10 +64,16 @@
POLARSSL_ECP_DP_BP256R1, /*!< 256-bits Brainpool curve */
POLARSSL_ECP_DP_BP384R1, /*!< 384-bits Brainpool curve */
POLARSSL_ECP_DP_BP512R1, /*!< 512-bits Brainpool curve */
+ POLARSSL_ECP_DP_M221, /*!< (not implemented yet) */
+ POLARSSL_ECP_DP_M255, /*!< Curve25519 */
+ POLARSSL_ECP_DP_M383, /*!< (not implemented yet) */
+ POLARSSL_ECP_DP_M511, /*!< (not implemented yet) */
} ecp_group_id;
/**
- * Number of supported curves (plus one for NONE)
+ * Number of supported curves (plus one for NONE).
+ *
+ * (Montgomery curves excluded for now.)
*/
#define POLARSSL_ECP_DP_MAX 9
@@ -102,10 +108,16 @@
/**
* \brief ECP group structure
*
- * The curves we consider are defined by y^2 = x^3 + A x + B mod P,
- * and a generator for a large subgroup of order N is fixed.
+ * We consider two types of curves equations:
+ * 1. Short Weierstrass y^2 = x^3 + A x + B mod P (SEC1 + RFC 4492)
+ * 2. Montgomery, y^2 = x^3 + A x^2 + x mod P (M255 + draft)
+ * In both cases, a generator G for a prime-order subgroup is fixed. In the
+ * short weierstrass, this subgroup is actually the whole curve, and its
+ * cardinal is denoted by N.
*
- * pbits and nbits must be the size of P and N in bits.
+ * In the case of Montgomery curves, we don't store A but (A + 2) / 4 which is
+ * the quantity actualy used in the formulas. Also, nbits is not the size of N
+ * but the required size for private keys.
*
* If modp is NULL, reduction modulo P is done using a generic algorithm.
* Otherwise, it must point to a function that takes an mpi in the range
@@ -118,18 +130,18 @@
{
ecp_group_id id; /*!< internal group identifier */
mpi P; /*!< prime modulus of the base field */
- mpi A; /*!< linear term in the equation */
- mpi B; /*!< constant term in the equation */
- ecp_point G; /*!< generator of the subgroup used */
- mpi N; /*!< the order of G */
+ mpi A; /*!< 1. A in the equation, or 2. (A + 2) / 4 */
+ mpi B; /*!< 1. B in the equation, or 2. unused */
+ ecp_point G; /*!< generator of the (sub)group used */
+ mpi N; /*!< 1. the order of G, or 2. unused */
size_t pbits; /*!< number of bits in P */
- size_t nbits; /*!< number of bits in N */
- unsigned int h; /*!< cofactor (unused now: assume 1) */
+ size_t nbits; /*!< number of bits in 1. P, or 2. private keys */
+ unsigned int h; /*!< unused */
int (*modp)(mpi *); /*!< function for fast reduction mod P */
- int (*t_pre)(ecp_point *, void *); /*!< currently unused */
- int (*t_post)(ecp_point *, void *); /*!< currently unused */
- void *t_data; /*!< currently unused */
- ecp_point *T; /*!< pre-computed points for ecp_mul() */
+ int (*t_pre)(ecp_point *, void *); /*!< unused */
+ int (*t_post)(ecp_point *, void *); /*!< unused */
+ void *t_data; /*!< unused */
+ ecp_point *T; /*!< pre-computed points for ecp_mul_comb() */
size_t T_size; /*!< number for pre-computed points */
}
ecp_group;
@@ -438,6 +450,9 @@
*
* \return 0 if successful,
* POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
+ *
+ * \note This function does not support Montgomery curves, such as
+ * Curve25519.
*/
int ecp_add( const ecp_group *grp, ecp_point *R,
const ecp_point *P, const ecp_point *Q );
@@ -452,6 +467,9 @@
*
* \return 0 if successful,
* POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
+ *
+ * \note This function does not support Montgomery curves, such as
+ * Curve25519.
*/
int ecp_sub( const ecp_group *grp, ecp_point *R,
const ecp_point *P, const ecp_point *Q );
diff --git a/library/bignum.c b/library/bignum.c
index 945da17..dd5c0bf 100644
--- a/library/bignum.c
+++ b/library/bignum.c
@@ -214,16 +214,16 @@
int ret = 0;
size_t i;
- if( assign * ( 1 - assign ) != 0 )
- return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
+ /* make sure assign is 0 or 1 */
+ assign = ( assign != 0 );
- if( Y->n > X->n )
- MPI_CHK( mpi_grow( X, Y->n ) );
+ MPI_CHK( mpi_grow( X, Y->n ) );
- /* Do the conditional assign safely */
X->s = X->s * (1 - assign) + Y->s * assign;
+
for( i = 0; i < Y->n; i++ )
X->p[i] = X->p[i] * (1 - assign) + Y->p[i] * assign;
+
for( ; i < X->n; i++ )
X->p[i] *= (1 - assign);
@@ -232,6 +232,43 @@
}
/*
+ * Conditionally swap X and Y, without leaking information
+ * about whether the swap was made or not.
+ * Here it is not ok to simply swap the pointers, which whould lead to
+ * different memory access patterns when X and Y are used afterwards.
+ */
+int mpi_safe_cond_swap( mpi *X, mpi *Y, unsigned char swap )
+{
+ int ret, s;
+ size_t i;
+ t_uint tmp;
+
+ if( X == Y )
+ return( 0 );
+
+ /* make sure swap is 0 or 1 */
+ swap = ( swap != 0 );
+
+ MPI_CHK( mpi_grow( X, Y->n ) );
+ MPI_CHK( mpi_grow( Y, X->n ) );
+
+ s = X->s;
+ X->s = X->s * (1 - swap) + Y->s * swap;
+ Y->s = Y->s * (1 - swap) + s * swap;
+
+
+ for( i = 0; i < X->n; i++ )
+ {
+ tmp = X->p[i];
+ X->p[i] = X->p[i] * (1 - swap) + Y->p[i] * swap;
+ Y->p[i] = Y->p[i] * (1 - swap) + tmp * swap;
+ }
+
+cleanup:
+ return( ret );
+}
+
+/*
* Set value from integer
*/
int mpi_lset( mpi *X, t_sint z )
@@ -280,7 +317,8 @@
MPI_CHK( mpi_grow( X, off + 1 ) );
}
- X->p[off] = ( X->p[off] & ~( 0x01 << idx ) ) | ( val << idx );
+ X->p[off] &= ~( (t_uint) 0x01 << idx );
+ X->p[off] |= (t_uint) val << idx;
cleanup:
diff --git a/library/ecdsa.c b/library/ecdsa.c
index 13f394b..2072d55 100644
--- a/library/ecdsa.c
+++ b/library/ecdsa.c
@@ -59,6 +59,10 @@
ecp_point R;
mpi k, e;
+ /* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */
+ if( grp->N.p == NULL )
+ return( POLARSSL_ERR_ECP_BAD_INPUT_DATA );
+
ecp_point_init( &R );
mpi_init( &k );
mpi_init( &e );
@@ -129,6 +133,10 @@
ecp_point_init( &R ); ecp_point_init( &P );
mpi_init( &e ); mpi_init( &s_inv ); mpi_init( &u1 ); mpi_init( &u2 );
+ /* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */
+ if( grp->N.p == NULL )
+ return( POLARSSL_ERR_ECP_BAD_INPUT_DATA );
+
/*
* Step 1: make sure r and s are in range 1..n-1
*/
diff --git a/library/ecp.c b/library/ecp.c
index 8338b2c..02f1b61 100644
--- a/library/ecp.c
+++ b/library/ecp.c
@@ -31,6 +31,8 @@
* FIPS 186-3 http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf
* RFC 4492 for the related TLS structures and constants
*
+ * [M255] http://cr.yp.to/ecdh/curve25519-20060209.pdf
+ *
* [2] CORON, Jean-Sébastien. Resistance against differential power analysis
* for elliptic curve cryptosystems. In : Cryptographic Hardware and
* Embedded Systems. Springer Berlin Heidelberg, 1999. p. 292-302.
@@ -78,6 +80,34 @@
static unsigned long add_count, dbl_count, mul_count;
#endif
+#if defined(POLARSSL_ECP_DP_SECP192R1_ENABLED) || \
+ defined(POLARSSL_ECP_DP_SECP224R1_ENABLED) || \
+ defined(POLARSSL_ECP_DP_SECP256R1_ENABLED) || \
+ defined(POLARSSL_ECP_DP_SECP384R1_ENABLED) || \
+ defined(POLARSSL_ECP_DP_SECP521R1_ENABLED) || \
+ defined(POLARSSL_ECP_DP_BP256R1_ENABLED) || \
+ defined(POLARSSL_ECP_DP_BP384R1_ENABLED) || \
+ defined(POLARSSL_ECP_DP_BP512R1_ENABLED)
+#define POLARSSL_ECP_SHORT_WEIERSTRASS
+#endif
+
+#if defined(POLARSSL_ECP_DP_M221_ENABLED) || \
+ defined(POLARSSL_ECP_DP_M255_ENABLED) || \
+ defined(POLARSSL_ECP_DP_M383_ENABLED) || \
+ defined(POLARSSL_ECP_DP_M511_ENABLED)
+#define POLARSSL_ECP_MONTGOMERY
+#endif
+
+/*
+ * Curve types: internal for now, might be exposed later
+ */
+typedef enum
+{
+ POLARSSL_ECP_TYPE_NONE = 0,
+ POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS, /* y^2 = x^3 + a x + b */
+ POLARSSL_ECP_TYPE_MONTGOMERY, /* y^2 = x^3 + a x^2 + x */
+} ecp_curve_type;
+
/*
* List of supported curves:
* - internal ID
@@ -177,6 +207,20 @@
}
/*
+ * Get the type of a curve
+ */
+static inline ecp_curve_type ecp_get_type( const ecp_group *grp )
+{
+ if( grp->G.X.p == NULL )
+ return( POLARSSL_ECP_TYPE_NONE );
+
+ if( grp->G.Y.p == NULL )
+ return( POLARSSL_ECP_TYPE_MONTGOMERY );
+ else
+ return( POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS );
+}
+
+/*
* Initialize (the components of) a point
*/
void ecp_point_init( ecp_point *pt )
@@ -632,11 +676,20 @@
while( mpi_cmp_mpi( &N, &grp->P ) >= 0 ) \
MPI_CHK( mpi_sub_abs( &N, &N, &grp->P ) )
+#if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
+/*
+ * For curves in short Weierstrass form, we do all the internal operations in
+ * Jacobian coordinates.
+ *
+ * For multiplication, we'll use a comb method with coutermeasueres against
+ * SPA, hence timing attacks.
+ */
+
/*
* Normalize jacobian coordinates so that Z == 0 || Z == 1 (GECC 3.2.1)
* Cost: 1N := 1I + 3M + 1S
*/
-static int ecp_normalize( const ecp_group *grp, ecp_point *pt )
+static int ecp_normalize_jac( const ecp_group *grp, ecp_point *pt )
{
int ret;
mpi Zi, ZZi;
@@ -678,19 +731,19 @@
* Theory", Algorithm 10.3.4.)
*
* Warning: fails (returning an error) if one of the points is zero!
- * This should never happen, see choice of w in ecp_mul().
+ * This should never happen, see choice of w in ecp_mul_comb().
*
* Cost: 1N(t) := 1I + (6t - 3)M + 1S
*/
-static int ecp_normalize_many( const ecp_group *grp,
- ecp_point *T[], size_t t_len )
+static int ecp_normalize_jac_many( const ecp_group *grp,
+ ecp_point *T[], size_t t_len )
{
int ret;
size_t i;
mpi *c, u, Zi, ZZi;
if( t_len < 2 )
- return( ecp_normalize( grp, *T ) );
+ return( ecp_normalize_jac( grp, *T ) );
if( ( c = (mpi *) polarssl_malloc( t_len * sizeof( mpi ) ) ) == NULL )
return( POLARSSL_ERR_ECP_MALLOC_FAILED );
@@ -756,7 +809,7 @@
* Conditional point inversion: Q -> -Q = (Q.X, -Q.Y, Q.Z) without leak.
* "inv" must be 0 (don't invert) or 1 (invert) or the result will be invalid
*/
-static int ecp_safe_invert( const ecp_group *grp,
+static int ecp_safe_invert_jac( const ecp_group *grp,
ecp_point *Q,
unsigned char inv )
{
@@ -843,7 +896,7 @@
* but those of P don't need to. R is not normalized.
*
* Special cases: (1) P or Q is zero, (2) R is zero, (3) P == Q.
- * None of these cases can happen as intermediate step in ecp_mul():
+ * None of these cases can happen as intermediate step in ecp_mul_comb():
* - at each step, P, Q and R are multiples of the base point, the factor
* being less than its order, so none of them is zero;
* - Q is an odd multiple of the base point, P an even multiple,
@@ -929,15 +982,17 @@
/*
* Addition: R = P + Q, result's coordinates normalized
- * Cost: 1A + 1N = 1I + 11M + 4S
*/
int ecp_add( const ecp_group *grp, ecp_point *R,
const ecp_point *P, const ecp_point *Q )
{
int ret;
+ if( ecp_get_type( grp ) != POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
+ return( POLARSSL_ERR_ECP_FEATURE_UNAVAILABLE );
+
MPI_CHK( ecp_add_mixed( grp, R, P, Q ) );
- MPI_CHK( ecp_normalize( grp, R ) );
+ MPI_CHK( ecp_normalize_jac( grp, R ) );
cleanup:
return( ret );
@@ -945,7 +1000,6 @@
/*
* Subtraction: R = P - Q, result's coordinates normalized
- * Cost: 1A + 1N = 1I + 11M + 4S
*/
int ecp_sub( const ecp_group *grp, ecp_point *R,
const ecp_point *P, const ecp_point *Q )
@@ -955,13 +1009,16 @@
ecp_point_init( &mQ );
+ if( ecp_get_type( grp ) != POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
+ return( POLARSSL_ERR_ECP_FEATURE_UNAVAILABLE );
+
/* mQ = - Q */
ecp_copy( &mQ, Q );
if( mpi_cmp_int( &mQ.Y, 0 ) != 0 )
MPI_CHK( mpi_sub_mpi( &mQ.Y, &grp->P, &mQ.Y ) );
MPI_CHK( ecp_add_mixed( grp, R, P, &mQ ) );
- MPI_CHK( ecp_normalize( grp, R ) );
+ MPI_CHK( ecp_normalize_jac( grp, R ) );
cleanup:
ecp_point_free( &mQ );
@@ -972,11 +1029,11 @@
/*
* Randomize jacobian coordinates:
* (X, Y, Z) -> (l^2 X, l^3 Y, l Z) for random l
- * This is sort of the reverse operation of ecp_normalize().
+ * This is sort of the reverse operation of ecp_normalize_jac().
*
* This countermeasure was first suggested in [2].
*/
-static int ecp_randomize_coordinates( const ecp_group *grp, ecp_point *pt,
+static int ecp_randomize_jac( const ecp_group *grp, ecp_point *pt,
int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
{
int ret;
@@ -1115,7 +1172,7 @@
TT[k++] = cur;
}
- ecp_normalize_many( grp, TT, k );
+ ecp_normalize_jac_many( grp, TT, k );
/*
* Compute the remaining ones using the minimal number of additions
@@ -1132,7 +1189,7 @@
}
}
- ecp_normalize_many( grp, TT, k );
+ ecp_normalize_jac_many( grp, TT, k );
/*
* Post-precessing: reclaim some memory by
@@ -1175,7 +1232,7 @@
MPI_CHK( mpi_lset( &R->Z, 1 ) );
/* Safely invert result if i is "negative" */
- MPI_CHK( ecp_safe_invert( grp, R, i >> 7 ) );
+ MPI_CHK( ecp_safe_invert_jac( grp, R, i >> 7 ) );
cleanup:
return( ret );
@@ -1203,7 +1260,7 @@
i = d;
MPI_CHK( ecp_select_comb( grp, R, T, t_len, x[i] ) );
if( f_rng != 0 )
- MPI_CHK( ecp_randomize_coordinates( grp, R, f_rng, p_rng ) );
+ MPI_CHK( ecp_randomize_jac( grp, R, f_rng, p_rng ) );
while( i-- != 0 )
{
@@ -1219,11 +1276,13 @@
}
/*
- * Multiplication using the comb method
+ * Multiplication using the comb method,
+ * for curves in short Weierstrass form
*/
-int ecp_mul( ecp_group *grp, ecp_point *R,
- const mpi *m, const ecp_point *P,
- int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
+static int ecp_mul_comb( ecp_group *grp, ecp_point *R,
+ const mpi *m, const ecp_point *P,
+ int (*f_rng)(void *, unsigned char *, size_t),
+ void *p_rng )
{
int ret;
unsigned char w, m_is_odd, p_eq_g, pre_len, i;
@@ -1232,28 +1291,13 @@
ecp_point *T;
mpi M, mm;
- /*
- * Sanity checks (before we even initialize anything)
- */
- if( mpi_cmp_int( &P->Z, 1 ) != 0 ||
- mpi_get_bit( &grp->N, 0 ) != 1 )
- {
- return( POLARSSL_ERR_ECP_BAD_INPUT_DATA );
- }
-
- if( ( ret = ecp_check_privkey( grp, m ) ) != 0 )
- return( ret );
-
- /* We'll need this later, but do it now to possibly avoid checking P */
- p_eq_g = ( mpi_cmp_mpi( &P->Y, &grp->G.Y ) == 0 &&
- mpi_cmp_mpi( &P->X, &grp->G.X ) == 0 );
-
- if( ! p_eq_g && ( ret = ecp_check_pubkey( grp, P ) ) != 0 )
- return( ret );
-
mpi_init( &M );
mpi_init( &mm );
+ /* we need N to be odd to trnaform m in an odd number, check now */
+ if( mpi_get_bit( &grp->N, 0 ) != 1 )
+ return( POLARSSL_ERR_ECP_BAD_INPUT_DATA );
+
/*
* Minimize the number of multiplications, that is minimize
* 10 * d * w + 18 * 2^(w-1) + 11 * d + 7 * w, with d = ceil( nbits / w )
@@ -1265,6 +1309,8 @@
* If P == G, pre-compute a bit more, since this may be re-used later.
* Just adding one ups the cost of the first mul by at most 3%.
*/
+ p_eq_g = ( mpi_cmp_mpi( &P->Y, &grp->G.Y ) == 0 &&
+ mpi_cmp_mpi( &P->X, &grp->G.X ) == 0 );
if( p_eq_g )
w++;
@@ -1326,8 +1372,8 @@
/*
* Now get m * P from M * P and normalize it
*/
- MPI_CHK( ecp_safe_invert( grp, R, ! m_is_odd ) );
- MPI_CHK( ecp_normalize( grp, R ) );
+ MPI_CHK( ecp_safe_invert_jac( grp, R, ! m_is_odd ) );
+ MPI_CHK( ecp_normalize_jac( grp, R ) );
cleanup:
@@ -1347,23 +1393,228 @@
return( ret );
}
+#endif /* POLARSSL_ECP_SHORT_WEIERSTRASS */
+
+#if defined(POLARSSL_ECP_MONTGOMERY)
/*
- * Check that a point is valid as a public key (SEC1 3.2.3.1)
+ * For Montgomery curves, we do all the internal arithmetic in projective
+ * coordinates. Import/export of points uses only the x coordinates, which is
+ * internaly represented as X / Z.
+ *
+ * For scalar multiplication, we'll use a Montgomery ladder.
*/
-int ecp_check_pubkey( const ecp_group *grp, const ecp_point *pt )
+
+/*
+ * Normalize Montgomery x/z coordinates: X = X/Z, Z = 1
+ * Cost: 1M + 1I
+ */
+static int ecp_normalize_mxz( const ecp_group *grp, ecp_point *P )
+{
+ int ret;
+
+ MPI_CHK( mpi_inv_mod( &P->Z, &P->Z, &grp->P ) );
+ MPI_CHK( mpi_mul_mpi( &P->X, &P->X, &P->Z ) ); MOD_MUL( P->X );
+ MPI_CHK( mpi_lset( &P->Z, 1 ) );
+
+cleanup:
+ return( ret );
+}
+
+/*
+ * Randomize projective x/z coordinates:
+ * (X, Z) -> (l X, l Z) for random l
+ * This is sort of the reverse operation of ecp_normalize_mxz().
+ *
+ * This countermeasure was first suggested in [2].
+ * Cost: 2M
+ */
+static int ecp_randomize_mxz( const ecp_group *grp, ecp_point *P,
+ int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
+{
+ int ret;
+ mpi l;
+ size_t p_size = (grp->pbits + 7) / 8;
+ int count = 0;
+
+ mpi_init( &l );
+
+ /* Generate l such that 1 < l < p */
+ do
+ {
+ mpi_fill_random( &l, p_size, f_rng, p_rng );
+
+ while( mpi_cmp_mpi( &l, &grp->P ) >= 0 )
+ mpi_shift_r( &l, 1 );
+
+ if( count++ > 10 )
+ return( POLARSSL_ERR_ECP_RANDOM_FAILED );
+ }
+ while( mpi_cmp_int( &l, 1 ) <= 0 );
+
+ MPI_CHK( mpi_mul_mpi( &P->X, &P->X, &l ) ); MOD_MUL( P->X );
+ MPI_CHK( mpi_mul_mpi( &P->Z, &P->Z, &l ) ); MOD_MUL( P->Z );
+
+cleanup:
+ mpi_free( &l );
+
+ return( ret );
+}
+
+/*
+ * Double-and-add: R = 2P, S = P + Q, with d = X(P - Q),
+ * for Montgomery curves in x/z coordinates.
+ *
+ * http://www.hyperelliptic.org/EFD/g1p/auto-code/montgom/xz/ladder/mladd-1987-m.op3
+ * with
+ * d = X1
+ * P = (X2, Z2)
+ * Q = (X3, Z3)
+ * R = (X4, Z4)
+ * S = (X5, Z5)
+ * and eliminating temporary variables tO, ..., t4.
+ *
+ * Cost: 5M + 4S
+ */
+static int ecp_double_add_mxz( const ecp_group *grp,
+ ecp_point *R, ecp_point *S,
+ const ecp_point *P, const ecp_point *Q,
+ const mpi *d )
+{
+ int ret;
+ mpi A, AA, B, BB, E, C, D, DA, CB;
+
+ mpi_init( &A ); mpi_init( &AA ); mpi_init( &B );
+ mpi_init( &BB ); mpi_init( &E ); mpi_init( &C );
+ mpi_init( &D ); mpi_init( &DA ); mpi_init( &CB );
+
+ MPI_CHK( mpi_add_mpi( &A, &P->X, &P->Z ) ); MOD_ADD( A );
+ MPI_CHK( mpi_mul_mpi( &AA, &A, &A ) ); MOD_MUL( AA );
+ MPI_CHK( mpi_sub_mpi( &B, &P->X, &P->Z ) ); MOD_SUB( B );
+ MPI_CHK( mpi_mul_mpi( &BB, &B, &B ) ); MOD_MUL( BB );
+ MPI_CHK( mpi_sub_mpi( &E, &AA, &BB ) ); MOD_SUB( E );
+ MPI_CHK( mpi_add_mpi( &C, &Q->X, &Q->Z ) ); MOD_ADD( C );
+ MPI_CHK( mpi_sub_mpi( &D, &Q->X, &Q->Z ) ); MOD_SUB( D );
+ MPI_CHK( mpi_mul_mpi( &DA, &D, &A ) ); MOD_MUL( DA );
+ MPI_CHK( mpi_mul_mpi( &CB, &C, &B ) ); MOD_MUL( CB );
+ MPI_CHK( mpi_add_mpi( &S->X, &DA, &CB ) ); MOD_MUL( S->X );
+ MPI_CHK( mpi_mul_mpi( &S->X, &S->X, &S->X ) ); MOD_MUL( S->X );
+ MPI_CHK( mpi_sub_mpi( &S->Z, &DA, &CB ) ); MOD_SUB( S->Z );
+ MPI_CHK( mpi_mul_mpi( &S->Z, &S->Z, &S->Z ) ); MOD_MUL( S->Z );
+ MPI_CHK( mpi_mul_mpi( &S->Z, d, &S->Z ) ); MOD_MUL( S->Z );
+ MPI_CHK( mpi_mul_mpi( &R->X, &AA, &BB ) ); MOD_MUL( R->X );
+ MPI_CHK( mpi_mul_mpi( &R->Z, &grp->A, &E ) ); MOD_MUL( R->Z );
+ MPI_CHK( mpi_add_mpi( &R->Z, &BB, &R->Z ) ); MOD_ADD( R->Z );
+ MPI_CHK( mpi_mul_mpi( &R->Z, &E, &R->Z ) ); MOD_MUL( R->Z );
+
+cleanup:
+ mpi_free( &A ); mpi_free( &AA ); mpi_free( &B );
+ mpi_free( &BB ); mpi_free( &E ); mpi_free( &C );
+ mpi_free( &D ); mpi_free( &DA ); mpi_free( &CB );
+
+ return( ret );
+}
+
+/*
+ * Multiplication with Montgomery ladder in x/z coordinates,
+ * for curves in Montgomery form
+ */
+static int ecp_mul_mxz( ecp_group *grp, ecp_point *R,
+ const mpi *m, const ecp_point *P,
+ int (*f_rng)(void *, unsigned char *, size_t),
+ void *p_rng )
+{
+ int ret;
+ size_t i;
+ unsigned char b;
+ ecp_point RP;
+ mpi PX;
+
+ ecp_point_init( &RP ); mpi_init( &PX );
+
+ /* Save PX and read from P before writing to R, in case P == R */
+ mpi_copy( &PX, &P->X );
+ MPI_CHK( ecp_copy( &RP, P ) );
+
+ /* Set R to zero in modified x/z coordinates */
+ MPI_CHK( mpi_lset( &R->X, 1 ) );
+ MPI_CHK( mpi_lset( &R->Z, 0 ) );
+ mpi_free( &R->Y );
+
+ /* RP.X might be sligtly larger than P, so reduce it */
+ MOD_ADD( RP.X );
+
+ /* Randomize coordinates of the starting point */
+ if( f_rng != NULL )
+ MPI_CHK( ecp_randomize_mxz( grp, &RP, f_rng, p_rng ) );
+
+ /* Loop invariant: R = result so far, RP = R + P */
+ i = mpi_msb( m ); /* one past the (zero-based) most significant bit */
+ while( i-- > 0 )
+ {
+ b = mpi_get_bit( m, i );
+ /*
+ * if (b) R = 2R + P else R = 2R,
+ * which is:
+ * if (b) double_add( RP, R, RP, R )
+ * else double_add( R, RP, R, RP )
+ * but using safe conditional swaps to avoid leaks
+ */
+ MPI_CHK( mpi_safe_cond_swap( &R->X, &RP.X, b ) );
+ MPI_CHK( mpi_safe_cond_swap( &R->Z, &RP.Z, b ) );
+ MPI_CHK( ecp_double_add_mxz( grp, R, &RP, R, &RP, &PX ) );
+ MPI_CHK( mpi_safe_cond_swap( &R->X, &RP.X, b ) );
+ MPI_CHK( mpi_safe_cond_swap( &R->Z, &RP.Z, b ) );
+ }
+
+ MPI_CHK( ecp_normalize_mxz( grp, R ) );
+
+cleanup:
+ ecp_point_free( &RP ); mpi_free( &PX );
+
+ return( ret );
+}
+
+#endif /* POLARSSL_ECP_MONTGOMERY */
+
+/*
+ * Multiplication R = m * P
+ */
+int ecp_mul( ecp_group *grp, ecp_point *R,
+ const mpi *m, const ecp_point *P,
+ int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
+{
+ int ret;
+
+ /* Common sanity checks */
+ if( mpi_cmp_int( &P->Z, 1 ) != 0 )
+ return( POLARSSL_ERR_ECP_BAD_INPUT_DATA );
+
+ if( ( ret = ecp_check_privkey( grp, m ) ) != 0 ||
+ ( ret = ecp_check_pubkey( grp, P ) ) != 0 )
+ return( ret );
+
+#if defined(POLARSSL_ECP_MONTGOMERY)
+ if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY )
+ return( ecp_mul_mxz( grp, R, m, P, f_rng, p_rng ) );
+#endif
+#if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
+ if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
+ return( ecp_mul_comb( grp, R, m, P, f_rng, p_rng ) );
+#endif
+ return( POLARSSL_ERR_ECP_BAD_INPUT_DATA );
+}
+
+#if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
+/*
+ * Check that an affine point is valid as a public key,
+ * short weierstrass curves (SEC1 3.2.3.1)
+ */
+static int ecp_check_pubkey_sw( const ecp_group *grp, const ecp_point *pt )
{
int ret;
mpi YY, RHS;
- if( mpi_cmp_int( &pt->Z, 0 ) == 0 )
- return( POLARSSL_ERR_ECP_INVALID_KEY );
-
- /*
- * pt coordinates must be normalized for our checks
- */
- if( mpi_cmp_int( &pt->Z, 1 ) != 0 )
- return( POLARSSL_ERR_ECP_INVALID_KEY );
-
+ /* pt coordinates must be normalized for our checks */
if( mpi_cmp_int( &pt->X, 0 ) < 0 ||
mpi_cmp_int( &pt->Y, 0 ) < 0 ||
mpi_cmp_mpi( &pt->X, &grp->P ) >= 0 ||
@@ -1391,43 +1642,127 @@
return( ret );
}
+#endif /* POLARSSL_ECP_SHORT_WEIERSTRASS */
+
+#if defined(POLARSSL_ECP_MONTGOMERY)
/*
- * Check that an mpi is valid as a private key (SEC1 3.2)
+ * Check validity of a public key for Montgomery curves with x-only schemes
*/
-int ecp_check_privkey( const ecp_group *grp, const mpi *d )
+static int ecp_check_pubkey_mx( const ecp_group *grp, const ecp_point *pt )
{
- /* We want 1 <= d <= N-1 */
- if ( mpi_cmp_int( d, 1 ) < 0 || mpi_cmp_mpi( d, &grp->N ) >= 0 )
+ /* [M255 p. 5] Just check X is the correct number of bytes */
+ if( mpi_size( &pt->X ) > ( grp->nbits + 7 ) / 8 )
return( POLARSSL_ERR_ECP_INVALID_KEY );
return( 0 );
}
+#endif /* POLARSSL_ECP_MONTGOMERY */
/*
- * Generate a keypair (SEC1 3.2.1)
+ * Check that a point is valid as a public key
+ */
+int ecp_check_pubkey( const ecp_group *grp, const ecp_point *pt )
+{
+ /* Must use affine coordinates */
+ if( mpi_cmp_int( &pt->Z, 1 ) != 0 )
+ return( POLARSSL_ERR_ECP_INVALID_KEY );
+
+#if defined(POLARSSL_ECP_MONTGOMERY)
+ if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY )
+ return( ecp_check_pubkey_mx( grp, pt ) );
+#endif
+#if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
+ if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
+ return( ecp_check_pubkey_sw( grp, pt ) );
+#endif
+ return( POLARSSL_ERR_ECP_BAD_INPUT_DATA );
+}
+
+/*
+ * Check that an mpi is valid as a private key
+ */
+int ecp_check_privkey( const ecp_group *grp, const mpi *d )
+{
+#if defined(POLARSSL_ECP_MONTGOMERY)
+ if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY )
+ {
+ /* see [M255] page 5 */
+ if( mpi_get_bit( d, 0 ) != 0 ||
+ mpi_get_bit( d, 1 ) != 0 ||
+ mpi_get_bit( d, 2 ) != 0 ||
+ mpi_msb( d ) - 1 != grp->nbits ) /* mpi_msb is one-based! */
+ return( POLARSSL_ERR_ECP_INVALID_KEY );
+ else
+ return( 0 );
+ }
+#endif
+#if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
+ if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
+ {
+ /* see SEC1 3.2 */
+ if( mpi_cmp_int( d, 1 ) < 0 ||
+ mpi_cmp_mpi( d, &grp->N ) >= 0 )
+ return( POLARSSL_ERR_ECP_INVALID_KEY );
+ else
+ return( 0 );
+ }
+#endif
+
+ return( POLARSSL_ERR_ECP_BAD_INPUT_DATA );
+}
+
+/*
+ * Generate a keypair
*/
int ecp_gen_keypair( ecp_group *grp, mpi *d, ecp_point *Q,
int (*f_rng)(void *, unsigned char *, size_t),
void *p_rng )
{
- int count = 0;
size_t n_size = (grp->nbits + 7) / 8;
- /*
- * Generate d such that 1 <= n < N
- */
- do
+#if defined(POLARSSL_ECP_MONTGOMERY)
+ if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY )
{
+ /* [M225] page 5 */
+ size_t b;
+
mpi_fill_random( d, n_size, f_rng, p_rng );
- while( mpi_cmp_mpi( d, &grp->N ) >= 0 )
- mpi_shift_r( d, 1 );
+ /* Make sure the most significant bit is nbits */
+ b = mpi_msb( d ) - 1; /* mpi_msb is one-based */
+ if( b > grp->nbits )
+ mpi_shift_r( d, b - grp->nbits );
+ else
+ mpi_set_bit( d, grp->nbits, 1 );
- if( count++ > 10 )
- return( POLARSSL_ERR_ECP_RANDOM_FAILED );
+ /* Make sure the last three bits are unset */
+ mpi_set_bit( d, 0, 0 );
+ mpi_set_bit( d, 1, 0 );
+ mpi_set_bit( d, 2, 0 );
}
- while( mpi_cmp_int( d, 1 ) < 0 );
+ else
+#endif
+#if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
+ if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
+ {
+ /* SEC1 3.2.1: Generate d such that 1 <= n < N */
+ int count = 0;
+ do
+ {
+ mpi_fill_random( d, n_size, f_rng, p_rng );
+
+ while( mpi_cmp_mpi( d, &grp->N ) >= 0 )
+ mpi_shift_r( d, 1 );
+
+ if( count++ > 10 )
+ return( POLARSSL_ERR_ECP_RANDOM_FAILED );
+ }
+ while( mpi_cmp_int( d, 1 ) < 0 );
+ }
+ else
+#endif
+ return( POLARSSL_ERR_ECP_BAD_INPUT_DATA );
return( ecp_mul( grp, Q, d, &grp->G, f_rng, p_rng ) );
}
diff --git a/library/ecp_curves.c b/library/ecp_curves.c
index d3b1b4d..26d9e1e 100644
--- a/library/ecp_curves.c
+++ b/library/ecp_curves.c
@@ -322,16 +322,29 @@
#if defined(POLARSSL_ECP_NIST_OPTIM)
/* Forward declarations */
+#if defined(POLARSSL_ECP_DP_SECP192R1_ENABLED)
static int ecp_mod_p192( mpi * );
+#endif
+#if defined(POLARSSL_ECP_DP_SECP224R1_ENABLED)
static int ecp_mod_p224( mpi * );
+#endif
+#if defined(POLARSSL_ECP_DP_SECP256R1_ENABLED)
static int ecp_mod_p256( mpi * );
+#endif
+#if defined(POLARSSL_ECP_DP_SECP384R1_ENABLED)
static int ecp_mod_p384( mpi * );
+#endif
+#if defined(POLARSSL_ECP_DP_SECP521R1_ENABLED)
static int ecp_mod_p521( mpi * );
+#endif
+#if defined(POLARSSL_ECP_DP_M255_ENABLED)
+static int ecp_mod_p255( mpi * );
+#endif
#define NIST_MODP( P ) grp->modp = ecp_mod_ ## P;
#else
#define NIST_MODP( P )
-#endif
+#endif /* POLARSSL_ECP_NIST_OPTIM */
#define LOAD_GROUP( G ) ecp_group_read_binary( grp, \
G ## _p, sizeof( G ## _p ), \
@@ -342,10 +355,44 @@
G ## _n, sizeof( G ## _n ) )
/*
+ * Specialized function for creating the Curve25519 group
+ */
+static int ecp_use_curve25519( ecp_group *grp )
+{
+ int ret;
+
+ /* Actually ( A + 2 ) / 4 */
+ MPI_CHK( mpi_read_string( &grp->A, 16, "01DB42" ) );
+
+ /* P = 2^255 - 19 */
+ MPI_CHK( mpi_lset( &grp->P, 1 ) );
+ MPI_CHK( mpi_shift_l( &grp->P, 255 ) );
+ MPI_CHK( mpi_sub_int( &grp->P, &grp->P, 19 ) );
+ grp->pbits = mpi_msb( &grp->P );
+
+ /* Y intentionaly not set, since we use x/z coordinates.
+ * This is used as a marker to identify Montgomery curves! */
+ MPI_CHK( mpi_lset( &grp->G.X, 9 ) );
+ MPI_CHK( mpi_lset( &grp->G.Z, 1 ) );
+ mpi_free( &grp->G.Y );
+
+ /* Actually, the required msb for private keys */
+ grp->nbits = 254;
+
+cleanup:
+ if( ret != 0 )
+ ecp_group_free( grp );
+
+ return( ret );
+}
+
+/*
* Set a group using well-known domain parameters
*/
int ecp_use_known_dp( ecp_group *grp, ecp_group_id id )
{
+ ecp_group_free( grp );
+
grp->id = id;
switch( id )
@@ -395,6 +442,12 @@
return( LOAD_GROUP( brainpoolP512r1 ) );
#endif /* POLARSSL_ECP_DP_BP512R1_ENABLED */
+#if defined(POLARSSL_ECP_DP_M255_ENABLED)
+ case POLARSSL_ECP_DP_M255:
+ grp->modp = ecp_mod_p255;
+ return( ecp_use_curve25519( grp ) );
+#endif /* POLARSSL_ECP_DP_M255_ENABLED */
+
default:
ecp_group_free( grp );
return( POLARSSL_ERR_ECP_FEATURE_UNAVAILABLE );
@@ -804,4 +857,48 @@
#endif /* POLARSSL_ECP_NIST_OPTIM */
+#if defined(POLARSSL_ECP_DP_M255_ENABLED)
+
+/* Size of p255 in terms of t_uint */
+#define P255_WIDTH ( 255 / 8 / sizeof( t_uint ) + 1 )
+
+/*
+ * Fast quasi-reduction modulo p255 = 2^255 - 19
+ * Write N as A1 + 2^255 A1, return A0 + 19 * A1
+ */
+static int ecp_mod_p255( mpi *N )
+{
+ int ret;
+ size_t i;
+ mpi M;
+ t_uint Mp[P255_WIDTH + 2];
+
+ if( N->n < P255_WIDTH )
+ return( 0 );
+
+ /* M = A1 */
+ M.s = 1;
+ M.n = N->n - ( P255_WIDTH - 1 );
+ if( M.n > P255_WIDTH + 1 )
+ M.n = P255_WIDTH + 1;
+ M.p = Mp;
+ memset( Mp, 0, sizeof Mp );
+ memcpy( Mp, N->p + P255_WIDTH - 1, M.n * sizeof( t_uint ) );
+ MPI_CHK( mpi_shift_r( &M, 255 % ( 8 * sizeof( t_uint ) ) ) );
+ M.n++; /* Make room for multiplication by 19 */
+
+ /* N = A0 */
+ mpi_set_bit( N, 255, 0 );
+ for( i = P255_WIDTH; i < N->n; i++ )
+ N->p[i] = 0;
+
+ /* N = A0 + 19 * A1 */
+ MPI_CHK( mpi_mul_int( &M, &M, 19 ) );
+ MPI_CHK( mpi_add_abs( N, N, &M ) );
+
+cleanup:
+ return( ret );
+}
+#endif /* POLARSSL_ECP_DP_M255_ENABLED */
+
#endif
diff --git a/tests/suites/test_suite_ecp.data b/tests/suites/test_suite_ecp.data
index 17ad8aa..dcf8ed6 100644
--- a/tests/suites/test_suite_ecp.data
+++ b/tests/suites/test_suite_ecp.data
@@ -159,6 +159,12 @@
ECP small check pubkey #10
ecp_small_check_pub:10:25:1:POLARSSL_ERR_ECP_INVALID_KEY
+ECP check pubkey Montgomery #1 (too big)
+ecp_check_pub_mx:POLARSSL_ECP_DP_M255:"010000000000000000000000000000000000000000000000000000000000000000":POLARSSL_ERR_ECP_INVALID_KEY
+
+ECP check pubkey Montgomery #2 (biggest)
+ecp_check_pub_mx:POLARSSL_ECP_DP_M255:"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF":0
+
ECP write binary #0 (zero, bad format)
depends_on:POLARSSL_ECP_DP_SECP192R1_ENABLED
ecp_write_binary:POLARSSL_ECP_DP_SECP192R1:"01":"01":"00":POLARSSL_ECP_PF_UNKNOWN:"00":1:POLARSSL_ERR_ECP_BAD_INPUT_DATA
@@ -271,14 +277,58 @@
depends_on:POLARSSL_ECP_DP_SECP521R1_ENABLED
ecp_tls_write_read_group:POLARSSL_ECP_DP_SECP521R1
-ECP check privkey
+ECP check privkey #1 (short weierstrass, too small)
depends_on:POLARSSL_ECP_DP_SECP192R1_ENABLED
-ecp_check_privkey:POLARSSL_ECP_DP_SECP192R1
+ecp_check_privkey:POLARSSL_ECP_DP_SECP192R1:"00":POLARSSL_ERR_ECP_INVALID_KEY
+
+ECP check privkey #2 (short weierstrass, smallest)
+depends_on:POLARSSL_ECP_DP_SECP192R1_ENABLED
+ecp_check_privkey:POLARSSL_ECP_DP_SECP192R1:"01":0
+
+ECP check privkey #3 (short weierstrass, biggest)
+depends_on:POLARSSL_ECP_DP_SECP192R1_ENABLED
+ecp_check_privkey:POLARSSL_ECP_DP_SECP192R1:"FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22830":0
+
+ECP check privkey #4 (short weierstrass, too big)
+depends_on:POLARSSL_ECP_DP_SECP192R1_ENABLED
+ecp_check_privkey:POLARSSL_ECP_DP_SECP192R1:"FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831":POLARSSL_ERR_ECP_INVALID_KEY
+
+ECP check privkey #5 (montgomery, too big)
+depends_on:POLARSSL_ECP_DP_M255_ENABLED
+ecp_check_privkey:POLARSSL_ECP_DP_M255:"C000000000000000000000000000000000000000000000000000000000000000":POLARSSL_ERR_ECP_INVALID_KEY
+
+ECP check privkey #6 (montgomery, not big enough)
+depends_on:POLARSSL_ECP_DP_M255_ENABLED
+ecp_check_privkey:POLARSSL_ECP_DP_M255:"3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF0":POLARSSL_ERR_ECP_INVALID_KEY
+
+ECP check privkey #7 (montgomery, msb OK)
+depends_on:POLARSSL_ECP_DP_M255_ENABLED
+ecp_check_privkey:POLARSSL_ECP_DP_M255:"4000000000000000000000000000000000000000000000000000000000000000":0
+
+ECP check privkey #8 (montgomery, bit 0 set)
+depends_on:POLARSSL_ECP_DP_M255_ENABLED
+ecp_check_privkey:POLARSSL_ECP_DP_M255:"4000000000000000000000000000000000000000000000000000000000000001":POLARSSL_ERR_ECP_INVALID_KEY
+
+ECP check privkey #9 (montgomery, bit 1 set)
+depends_on:POLARSSL_ECP_DP_M255_ENABLED
+ecp_check_privkey:POLARSSL_ECP_DP_M255:"4000000000000000000000000000000000000000000000000000000000000002":POLARSSL_ERR_ECP_INVALID_KEY
+
+ECP check privkey #10 (montgomery, bit 2 set)
+depends_on:POLARSSL_ECP_DP_M255_ENABLED
+ecp_check_privkey:POLARSSL_ECP_DP_M255:"4000000000000000000000000000000000000000000000000000000000000004":POLARSSL_ERR_ECP_INVALID_KEY
+
+ECP check privkey #11 (montgomery, OK)
+depends_on:POLARSSL_ECP_DP_M255_ENABLED
+ecp_check_privkey:POLARSSL_ECP_DP_M255:"7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF8":0
ECP gen keypair
depends_on:POLARSSL_ECP_DP_SECP192R1_ENABLED
ecp_gen_keypair:POLARSSL_ECP_DP_SECP192R1
+ECP gen keypair
+depends_on:POLARSSL_ECP_DP_M255_ENABLED
+ecp_gen_keypair:POLARSSL_ECP_DP_M255
+
ECP gen keypair wrapper
depends_on:POLARSSL_ECP_DP_SECP192R1_ENABLED
ecp_gen_key:POLARSSL_ECP_DP_SECP192R1
@@ -367,5 +417,9 @@
depends_on:POLARSSL_ECP_DP_BP512R1_ENABLED
ecp_test_vect:POLARSSL_ECP_DP_BP512R1:"16302FF0DBBB5A8D733DAB7141C1B45ACBC8715939677F6A56850A38BD87BD59B09E80279609FF333EB9D4C061231FB26F92EEB04982A5F1D1764CAD57665422":"0A420517E406AAC0ACDCE90FCD71487718D3B953EFD7FBEC5F7F27E28C6149999397E91E029E06457DB2D3E640668B392C2A7E737A7F0BF04436D11640FD09FD":"72E6882E8DB28AAD36237CD25D580DB23783961C8DC52DFA2EC138AD472A0FCEF3887CF62B623B2A87DE5C588301EA3E5FC269B373B60724F5E82A6AD147FDE7":"230E18E1BCC88A362FA54E4EA3902009292F7F8033624FD471B5D8ACE49D12CFABBC19963DAB8E2F1EBA00BFFB29E4D72D13F2224562F405CB80503666B25429":"9D45F66DE5D67E2E6DB6E93A59CE0BB48106097FF78A081DE781CDB31FCE8CCBAAEA8DD4320C4119F1E9CD437A2EAB3731FA9668AB268D871DEDA55A5473199F":"2FDC313095BCDD5FB3A91636F07A959C8E86B5636A1E930E8396049CB481961D365CC11453A06C719835475B12CB52FC3C383BCE35E27EF194512B71876285FA":"A7927098655F1F9976FA50A9D566865DC530331846381C87256BAF3226244B76D36403C024D7BBF0AA0803EAFF405D3D24F11A9B5C0BEF679FE1454B21C4CD1F":"7DB71C3DEF63212841C463E881BDCF055523BD368240E6C3143BD8DEF8B3B3223B95E0F53082FF5E412F4222537A43DF1C6D25729DDB51620A832BE6A26680A2"
+ECP test vectors M255 aka Curve25519
+depends_on:POLARSSL_ECP_DP_M255_ENABLED
+ecp_test_vec_x:POLARSSL_ECP_DP_M255:"5AC99F33632E5A768DE7E81BF854C27C46E3FBF2ABBACD29EC4AFF517369C660":"057E23EA9F1CBE8A27168F6E696A791DE61DD3AF7ACD4EEACC6E7BA514FDA863":"47DC3D214174820E1154B49BC6CDB2ABD45EE95817055D255AA35831B70D3260":"6EB89DA91989AE37C7EAC7618D9E5C4951DBA1D73C285AE1CD26A855020EEF04":"61450CD98E36016B58776A897A9F0AEF738B99F09468B8D6B8511184D53494AB"
+
ECP selftest
ecp_selftest:
diff --git a/tests/suites/test_suite_ecp.function b/tests/suites/test_suite_ecp.function
index cb93e85..1f04d67 100644
--- a/tests/suites/test_suite_ecp.function
+++ b/tests/suites/test_suite_ecp.function
@@ -189,6 +189,27 @@
/* END_CASE */
/* BEGIN_CASE */
+void ecp_check_pub_mx( int grp_id, char *key_hex, int ret )
+{
+ ecp_group grp;
+ ecp_point P;
+
+ ecp_group_init( &grp );
+ ecp_point_init( &P );
+
+ TEST_ASSERT( ecp_use_known_dp( &grp, grp_id ) == 0 );
+
+ TEST_ASSERT( mpi_read_string( &P.X, 16, key_hex ) == 0 );
+ TEST_ASSERT( mpi_lset( &P.Z, 1 ) == 0 );
+
+ TEST_ASSERT( ecp_check_pubkey( &grp, &P ) == ret );
+
+ ecp_group_free( &grp );
+ ecp_point_free( &P );
+}
+/* END_CASE */
+
+/* BEGIN_CASE */
void ecp_test_vect( int id, char *dA_str, char *xA_str, char *yA_str,
char *dB_str, char *xB_str, char *yB_str, char *xZ_str,
char *yZ_str )
@@ -243,6 +264,56 @@
/* END_CASE */
/* BEGIN_CASE */
+void ecp_test_vec_x( int id, char *dA_hex, char *xA_hex,
+ char *dB_hex, char *xB_hex, char *xS_hex )
+{
+ ecp_group grp;
+ ecp_point R;
+ mpi dA, xA, dB, xB, xS;
+ rnd_pseudo_info rnd_info;
+
+ ecp_group_init( &grp ); ecp_point_init( &R );
+ mpi_init( &dA ); mpi_init( &xA );
+ mpi_init( &dB ); mpi_init( &xB );
+ mpi_init( &xS );
+ memset( &rnd_info, 0x00, sizeof( rnd_pseudo_info ) );
+
+ TEST_ASSERT( ecp_use_known_dp( &grp, id ) == 0 );
+
+ TEST_ASSERT( ecp_check_pubkey( &grp, &grp.G ) == 0 );
+
+ TEST_ASSERT( mpi_read_string( &dA, 16, dA_hex ) == 0 );
+ TEST_ASSERT( mpi_read_string( &dB, 16, dB_hex ) == 0 );
+ TEST_ASSERT( mpi_read_string( &xA, 16, xA_hex ) == 0 );
+ TEST_ASSERT( mpi_read_string( &xB, 16, xB_hex ) == 0 );
+ TEST_ASSERT( mpi_read_string( &xS, 16, xS_hex ) == 0 );
+
+ TEST_ASSERT( ecp_mul( &grp, &R, &dA, &grp.G,
+ &rnd_pseudo_rand, &rnd_info ) == 0 );
+ TEST_ASSERT( ecp_check_pubkey( &grp, &R ) == 0 );
+ TEST_ASSERT( mpi_cmp_mpi( &R.X, &xA ) == 0 );
+
+ TEST_ASSERT( ecp_mul( &grp, &R, &dB, &R,
+ &rnd_pseudo_rand, &rnd_info ) == 0 );
+ TEST_ASSERT( ecp_check_pubkey( &grp, &R ) == 0 );
+ TEST_ASSERT( mpi_cmp_mpi( &R.X, &xS ) == 0 );
+
+ TEST_ASSERT( ecp_mul( &grp, &R, &dB, &grp.G, NULL, NULL ) == 0 );
+ TEST_ASSERT( ecp_check_pubkey( &grp, &R ) == 0 );
+ TEST_ASSERT( mpi_cmp_mpi( &R.X, &xB ) == 0 );
+
+ TEST_ASSERT( ecp_mul( &grp, &R, &dA, &R, NULL, NULL ) == 0 );
+ TEST_ASSERT( ecp_check_pubkey( &grp, &R ) == 0 );
+ TEST_ASSERT( mpi_cmp_mpi( &R.X, &xS ) == 0 );
+
+ ecp_group_free( &grp ); ecp_point_free( &R );
+ mpi_free( &dA ); mpi_free( &xA );
+ mpi_free( &dB ); mpi_free( &xB );
+ mpi_free( &xS );
+}
+/* END_CASE */
+
+/* BEGIN_CASE */
void ecp_fast_mod( int id, char *N_str )
{
ecp_group grp;
@@ -490,7 +561,7 @@
/* END_CASE */
/* BEGIN_CASE */
-void ecp_check_privkey( int id )
+void ecp_check_privkey( int id, char *key_hex, int ret )
{
ecp_group grp;
mpi d;
@@ -499,12 +570,9 @@
mpi_init( &d );
TEST_ASSERT( ecp_use_known_dp( &grp, id ) == 0 );
+ TEST_ASSERT( mpi_read_string( &d, 16, key_hex ) == 0 );
- TEST_ASSERT( mpi_lset( &d, 0 ) == 0 );
- TEST_ASSERT( ecp_check_privkey( &grp, &d ) == POLARSSL_ERR_ECP_INVALID_KEY );
-
- TEST_ASSERT( mpi_copy( &d, &grp.N ) == 0 );
- TEST_ASSERT( ecp_check_privkey( &grp, &d ) == POLARSSL_ERR_ECP_INVALID_KEY );
+ TEST_ASSERT( ecp_check_privkey( &grp, &d ) == ret );
ecp_group_free( &grp );
mpi_free( &d );
diff --git a/tests/suites/test_suite_mpi.data b/tests/suites/test_suite_mpi.data
index b9e00f1..fdbef02 100644
--- a/tests/suites/test_suite_mpi.data
+++ b/tests/suites/test_suite_mpi.data
@@ -223,6 +223,24 @@
Test mpi_safe_cond_assign #6
mpi_safe_cond_assign:-1:"01":-1:"02"
+Test mpi_safe_cond_swap #1
+mpi_safe_cond_swap:+1:"01":+1:"02"
+
+Test mpi_safe_cond_swap #2
+mpi_safe_cond_swap:+1:"FF000000000000000001":+1:"02"
+
+Test mpi_safe_cond_swap #3
+mpi_safe_cond_swap:+1:"01":+1:"FF000000000000000002"
+
+Test mpi_safe_cond_swap #4
+mpi_safe_cond_swap:+1:"01":-1:"02"
+
+Test mpi_safe_cond_swap #5
+mpi_safe_cond_swap:-1:"01":+1:"02"
+
+Test mpi_safe_cond_swap #6
+mpi_safe_cond_swap:-1:"01":-1:"02"
+
Base test mpi_add_abs #1
mpi_add_abs:10:"12345678":10:"642531":10:"12988209"
@@ -665,6 +683,12 @@
Test bit set (Add above existing limbs with a 1)
mpi_set_bit:10:"49979687":80:1:10:"1208925819614629224685863"
+Test bit set (Bit index larger than 31 with a 0)
+mpi_set_bit:16:"FFFFFFFFFFFFFFFF":32:0:16:"FFFFFFFEFFFFFFFF"
+
+Test bit set (Bit index larger than 31 with a 1)
+mpi_set_bit:16:"00":32:1:16:"0100000000"
+
MPI Selftest
depends_on:POLARSSL_SELF_TEST
mpi_selftest:
diff --git a/tests/suites/test_suite_mpi.function b/tests/suites/test_suite_mpi.function
index 394cd33..620c368 100644
--- a/tests/suites/test_suite_mpi.function
+++ b/tests/suites/test_suite_mpi.function
@@ -332,6 +332,36 @@
/* END_CASE */
/* BEGIN_CASE */
+void mpi_safe_cond_swap( int x_sign, char *x_str,
+ int y_sign, char *y_str )
+{
+ mpi X, Y, XX, YY;
+
+ mpi_init( &X ); mpi_init( &Y );
+ mpi_init( &XX ); mpi_init( &YY );
+
+ TEST_ASSERT( mpi_read_string( &X, 16, x_str ) == 0 );
+ X.s = x_sign;
+ TEST_ASSERT( mpi_read_string( &Y, 16, y_str ) == 0 );
+ Y.s = y_sign;
+
+ TEST_ASSERT( mpi_copy( &XX, &X ) == 0 );
+ TEST_ASSERT( mpi_copy( &YY, &Y ) == 0 );
+
+ TEST_ASSERT( mpi_safe_cond_swap( &X, &Y, 0 ) == 0 );
+ TEST_ASSERT( mpi_cmp_mpi( &X, &XX ) == 0 );
+ TEST_ASSERT( mpi_cmp_mpi( &Y, &YY ) == 0 );
+
+ TEST_ASSERT( mpi_safe_cond_swap( &X, &Y, 1 ) == 0 );
+ TEST_ASSERT( mpi_cmp_mpi( &Y, &XX ) == 0 );
+ TEST_ASSERT( mpi_cmp_mpi( &X, &YY ) == 0 );
+
+ mpi_free( &X ); mpi_free( &Y );
+ mpi_free( &XX ); mpi_free( &YY );
+}
+/* END_CASE */
+
+/* BEGIN_CASE */
void mpi_swap( int input_X, int input_Y )
{
mpi X, Y, A;