123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492 |
- #if !defined(MBEDTLS_CONFIG_FILE)
- #include "mbedtls/config.h"
- #else
- #include MBEDTLS_CONFIG_FILE
- #endif
- #if defined(MBEDTLS_RSA_C)
- #include "mbedtls/rsa.h"
- #include "mbedtls/bignum.h"
- #include "mbedtls/rsa_internal.h"
- int mbedtls_rsa_deduce_primes( mbedtls_mpi const *N,
- mbedtls_mpi const *E, mbedtls_mpi const *D,
- mbedtls_mpi *P, mbedtls_mpi *Q )
- {
- int ret = 0;
- uint16_t attempt;
- uint16_t iter;
- uint16_t order;
- mbedtls_mpi T;
- mbedtls_mpi K;
- const unsigned char primes[] = { 2,
- 3, 5, 7, 11, 13, 17, 19, 23,
- 29, 31, 37, 41, 43, 47, 53, 59,
- 61, 67, 71, 73, 79, 83, 89, 97,
- 101, 103, 107, 109, 113, 127, 131, 137,
- 139, 149, 151, 157, 163, 167, 173, 179,
- 181, 191, 193, 197, 199, 211, 223, 227,
- 229, 233, 239, 241, 251
- };
- const size_t num_primes = sizeof( primes ) / sizeof( *primes );
- if( P == NULL || Q == NULL || P->p != NULL || Q->p != NULL )
- return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
- if( mbedtls_mpi_cmp_int( N, 0 ) <= 0 ||
- mbedtls_mpi_cmp_int( D, 1 ) <= 0 ||
- mbedtls_mpi_cmp_mpi( D, N ) >= 0 ||
- mbedtls_mpi_cmp_int( E, 1 ) <= 0 ||
- mbedtls_mpi_cmp_mpi( E, N ) >= 0 )
- {
- return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
- }
-
- mbedtls_mpi_init( &K );
- mbedtls_mpi_init( &T );
-
- MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, D, E ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &T, &T, 1 ) );
- if( ( order = (uint16_t) mbedtls_mpi_lsb( &T ) ) == 0 )
- {
- ret = MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
- goto cleanup;
- }
-
- MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &T, order ) );
-
-
- attempt = 0;
- if( N->p[0] % 8 == 1 )
- attempt = 1;
- for( ; attempt < num_primes; ++attempt )
- {
- mbedtls_mpi_lset( &K, primes[attempt] );
-
- MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( P, &K, N ) );
- if( mbedtls_mpi_cmp_int( P, 1 ) != 0 )
- continue;
-
- MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &K, &K, &T, N,
- Q
- ) );
- for( iter = 1; iter <= order; ++iter )
- {
-
- if( mbedtls_mpi_cmp_int( &K, 1 ) == 0 )
- break;
- MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &K, &K, 1 ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( P, &K, N ) );
- if( mbedtls_mpi_cmp_int( P, 1 ) == 1 &&
- mbedtls_mpi_cmp_mpi( P, N ) == -1 )
- {
-
- MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( Q, NULL, N, P ) );
- goto cleanup;
- }
- MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, &K, 1 ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K, &K, &K ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &K, &K, N ) );
- }
-
- if( mbedtls_mpi_cmp_int( &K, 1 ) != 0 )
- {
- break;
- }
- }
- ret = MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
- cleanup:
- mbedtls_mpi_free( &K );
- mbedtls_mpi_free( &T );
- return( ret );
- }
- int mbedtls_rsa_deduce_private_exponent( mbedtls_mpi const *P,
- mbedtls_mpi const *Q,
- mbedtls_mpi const *E,
- mbedtls_mpi *D )
- {
- int ret = 0;
- mbedtls_mpi K, L;
- if( D == NULL || mbedtls_mpi_cmp_int( D, 0 ) != 0 )
- return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
- if( mbedtls_mpi_cmp_int( P, 1 ) <= 0 ||
- mbedtls_mpi_cmp_int( Q, 1 ) <= 0 ||
- mbedtls_mpi_cmp_int( E, 0 ) == 0 )
- {
- return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
- }
- mbedtls_mpi_init( &K );
- mbedtls_mpi_init( &L );
-
- MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, P, 1 ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &L, Q, 1 ) );
-
- MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( D, &K, &L ) );
-
- MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K, &K, &L ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( &K, NULL, &K, D ) );
-
- MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( D, E, &K ) );
- cleanup:
- mbedtls_mpi_free( &K );
- mbedtls_mpi_free( &L );
- return( ret );
- }
- int mbedtls_rsa_validate_crt( const mbedtls_mpi *P, const mbedtls_mpi *Q,
- const mbedtls_mpi *D, const mbedtls_mpi *DP,
- const mbedtls_mpi *DQ, const mbedtls_mpi *QP )
- {
- int ret = 0;
- mbedtls_mpi K, L;
- mbedtls_mpi_init( &K );
- mbedtls_mpi_init( &L );
-
- if( DP != NULL )
- {
- if( P == NULL )
- {
- ret = MBEDTLS_ERR_RSA_BAD_INPUT_DATA;
- goto cleanup;
- }
- MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, P, 1 ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &L, DP, D ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &L, &L, &K ) );
- if( mbedtls_mpi_cmp_int( &L, 0 ) != 0 )
- {
- ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
- goto cleanup;
- }
- }
-
- if( DQ != NULL )
- {
- if( Q == NULL )
- {
- ret = MBEDTLS_ERR_RSA_BAD_INPUT_DATA;
- goto cleanup;
- }
- MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, Q, 1 ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &L, DQ, D ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &L, &L, &K ) );
- if( mbedtls_mpi_cmp_int( &L, 0 ) != 0 )
- {
- ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
- goto cleanup;
- }
- }
-
- if( QP != NULL )
- {
- if( P == NULL || Q == NULL )
- {
- ret = MBEDTLS_ERR_RSA_BAD_INPUT_DATA;
- goto cleanup;
- }
- MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K, QP, Q ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, &K, 1 ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &K, &K, P ) );
- if( mbedtls_mpi_cmp_int( &K, 0 ) != 0 )
- {
- ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
- goto cleanup;
- }
- }
- cleanup:
-
- if( ret != 0 &&
- ret != MBEDTLS_ERR_RSA_KEY_CHECK_FAILED &&
- ret != MBEDTLS_ERR_RSA_BAD_INPUT_DATA )
- {
- ret += MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
- }
- mbedtls_mpi_free( &K );
- mbedtls_mpi_free( &L );
- return( ret );
- }
- int mbedtls_rsa_validate_params( const mbedtls_mpi *N, const mbedtls_mpi *P,
- const mbedtls_mpi *Q, const mbedtls_mpi *D,
- const mbedtls_mpi *E,
- int (*f_rng)(void *, unsigned char *, size_t),
- void *p_rng )
- {
- int ret = 0;
- mbedtls_mpi K, L;
- mbedtls_mpi_init( &K );
- mbedtls_mpi_init( &L );
-
- #if defined(MBEDTLS_GENPRIME)
-
- if( f_rng != NULL && P != NULL &&
- ( ret = mbedtls_mpi_is_prime_ext( P, 50, f_rng, p_rng ) ) != 0 )
- {
- ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
- goto cleanup;
- }
- if( f_rng != NULL && Q != NULL &&
- ( ret = mbedtls_mpi_is_prime_ext( Q, 50, f_rng, p_rng ) ) != 0 )
- {
- ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
- goto cleanup;
- }
- #else
- ((void) f_rng);
- ((void) p_rng);
- #endif
-
- if( P != NULL && Q != NULL && N != NULL )
- {
- MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K, P, Q ) );
- if( mbedtls_mpi_cmp_int( N, 1 ) <= 0 ||
- mbedtls_mpi_cmp_mpi( &K, N ) != 0 )
- {
- ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
- goto cleanup;
- }
- }
-
- if( N != NULL && D != NULL && E != NULL )
- {
- if ( mbedtls_mpi_cmp_int( D, 1 ) <= 0 ||
- mbedtls_mpi_cmp_int( E, 1 ) <= 0 ||
- mbedtls_mpi_cmp_mpi( D, N ) >= 0 ||
- mbedtls_mpi_cmp_mpi( E, N ) >= 0 )
- {
- ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
- goto cleanup;
- }
- }
-
- if( P != NULL && Q != NULL && D != NULL && E != NULL )
- {
- if( mbedtls_mpi_cmp_int( P, 1 ) <= 0 ||
- mbedtls_mpi_cmp_int( Q, 1 ) <= 0 )
- {
- ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
- goto cleanup;
- }
-
- MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K, D, E ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, &K, 1 ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &L, P, 1 ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &K, &K, &L ) );
- if( mbedtls_mpi_cmp_int( &K, 0 ) != 0 )
- {
- ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
- goto cleanup;
- }
-
- MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &K, D, E ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, &K, 1 ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &L, Q, 1 ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &K, &K, &L ) );
- if( mbedtls_mpi_cmp_int( &K, 0 ) != 0 )
- {
- ret = MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
- goto cleanup;
- }
- }
- cleanup:
- mbedtls_mpi_free( &K );
- mbedtls_mpi_free( &L );
-
- if( ret != 0 && ret != MBEDTLS_ERR_RSA_KEY_CHECK_FAILED )
- {
- ret += MBEDTLS_ERR_RSA_KEY_CHECK_FAILED;
- }
- return( ret );
- }
- int mbedtls_rsa_deduce_crt( const mbedtls_mpi *P, const mbedtls_mpi *Q,
- const mbedtls_mpi *D, mbedtls_mpi *DP,
- mbedtls_mpi *DQ, mbedtls_mpi *QP )
- {
- int ret = 0;
- mbedtls_mpi K;
- mbedtls_mpi_init( &K );
-
- if( DP != NULL )
- {
- MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, P, 1 ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( DP, D, &K ) );
- }
-
- if( DQ != NULL )
- {
- MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &K, Q, 1 ) );
- MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( DQ, D, &K ) );
- }
-
- if( QP != NULL )
- {
- MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( QP, Q, P ) );
- }
- cleanup:
- mbedtls_mpi_free( &K );
- return( ret );
- }
- #endif
|