Added fast mod_p192
diff --git a/library/ecp.c b/library/ecp.c
index 574b181..6ee8ff0 100644
--- a/library/ecp.c
+++ b/library/ecp.c
@@ -36,6 +36,7 @@
#if defined(POLARSSL_ECP_C)
#include "polarssl/ecp.h"
+#include <limits.h>
/*
* Initialize (the components of) a point
@@ -184,9 +185,83 @@
}
/*
+ * 192 bits in terms of t_uint
+ */
+#define P192_SIZE_INT ( 192 / CHAR_BIT / sizeof( t_uint ) )
+
+/*
+ * Table to get S1, S2, S3 of FIPS 186-3 D.2.1:
+ * -1 means let this chunk be 0
+ * a positive value i means A_i.
+ */
+#define P192_CHUNKS 3
+#define P192_CHUNK_CHAR ( 64 / CHAR_BIT )
+#define P192_CHUNK_INT ( P192_CHUNK_CHAR / sizeof( t_uint ) )
+
+const signed char p192_tbl[][P192_CHUNKS] = {
+ { -1, 3, 3 }, /* S1 */
+ { 4, 4, -1 }, /* S2 */
+ { 5, 5, 5 }, /* S3 */
+};
+
+/*
+ * Fast quasi-reduction modulo p192 (FIPS 186-3 D.2.1)
+ */
+static int ecp_mod_p192( mpi *N )
+{
+ int ret;
+ unsigned char i, j, offset;
+ signed char chunk;
+ mpi tmp, acc;
+ t_uint tmp_p[P192_SIZE_INT], acc_p[P192_SIZE_INT + 1];
+
+ tmp.s = 1;
+ tmp.n = sizeof( tmp_p ) / sizeof( tmp_p[0] );
+ tmp.p = tmp_p;
+
+ acc.s = 1;
+ acc.n = sizeof( acc_p ) / sizeof( acc_p[0] );
+ acc.p = acc_p;
+
+ MPI_CHK( mpi_grow( N, P192_SIZE_INT * 2 ) );
+
+ /*
+ * acc = T
+ */
+ memset( acc_p, 0, sizeof( acc_p ) );
+ memcpy( acc_p, N->p, P192_CHUNK_CHAR * P192_CHUNKS );
+
+ for( i = 0; i < sizeof( p192_tbl ) / sizeof( p192_tbl[0] ); i++)
+ {
+ /*
+ * tmp = S_i
+ */
+ memset( tmp_p, 0, sizeof( tmp_p ) );
+ for( j = 0, offset = P192_CHUNKS - 1; j < P192_CHUNKS; j++, offset-- )
+ {
+ chunk = p192_tbl[i][j];
+ if( chunk >= 0 )
+ memcpy( tmp_p + offset * P192_CHUNK_INT,
+ N->p + chunk * P192_CHUNK_INT,
+ P192_CHUNK_CHAR );
+ }
+
+ /*
+ * acc += tmp
+ */
+ MPI_CHK( mpi_add_abs( &acc, &acc, &tmp ) );
+ }
+
+ MPI_CHK( mpi_copy( N, &acc ) );
+
+cleanup:
+ return( ret );
+}
+
+/*
* Size of p521 in terms of t_uint
*/
-#define P521_SIZE_INT ( 521 / ( sizeof( t_uint ) << 3 ) + 1 )
+#define P521_SIZE_INT ( 521 / CHAR_BIT / sizeof( t_uint ) + 1 )
/*
* Bits to keep in the most significant t_uint
@@ -318,6 +393,8 @@
switch( index )
{
case POLARSSL_ECP_DP_SECP192R1:
+ grp->modp = ecp_mod_p192;
+ grp->pbits = 192;
return( ecp_group_read_string( grp, 16,
SECP192R1_P, SECP192R1_B,
SECP192R1_GX, SECP192R1_GY, SECP192R1_N ) );
diff --git a/tests/suites/test_suite_ecp.data b/tests/suites/test_suite_ecp.data
index 41d3145..188d558 100644
--- a/tests/suites/test_suite_ecp.data
+++ b/tests/suites/test_suite_ecp.data
@@ -64,6 +64,12 @@
ECP small multiplication #13
ecp_small_mul:13:1:0:0
+ECP mod p192 readable
+ecp_fast_mod:SECP192R1:"000000000000010500000000000001040000000000000103000000000000010200000000000001010000000000000100"
+
+ECP mod p192 random
+ecp_fast_mod:SECP192R1:"36CF96B45D706A0954D89E52CE5F38517A2270E0175849B6F3740151D238CCABEF921437E475881D83BB69E4AA258EBD"
+
ECP test vectors secp192r1
ecp_test_vect:SECP192R1:"323FA3169D8E9C6593F59476BC142000AB5BE0E249C43426":"CD46489ECFD6C105E7B3D32566E2B122E249ABAADD870612":"68887B4877DF51DD4DC3D6FD11F0A26F8FD3844317916E9A":"631F95BB4A67632C9C476EEE9AB695AB240A0499307FCF62":"519A121680E0045466BA21DF2EEE47F5973B500577EF13D5":"FF613AB4D64CEE3A20875BDB10F953F6B30CA072C60AA57F":"AD420182633F8526BFE954ACDA376F05E5FF4F837F54FEBE":"4371545ED772A59741D0EDA32C671112B7FDDD51461FCF32"
diff --git a/tests/suites/test_suite_ecp.function b/tests/suites/test_suite_ecp.function
index d81ff88..471bbec 100644
--- a/tests/suites/test_suite_ecp.function
+++ b/tests/suites/test_suite_ecp.function
@@ -126,3 +126,34 @@
mpi_free( &xB ); mpi_free( &yB ); mpi_free( &xZ ); mpi_free( &yZ );
}
END_CASE
+
+BEGIN_CASE
+ecp_fast_mod:id:N
+{
+ ecp_group grp;
+ mpi N, R;
+
+ mpi_init( &N ); mpi_init( &R );
+ ecp_group_init( &grp );
+
+ TEST_ASSERT( ecp_use_known_dp( &grp, POLARSSL_ECP_DP_{id} ) == 0 );
+ TEST_ASSERT( mpi_read_string( &N, 16, {N} ) == 0 );
+
+ /*
+ * Store correct result before we touch N
+ */
+ TEST_ASSERT( mpi_mod_mpi( &R, &N, &grp.P ) == 0 );
+
+ TEST_ASSERT( grp.modp( &N ) == 0 );
+ TEST_ASSERT( mpi_msb( &N ) <= grp.pbits + 3 );
+
+ /*
+ * Use mod rather than addition/substraction in case previous test fails
+ */
+ TEST_ASSERT( mpi_mod_mpi( &N, &N, &grp.P ) == 0 );
+ TEST_ASSERT( mpi_cmp_mpi( &N, &R ) == 0 );
+
+ mpi_free( &N ); mpi_free( &R );
+ ecp_group_free( &grp );
+}
+END_CASE