PolarSSL v1.1.4
|
00001 /* 00002 * The RSA public-key cryptosystem 00003 * 00004 * Copyright (C) 2006-2011, Brainspark B.V. 00005 * 00006 * This file is part of PolarSSL (http://www.polarssl.org) 00007 * Lead Maintainer: Paul Bakker <polarssl_maintainer at polarssl.org> 00008 * 00009 * All rights reserved. 00010 * 00011 * This program is free software; you can redistribute it and/or modify 00012 * it under the terms of the GNU General Public License as published by 00013 * the Free Software Foundation; either version 2 of the License, or 00014 * (at your option) any later version. 00015 * 00016 * This program is distributed in the hope that it will be useful, 00017 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00018 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00019 * GNU General Public License for more details. 00020 * 00021 * You should have received a copy of the GNU General Public License along 00022 * with this program; if not, write to the Free Software Foundation, Inc., 00023 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 00024 */ 00025 /* 00026 * RSA was designed by Ron Rivest, Adi Shamir and Len Adleman. 00027 * 00028 * http://theory.lcs.mit.edu/~rivest/rsapaper.pdf 00029 * http://www.cacr.math.uwaterloo.ca/hac/about/chap8.pdf 00030 */ 00031 00032 #include "polarssl/config.h" 00033 00034 #if defined(POLARSSL_RSA_C) 00035 00036 #include "polarssl/rsa.h" 00037 #include "polarssl/md.h" 00038 00039 #include <stdlib.h> 00040 #include <stdio.h> 00041 00042 /* 00043 * Initialize an RSA context 00044 */ 00045 void rsa_init( rsa_context *ctx, 00046 int padding, 00047 int hash_id ) 00048 { 00049 memset( ctx, 0, sizeof( rsa_context ) ); 00050 00051 ctx->padding = padding; 00052 ctx->hash_id = hash_id; 00053 } 00054 00055 #if defined(POLARSSL_GENPRIME) 00056 00057 /* 00058 * Generate an RSA keypair 00059 */ 00060 int rsa_gen_key( rsa_context *ctx, 00061 int (*f_rng)(void *, unsigned char *, size_t), 00062 void *p_rng, 00063 unsigned int nbits, int exponent ) 00064 { 00065 int ret; 00066 mpi P1, Q1, H, G; 00067 00068 if( f_rng == NULL || nbits < 128 || exponent < 3 ) 00069 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA ); 00070 00071 mpi_init( &P1 ); mpi_init( &Q1 ); mpi_init( &H ); mpi_init( &G ); 00072 00073 /* 00074 * find primes P and Q with Q < P so that: 00075 * GCD( E, (P-1)*(Q-1) ) == 1 00076 */ 00077 MPI_CHK( mpi_lset( &ctx->E, exponent ) ); 00078 00079 do 00080 { 00081 MPI_CHK( mpi_gen_prime( &ctx->P, ( nbits + 1 ) >> 1, 0, 00082 f_rng, p_rng ) ); 00083 00084 MPI_CHK( mpi_gen_prime( &ctx->Q, ( nbits + 1 ) >> 1, 0, 00085 f_rng, p_rng ) ); 00086 00087 if( mpi_cmp_mpi( &ctx->P, &ctx->Q ) < 0 ) 00088 mpi_swap( &ctx->P, &ctx->Q ); 00089 00090 if( mpi_cmp_mpi( &ctx->P, &ctx->Q ) == 0 ) 00091 continue; 00092 00093 MPI_CHK( mpi_mul_mpi( &ctx->N, &ctx->P, &ctx->Q ) ); 00094 if( mpi_msb( &ctx->N ) != nbits ) 00095 continue; 00096 00097 MPI_CHK( mpi_sub_int( &P1, &ctx->P, 1 ) ); 00098 MPI_CHK( mpi_sub_int( &Q1, &ctx->Q, 1 ) ); 00099 MPI_CHK( mpi_mul_mpi( &H, &P1, &Q1 ) ); 00100 MPI_CHK( mpi_gcd( &G, &ctx->E, &H ) ); 00101 } 00102 while( mpi_cmp_int( &G, 1 ) != 0 ); 00103 00104 /* 00105 * D = E^-1 mod ((P-1)*(Q-1)) 00106 * DP = D mod (P - 1) 00107 * DQ = D mod (Q - 1) 00108 * QP = Q^-1 mod P 00109 */ 00110 MPI_CHK( mpi_inv_mod( &ctx->D , &ctx->E, &H ) ); 00111 MPI_CHK( mpi_mod_mpi( &ctx->DP, &ctx->D, &P1 ) ); 00112 MPI_CHK( mpi_mod_mpi( &ctx->DQ, &ctx->D, &Q1 ) ); 00113 MPI_CHK( mpi_inv_mod( &ctx->QP, &ctx->Q, &ctx->P ) ); 00114 00115 ctx->len = ( mpi_msb( &ctx->N ) + 7 ) >> 3; 00116 00117 cleanup: 00118 00119 mpi_free( &P1 ); mpi_free( &Q1 ); mpi_free( &H ); mpi_free( &G ); 00120 00121 if( ret != 0 ) 00122 { 00123 rsa_free( ctx ); 00124 return( POLARSSL_ERR_RSA_KEY_GEN_FAILED + ret ); 00125 } 00126 00127 return( 0 ); 00128 } 00129 00130 #endif 00131 00132 /* 00133 * Check a public RSA key 00134 */ 00135 int rsa_check_pubkey( const rsa_context *ctx ) 00136 { 00137 if( !ctx->N.p || !ctx->E.p ) 00138 return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED ); 00139 00140 if( ( ctx->N.p[0] & 1 ) == 0 || 00141 ( ctx->E.p[0] & 1 ) == 0 ) 00142 return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED ); 00143 00144 if( mpi_msb( &ctx->N ) < 128 || 00145 mpi_msb( &ctx->N ) > POLARSSL_MPI_MAX_BITS ) 00146 return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED ); 00147 00148 if( mpi_msb( &ctx->E ) < 2 || 00149 mpi_msb( &ctx->E ) > 64 ) 00150 return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED ); 00151 00152 return( 0 ); 00153 } 00154 00155 /* 00156 * Check a private RSA key 00157 */ 00158 int rsa_check_privkey( const rsa_context *ctx ) 00159 { 00160 int ret; 00161 mpi PQ, DE, P1, Q1, H, I, G, G2, L1, L2; 00162 00163 if( ( ret = rsa_check_pubkey( ctx ) ) != 0 ) 00164 return( ret ); 00165 00166 if( !ctx->P.p || !ctx->Q.p || !ctx->D.p ) 00167 return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED ); 00168 00169 mpi_init( &PQ ); mpi_init( &DE ); mpi_init( &P1 ); mpi_init( &Q1 ); 00170 mpi_init( &H ); mpi_init( &I ); mpi_init( &G ); mpi_init( &G2 ); 00171 mpi_init( &L1 ); mpi_init( &L2 ); 00172 00173 MPI_CHK( mpi_mul_mpi( &PQ, &ctx->P, &ctx->Q ) ); 00174 MPI_CHK( mpi_mul_mpi( &DE, &ctx->D, &ctx->E ) ); 00175 MPI_CHK( mpi_sub_int( &P1, &ctx->P, 1 ) ); 00176 MPI_CHK( mpi_sub_int( &Q1, &ctx->Q, 1 ) ); 00177 MPI_CHK( mpi_mul_mpi( &H, &P1, &Q1 ) ); 00178 MPI_CHK( mpi_gcd( &G, &ctx->E, &H ) ); 00179 00180 MPI_CHK( mpi_gcd( &G2, &P1, &Q1 ) ); 00181 MPI_CHK( mpi_div_mpi( &L1, &L2, &H, &G2 ) ); 00182 MPI_CHK( mpi_mod_mpi( &I, &DE, &L1 ) ); 00183 00184 /* 00185 * Check for a valid PKCS1v2 private key 00186 */ 00187 if( mpi_cmp_mpi( &PQ, &ctx->N ) != 0 || 00188 mpi_cmp_int( &L2, 0 ) != 0 || 00189 mpi_cmp_int( &I, 1 ) != 0 || 00190 mpi_cmp_int( &G, 1 ) != 0 ) 00191 { 00192 ret = POLARSSL_ERR_RSA_KEY_CHECK_FAILED; 00193 } 00194 00195 00196 cleanup: 00197 00198 mpi_free( &PQ ); mpi_free( &DE ); mpi_free( &P1 ); mpi_free( &Q1 ); 00199 mpi_free( &H ); mpi_free( &I ); mpi_free( &G ); mpi_free( &G2 ); 00200 mpi_free( &L1 ); mpi_free( &L2 ); 00201 00202 if( ret == POLARSSL_ERR_RSA_KEY_CHECK_FAILED ) 00203 return( ret ); 00204 00205 if( ret != 0 ) 00206 return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED + ret ); 00207 00208 return( 0 ); 00209 } 00210 00211 /* 00212 * Do an RSA public key operation 00213 */ 00214 int rsa_public( rsa_context *ctx, 00215 const unsigned char *input, 00216 unsigned char *output ) 00217 { 00218 int ret; 00219 size_t olen; 00220 mpi T; 00221 00222 mpi_init( &T ); 00223 00224 MPI_CHK( mpi_read_binary( &T, input, ctx->len ) ); 00225 00226 if( mpi_cmp_mpi( &T, &ctx->N ) >= 0 ) 00227 { 00228 mpi_free( &T ); 00229 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA ); 00230 } 00231 00232 olen = ctx->len; 00233 MPI_CHK( mpi_exp_mod( &T, &T, &ctx->E, &ctx->N, &ctx->RN ) ); 00234 MPI_CHK( mpi_write_binary( &T, output, olen ) ); 00235 00236 cleanup: 00237 00238 mpi_free( &T ); 00239 00240 if( ret != 0 ) 00241 return( POLARSSL_ERR_RSA_PUBLIC_FAILED + ret ); 00242 00243 return( 0 ); 00244 } 00245 00246 /* 00247 * Do an RSA private key operation 00248 */ 00249 int rsa_private( rsa_context *ctx, 00250 const unsigned char *input, 00251 unsigned char *output ) 00252 { 00253 int ret; 00254 size_t olen; 00255 mpi T, T1, T2; 00256 00257 mpi_init( &T ); mpi_init( &T1 ); mpi_init( &T2 ); 00258 00259 MPI_CHK( mpi_read_binary( &T, input, ctx->len ) ); 00260 00261 if( mpi_cmp_mpi( &T, &ctx->N ) >= 0 ) 00262 { 00263 mpi_free( &T ); 00264 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA ); 00265 } 00266 00267 #if defined(POLARSSL_RSA_NO_CRT) 00268 MPI_CHK( mpi_exp_mod( &T, &T, &ctx->D, &ctx->N, &ctx->RN ) ); 00269 #else 00270 /* 00271 * faster decryption using the CRT 00272 * 00273 * T1 = input ^ dP mod P 00274 * T2 = input ^ dQ mod Q 00275 */ 00276 MPI_CHK( mpi_exp_mod( &T1, &T, &ctx->DP, &ctx->P, &ctx->RP ) ); 00277 MPI_CHK( mpi_exp_mod( &T2, &T, &ctx->DQ, &ctx->Q, &ctx->RQ ) ); 00278 00279 /* 00280 * T = (T1 - T2) * (Q^-1 mod P) mod P 00281 */ 00282 MPI_CHK( mpi_sub_mpi( &T, &T1, &T2 ) ); 00283 MPI_CHK( mpi_mul_mpi( &T1, &T, &ctx->QP ) ); 00284 MPI_CHK( mpi_mod_mpi( &T, &T1, &ctx->P ) ); 00285 00286 /* 00287 * output = T2 + T * Q 00288 */ 00289 MPI_CHK( mpi_mul_mpi( &T1, &T, &ctx->Q ) ); 00290 MPI_CHK( mpi_add_mpi( &T, &T2, &T1 ) ); 00291 #endif 00292 00293 olen = ctx->len; 00294 MPI_CHK( mpi_write_binary( &T, output, olen ) ); 00295 00296 cleanup: 00297 00298 mpi_free( &T ); mpi_free( &T1 ); mpi_free( &T2 ); 00299 00300 if( ret != 0 ) 00301 return( POLARSSL_ERR_RSA_PRIVATE_FAILED + ret ); 00302 00303 return( 0 ); 00304 } 00305 00306 #if defined(POLARSSL_PKCS1_V21) 00307 00316 static void mgf_mask( unsigned char *dst, size_t dlen, unsigned char *src, size_t slen, 00317 md_context_t *md_ctx ) 00318 { 00319 unsigned char mask[POLARSSL_MD_MAX_SIZE]; 00320 unsigned char counter[4]; 00321 unsigned char *p; 00322 unsigned int hlen; 00323 size_t i, use_len; 00324 00325 memset( mask, 0, POLARSSL_MD_MAX_SIZE ); 00326 memset( counter, 0, 4 ); 00327 00328 hlen = md_ctx->md_info->size; 00329 00330 // Generate and apply dbMask 00331 // 00332 p = dst; 00333 00334 while( dlen > 0 ) 00335 { 00336 use_len = hlen; 00337 if( dlen < hlen ) 00338 use_len = dlen; 00339 00340 md_starts( md_ctx ); 00341 md_update( md_ctx, src, slen ); 00342 md_update( md_ctx, counter, 4 ); 00343 md_finish( md_ctx, mask ); 00344 00345 for( i = 0; i < use_len; ++i ) 00346 *p++ ^= mask[i]; 00347 00348 counter[3]++; 00349 00350 dlen -= use_len; 00351 } 00352 } 00353 #endif 00354 00355 /* 00356 * Add the message padding, then do an RSA operation 00357 */ 00358 int rsa_pkcs1_encrypt( rsa_context *ctx, 00359 int (*f_rng)(void *, unsigned char *, size_t), 00360 void *p_rng, 00361 int mode, size_t ilen, 00362 const unsigned char *input, 00363 unsigned char *output ) 00364 { 00365 size_t nb_pad, olen; 00366 int ret; 00367 unsigned char *p = output; 00368 #if defined(POLARSSL_PKCS1_V21) 00369 unsigned int hlen; 00370 const md_info_t *md_info; 00371 md_context_t md_ctx; 00372 #endif 00373 00374 olen = ctx->len; 00375 00376 if( f_rng == NULL ) 00377 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA ); 00378 00379 switch( ctx->padding ) 00380 { 00381 case RSA_PKCS_V15: 00382 00383 if( olen < ilen + 11 ) 00384 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA ); 00385 00386 nb_pad = olen - 3 - ilen; 00387 00388 *p++ = 0; 00389 *p++ = RSA_CRYPT; 00390 00391 while( nb_pad-- > 0 ) 00392 { 00393 int rng_dl = 100; 00394 00395 do { 00396 ret = f_rng( p_rng, p, 1 ); 00397 } while( *p == 0 && --rng_dl && ret == 0 ); 00398 00399 // Check if RNG failed to generate data 00400 // 00401 if( rng_dl == 0 || ret != 0) 00402 return POLARSSL_ERR_RSA_RNG_FAILED + ret; 00403 00404 p++; 00405 } 00406 *p++ = 0; 00407 memcpy( p, input, ilen ); 00408 break; 00409 00410 #if defined(POLARSSL_PKCS1_V21) 00411 case RSA_PKCS_V21: 00412 00413 md_info = md_info_from_type( ctx->hash_id ); 00414 if( md_info == NULL ) 00415 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA ); 00416 00417 hlen = md_get_size( md_info ); 00418 00419 if( olen < ilen + 2 * hlen + 2 || f_rng == NULL ) 00420 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA ); 00421 00422 memset( output, 0, olen ); 00423 memset( &md_ctx, 0, sizeof( md_context_t ) ); 00424 00425 md_init_ctx( &md_ctx, md_info ); 00426 00427 *p++ = 0; 00428 00429 // Generate a random octet string seed 00430 // 00431 if( ( ret = f_rng( p_rng, p, hlen ) ) != 0 ) 00432 return( POLARSSL_ERR_RSA_RNG_FAILED + ret ); 00433 00434 p += hlen; 00435 00436 // Construct DB 00437 // 00438 md( md_info, p, 0, p ); 00439 p += hlen; 00440 p += olen - 2 * hlen - 2 - ilen; 00441 *p++ = 1; 00442 memcpy( p, input, ilen ); 00443 00444 // maskedDB: Apply dbMask to DB 00445 // 00446 mgf_mask( output + hlen + 1, olen - hlen - 1, output + 1, hlen, 00447 &md_ctx ); 00448 00449 // maskedSeed: Apply seedMask to seed 00450 // 00451 mgf_mask( output + 1, hlen, output + hlen + 1, olen - hlen - 1, 00452 &md_ctx ); 00453 break; 00454 #endif 00455 00456 default: 00457 00458 return( POLARSSL_ERR_RSA_INVALID_PADDING ); 00459 } 00460 00461 return( ( mode == RSA_PUBLIC ) 00462 ? rsa_public( ctx, output, output ) 00463 : rsa_private( ctx, output, output ) ); 00464 } 00465 00466 /* 00467 * Do an RSA operation, then remove the message padding 00468 */ 00469 int rsa_pkcs1_decrypt( rsa_context *ctx, 00470 int mode, size_t *olen, 00471 const unsigned char *input, 00472 unsigned char *output, 00473 size_t output_max_len) 00474 { 00475 int ret; 00476 size_t ilen; 00477 unsigned char *p; 00478 unsigned char buf[1024]; 00479 #if defined(POLARSSL_PKCS1_V21) 00480 unsigned char lhash[POLARSSL_MD_MAX_SIZE]; 00481 unsigned int hlen; 00482 const md_info_t *md_info; 00483 md_context_t md_ctx; 00484 #endif 00485 00486 ilen = ctx->len; 00487 00488 if( ilen < 16 || ilen > sizeof( buf ) ) 00489 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA ); 00490 00491 ret = ( mode == RSA_PUBLIC ) 00492 ? rsa_public( ctx, input, buf ) 00493 : rsa_private( ctx, input, buf ); 00494 00495 if( ret != 0 ) 00496 return( ret ); 00497 00498 p = buf; 00499 00500 switch( ctx->padding ) 00501 { 00502 case RSA_PKCS_V15: 00503 00504 if( *p++ != 0 || *p++ != RSA_CRYPT ) 00505 return( POLARSSL_ERR_RSA_INVALID_PADDING ); 00506 00507 while( *p != 0 ) 00508 { 00509 if( p >= buf + ilen - 1 ) 00510 return( POLARSSL_ERR_RSA_INVALID_PADDING ); 00511 p++; 00512 } 00513 p++; 00514 break; 00515 00516 #if defined(POLARSSL_PKCS1_V21) 00517 case RSA_PKCS_V21: 00518 00519 if( *p++ != 0 ) 00520 return( POLARSSL_ERR_RSA_INVALID_PADDING ); 00521 00522 md_info = md_info_from_type( ctx->hash_id ); 00523 if( md_info == NULL ) 00524 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA ); 00525 00526 hlen = md_get_size( md_info ); 00527 memset( &md_ctx, 0, sizeof( md_context_t ) ); 00528 00529 md_init_ctx( &md_ctx, md_info ); 00530 00531 // Generate lHash 00532 // 00533 md( md_info, lhash, 0, lhash ); 00534 00535 // seed: Apply seedMask to maskedSeed 00536 // 00537 mgf_mask( buf + 1, hlen, buf + hlen + 1, ilen - hlen - 1, 00538 &md_ctx ); 00539 00540 // DB: Apply dbMask to maskedDB 00541 // 00542 mgf_mask( buf + hlen + 1, ilen - hlen - 1, buf + 1, hlen, 00543 &md_ctx ); 00544 00545 p += hlen; 00546 00547 // Check validity 00548 // 00549 if( memcmp( lhash, p, hlen ) != 0 ) 00550 return( POLARSSL_ERR_RSA_INVALID_PADDING ); 00551 00552 p += hlen; 00553 00554 while( *p == 0 && p < buf + ilen ) 00555 p++; 00556 00557 if( p == buf + ilen ) 00558 return( POLARSSL_ERR_RSA_INVALID_PADDING ); 00559 00560 if( *p++ != 0x01 ) 00561 return( POLARSSL_ERR_RSA_INVALID_PADDING ); 00562 00563 break; 00564 #endif 00565 00566 default: 00567 00568 return( POLARSSL_ERR_RSA_INVALID_PADDING ); 00569 } 00570 00571 if (ilen - (p - buf) > output_max_len) 00572 return( POLARSSL_ERR_RSA_OUTPUT_TOO_LARGE ); 00573 00574 *olen = ilen - (p - buf); 00575 memcpy( output, p, *olen ); 00576 00577 return( 0 ); 00578 } 00579 00580 /* 00581 * Do an RSA operation to sign the message digest 00582 */ 00583 int rsa_pkcs1_sign( rsa_context *ctx, 00584 int (*f_rng)(void *, unsigned char *, size_t), 00585 void *p_rng, 00586 int mode, 00587 int hash_id, 00588 unsigned int hashlen, 00589 const unsigned char *hash, 00590 unsigned char *sig ) 00591 { 00592 size_t nb_pad, olen; 00593 unsigned char *p = sig; 00594 #if defined(POLARSSL_PKCS1_V21) 00595 unsigned char salt[POLARSSL_MD_MAX_SIZE]; 00596 unsigned int slen, hlen, offset = 0; 00597 int ret; 00598 size_t msb; 00599 const md_info_t *md_info; 00600 md_context_t md_ctx; 00601 #else 00602 (void) f_rng; 00603 (void) p_rng; 00604 #endif 00605 00606 olen = ctx->len; 00607 00608 switch( ctx->padding ) 00609 { 00610 case RSA_PKCS_V15: 00611 00612 switch( hash_id ) 00613 { 00614 case SIG_RSA_RAW: 00615 nb_pad = olen - 3 - hashlen; 00616 break; 00617 00618 case SIG_RSA_MD2: 00619 case SIG_RSA_MD4: 00620 case SIG_RSA_MD5: 00621 nb_pad = olen - 3 - 34; 00622 break; 00623 00624 case SIG_RSA_SHA1: 00625 nb_pad = olen - 3 - 35; 00626 break; 00627 00628 case SIG_RSA_SHA224: 00629 nb_pad = olen - 3 - 47; 00630 break; 00631 00632 case SIG_RSA_SHA256: 00633 nb_pad = olen - 3 - 51; 00634 break; 00635 00636 case SIG_RSA_SHA384: 00637 nb_pad = olen - 3 - 67; 00638 break; 00639 00640 case SIG_RSA_SHA512: 00641 nb_pad = olen - 3 - 83; 00642 break; 00643 00644 00645 default: 00646 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA ); 00647 } 00648 00649 if( nb_pad < 8 ) 00650 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA ); 00651 00652 *p++ = 0; 00653 *p++ = RSA_SIGN; 00654 memset( p, 0xFF, nb_pad ); 00655 p += nb_pad; 00656 *p++ = 0; 00657 00658 switch( hash_id ) 00659 { 00660 case SIG_RSA_RAW: 00661 memcpy( p, hash, hashlen ); 00662 break; 00663 00664 case SIG_RSA_MD2: 00665 memcpy( p, ASN1_HASH_MDX, 18 ); 00666 memcpy( p + 18, hash, 16 ); 00667 p[13] = 2; break; 00668 00669 case SIG_RSA_MD4: 00670 memcpy( p, ASN1_HASH_MDX, 18 ); 00671 memcpy( p + 18, hash, 16 ); 00672 p[13] = 4; break; 00673 00674 case SIG_RSA_MD5: 00675 memcpy( p, ASN1_HASH_MDX, 18 ); 00676 memcpy( p + 18, hash, 16 ); 00677 p[13] = 5; break; 00678 00679 case SIG_RSA_SHA1: 00680 memcpy( p, ASN1_HASH_SHA1, 15 ); 00681 memcpy( p + 15, hash, 20 ); 00682 break; 00683 00684 case SIG_RSA_SHA224: 00685 memcpy( p, ASN1_HASH_SHA2X, 19 ); 00686 memcpy( p + 19, hash, 28 ); 00687 p[1] += 28; p[14] = 4; p[18] += 28; break; 00688 00689 case SIG_RSA_SHA256: 00690 memcpy( p, ASN1_HASH_SHA2X, 19 ); 00691 memcpy( p + 19, hash, 32 ); 00692 p[1] += 32; p[14] = 1; p[18] += 32; break; 00693 00694 case SIG_RSA_SHA384: 00695 memcpy( p, ASN1_HASH_SHA2X, 19 ); 00696 memcpy( p + 19, hash, 48 ); 00697 p[1] += 48; p[14] = 2; p[18] += 48; break; 00698 00699 case SIG_RSA_SHA512: 00700 memcpy( p, ASN1_HASH_SHA2X, 19 ); 00701 memcpy( p + 19, hash, 64 ); 00702 p[1] += 64; p[14] = 3; p[18] += 64; break; 00703 00704 default: 00705 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA ); 00706 } 00707 00708 break; 00709 00710 #if defined(POLARSSL_PKCS1_V21) 00711 case RSA_PKCS_V21: 00712 00713 if( f_rng == NULL ) 00714 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA ); 00715 00716 switch( hash_id ) 00717 { 00718 case SIG_RSA_MD2: 00719 case SIG_RSA_MD4: 00720 case SIG_RSA_MD5: 00721 hashlen = 16; 00722 break; 00723 00724 case SIG_RSA_SHA1: 00725 hashlen = 20; 00726 break; 00727 00728 case SIG_RSA_SHA224: 00729 hashlen = 28; 00730 break; 00731 00732 case SIG_RSA_SHA256: 00733 hashlen = 32; 00734 break; 00735 00736 case SIG_RSA_SHA384: 00737 hashlen = 48; 00738 break; 00739 00740 case SIG_RSA_SHA512: 00741 hashlen = 64; 00742 break; 00743 00744 default: 00745 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA ); 00746 } 00747 00748 md_info = md_info_from_type( ctx->hash_id ); 00749 if( md_info == NULL ) 00750 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA ); 00751 00752 hlen = md_get_size( md_info ); 00753 slen = hlen; 00754 00755 memset( sig, 0, olen ); 00756 memset( &md_ctx, 0, sizeof( md_context_t ) ); 00757 00758 md_init_ctx( &md_ctx, md_info ); 00759 00760 msb = mpi_msb( &ctx->N ) - 1; 00761 00762 // Generate salt of length slen 00763 // 00764 if( ( ret = f_rng( p_rng, salt, slen ) ) != 0 ) 00765 return( POLARSSL_ERR_RSA_RNG_FAILED + ret ); 00766 00767 // Note: EMSA-PSS encoding is over the length of N - 1 bits 00768 // 00769 msb = mpi_msb( &ctx->N ) - 1; 00770 p += olen - hlen * 2 - 2; 00771 *p++ = 0x01; 00772 memcpy( p, salt, slen ); 00773 p += slen; 00774 00775 // Generate H = Hash( M' ) 00776 // 00777 md_starts( &md_ctx ); 00778 md_update( &md_ctx, p, 8 ); 00779 md_update( &md_ctx, hash, hashlen ); 00780 md_update( &md_ctx, salt, slen ); 00781 md_finish( &md_ctx, p ); 00782 00783 // Compensate for boundary condition when applying mask 00784 // 00785 if( msb % 8 == 0 ) 00786 offset = 1; 00787 00788 // maskedDB: Apply dbMask to DB 00789 // 00790 mgf_mask( sig + offset, olen - hlen - 1 - offset, p, hlen, &md_ctx ); 00791 00792 msb = mpi_msb( &ctx->N ) - 1; 00793 sig[0] &= 0xFF >> ( olen * 8 - msb ); 00794 00795 p += hlen; 00796 *p++ = 0xBC; 00797 break; 00798 #endif 00799 00800 default: 00801 00802 return( POLARSSL_ERR_RSA_INVALID_PADDING ); 00803 } 00804 00805 return( ( mode == RSA_PUBLIC ) 00806 ? rsa_public( ctx, sig, sig ) 00807 : rsa_private( ctx, sig, sig ) ); 00808 } 00809 00810 /* 00811 * Do an RSA operation and check the message digest 00812 */ 00813 int rsa_pkcs1_verify( rsa_context *ctx, 00814 int mode, 00815 int hash_id, 00816 unsigned int hashlen, 00817 const unsigned char *hash, 00818 unsigned char *sig ) 00819 { 00820 int ret; 00821 size_t len, siglen; 00822 unsigned char *p, c; 00823 unsigned char buf[1024]; 00824 #if defined(POLARSSL_PKCS1_V21) 00825 unsigned char result[POLARSSL_MD_MAX_SIZE]; 00826 unsigned char zeros[8]; 00827 unsigned int hlen; 00828 size_t slen, msb; 00829 const md_info_t *md_info; 00830 md_context_t md_ctx; 00831 #endif 00832 siglen = ctx->len; 00833 00834 if( siglen < 16 || siglen > sizeof( buf ) ) 00835 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA ); 00836 00837 ret = ( mode == RSA_PUBLIC ) 00838 ? rsa_public( ctx, sig, buf ) 00839 : rsa_private( ctx, sig, buf ); 00840 00841 if( ret != 0 ) 00842 return( ret ); 00843 00844 p = buf; 00845 00846 switch( ctx->padding ) 00847 { 00848 case RSA_PKCS_V15: 00849 00850 if( *p++ != 0 || *p++ != RSA_SIGN ) 00851 return( POLARSSL_ERR_RSA_INVALID_PADDING ); 00852 00853 while( *p != 0 ) 00854 { 00855 if( p >= buf + siglen - 1 || *p != 0xFF ) 00856 return( POLARSSL_ERR_RSA_INVALID_PADDING ); 00857 p++; 00858 } 00859 p++; 00860 00861 len = siglen - ( p - buf ); 00862 00863 if( len == 34 ) 00864 { 00865 c = p[13]; 00866 p[13] = 0; 00867 00868 if( memcmp( p, ASN1_HASH_MDX, 18 ) != 0 ) 00869 return( POLARSSL_ERR_RSA_VERIFY_FAILED ); 00870 00871 if( ( c == 2 && hash_id == SIG_RSA_MD2 ) || 00872 ( c == 4 && hash_id == SIG_RSA_MD4 ) || 00873 ( c == 5 && hash_id == SIG_RSA_MD5 ) ) 00874 { 00875 if( memcmp( p + 18, hash, 16 ) == 0 ) 00876 return( 0 ); 00877 else 00878 return( POLARSSL_ERR_RSA_VERIFY_FAILED ); 00879 } 00880 } 00881 00882 if( len == 35 && hash_id == SIG_RSA_SHA1 ) 00883 { 00884 if( memcmp( p, ASN1_HASH_SHA1, 15 ) == 0 && 00885 memcmp( p + 15, hash, 20 ) == 0 ) 00886 return( 0 ); 00887 else 00888 return( POLARSSL_ERR_RSA_VERIFY_FAILED ); 00889 } 00890 if( ( len == 19 + 28 && p[14] == 4 && hash_id == SIG_RSA_SHA224 ) || 00891 ( len == 19 + 32 && p[14] == 1 && hash_id == SIG_RSA_SHA256 ) || 00892 ( len == 19 + 48 && p[14] == 2 && hash_id == SIG_RSA_SHA384 ) || 00893 ( len == 19 + 64 && p[14] == 3 && hash_id == SIG_RSA_SHA512 ) ) 00894 { 00895 c = p[1] - 17; 00896 p[1] = 17; 00897 p[14] = 0; 00898 00899 if( p[18] == c && 00900 memcmp( p, ASN1_HASH_SHA2X, 18 ) == 0 && 00901 memcmp( p + 19, hash, c ) == 0 ) 00902 return( 0 ); 00903 else 00904 return( POLARSSL_ERR_RSA_VERIFY_FAILED ); 00905 } 00906 00907 if( len == hashlen && hash_id == SIG_RSA_RAW ) 00908 { 00909 if( memcmp( p, hash, hashlen ) == 0 ) 00910 return( 0 ); 00911 else 00912 return( POLARSSL_ERR_RSA_VERIFY_FAILED ); 00913 } 00914 00915 break; 00916 00917 #if defined(POLARSSL_PKCS1_V21) 00918 case RSA_PKCS_V21: 00919 00920 if( buf[siglen - 1] != 0xBC ) 00921 return( POLARSSL_ERR_RSA_INVALID_PADDING ); 00922 00923 switch( hash_id ) 00924 { 00925 case SIG_RSA_MD2: 00926 case SIG_RSA_MD4: 00927 case SIG_RSA_MD5: 00928 hashlen = 16; 00929 break; 00930 00931 case SIG_RSA_SHA1: 00932 hashlen = 20; 00933 break; 00934 00935 case SIG_RSA_SHA224: 00936 hashlen = 28; 00937 break; 00938 00939 case SIG_RSA_SHA256: 00940 hashlen = 32; 00941 break; 00942 00943 case SIG_RSA_SHA384: 00944 hashlen = 48; 00945 break; 00946 00947 case SIG_RSA_SHA512: 00948 hashlen = 64; 00949 break; 00950 00951 default: 00952 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA ); 00953 } 00954 00955 md_info = md_info_from_type( ctx->hash_id ); 00956 if( md_info == NULL ) 00957 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA ); 00958 00959 hlen = md_get_size( md_info ); 00960 slen = siglen - hlen - 1; 00961 00962 memset( &md_ctx, 0, sizeof( md_context_t ) ); 00963 memset( zeros, 0, 8 ); 00964 00965 md_init_ctx( &md_ctx, md_info ); 00966 00967 // Note: EMSA-PSS verification is over the length of N - 1 bits 00968 // 00969 msb = mpi_msb( &ctx->N ) - 1; 00970 00971 // Compensate for boundary condition when applying mask 00972 // 00973 if( msb % 8 == 0 ) 00974 { 00975 p++; 00976 siglen -= 1; 00977 } 00978 if( buf[0] >> ( 8 - siglen * 8 + msb ) ) 00979 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA ); 00980 00981 mgf_mask( p, siglen - hlen - 1, p + siglen - hlen - 1, hlen, &md_ctx ); 00982 00983 buf[0] &= 0xFF >> ( siglen * 8 - msb ); 00984 00985 while( *p == 0 && p < buf + siglen ) 00986 p++; 00987 00988 if( p == buf + siglen ) 00989 return( POLARSSL_ERR_RSA_INVALID_PADDING ); 00990 00991 if( *p++ != 0x01 ) 00992 return( POLARSSL_ERR_RSA_INVALID_PADDING ); 00993 00994 slen -= p - buf; 00995 00996 // Generate H = Hash( M' ) 00997 // 00998 md_starts( &md_ctx ); 00999 md_update( &md_ctx, zeros, 8 ); 01000 md_update( &md_ctx, hash, hashlen ); 01001 md_update( &md_ctx, p, slen ); 01002 md_finish( &md_ctx, result ); 01003 01004 if( memcmp( p + slen, result, hlen ) == 0 ) 01005 return( 0 ); 01006 else 01007 return( POLARSSL_ERR_RSA_VERIFY_FAILED ); 01008 #endif 01009 01010 default: 01011 01012 return( POLARSSL_ERR_RSA_INVALID_PADDING ); 01013 } 01014 01015 return( POLARSSL_ERR_RSA_INVALID_PADDING ); 01016 } 01017 01018 /* 01019 * Free the components of an RSA key 01020 */ 01021 void rsa_free( rsa_context *ctx ) 01022 { 01023 mpi_free( &ctx->RQ ); mpi_free( &ctx->RP ); mpi_free( &ctx->RN ); 01024 mpi_free( &ctx->QP ); mpi_free( &ctx->DQ ); mpi_free( &ctx->DP ); 01025 mpi_free( &ctx->Q ); mpi_free( &ctx->P ); mpi_free( &ctx->D ); 01026 mpi_free( &ctx->E ); mpi_free( &ctx->N ); 01027 } 01028 01029 #if defined(POLARSSL_SELF_TEST) 01030 01031 #include "polarssl/sha1.h" 01032 01033 /* 01034 * Example RSA-1024 keypair, for test purposes 01035 */ 01036 #define KEY_LEN 128 01037 01038 #define RSA_N "9292758453063D803DD603D5E777D788" \ 01039 "8ED1D5BF35786190FA2F23EBC0848AEA" \ 01040 "DDA92CA6C3D80B32C4D109BE0F36D6AE" \ 01041 "7130B9CED7ACDF54CFC7555AC14EEBAB" \ 01042 "93A89813FBF3C4F8066D2D800F7C38A8" \ 01043 "1AE31942917403FF4946B0A83D3D3E05" \ 01044 "EE57C6F5F5606FB5D4BC6CD34EE0801A" \ 01045 "5E94BB77B07507233A0BC7BAC8F90F79" 01046 01047 #define RSA_E "10001" 01048 01049 #define RSA_D "24BF6185468786FDD303083D25E64EFC" \ 01050 "66CA472BC44D253102F8B4A9D3BFA750" \ 01051 "91386C0077937FE33FA3252D28855837" \ 01052 "AE1B484A8A9A45F7EE8C0C634F99E8CD" \ 01053 "DF79C5CE07EE72C7F123142198164234" \ 01054 "CABB724CF78B8173B9F880FC86322407" \ 01055 "AF1FEDFDDE2BEB674CA15F3E81A1521E" \ 01056 "071513A1E85B5DFA031F21ECAE91A34D" 01057 01058 #define RSA_P "C36D0EB7FCD285223CFB5AABA5BDA3D8" \ 01059 "2C01CAD19EA484A87EA4377637E75500" \ 01060 "FCB2005C5C7DD6EC4AC023CDA285D796" \ 01061 "C3D9E75E1EFC42488BB4F1D13AC30A57" 01062 01063 #define RSA_Q "C000DF51A7C77AE8D7C7370C1FF55B69" \ 01064 "E211C2B9E5DB1ED0BF61D0D9899620F4" \ 01065 "910E4168387E3C30AA1E00C339A79508" \ 01066 "8452DD96A9A5EA5D9DCA68DA636032AF" 01067 01068 #define RSA_DP "C1ACF567564274FB07A0BBAD5D26E298" \ 01069 "3C94D22288ACD763FD8E5600ED4A702D" \ 01070 "F84198A5F06C2E72236AE490C93F07F8" \ 01071 "3CC559CD27BC2D1CA488811730BB5725" 01072 01073 #define RSA_DQ "4959CBF6F8FEF750AEE6977C155579C7" \ 01074 "D8AAEA56749EA28623272E4F7D0592AF" \ 01075 "7C1F1313CAC9471B5C523BFE592F517B" \ 01076 "407A1BD76C164B93DA2D32A383E58357" 01077 01078 #define RSA_QP "9AE7FBC99546432DF71896FC239EADAE" \ 01079 "F38D18D2B2F0E2DD275AA977E2BF4411" \ 01080 "F5A3B2A5D33605AEBBCCBA7FEB9F2D2F" \ 01081 "A74206CEC169D74BF5A8C50D6F48EA08" 01082 01083 #define PT_LEN 24 01084 #define RSA_PT "\xAA\xBB\xCC\x03\x02\x01\x00\xFF\xFF\xFF\xFF\xFF" \ 01085 "\x11\x22\x33\x0A\x0B\x0C\xCC\xDD\xDD\xDD\xDD\xDD" 01086 01087 static int myrand( void *rng_state, unsigned char *output, size_t len ) 01088 { 01089 size_t i; 01090 01091 if( rng_state != NULL ) 01092 rng_state = NULL; 01093 01094 for( i = 0; i < len; ++i ) 01095 output[i] = rand(); 01096 01097 return( 0 ); 01098 } 01099 01100 /* 01101 * Checkup routine 01102 */ 01103 int rsa_self_test( int verbose ) 01104 { 01105 size_t len; 01106 rsa_context rsa; 01107 unsigned char rsa_plaintext[PT_LEN]; 01108 unsigned char rsa_decrypted[PT_LEN]; 01109 unsigned char rsa_ciphertext[KEY_LEN]; 01110 #if defined(POLARSSL_SHA1_C) 01111 unsigned char sha1sum[20]; 01112 #endif 01113 01114 rsa_init( &rsa, RSA_PKCS_V15, 0 ); 01115 01116 rsa.len = KEY_LEN; 01117 mpi_read_string( &rsa.N , 16, RSA_N ); 01118 mpi_read_string( &rsa.E , 16, RSA_E ); 01119 mpi_read_string( &rsa.D , 16, RSA_D ); 01120 mpi_read_string( &rsa.P , 16, RSA_P ); 01121 mpi_read_string( &rsa.Q , 16, RSA_Q ); 01122 mpi_read_string( &rsa.DP, 16, RSA_DP ); 01123 mpi_read_string( &rsa.DQ, 16, RSA_DQ ); 01124 mpi_read_string( &rsa.QP, 16, RSA_QP ); 01125 01126 if( verbose != 0 ) 01127 printf( " RSA key validation: " ); 01128 01129 if( rsa_check_pubkey( &rsa ) != 0 || 01130 rsa_check_privkey( &rsa ) != 0 ) 01131 { 01132 if( verbose != 0 ) 01133 printf( "failed\n" ); 01134 01135 return( 1 ); 01136 } 01137 01138 if( verbose != 0 ) 01139 printf( "passed\n PKCS#1 encryption : " ); 01140 01141 memcpy( rsa_plaintext, RSA_PT, PT_LEN ); 01142 01143 if( rsa_pkcs1_encrypt( &rsa, &myrand, NULL, RSA_PUBLIC, PT_LEN, 01144 rsa_plaintext, rsa_ciphertext ) != 0 ) 01145 { 01146 if( verbose != 0 ) 01147 printf( "failed\n" ); 01148 01149 return( 1 ); 01150 } 01151 01152 if( verbose != 0 ) 01153 printf( "passed\n PKCS#1 decryption : " ); 01154 01155 if( rsa_pkcs1_decrypt( &rsa, RSA_PRIVATE, &len, 01156 rsa_ciphertext, rsa_decrypted, 01157 sizeof(rsa_decrypted) ) != 0 ) 01158 { 01159 if( verbose != 0 ) 01160 printf( "failed\n" ); 01161 01162 return( 1 ); 01163 } 01164 01165 if( memcmp( rsa_decrypted, rsa_plaintext, len ) != 0 ) 01166 { 01167 if( verbose != 0 ) 01168 printf( "failed\n" ); 01169 01170 return( 1 ); 01171 } 01172 01173 #if defined(POLARSSL_SHA1_C) 01174 if( verbose != 0 ) 01175 printf( "passed\n PKCS#1 data sign : " ); 01176 01177 sha1( rsa_plaintext, PT_LEN, sha1sum ); 01178 01179 if( rsa_pkcs1_sign( &rsa, NULL, NULL, RSA_PRIVATE, SIG_RSA_SHA1, 20, 01180 sha1sum, rsa_ciphertext ) != 0 ) 01181 { 01182 if( verbose != 0 ) 01183 printf( "failed\n" ); 01184 01185 return( 1 ); 01186 } 01187 01188 if( verbose != 0 ) 01189 printf( "passed\n PKCS#1 sig. verify: " ); 01190 01191 if( rsa_pkcs1_verify( &rsa, RSA_PUBLIC, SIG_RSA_SHA1, 20, 01192 sha1sum, rsa_ciphertext ) != 0 ) 01193 { 01194 if( verbose != 0 ) 01195 printf( "failed\n" ); 01196 01197 return( 1 ); 01198 } 01199 01200 if( verbose != 0 ) 01201 printf( "passed\n\n" ); 01202 #endif /* POLARSSL_SHA1_C */ 01203 01204 rsa_free( &rsa ); 01205 01206 return( 0 ); 01207 } 01208 01209 #endif 01210 01211 #endif