src/src/pdkim/rsa.c

   1 /*
   2  *  The RSA public-key cryptosystem
   3  *
   4  *  Copyright (C) 2006-2010, Brainspark B.V.
   5  *
   6  *  This file is part of PolarSSL (http://www.polarssl.org)
   7  *  Lead Maintainer: Paul Bakker <polarssl_maintainer at polarssl.org>
   8  *
   9  *  All rights reserved.
  10  *
  11  *  This program is free software; you can redistribute it and/or modify
  12  *  it under the terms of the GNU General Public License as published by
  13  *  the Free Software Foundation; either version 2 of the License, or
  14  *  (at your option) any later version.
  15  *
  16  *  This program is distributed in the hope that it will be useful,
  17  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19  *  GNU General Public License for more details.
  20  *
  21  *  You should have received a copy of the GNU General Public License along
  22  *  with this program; if not, write to the Free Software Foundation, Inc.,
  23  *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  24  */
  25 /*
  26  *  RSA was designed by Ron Rivest, Adi Shamir and Len Adleman.
  27  *
  28  *  http://theory.lcs.mit.edu/~rivest/rsapaper.pdf
  29  *  http://www.cacr.math.uwaterloo.ca/hac/about/chap8.pdf
  30  */
  31
  32 /* $Cambridge: exim/src/src/pdkim/rsa.c,v 1.3 2009/12/07 13:05:07 tom Exp $ */
  33
  34 #include "rsa.h"
  35 #include "base64.h"
  36
  37 #include <stdlib.h>
  38 #include <string.h>
  39 #include <stdio.h>
  40
  41
  42
  43 /* *************** begin copy from x509parse.c ********************/
  44 /*
  45  * ASN.1 DER decoding routines
  46  */
  47 static int asn1_get_len( unsigned char **p,
  48                          const unsigned char *end,
  49                          int *len )
  50 {
  51     if( ( end - *p ) < 1 )
  52         return( POLARSSL_ERR_ASN1_OUT_OF_DATA );
  53
  54     if( ( **p & 0x80 ) == 0 )
  55         *len = *(*p)++;
  56     else
  57     {
  58         switch( **p & 0x7F )
  59         {
  60         case 1:
  61             if( ( end - *p ) < 2 )
  62                 return( POLARSSL_ERR_ASN1_OUT_OF_DATA );
  63
  64             *len = (*p)[1];
  65             (*p) += 2;
  66             break;
  67
  68         case 2:
  69             if( ( end - *p ) < 3 )
  70                 return( POLARSSL_ERR_ASN1_OUT_OF_DATA );
  71
  72             *len = ( (*p)[1] << 8 ) | (*p)[2];
  73             (*p) += 3;
  74             break;
  75
  76         default:
  77             return( POLARSSL_ERR_ASN1_INVALID_LENGTH );
  78             break;
  79         }
  80     }
  81
  82     if( *len > (int) ( end - *p ) )
  83         return( POLARSSL_ERR_ASN1_OUT_OF_DATA );
  84
  85     return( 0 );
  86 }
  87
  88 static int asn1_get_tag( unsigned char **p,
  89                          const unsigned char *end,
  90                          int *len, int tag )
  91 {
  92     if( ( end - *p ) < 1 )
  93         return( POLARSSL_ERR_ASN1_OUT_OF_DATA );
  94
  95     if( **p != tag )
  96         return( POLARSSL_ERR_ASN1_UNEXPECTED_TAG );
  97
  98     (*p)++;
  99
 100     return( asn1_get_len( p, end, len ) );
 101 }
 102
 103 static int asn1_get_int( unsigned char **p,
 104                          const unsigned char *end,
 105                          int *val )
 106 {
 107     int ret, len;
 108
 109     if( ( ret = asn1_get_tag( p, end, &len, ASN1_INTEGER ) ) != 0 )
 110         return( ret );
 111
 112     if( len > (int) sizeof( int ) || ( **p & 0x80 ) != 0 )
 113         return( POLARSSL_ERR_ASN1_INVALID_LENGTH );
 114
 115     *val = 0;
 116
 117     while( len-- > 0 )
 118     {
 119         *val = ( *val << 8 ) | **p;
 120         (*p)++;
 121     }
 122
 123     return( 0 );
 124 }
 125
 126 static int asn1_get_mpi( unsigned char **p,
 127                          const unsigned char *end,
 128                          mpi *X )
 129 {
 130     int ret, len;
 131
 132     if( ( ret = asn1_get_tag( p, end, &len, ASN1_INTEGER ) ) != 0 )
 133         return( ret );
 134
 135     ret = mpi_read_binary( X, *p, len );
 136
 137     *p += len;
 138
 139     return( ret );
 140 }
 141 /* ***************   end copy from x509parse.c ********************/
 142
 143
 144
 145
 146 /*
 147  * Initialize an RSA context
 148  */
 149 void rsa_init( rsa_context *ctx,
 150                int padding,
 151                int hash_id )
 152 {
 153     memset( ctx, 0, sizeof( rsa_context ) );
 154
 155     ctx->padding = padding;
 156     ctx->hash_id = hash_id;
 157 }
 158
 159 #if defined(POLARSSL_GENPRIME)
 160
 161 /*
 162  * Generate an RSA keypair
 163  */
 164 int rsa_gen_key( rsa_context *ctx,
 165         int (*f_rng)(void *),
 166         void *p_rng,
 167         int nbits, int exponent )
 168 {
 169     int ret;
 170     mpi P1, Q1, H, G;
 171
 172     if( f_rng == NULL || nbits < 128 || exponent < 3 )
 173         return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
 174
 175     mpi_init( &P1, &Q1, &H, &G, NULL );
 176
 177     /*
 178      * find primes P and Q with Q < P so that:
 179      * GCD( E, (P-1)*(Q-1) ) == 1
 180      */
 181     MPI_CHK( mpi_lset( &ctx->E, exponent ) );
 182
 183     do
 184     {
 185         MPI_CHK( mpi_gen_prime( &ctx->P, ( nbits + 1 ) >> 1, 0,
 186                                 f_rng, p_rng ) );
 187
 188         MPI_CHK( mpi_gen_prime( &ctx->Q, ( nbits + 1 ) >> 1, 0,
 189                                 f_rng, p_rng ) );
 190
 191         if( mpi_cmp_mpi( &ctx->P, &ctx->Q ) < 0 )
 192             mpi_swap( &ctx->P, &ctx->Q );
 193
 194         if( mpi_cmp_mpi( &ctx->P, &ctx->Q ) == 0 )
 195             continue;
 196
 197         MPI_CHK( mpi_mul_mpi( &ctx->N, &ctx->P, &ctx->Q ) );
 198         if( mpi_msb( &ctx->N ) != nbits )
 199             continue;
 200
 201         MPI_CHK( mpi_sub_int( &P1, &ctx->P, 1 ) );
 202         MPI_CHK( mpi_sub_int( &Q1, &ctx->Q, 1 ) );
 203         MPI_CHK( mpi_mul_mpi( &H, &P1, &Q1 ) );
 204         MPI_CHK( mpi_gcd( &G, &ctx->E, &H  ) );
 205     }
 206     while( mpi_cmp_int( &G, 1 ) != 0 );
 207
 208     /*
 209      * D  = E^-1 mod ((P-1)*(Q-1))
 210      * DP = D mod (P - 1)
 211      * DQ = D mod (Q - 1)
 212      * QP = Q^-1 mod P
 213      */
 214     MPI_CHK( mpi_inv_mod( &ctx->D , &ctx->E, &H  ) );
 215     MPI_CHK( mpi_mod_mpi( &ctx->DP, &ctx->D, &P1 ) );
 216     MPI_CHK( mpi_mod_mpi( &ctx->DQ, &ctx->D, &Q1 ) );
 217     MPI_CHK( mpi_inv_mod( &ctx->QP, &ctx->Q, &ctx->P ) );
 218
 219     ctx->len = ( mpi_msb( &ctx->N ) + 7 ) >> 3;
 220
 221 cleanup:
 222
 223     mpi_free( &G, &H, &Q1, &P1, NULL );
 224
 225     if( ret != 0 )
 226     {
 227         rsa_free( ctx );
 228         return( POLARSSL_ERR_RSA_KEY_GEN_FAILED | ret );
 229     }
 230
 231     return( 0 );
 232 }
 233
 234 #endif
 235
 236 /*
 237  * Check a public RSA key
 238  */
 239 int rsa_check_pubkey( const rsa_context *ctx )
 240 {
 241     if( !ctx->N.p || !ctx->E.p )
 242         return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED );
 243
 244     if( ( ctx->N.p[0] & 1 ) == 0 ||
 245         ( ctx->E.p[0] & 1 ) == 0 )
 246         return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED );
 247
 248     if( mpi_msb( &ctx->N ) < 128 ||
 249         mpi_msb( &ctx->N ) > 4096 )
 250         return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED );
 251
 252     if( mpi_msb( &ctx->E ) < 2 ||
 253         mpi_msb( &ctx->E ) > 64 )
 254         return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED );
 255
 256     return( 0 );
 257 }
 258
 259 /*
 260  * Check a private RSA key
 261  */
 262 int rsa_check_privkey( const rsa_context *ctx )
 263 {
 264     int ret;
 265     mpi PQ, DE, P1, Q1, H, I, G, G2, L1, L2;
 266
 267     if( ( ret = rsa_check_pubkey( ctx ) ) != 0 )
 268         return( ret );
 269
 270     if( !ctx->P.p || !ctx->Q.p || !ctx->D.p )
 271         return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED );
 272
 273     mpi_init( &PQ, &DE, &P1, &Q1, &H, &I, &G, &G2, &L1, &L2, NULL );
 274
 275     MPI_CHK( mpi_mul_mpi( &PQ, &ctx->P, &ctx->Q ) );
 276     MPI_CHK( mpi_mul_mpi( &DE, &ctx->D, &ctx->E ) );
 277     MPI_CHK( mpi_sub_int( &P1, &ctx->P, 1 ) );
 278     MPI_CHK( mpi_sub_int( &Q1, &ctx->Q, 1 ) );
 279     MPI_CHK( mpi_mul_mpi( &H, &P1, &Q1 ) );
 280     MPI_CHK( mpi_gcd( &G, &ctx->E, &H  ) );
 281
 282     MPI_CHK( mpi_gcd( &G2, &P1, &Q1 ) );
 283     MPI_CHK( mpi_div_mpi( &L1, &L2, &H, &G2 ) );
 284     MPI_CHK( mpi_mod_mpi( &I, &DE, &L1  ) );
 285
 286     /*
 287      * Check for a valid PKCS1v2 private key
 288      */
 289     if( mpi_cmp_mpi( &PQ, &ctx->N ) == 0 &&
 290         mpi_cmp_int( &L2, 0 ) == 0 &&
 291         mpi_cmp_int( &I, 1 ) == 0 &&
 292         mpi_cmp_int( &G, 1 ) == 0 )
 293     {
 294         mpi_free( &G, &I, &H, &Q1, &P1, &DE, &PQ, &G2, &L1, &L2, NULL );
 295         return( 0 );
 296     }
 297
 298
 299 cleanup:
 300
 301     mpi_free( &G, &I, &H, &Q1, &P1, &DE, &PQ, &G2, &L1, &L2, NULL );
 302     return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED | ret );
 303 }
 304
 305 /*
 306  * Do an RSA public key operation
 307  */
 308 int rsa_public( rsa_context *ctx,
 309                 const unsigned char *input,
 310                 unsigned char *output )
 311 {
 312     int ret, olen;
 313     mpi T;
 314
 315     mpi_init( &T, NULL );
 316
 317     MPI_CHK( mpi_read_binary( &T, input, ctx->len ) );
 318
 319     if( mpi_cmp_mpi( &T, &ctx->N ) >= 0 )
 320     {
 321         mpi_free( &T, NULL );
 322         return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
 323     }
 324
 325     olen = ctx->len;
 326     MPI_CHK( mpi_exp_mod( &T, &T, &ctx->E, &ctx->N, &ctx->RN ) );
 327     MPI_CHK( mpi_write_binary( &T, output, olen ) );
 328
 329 cleanup:
 330
 331     mpi_free( &T, NULL );
 332
 333     if( ret != 0 )
 334         return( POLARSSL_ERR_RSA_PUBLIC_FAILED | ret );
 335
 336     return( 0 );
 337 }
 338
 339 /*
 340  * Do an RSA private key operation
 341  */
 342 int rsa_private( rsa_context *ctx,
 343                  const unsigned char *input,
 344                  unsigned char *output )
 345 {
 346     int ret, olen;
 347     mpi T, T1, T2;
 348
 349     mpi_init( &T, &T1, &T2, NULL );
 350
 351     MPI_CHK( mpi_read_binary( &T, input, ctx->len ) );
 352
 353     if( mpi_cmp_mpi( &T, &ctx->N ) >= 0 )
 354     {
 355         mpi_free( &T, NULL );
 356         return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
 357     }
 358
 359 #if 0
 360     MPI_CHK( mpi_exp_mod( &T, &T, &ctx->D, &ctx->N, &ctx->RN ) );
 361 #else
 362     /*
 363      * faster decryption using the CRT
 364      *
 365      * T1 = input ^ dP mod P
 366      * T2 = input ^ dQ mod Q
 367      */
 368     MPI_CHK( mpi_exp_mod( &T1, &T, &ctx->DP, &ctx->P, &ctx->RP ) );
 369     MPI_CHK( mpi_exp_mod( &T2, &T, &ctx->DQ, &ctx->Q, &ctx->RQ ) );
 370
 371     /*
 372      * T = (T1 - T2) * (Q^-1 mod P) mod P
 373      */
 374     MPI_CHK( mpi_sub_mpi( &T, &T1, &T2 ) );
 375     MPI_CHK( mpi_mul_mpi( &T1, &T, &ctx->QP ) );
 376     MPI_CHK( mpi_mod_mpi( &T, &T1, &ctx->P ) );
 377
 378     /*
 379      * output = T2 + T * Q
 380      */
 381     MPI_CHK( mpi_mul_mpi( &T1, &T, &ctx->Q ) );
 382     MPI_CHK( mpi_add_mpi( &T, &T2, &T1 ) );
 383 #endif
 384
 385     olen = ctx->len;
 386     MPI_CHK( mpi_write_binary( &T, output, olen ) );
 387
 388 cleanup:
 389
 390     mpi_free( &T, &T1, &T2, NULL );
 391
 392     if( ret != 0 )
 393         return( POLARSSL_ERR_RSA_PRIVATE_FAILED | ret );
 394
 395     return( 0 );
 396 }
 397
 398 /*
 399  * Add the message padding, then do an RSA operation
 400  */
 401 int rsa_pkcs1_encrypt( rsa_context *ctx,
 402                        int (*f_rng)(void *),
 403                        void *p_rng,
 404                        int mode, int  ilen,
 405                        const unsigned char *input,
 406                        unsigned char *output )
 407 {
 408     int nb_pad, olen;
 409     unsigned char *p = output;
 410
 411     olen = ctx->len;
 412
 413     switch( ctx->padding )
 414     {
 415         case RSA_PKCS_V15:
 416
 417             if( ilen < 0 || olen < ilen + 11 || f_rng == NULL )
 418                 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
 419
 420             nb_pad = olen - 3 - ilen;
 421
 422             *p++ = 0;
 423             *p++ = RSA_CRYPT;
 424
 425             while( nb_pad-- > 0 )
 426             {
 427                 int rng_dl = 100;
 428
 429                 do {
 430                     *p = (unsigned char) f_rng( p_rng );
 431                 } while( *p == 0 && --rng_dl );
 432
 433                 // Check if RNG failed to generate data
 434                 //
 435                 if( rng_dl == 0 )
 436                     return POLARSSL_ERR_RSA_RNG_FAILED;
 437
 438                 p++;
 439             }
 440             *p++ = 0;
 441             memcpy( p, input, ilen );
 442             break;
 443
 444         default:
 445
 446             return( POLARSSL_ERR_RSA_INVALID_PADDING );
 447     }
 448
 449     return( ( mode == RSA_PUBLIC )
 450             ? rsa_public(  ctx, output, output )
 451             : rsa_private( ctx, output, output ) );
 452 }
 453
 454 /*
 455  * Do an RSA operation, then remove the message padding
 456  */
 457 int rsa_pkcs1_decrypt( rsa_context *ctx,
 458                        int mode, int *olen,
 459                        const unsigned char *input,
 460                        unsigned char *output,
 461                        int output_max_len)
 462 {
 463     int ret, ilen;
 464     unsigned char *p;
 465     unsigned char buf[1024];
 466
 467     ilen = ctx->len;
 468
 469     if( ilen < 16 || ilen > (int) sizeof( buf ) )
 470         return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
 471
 472     ret = ( mode == RSA_PUBLIC )
 473           ? rsa_public(  ctx, input, buf )
 474           : rsa_private( ctx, input, buf );
 475
 476     if( ret != 0 )
 477         return( ret );
 478
 479     p = buf;
 480
 481     switch( ctx->padding )
 482     {
 483         case RSA_PKCS_V15:
 484
 485             if( *p++ != 0 || *p++ != RSA_CRYPT )
 486                 return( POLARSSL_ERR_RSA_INVALID_PADDING );
 487
 488             while( *p != 0 )
 489             {
 490                 if( p >= buf + ilen - 1 )
 491                     return( POLARSSL_ERR_RSA_INVALID_PADDING );
 492                 p++;
 493             }
 494             p++;
 495             break;
 496
 497         default:
 498
 499             return( POLARSSL_ERR_RSA_INVALID_PADDING );
 500     }
 501
 502     if (ilen - (int)(p - buf) > output_max_len)
 503       return( POLARSSL_ERR_RSA_OUTPUT_TOO_LARGE );
 504
 505     *olen = ilen - (int)(p - buf);
 506     memcpy( output, p, *olen );
 507
 508     return( 0 );
 509 }
 510
 511 /*
 512  * Do an RSA operation to sign the message digest
 513  */
 514 int rsa_pkcs1_sign( rsa_context *ctx,
 515                     int mode,
 516                     int hash_id,
 517                     int hashlen,
 518                     const unsigned char *hash,
 519                     unsigned char *sig )
 520 {
 521     int nb_pad, olen;
 522     unsigned char *p = sig;
 523
 524     olen = ctx->len;
 525
 526     switch( ctx->padding )
 527     {
 528         case RSA_PKCS_V15:
 529
 530             switch( hash_id )
 531             {
 532                 case SIG_RSA_RAW:
 533                     nb_pad = olen - 3 - hashlen;
 534                     break;
 535
 536                 case SIG_RSA_MD2:
 537                 case SIG_RSA_MD4:
 538                 case SIG_RSA_MD5:
 539                     nb_pad = olen - 3 - 34;
 540                     break;
 541
 542                 case SIG_RSA_SHA1:
 543                     nb_pad = olen - 3 - 35;
 544                     break;
 545
 546                 case SIG_RSA_SHA224:
 547                     nb_pad = olen - 3 - 47;
 548                     break;
 549
 550                 case SIG_RSA_SHA256:
 551                     nb_pad = olen - 3 - 51;
 552                     break;
 553
 554                 case SIG_RSA_SHA384:
 555                     nb_pad = olen - 3 - 67;
 556                     break;
 557
 558                 case SIG_RSA_SHA512:
 559                     nb_pad = olen - 3 - 83;
 560                     break;
 561
 562
 563                 default:
 564                     return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
 565             }
 566
 567             if( nb_pad < 8 )
 568                 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
 569
 570             *p++ = 0;
 571             *p++ = RSA_SIGN;
 572             memset( p, 0xFF, nb_pad );
 573             p += nb_pad;
 574             *p++ = 0;
 575             break;
 576
 577         default:
 578
 579             return( POLARSSL_ERR_RSA_INVALID_PADDING );
 580     }
 581
 582     switch( hash_id )
 583     {
 584         case SIG_RSA_RAW:
 585             memcpy( p, hash, hashlen );
 586             break;
 587
 588         case SIG_RSA_MD2:
 589             memcpy( p, ASN1_HASH_MDX, 18 );
 590             memcpy( p + 18, hash, 16 );
 591             p[13] = 2; break;
 592
 593         case SIG_RSA_MD4:
 594             memcpy( p, ASN1_HASH_MDX, 18 );
 595             memcpy( p + 18, hash, 16 );
 596             p[13] = 4; break;
 597
 598         case SIG_RSA_MD5:
 599             memcpy( p, ASN1_HASH_MDX, 18 );
 600             memcpy( p + 18, hash, 16 );
 601             p[13] = 5; break;
 602
 603         case SIG_RSA_SHA1:
 604             memcpy( p, ASN1_HASH_SHA1, 15 );
 605             memcpy( p + 15, hash, 20 );
 606             break;
 607
 608         case SIG_RSA_SHA224:
 609             memcpy( p, ASN1_HASH_SHA2X, 19 );
 610             memcpy( p + 19, hash, 28 );
 611             p[1] += 28; p[14] = 4; p[18] += 28; break;
 612
 613         case SIG_RSA_SHA256:
 614             memcpy( p, ASN1_HASH_SHA2X, 19 );
 615             memcpy( p + 19, hash, 32 );
 616             p[1] += 32; p[14] = 1; p[18] += 32; break;
 617
 618         case SIG_RSA_SHA384:
 619             memcpy( p, ASN1_HASH_SHA2X, 19 );
 620             memcpy( p + 19, hash, 48 );
 621             p[1] += 48; p[14] = 2; p[18] += 48; break;
 622
 623         case SIG_RSA_SHA512:
 624             memcpy( p, ASN1_HASH_SHA2X, 19 );
 625             memcpy( p + 19, hash, 64 );
 626             p[1] += 64; p[14] = 3; p[18] += 64; break;
 627
 628         default:
 629             return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
 630     }
 631
 632     return( ( mode == RSA_PUBLIC )
 633             ? rsa_public(  ctx, sig, sig )
 634             : rsa_private( ctx, sig, sig ) );
 635 }
 636
 637 /*
 638  * Do an RSA operation and check the message digest
 639  */
 640 int rsa_pkcs1_verify( rsa_context *ctx,
 641                       int mode,
 642                       int hash_id,
 643                       int hashlen,
 644                       const unsigned char *hash,
 645                       unsigned char *sig )
 646 {
 647     int ret, len, siglen;
 648     unsigned char *p, c;
 649     unsigned char buf[1024];
 650
 651     siglen = ctx->len;
 652
 653     if( siglen < 16 || siglen > (int) sizeof( buf ) )
 654         return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
 655
 656     ret = ( mode == RSA_PUBLIC )
 657           ? rsa_public(  ctx, sig, buf )
 658           : rsa_private( ctx, sig, buf );
 659
 660     if( ret != 0 )
 661         return( ret );
 662
 663     p = buf;
 664
 665     switch( ctx->padding )
 666     {
 667         case RSA_PKCS_V15:
 668
 669             if( *p++ != 0 || *p++ != RSA_SIGN )
 670                 return( POLARSSL_ERR_RSA_INVALID_PADDING );
 671
 672             while( *p != 0 )
 673             {
 674                 if( p >= buf + siglen - 1 || *p != 0xFF )
 675                     return( POLARSSL_ERR_RSA_INVALID_PADDING );
 676                 p++;
 677             }
 678             p++;
 679             break;
 680
 681         default:
 682
 683             return( POLARSSL_ERR_RSA_INVALID_PADDING );
 684     }
 685
 686     len = siglen - (int)( p - buf );
 687
 688     if( len == 34 )
 689     {
 690         c = p[13];
 691         p[13] = 0;
 692
 693         if( memcmp( p, ASN1_HASH_MDX, 18 ) != 0 )
 694             return( POLARSSL_ERR_RSA_VERIFY_FAILED );
 695
 696         if( ( c == 2 && hash_id == SIG_RSA_MD2 ) ||
 697             ( c == 4 && hash_id == SIG_RSA_MD4 ) ||
 698             ( c == 5 && hash_id == SIG_RSA_MD5 ) )
 699         {
 700             if( memcmp( p + 18, hash, 16 ) == 0 )
 701                 return( 0 );
 702             else
 703                 return( POLARSSL_ERR_RSA_VERIFY_FAILED );
 704         }
 705     }
 706
 707     if( len == 35 && hash_id == SIG_RSA_SHA1 )
 708     {
 709         if( memcmp( p, ASN1_HASH_SHA1, 15 ) == 0 &&
 710             memcmp( p + 15, hash, 20 ) == 0 )
 711             return( 0 );
 712         else
 713             return( POLARSSL_ERR_RSA_VERIFY_FAILED );
 714     }
 715     if( ( len == 19 + 28 && p[14] == 4 && hash_id == SIG_RSA_SHA224 ) ||
 716         ( len == 19 + 32 && p[14] == 1 && hash_id == SIG_RSA_SHA256 ) ||
 717         ( len == 19 + 48 && p[14] == 2 && hash_id == SIG_RSA_SHA384 ) ||
 718         ( len == 19 + 64 && p[14] == 3 && hash_id == SIG_RSA_SHA512 ) )
 719     {
 720         c = p[1] - 17;
 721         p[1] = 17;
 722         p[14] = 0;
 723
 724         if( p[18] == c &&
 725                 memcmp( p, ASN1_HASH_SHA2X, 18 ) == 0 &&
 726                 memcmp( p + 19, hash, c ) == 0 )
 727             return( 0 );
 728         else
 729             return( POLARSSL_ERR_RSA_VERIFY_FAILED );
 730     }
 731
 732     if( len == hashlen && hash_id == SIG_RSA_RAW )
 733     {
 734         if( memcmp( p, hash, hashlen ) == 0 )
 735             return( 0 );
 736         else
 737             return( POLARSSL_ERR_RSA_VERIFY_FAILED );
 738     }
 739
 740     return( POLARSSL_ERR_RSA_INVALID_PADDING );
 741 }
 742
 743 /*
 744  * Free the components of an RSA key
 745  */
 746 void rsa_free( rsa_context *ctx )
 747 {
 748     mpi_free( &ctx->RQ, &ctx->RP, &ctx->RN,
 749               &ctx->QP, &ctx->DQ, &ctx->DP,
 750               &ctx->Q,  &ctx->P,  &ctx->D,
 751               &ctx->E,  &ctx->N,  NULL );
 752 }
 753
 754
 755 /* PDKIM code (not copied from polarssl) */
 756 /*
 757  * Parse a public RSA key
 758
 759 OpenSSL RSA public key ASN1 container
 760   0:d=0  hl=3 l= 159 cons: SEQUENCE
 761   3:d=1  hl=2 l=  13 cons: SEQUENCE
 762   5:d=2  hl=2 l=   9 prim: OBJECT:rsaEncryption
 763  16:d=2  hl=2 l=   0 prim: NULL
 764  18:d=1  hl=3 l= 141 prim: BIT STRING:RSAPublicKey (below)
 765
 766 RSAPublicKey ASN1 container
 767   0:d=0  hl=3 l= 137 cons: SEQUENCE
 768   3:d=1  hl=3 l= 129 prim: INTEGER:Public modulus
 769 135:d=1  hl=2 l=   3 prim: INTEGER:Public exponent
 770 */
 771
 772 int rsa_parse_public_key( rsa_context *rsa, unsigned char *buf, int buflen )
 773 {
 774     unsigned char *p, *end;
 775     int ret, len;
 776
 777     p = buf;
 778     end = buf+buflen;
 779
 780     if( ( ret = asn1_get_tag( &p, end, &len,
 781             ASN1_CONSTRUCTED | ASN1_SEQUENCE ) ) != 0 ) {
 782         return( POLARSSL_ERR_X509_KEY_INVALID_FORMAT | ret );
 783     }
 784
 785     if( ( ret = asn1_get_tag( &p, end, &len,
 786             ASN1_CONSTRUCTED | ASN1_SEQUENCE ) ) == 0 ) {
 787         /* Skip over embedded rsaEncryption Object */
 788         p+=len;
 789
 790         /* The RSAPublicKey ASN1 container is wrapped in a BIT STRING */
 791         if( ( ret = asn1_get_tag( &p, end, &len,
 792                 ASN1_BIT_STRING ) ) != 0 ) {
 793             return( POLARSSL_ERR_X509_KEY_INVALID_FORMAT | ret );
 794         }
 795
 796         /* Limit range to that BIT STRING */
 797         end = p + len;
 798         p++;
 799
 800         if( ( ret = asn1_get_tag( &p, end, &len,
 801                 ASN1_CONSTRUCTED | ASN1_SEQUENCE ) ) != 0 ) {
 802             return( POLARSSL_ERR_X509_KEY_INVALID_FORMAT | ret );
 803         }
 804     }
 805
 806     if ( ( ( ret = asn1_get_mpi( &p, end, &(rsa->N)  ) ) == 0 ) &&
 807          ( ( ret = asn1_get_mpi( &p, end, &(rsa->E)  ) ) == 0 ) ) {
 808         rsa->len = mpi_size( &rsa->N );
 809         return 0;
 810     }
 811
 812     return( POLARSSL_ERR_X509_KEY_INVALID_FORMAT | ret );
 813 }
 814
 815 /*
 816  * Parse a private RSA key
 817  */
 818 int rsa_parse_key( rsa_context *rsa, unsigned char *buf, int buflen,
 819                                      unsigned char *pwd, int pwdlen )
 820 {
 821     int ret, len, enc;
 822     unsigned char *s1, *s2;
 823     unsigned char *p, *end;
 824
 825     s1 = (unsigned char *) strstr( (char *) buf,
 826         "-----BEGIN RSA PRIVATE KEY-----" );
 827
 828     if( s1 != NULL )
 829     {
 830         s2 = (unsigned char *) strstr( (char *) buf,
 831             "-----END RSA PRIVATE KEY-----" );
 832
 833         if( s2 == NULL || s2 <= s1 )
 834             return( POLARSSL_ERR_X509_KEY_INVALID_PEM );
 835
 836         s1 += 31;
 837         if( *s1 == '\r' ) s1++;
 838         if( *s1 == '\n' ) s1++;
 839             else return( POLARSSL_ERR_X509_KEY_INVALID_PEM );
 840
 841         enc = 0;
 842
 843         if( memcmp( s1, "Proc-Type: 4,ENCRYPTED", 22 ) == 0 )
 844         {
 845             return( POLARSSL_ERR_X509_FEATURE_UNAVAILABLE );
 846         }
 847
 848         len = 0;
 849         ret = base64_decode( NULL, &len, s1, s2 - s1 );
 850
 851         if( ret == POLARSSL_ERR_BASE64_INVALID_CHARACTER )
 852             return( ret | POLARSSL_ERR_X509_KEY_INVALID_PEM );
 853
 854         if( ( buf = (unsigned char *) malloc( len ) ) == NULL )
 855             return( 1 );
 856
 857         if( ( ret = base64_decode( buf, &len, s1, s2 - s1 ) ) != 0 )
 858         {
 859             free( buf );
 860             return( ret | POLARSSL_ERR_X509_KEY_INVALID_PEM );
 861         }
 862
 863         buflen = len;
 864
 865         if( enc != 0 )
 866         {
 867             return( POLARSSL_ERR_X509_FEATURE_UNAVAILABLE );
 868         }
 869     }
 870
 871     memset( rsa, 0, sizeof( rsa_context ) );
 872
 873     p = buf;
 874     end = buf + buflen;
 875
 876     /*
 877      *  RSAPrivateKey ::= SEQUENCE {
 878      *      version           Version,
 879      *      modulus           INTEGER,  -- n
 880      *      publicExponent    INTEGER,  -- e
 881      *      privateExponent   INTEGER,  -- d
 882      *      prime1            INTEGER,  -- p
 883      *      prime2            INTEGER,  -- q
 884      *      exponent1         INTEGER,  -- d mod (p-1)
 885      *      exponent2         INTEGER,  -- d mod (q-1)
 886      *      coefficient       INTEGER,  -- (inverse of q) mod p
 887      *      otherPrimeInfos   OtherPrimeInfos OPTIONAL
 888      *  }
 889      */
 890     if( ( ret = asn1_get_tag( &p, end, &len,
 891             ASN1_CONSTRUCTED | ASN1_SEQUENCE ) ) != 0 )
 892     {
 893         if( s1 != NULL )
 894             free( buf );
 895
 896         rsa_free( rsa );
 897         return( POLARSSL_ERR_X509_KEY_INVALID_FORMAT | ret );
 898     }
 899
 900     end = p + len;
 901
 902     if( ( ret = asn1_get_int( &p, end, &rsa->ver ) ) != 0 )
 903     {
 904         if( s1 != NULL )
 905             free( buf );
 906
 907         rsa_free( rsa );
 908         return( POLARSSL_ERR_X509_KEY_INVALID_FORMAT | ret );
 909     }
 910
 911     if( rsa->ver != 0 )
 912     {
 913         if( s1 != NULL )
 914             free( buf );
 915
 916         rsa_free( rsa );
 917         return( ret | POLARSSL_ERR_X509_KEY_INVALID_VERSION );
 918     }
 919
 920     if( ( ret = asn1_get_mpi( &p, end, &rsa->N  ) ) != 0 ||
 921         ( ret = asn1_get_mpi( &p, end, &rsa->E  ) ) != 0 ||
 922         ( ret = asn1_get_mpi( &p, end, &rsa->D  ) ) != 0 ||
 923         ( ret = asn1_get_mpi( &p, end, &rsa->P  ) ) != 0 ||
 924         ( ret = asn1_get_mpi( &p, end, &rsa->Q  ) ) != 0 ||
 925         ( ret = asn1_get_mpi( &p, end, &rsa->DP ) ) != 0 ||
 926         ( ret = asn1_get_mpi( &p, end, &rsa->DQ ) ) != 0 ||
 927         ( ret = asn1_get_mpi( &p, end, &rsa->QP ) ) != 0 )
 928     {
 929         if( s1 != NULL )
 930             free( buf );
 931
 932         rsa_free( rsa );
 933         return( ret | POLARSSL_ERR_X509_KEY_INVALID_FORMAT );
 934     }
 935
 936     rsa->len = mpi_size( &rsa->N );
 937
 938     if( p != end )
 939     {
 940         if( s1 != NULL )
 941             free( buf );
 942
 943         rsa_free( rsa );
 944         return( POLARSSL_ERR_X509_KEY_INVALID_FORMAT |
 945                 POLARSSL_ERR_ASN1_LENGTH_MISMATCH );
 946     }
 947
 948     if( ( ret = rsa_check_privkey( rsa ) ) != 0 )
 949     {
 950         if( s1 != NULL )
 951             free( buf );
 952
 953         rsa_free( rsa );
 954         return( ret );
 955     }
 956
 957     if( s1 != NULL )
 958         free( buf );
 959
 960     return( 0 );
 961 }