summaryrefslogtreecommitdiff
path: root/thirdparty/mbedtls/library/bignum.c
diff options
context:
space:
mode:
Diffstat (limited to 'thirdparty/mbedtls/library/bignum.c')
-rw-r--r--thirdparty/mbedtls/library/bignum.c265
1 files changed, 216 insertions, 49 deletions
diff --git a/thirdparty/mbedtls/library/bignum.c b/thirdparty/mbedtls/library/bignum.c
index 423e375fd1..f968a0ad7d 100644
--- a/thirdparty/mbedtls/library/bignum.c
+++ b/thirdparty/mbedtls/library/bignum.c
@@ -59,6 +59,11 @@
#define mbedtls_free free
#endif
+#define MPI_VALIDATE_RET( cond ) \
+ MBEDTLS_INTERNAL_VALIDATE_RET( cond, MBEDTLS_ERR_MPI_BAD_INPUT_DATA )
+#define MPI_VALIDATE( cond ) \
+ MBEDTLS_INTERNAL_VALIDATE( cond )
+
#define ciL (sizeof(mbedtls_mpi_uint)) /* chars in limb */
#define biL (ciL << 3) /* bits in limb */
#define biH (ciL << 2) /* half limb size */
@@ -83,8 +88,7 @@ static void mbedtls_mpi_zeroize( mbedtls_mpi_uint *v, size_t n )
*/
void mbedtls_mpi_init( mbedtls_mpi *X )
{
- if( X == NULL )
- return;
+ MPI_VALIDATE( X != NULL );
X->s = 1;
X->n = 0;
@@ -116,6 +120,7 @@ void mbedtls_mpi_free( mbedtls_mpi *X )
int mbedtls_mpi_grow( mbedtls_mpi *X, size_t nblimbs )
{
mbedtls_mpi_uint *p;
+ MPI_VALIDATE_RET( X != NULL );
if( nblimbs > MBEDTLS_MPI_MAX_LIMBS )
return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
@@ -147,6 +152,10 @@ int mbedtls_mpi_shrink( mbedtls_mpi *X, size_t nblimbs )
{
mbedtls_mpi_uint *p;
size_t i;
+ MPI_VALIDATE_RET( X != NULL );
+
+ if( nblimbs > MBEDTLS_MPI_MAX_LIMBS )
+ return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
/* Actually resize up in this case */
if( X->n <= nblimbs )
@@ -183,6 +192,8 @@ int mbedtls_mpi_copy( mbedtls_mpi *X, const mbedtls_mpi *Y )
{
int ret = 0;
size_t i;
+ MPI_VALIDATE_RET( X != NULL );
+ MPI_VALIDATE_RET( Y != NULL );
if( X == Y )
return( 0 );
@@ -222,6 +233,8 @@ cleanup:
void mbedtls_mpi_swap( mbedtls_mpi *X, mbedtls_mpi *Y )
{
mbedtls_mpi T;
+ MPI_VALIDATE( X != NULL );
+ MPI_VALIDATE( Y != NULL );
memcpy( &T, X, sizeof( mbedtls_mpi ) );
memcpy( X, Y, sizeof( mbedtls_mpi ) );
@@ -237,6 +250,8 @@ int mbedtls_mpi_safe_cond_assign( mbedtls_mpi *X, const mbedtls_mpi *Y, unsigned
{
int ret = 0;
size_t i;
+ MPI_VALIDATE_RET( X != NULL );
+ MPI_VALIDATE_RET( Y != NULL );
/* make sure assign is 0 or 1 in a time-constant manner */
assign = (assign | (unsigned char)-assign) >> 7;
@@ -266,6 +281,8 @@ int mbedtls_mpi_safe_cond_swap( mbedtls_mpi *X, mbedtls_mpi *Y, unsigned char sw
int ret, s;
size_t i;
mbedtls_mpi_uint tmp;
+ MPI_VALIDATE_RET( X != NULL );
+ MPI_VALIDATE_RET( Y != NULL );
if( X == Y )
return( 0 );
@@ -298,6 +315,7 @@ cleanup:
int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z )
{
int ret;
+ MPI_VALIDATE_RET( X != NULL );
MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, 1 ) );
memset( X->p, 0, X->n * ciL );
@@ -315,12 +333,18 @@ cleanup:
*/
int mbedtls_mpi_get_bit( const mbedtls_mpi *X, size_t pos )
{
+ MPI_VALIDATE_RET( X != NULL );
+
if( X->n * biL <= pos )
return( 0 );
return( ( X->p[pos / biL] >> ( pos % biL ) ) & 0x01 );
}
+/* Get a specific byte, without range checks. */
+#define GET_BYTE( X, i ) \
+ ( ( ( X )->p[( i ) / ciL] >> ( ( ( i ) % ciL ) * 8 ) ) & 0xff )
+
/*
* Set a bit to a specific value of 0 or 1
*/
@@ -329,6 +353,7 @@ int mbedtls_mpi_set_bit( mbedtls_mpi *X, size_t pos, unsigned char val )
int ret = 0;
size_t off = pos / biL;
size_t idx = pos % biL;
+ MPI_VALIDATE_RET( X != NULL );
if( val != 0 && val != 1 )
return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
@@ -355,6 +380,7 @@ cleanup:
size_t mbedtls_mpi_lsb( const mbedtls_mpi *X )
{
size_t i, j, count = 0;
+ MBEDTLS_INTERNAL_VALIDATE_RET( X != NULL, 0 );
for( i = 0; i < X->n; i++ )
for( j = 0; j < biL; j++, count++ )
@@ -435,6 +461,8 @@ int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s )
size_t i, j, slen, n;
mbedtls_mpi_uint d;
mbedtls_mpi T;
+ MPI_VALIDATE_RET( X != NULL );
+ MPI_VALIDATE_RET( s != NULL );
if( radix < 2 || radix > 16 )
return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
@@ -535,6 +563,9 @@ int mbedtls_mpi_write_string( const mbedtls_mpi *X, int radix,
size_t n;
char *p;
mbedtls_mpi T;
+ MPI_VALIDATE_RET( X != NULL );
+ MPI_VALIDATE_RET( olen != NULL );
+ MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
if( radix < 2 || radix > 16 )
return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
@@ -616,6 +647,12 @@ int mbedtls_mpi_read_file( mbedtls_mpi *X, int radix, FILE *fin )
*/
char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
+ MPI_VALIDATE_RET( X != NULL );
+ MPI_VALIDATE_RET( fin != NULL );
+
+ if( radix < 2 || radix > 16 )
+ return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
+
memset( s, 0, sizeof( s ) );
if( fgets( s, sizeof( s ) - 1, fin ) == NULL )
return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
@@ -647,6 +684,10 @@ int mbedtls_mpi_write_file( const char *p, const mbedtls_mpi *X, int radix, FILE
* newline characters and '\0'
*/
char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
+ MPI_VALIDATE_RET( X != NULL );
+
+ if( radix < 2 || radix > 16 )
+ return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
memset( s, 0, sizeof( s ) );
@@ -683,6 +724,9 @@ int mbedtls_mpi_read_binary( mbedtls_mpi *X, const unsigned char *buf, size_t bu
size_t i, j;
size_t const limbs = CHARS_TO_LIMBS( buflen );
+ MPI_VALIDATE_RET( X != NULL );
+ MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
+
/* Ensure that target MPI has exactly the necessary number of limbs */
if( X->n != limbs )
{
@@ -704,19 +748,45 @@ cleanup:
/*
* Export X into unsigned binary data, big endian
*/
-int mbedtls_mpi_write_binary( const mbedtls_mpi *X, unsigned char *buf, size_t buflen )
+int mbedtls_mpi_write_binary( const mbedtls_mpi *X,
+ unsigned char *buf, size_t buflen )
{
- size_t i, j, n;
+ size_t stored_bytes;
+ size_t bytes_to_copy;
+ unsigned char *p;
+ size_t i;
- n = mbedtls_mpi_size( X );
+ MPI_VALIDATE_RET( X != NULL );
+ MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
- if( buflen < n )
- return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
+ stored_bytes = X->n * ciL;
- memset( buf, 0, buflen );
+ if( stored_bytes < buflen )
+ {
+ /* There is enough space in the output buffer. Write initial
+ * null bytes and record the position at which to start
+ * writing the significant bytes. In this case, the execution
+ * trace of this function does not depend on the value of the
+ * number. */
+ bytes_to_copy = stored_bytes;
+ p = buf + buflen - stored_bytes;
+ memset( buf, 0, buflen - stored_bytes );
+ }
+ else
+ {
+ /* The output buffer is smaller than the allocated size of X.
+ * However X may fit if its leading bytes are zero. */
+ bytes_to_copy = buflen;
+ p = buf;
+ for( i = bytes_to_copy; i < stored_bytes; i++ )
+ {
+ if( GET_BYTE( X, i ) != 0 )
+ return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
+ }
+ }
- for( i = buflen - 1, j = 0; n > 0; i--, j++, n-- )
- buf[i] = (unsigned char)( X->p[j / ciL] >> ((j % ciL) << 3) );
+ for( i = 0; i < bytes_to_copy; i++ )
+ p[bytes_to_copy - i - 1] = GET_BYTE( X, i );
return( 0 );
}
@@ -729,6 +799,7 @@ int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count )
int ret;
size_t i, v0, t1;
mbedtls_mpi_uint r0 = 0, r1;
+ MPI_VALIDATE_RET( X != NULL );
v0 = count / (biL );
t1 = count & (biL - 1);
@@ -778,6 +849,7 @@ int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count )
{
size_t i, v0, v1;
mbedtls_mpi_uint r0 = 0, r1;
+ MPI_VALIDATE_RET( X != NULL );
v0 = count / biL;
v1 = count & (biL - 1);
@@ -820,6 +892,8 @@ int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count )
int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y )
{
size_t i, j;
+ MPI_VALIDATE_RET( X != NULL );
+ MPI_VALIDATE_RET( Y != NULL );
for( i = X->n; i > 0; i-- )
if( X->p[i - 1] != 0 )
@@ -850,6 +924,8 @@ int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y )
int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y )
{
size_t i, j;
+ MPI_VALIDATE_RET( X != NULL );
+ MPI_VALIDATE_RET( Y != NULL );
for( i = X->n; i > 0; i-- )
if( X->p[i - 1] != 0 )
@@ -884,6 +960,7 @@ int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z )
{
mbedtls_mpi Y;
mbedtls_mpi_uint p[1];
+ MPI_VALIDATE_RET( X != NULL );
*p = ( z < 0 ) ? -z : z;
Y.s = ( z < 0 ) ? -1 : 1;
@@ -901,6 +978,9 @@ int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi
int ret;
size_t i, j;
mbedtls_mpi_uint *o, *p, c, tmp;
+ MPI_VALIDATE_RET( X != NULL );
+ MPI_VALIDATE_RET( A != NULL );
+ MPI_VALIDATE_RET( B != NULL );
if( X == B )
{
@@ -978,6 +1058,9 @@ int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi
mbedtls_mpi TB;
int ret;
size_t n;
+ MPI_VALIDATE_RET( X != NULL );
+ MPI_VALIDATE_RET( A != NULL );
+ MPI_VALIDATE_RET( B != NULL );
if( mbedtls_mpi_cmp_abs( A, B ) < 0 )
return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
@@ -1018,8 +1101,12 @@ cleanup:
*/
int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
{
- int ret, s = A->s;
+ int ret, s;
+ MPI_VALIDATE_RET( X != NULL );
+ MPI_VALIDATE_RET( A != NULL );
+ MPI_VALIDATE_RET( B != NULL );
+ s = A->s;
if( A->s * B->s < 0 )
{
if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
@@ -1049,8 +1136,12 @@ cleanup:
*/
int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
{
- int ret, s = A->s;
+ int ret, s;
+ MPI_VALIDATE_RET( X != NULL );
+ MPI_VALIDATE_RET( A != NULL );
+ MPI_VALIDATE_RET( B != NULL );
+ s = A->s;
if( A->s * B->s > 0 )
{
if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
@@ -1082,6 +1173,8 @@ int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint
{
mbedtls_mpi _B;
mbedtls_mpi_uint p[1];
+ MPI_VALIDATE_RET( X != NULL );
+ MPI_VALIDATE_RET( A != NULL );
p[0] = ( b < 0 ) ? -b : b;
_B.s = ( b < 0 ) ? -1 : 1;
@@ -1098,6 +1191,8 @@ int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint
{
mbedtls_mpi _B;
mbedtls_mpi_uint p[1];
+ MPI_VALIDATE_RET( X != NULL );
+ MPI_VALIDATE_RET( A != NULL );
p[0] = ( b < 0 ) ? -b : b;
_B.s = ( b < 0 ) ? -1 : 1;
@@ -1187,6 +1282,9 @@ int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi
int ret;
size_t i, j;
mbedtls_mpi TA, TB;
+ MPI_VALIDATE_RET( X != NULL );
+ MPI_VALIDATE_RET( A != NULL );
+ MPI_VALIDATE_RET( B != NULL );
mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
@@ -1223,6 +1321,8 @@ int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint
{
mbedtls_mpi _B;
mbedtls_mpi_uint p[1];
+ MPI_VALIDATE_RET( X != NULL );
+ MPI_VALIDATE_RET( A != NULL );
_B.s = 1;
_B.n = 1;
@@ -1331,11 +1431,14 @@ static mbedtls_mpi_uint mbedtls_int_div_int( mbedtls_mpi_uint u1,
/*
* Division by mbedtls_mpi: A = Q * B + R (HAC 14.20)
*/
-int mbedtls_mpi_div_mpi( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B )
+int mbedtls_mpi_div_mpi( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A,
+ const mbedtls_mpi *B )
{
int ret;
size_t i, n, t, k;
mbedtls_mpi X, Y, Z, T1, T2;
+ MPI_VALIDATE_RET( A != NULL );
+ MPI_VALIDATE_RET( B != NULL );
if( mbedtls_mpi_cmp_int( B, 0 ) == 0 )
return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
@@ -1446,10 +1549,13 @@ cleanup:
/*
* Division by int: A = Q * b + R
*/
-int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, mbedtls_mpi_sint b )
+int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R,
+ const mbedtls_mpi *A,
+ mbedtls_mpi_sint b )
{
mbedtls_mpi _B;
mbedtls_mpi_uint p[1];
+ MPI_VALIDATE_RET( A != NULL );
p[0] = ( b < 0 ) ? -b : b;
_B.s = ( b < 0 ) ? -1 : 1;
@@ -1465,6 +1571,9 @@ int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, m
int mbedtls_mpi_mod_mpi( mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B )
{
int ret;
+ MPI_VALIDATE_RET( R != NULL );
+ MPI_VALIDATE_RET( A != NULL );
+ MPI_VALIDATE_RET( B != NULL );
if( mbedtls_mpi_cmp_int( B, 0 ) < 0 )
return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
@@ -1489,6 +1598,8 @@ int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_
{
size_t i;
mbedtls_mpi_uint x, y, z;
+ MPI_VALIDATE_RET( r != NULL );
+ MPI_VALIDATE_RET( A != NULL );
if( b == 0 )
return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
@@ -1602,7 +1713,8 @@ static int mpi_montmul( mbedtls_mpi *A, const mbedtls_mpi *B, const mbedtls_mpi
/*
* Montgomery reduction: A = A * R^-1 mod N
*/
-static int mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N, mbedtls_mpi_uint mm, const mbedtls_mpi *T )
+static int mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N,
+ mbedtls_mpi_uint mm, const mbedtls_mpi *T )
{
mbedtls_mpi_uint z = 1;
mbedtls_mpi U;
@@ -1616,7 +1728,9 @@ static int mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N, mbedtls_mpi_uint m
/*
* Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
*/
-int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *E, const mbedtls_mpi *N, mbedtls_mpi *_RR )
+int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A,
+ const mbedtls_mpi *E, const mbedtls_mpi *N,
+ mbedtls_mpi *_RR )
{
int ret;
size_t wbits, wsize, one = 1;
@@ -1626,6 +1740,11 @@ int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi
mbedtls_mpi RR, T, W[ 2 << MBEDTLS_MPI_WINDOW_SIZE ], Apos;
int neg;
+ MPI_VALIDATE_RET( X != NULL );
+ MPI_VALIDATE_RET( A != NULL );
+ MPI_VALIDATE_RET( E != NULL );
+ MPI_VALIDATE_RET( N != NULL );
+
if( mbedtls_mpi_cmp_int( N, 0 ) <= 0 || ( N->p[0] & 1 ) == 0 )
return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
@@ -1830,6 +1949,10 @@ int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B
size_t lz, lzt;
mbedtls_mpi TG, TA, TB;
+ MPI_VALIDATE_RET( G != NULL );
+ MPI_VALIDATE_RET( A != NULL );
+ MPI_VALIDATE_RET( B != NULL );
+
mbedtls_mpi_init( &TG ); mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) );
@@ -1886,6 +2009,8 @@ int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size,
{
int ret;
unsigned char buf[MBEDTLS_MPI_MAX_SIZE];
+ MPI_VALIDATE_RET( X != NULL );
+ MPI_VALIDATE_RET( f_rng != NULL );
if( size > MBEDTLS_MPI_MAX_SIZE )
return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
@@ -1905,6 +2030,9 @@ int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi
{
int ret;
mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
+ MPI_VALIDATE_RET( X != NULL );
+ MPI_VALIDATE_RET( A != NULL );
+ MPI_VALIDATE_RET( N != NULL );
if( mbedtls_mpi_cmp_int( N, 1 ) <= 0 )
return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
@@ -2056,15 +2184,19 @@ cleanup:
/*
* Miller-Rabin pseudo-primality test (HAC 4.24)
*/
-static int mpi_miller_rabin( const mbedtls_mpi *X,
+static int mpi_miller_rabin( const mbedtls_mpi *X, size_t rounds,
int (*f_rng)(void *, unsigned char *, size_t),
void *p_rng )
{
int ret, count;
- size_t i, j, k, n, s;
+ size_t i, j, k, s;
mbedtls_mpi W, R, T, A, RR;
- mbedtls_mpi_init( &W ); mbedtls_mpi_init( &R ); mbedtls_mpi_init( &T ); mbedtls_mpi_init( &A );
+ MPI_VALIDATE_RET( X != NULL );
+ MPI_VALIDATE_RET( f_rng != NULL );
+
+ mbedtls_mpi_init( &W ); mbedtls_mpi_init( &R );
+ mbedtls_mpi_init( &T ); mbedtls_mpi_init( &A );
mbedtls_mpi_init( &RR );
/*
@@ -2077,27 +2209,12 @@ static int mpi_miller_rabin( const mbedtls_mpi *X,
MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &R, s ) );
i = mbedtls_mpi_bitlen( X );
- /*
- * HAC, table 4.4
- */
- n = ( ( i >= 1300 ) ? 2 : ( i >= 850 ) ? 3 :
- ( i >= 650 ) ? 4 : ( i >= 350 ) ? 8 :
- ( i >= 250 ) ? 12 : ( i >= 150 ) ? 18 : 27 );
- for( i = 0; i < n; i++ )
+ for( i = 0; i < rounds; i++ )
{
/*
* pick a random A, 1 < A < |X| - 1
*/
- MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
-
- if( mbedtls_mpi_cmp_mpi( &A, &W ) >= 0 )
- {
- j = mbedtls_mpi_bitlen( &A ) - mbedtls_mpi_bitlen( &W );
- MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &A, j + 1 ) );
- }
- A.p[0] |= 3;
-
count = 0;
do {
MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
@@ -2105,7 +2222,7 @@ static int mpi_miller_rabin( const mbedtls_mpi *X,
j = mbedtls_mpi_bitlen( &A );
k = mbedtls_mpi_bitlen( &W );
if (j > k) {
- MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &A, j - k ) );
+ A.p[A.n - 1] &= ( (mbedtls_mpi_uint) 1 << ( k - ( A.n - 1 ) * biL - 1 ) ) - 1;
}
if (count++ > 30) {
@@ -2151,7 +2268,8 @@ static int mpi_miller_rabin( const mbedtls_mpi *X,
}
cleanup:
- mbedtls_mpi_free( &W ); mbedtls_mpi_free( &R ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &A );
+ mbedtls_mpi_free( &W ); mbedtls_mpi_free( &R );
+ mbedtls_mpi_free( &T ); mbedtls_mpi_free( &A );
mbedtls_mpi_free( &RR );
return( ret );
@@ -2160,12 +2278,14 @@ cleanup:
/*
* Pseudo-primality test: small factors, then Miller-Rabin
*/
-int mbedtls_mpi_is_prime( const mbedtls_mpi *X,
- int (*f_rng)(void *, unsigned char *, size_t),
- void *p_rng )
+int mbedtls_mpi_is_prime_ext( const mbedtls_mpi *X, int rounds,
+ int (*f_rng)(void *, unsigned char *, size_t),
+ void *p_rng )
{
int ret;
mbedtls_mpi XX;
+ MPI_VALIDATE_RET( X != NULL );
+ MPI_VALIDATE_RET( f_rng != NULL );
XX.s = 1;
XX.n = X->n;
@@ -2186,17 +2306,37 @@ int mbedtls_mpi_is_prime( const mbedtls_mpi *X,
return( ret );
}
- return( mpi_miller_rabin( &XX, f_rng, p_rng ) );
+ return( mpi_miller_rabin( &XX, rounds, f_rng, p_rng ) );
+}
+
+#if !defined(MBEDTLS_DEPRECATED_REMOVED)
+/*
+ * Pseudo-primality test, error probability 2^-80
+ */
+int mbedtls_mpi_is_prime( const mbedtls_mpi *X,
+ int (*f_rng)(void *, unsigned char *, size_t),
+ void *p_rng )
+{
+ MPI_VALIDATE_RET( X != NULL );
+ MPI_VALIDATE_RET( f_rng != NULL );
+
+ /*
+ * In the past our key generation aimed for an error rate of at most
+ * 2^-80. Since this function is deprecated, aim for the same certainty
+ * here as well.
+ */
+ return( mbedtls_mpi_is_prime_ext( X, 40, f_rng, p_rng ) );
}
+#endif
/*
* Prime number generation
*
- * If dh_flag is 0 and nbits is at least 1024, then the procedure
- * follows the RSA probably-prime generation method of FIPS 186-4.
- * NB. FIPS 186-4 only allows the specific bit lengths of 1024 and 1536.
+ * To generate an RSA key in a way recommended by FIPS 186-4, both primes must
+ * be either 1024 bits or 1536 bits long, and flags must contain
+ * MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR.
*/
-int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int dh_flag,
+int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int flags,
int (*f_rng)(void *, unsigned char *, size_t),
void *p_rng )
{
@@ -2209,9 +2349,13 @@ int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int dh_flag,
#endif
int ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
size_t k, n;
+ int rounds;
mbedtls_mpi_uint r;
mbedtls_mpi Y;
+ MPI_VALIDATE_RET( X != NULL );
+ MPI_VALIDATE_RET( f_rng != NULL );
+
if( nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS )
return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
@@ -2219,6 +2363,27 @@ int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int dh_flag,
n = BITS_TO_LIMBS( nbits );
+ if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR ) == 0 )
+ {
+ /*
+ * 2^-80 error probability, number of rounds chosen per HAC, table 4.4
+ */
+ rounds = ( ( nbits >= 1300 ) ? 2 : ( nbits >= 850 ) ? 3 :
+ ( nbits >= 650 ) ? 4 : ( nbits >= 350 ) ? 8 :
+ ( nbits >= 250 ) ? 12 : ( nbits >= 150 ) ? 18 : 27 );
+ }
+ else
+ {
+ /*
+ * 2^-100 error probability, number of rounds computed based on HAC,
+ * fact 4.48
+ */
+ rounds = ( ( nbits >= 1450 ) ? 4 : ( nbits >= 1150 ) ? 5 :
+ ( nbits >= 1000 ) ? 6 : ( nbits >= 850 ) ? 7 :
+ ( nbits >= 750 ) ? 8 : ( nbits >= 500 ) ? 13 :
+ ( nbits >= 250 ) ? 28 : ( nbits >= 150 ) ? 40 : 51 );
+ }
+
while( 1 )
{
MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( X, n * ciL, f_rng, p_rng ) );
@@ -2229,9 +2394,9 @@ int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int dh_flag,
if( k > nbits ) MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, k - nbits ) );
X->p[0] |= 1;
- if( dh_flag == 0 )
+ if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_DH ) == 0 )
{
- ret = mbedtls_mpi_is_prime( X, f_rng, p_rng );
+ ret = mbedtls_mpi_is_prime_ext( X, rounds, f_rng, p_rng );
if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
goto cleanup;
@@ -2264,8 +2429,10 @@ int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int dh_flag,
*/
if( ( ret = mpi_check_small_factors( X ) ) == 0 &&
( ret = mpi_check_small_factors( &Y ) ) == 0 &&
- ( ret = mpi_miller_rabin( X, f_rng, p_rng ) ) == 0 &&
- ( ret = mpi_miller_rabin( &Y, f_rng, p_rng ) ) == 0 )
+ ( ret = mpi_miller_rabin( X, rounds, f_rng, p_rng ) )
+ == 0 &&
+ ( ret = mpi_miller_rabin( &Y, rounds, f_rng, p_rng ) )
+ == 0 )
goto cleanup;
if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-07 13:22:06 +0000