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