Rm multiplication using NAF
Comb method is at most 1% slower for random points,
and is way faster for fixed point (repeated).
diff --git a/include/polarssl/ecp.h b/include/polarssl/ecp.h
index e46dd63..3dfb311 100644
--- a/include/polarssl/ecp.h
+++ b/include/polarssl/ecp.h
@@ -476,14 +476,9 @@
* has very low overhead, it is recommended to always provide
* a non-NULL f_rng parameter when using secret inputs.
*/
-// Temporary, WIP
-int ecp_mul_wnaf( 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 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 );
-#define ecp_mul ecp_mul_comb
+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 );
/**
* \brief Check that a point is a valid public key on this curve
diff --git a/library/ecp.c b/library/ecp.c
index 0cefd0a..2dd95bb 100644
--- a/library/ecp.c
+++ b/library/ecp.c
@@ -1191,105 +1191,6 @@
}
/*
- * Compute a modified width-w non-adjacent form (NAF) of a number,
- * with a fixed pattern for resistance to simple timing attacks (even SPA),
- * see [1]. (The resulting multiplication algorithm can also been seen as a
- * modification of 2^w-ary multiplication, with signed coefficients, all of
- * them odd.)
- *
- * Input:
- * m must be an odd positive mpi less than w * k bits long
- * x must be an array of k elements
- * w must be less than a certain maximum (currently 8)
- *
- * The result is a sequence x[0], ..., x[k-1] with x[i] in the range
- * - 2^(width - 1) .. 2^(width - 1) - 1 such that
- * m = (2 * x[0] + 1) + 2^width * (2 * x[1] + 1) + ...
- * + 2^((k-1) * width) * (2 * x[k-1] + 1)
- *
- * Compared to "Algorithm SPA-resistant Width-w NAF with Odd Scalar"
- * p. 335 of the cited reference, here we return only u, not d_w since
- * it is known that the other d_w[j] will be 0. Moreover, the returned
- * string doesn't actually store u_i but x_i = u_i / 2 since it is known
- * that u_i is odd. Also, since we always select a positive value for d
- * mod 2^w, we don't need to check the sign of u[i-1] when the reference
- * does. Finally, there is an off-by-one error in the reference: the
- * last index should be k-1, not k.
- */
-static int ecp_w_naf_fixed( signed char x[], size_t k,
- unsigned char w, const mpi *m )
-{
- int ret;
- unsigned int i, u, mask, carry;
- mpi M;
-
- mpi_init( &M );
-
- MPI_CHK( mpi_copy( &M, m ) );
- mask = ( 1 << w ) - 1;
- carry = 1 << ( w - 1 );
-
- for( i = 0; i < k; i++ )
- {
- u = M.p[0] & mask;
-
- if( ( u & 1 ) == 0 && i > 0 )
- x[i - 1] -= carry;
-
- x[i] = u >> 1;
- mpi_shift_r( &M, w );
- }
-
- /*
- * We should have consumed all bits, unless the input value was too big
- */
- if( mpi_cmp_int( &M, 0 ) != 0 )
- ret = POLARSSL_ERR_ECP_BAD_INPUT_DATA;
-
-cleanup:
-
- mpi_free( &M );
-
- return( ret );
-}
-
-/*
- * Precompute odd multiples of P up to (2 * t_len - 1) P.
- * The table is filled with T[i] = (2 * i + 1) P.
- */
-static int ecp_precompute( const ecp_group *grp,
- ecp_point T[], size_t t_len,
- const ecp_point *P )
-{
- int ret;
- size_t i;
- ecp_point PP;
- ecp_point *TT[ 1 << ( POLARSSL_ECP_WINDOW_SIZE - 1 ) ];
-
- ecp_point_init( &PP );
-
- MPI_CHK( ecp_add( grp, &PP, P, P ) );
-
- MPI_CHK( ecp_copy( &T[0], P ) );
-
- for( i = 1; i < t_len; i++ )
- MPI_CHK( ecp_add_mixed( grp, &T[i], &T[i-1], &PP, +1 ) );
-
- /*
- * T[0] = P already has normalized coordinates, normalize others
- */
- for( i = 1; i < t_len; i++ )
- TT[i-1] = &T[i];
- MPI_CHK( ecp_normalize_many( grp, TT, t_len - 1 ) );
-
-cleanup:
-
- ecp_point_free( &PP );
-
- return( ret );
-}
-
-/*
* 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().
@@ -1335,192 +1236,6 @@
}
/*
- * Maximum length of the precomputed table
- */
-#define MAX_PRE_LEN ( 1 << (POLARSSL_ECP_WINDOW_SIZE - 1) )
-
-/*
- * Maximum length of the NAF: ceil( grp->nbits + 1 ) / w
- * (that is: grp->nbits / w + 1)
- * Allow p_bits + 1 bits in case M = grp->N + 1 is one bit longer than N.
- */
-#define MAX_NAF_LEN ( POLARSSL_ECP_MAX_BITS / 2 + 1 )
-
-/*
- * Integer multiplication: R = m * P
- *
- * Based on fixed-pattern width-w NAF, see comments of ecp_w_naf_fixed().
- *
- * This function executes a fixed number of operations for
- * random m in the range 0 .. 2^nbits - 1.
- *
- * As an additional countermeasure against potential timing attacks,
- * we randomize coordinates before each addition. This was suggested as a
- * countermeasure against DPA in 5.3 of [2] (with the obvious adaptation that
- * we use jacobian coordinates, not standard projective coordinates).
- */
-int ecp_mul_wnaf( 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;
- size_t pre_len = 1, naf_len, i, j;
- signed char naf[ MAX_NAF_LEN ];
- ecp_point Q, *T = NULL, S[2];
- mpi M;
-
- if( mpi_cmp_int( m, 0 ) < 0 || mpi_msb( m ) > grp->nbits )
- return( POLARSSL_ERR_ECP_BAD_INPUT_DATA );
-
- mpi_init( &M );
- ecp_point_init( &Q );
- ecp_point_init( &S[0] );
- ecp_point_init( &S[1] );
-
- /*
- * Check if P == G
- */
- p_eq_g = ( mpi_cmp_int( &P->Z, 1 ) == 0 &&
- mpi_cmp_mpi( &P->Y, &grp->G.Y ) == 0 &&
- mpi_cmp_mpi( &P->X, &grp->G.X ) == 0 );
-
- /*
- * If P == G, pre-compute a lot of points: this will be re-used later,
- * otherwise, choose window size depending on curve size
- */
- if( p_eq_g )
- w = POLARSSL_ECP_WINDOW_SIZE;
- else
- w = grp->nbits >= 512 ? 6 :
- grp->nbits >= 224 ? 5 :
- 4;
-
- /*
- * Make sure w is within the limits.
- * The last test ensures that none of the precomputed points is zero,
- * which wouldn't be handled correctly by ecp_normalize_many().
- * It is only useful for very small curves as used in the test suite.
- */
- if( w > POLARSSL_ECP_WINDOW_SIZE )
- w = POLARSSL_ECP_WINDOW_SIZE;
- if( w < 2 || w >= grp->nbits )
- w = 2;
-
- pre_len <<= ( w - 1 );
- naf_len = grp->nbits / w + 1;
-
- /*
- * Prepare precomputed points: if P == G we want to
- * use grp->T if already initialized, or initiliaze it.
- */
- if( ! p_eq_g || grp->T == NULL )
- {
- T = (ecp_point *) polarssl_malloc( pre_len * sizeof( ecp_point ) );
- if( T == NULL )
- {
- ret = POLARSSL_ERR_ECP_MALLOC_FAILED;
- goto cleanup;
- }
-
- for( i = 0; i < pre_len; i++ )
- ecp_point_init( &T[i] );
-
- MPI_CHK( ecp_precompute( grp, T, pre_len, P ) );
-
- if( p_eq_g )
- {
- grp->T = T;
- grp->T_size = pre_len;
- }
- }
- else
- {
- T = grp->T;
-
- /* Should never happen, but we want to be extra sure */
- if( pre_len != grp->T_size )
- {
- ret = POLARSSL_ERR_ECP_BAD_INPUT_DATA;
- goto cleanup;
- }
- }
-
- /*
- * Make sure M is odd (M = m + 1 or M = m + 2)
- * later we'll get m * P by subtracting P or 2 * P to M * P.
- */
- m_is_odd = ( mpi_get_bit( m, 0 ) == 1 );
-
- MPI_CHK( mpi_copy( &M, m ) );
- MPI_CHK( mpi_add_int( &M, &M, 1 + m_is_odd ) );
-
- /*
- * Compute the fixed-pattern NAF of M
- */
- MPI_CHK( ecp_w_naf_fixed( naf, naf_len, w, &M ) );
-
- /*
- * Compute M * P, using a variant of left-to-right 2^w-ary multiplication:
- * at each step we add (2 * naf[i] + 1) P, then multiply by 2^w.
- *
- * If naf[i] >= 0, we have (2 * naf[i] + 1) P == T[ naf[i] ]
- * Otherwise, (2 * naf[i] + 1) P == - ( 2 * ( - naf[i] - 1 ) + 1) P
- * == T[ - naf[i] - 1 ]
- */
- MPI_CHK( ecp_set_zero( &Q ) );
- i = naf_len - 1;
- while( 1 )
- {
- /* Countermeasure (see comments above) */
- if( f_rng != NULL )
- ecp_randomize_coordinates( grp, &Q, f_rng, p_rng );
-
- if( naf[i] < 0 )
- {
- MPI_CHK( ecp_add_mixed( grp, &Q, &Q, &T[ - naf[i] - 1 ], -1 ) );
- }
- else
- {
- MPI_CHK( ecp_add_mixed( grp, &Q, &Q, &T[ naf[i] ], +1 ) );
- }
-
- if( i == 0 )
- break;
- i--;
-
- for( j = 0; j < w; j++ )
- {
- MPI_CHK( ecp_double_jac( grp, &Q, &Q ) );
- }
- }
-
- /*
- * Now get m * P from M * P
- */
- MPI_CHK( ecp_copy( &S[0], P ) );
- MPI_CHK( ecp_add( grp, &S[1], P, P ) );
- MPI_CHK( ecp_sub( grp, R, &Q, &S[m_is_odd] ) );
-
-
-cleanup:
-
- if( T != NULL && ! p_eq_g )
- {
- for( i = 0; i < pre_len; i++ )
- ecp_point_free( &T[i] );
- polarssl_free( T );
- }
-
- ecp_point_free( &S[1] );
- ecp_point_free( &S[0] );
- ecp_point_free( &Q );
- mpi_free( &M );
-
- return( ret );
-}
-
-/*
* Check and define parameters used by the comb method (see below for details)
*/
#if POLARSSL_ECP_WINDOW_SIZE < 2 || POLARSSL_ECP_WINDOW_SIZE > 7
@@ -1714,9 +1429,9 @@
/*
* Multiplication using the comb method
*/
-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 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;
unsigned char w, m_is_odd, p_eq_g;