PolarSSL v1.1.5
rsa.c
Go to the documentation of this file.
1 /*
2  * The RSA public-key cryptosystem
3  *
4  * Copyright (C) 2006-2011, 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 "polarssl/config.h"
33 
34 #if defined(POLARSSL_RSA_C)
35 
36 #include "polarssl/rsa.h"
37 #include "polarssl/md.h"
38 
39 #include <stdlib.h>
40 #include <stdio.h>
41 
42 /*
43  * Initialize an RSA context
44  */
45 void rsa_init( rsa_context *ctx,
46  int padding,
47  int hash_id )
48 {
49  memset( ctx, 0, sizeof( rsa_context ) );
50 
51  ctx->padding = padding;
52  ctx->hash_id = hash_id;
53 }
54 
55 #if defined(POLARSSL_GENPRIME)
56 
57 /*
58  * Generate an RSA keypair
59  */
60 int rsa_gen_key( rsa_context *ctx,
61  int (*f_rng)(void *, unsigned char *, size_t),
62  void *p_rng,
63  unsigned int nbits, int exponent )
64 {
65  int ret;
66  mpi P1, Q1, H, G;
67 
68  if( f_rng == NULL || nbits < 128 || exponent < 3 )
70 
71  mpi_init( &P1 ); mpi_init( &Q1 ); mpi_init( &H ); mpi_init( &G );
72 
73  /*
74  * find primes P and Q with Q < P so that:
75  * GCD( E, (P-1)*(Q-1) ) == 1
76  */
77  MPI_CHK( mpi_lset( &ctx->E, exponent ) );
78 
79  do
80  {
81  MPI_CHK( mpi_gen_prime( &ctx->P, ( nbits + 1 ) >> 1, 0,
82  f_rng, p_rng ) );
83 
84  MPI_CHK( mpi_gen_prime( &ctx->Q, ( nbits + 1 ) >> 1, 0,
85  f_rng, p_rng ) );
86 
87  if( mpi_cmp_mpi( &ctx->P, &ctx->Q ) < 0 )
88  mpi_swap( &ctx->P, &ctx->Q );
89 
90  if( mpi_cmp_mpi( &ctx->P, &ctx->Q ) == 0 )
91  continue;
92 
93  MPI_CHK( mpi_mul_mpi( &ctx->N, &ctx->P, &ctx->Q ) );
94  if( mpi_msb( &ctx->N ) != nbits )
95  continue;
96 
97  MPI_CHK( mpi_sub_int( &P1, &ctx->P, 1 ) );
98  MPI_CHK( mpi_sub_int( &Q1, &ctx->Q, 1 ) );
99  MPI_CHK( mpi_mul_mpi( &H, &P1, &Q1 ) );
100  MPI_CHK( mpi_gcd( &G, &ctx->E, &H ) );
101  }
102  while( mpi_cmp_int( &G, 1 ) != 0 );
103 
104  /*
105  * D = E^-1 mod ((P-1)*(Q-1))
106  * DP = D mod (P - 1)
107  * DQ = D mod (Q - 1)
108  * QP = Q^-1 mod P
109  */
110  MPI_CHK( mpi_inv_mod( &ctx->D , &ctx->E, &H ) );
111  MPI_CHK( mpi_mod_mpi( &ctx->DP, &ctx->D, &P1 ) );
112  MPI_CHK( mpi_mod_mpi( &ctx->DQ, &ctx->D, &Q1 ) );
113  MPI_CHK( mpi_inv_mod( &ctx->QP, &ctx->Q, &ctx->P ) );
114 
115  ctx->len = ( mpi_msb( &ctx->N ) + 7 ) >> 3;
116 
117 cleanup:
118 
119  mpi_free( &P1 ); mpi_free( &Q1 ); mpi_free( &H ); mpi_free( &G );
120 
121  if( ret != 0 )
122  {
123  rsa_free( ctx );
124  return( POLARSSL_ERR_RSA_KEY_GEN_FAILED + ret );
125  }
126 
127  return( 0 );
128 }
129 
130 #endif
131 
132 /*
133  * Check a public RSA key
134  */
135 int rsa_check_pubkey( const rsa_context *ctx )
136 {
137  if( !ctx->N.p || !ctx->E.p )
139 
140  if( ( ctx->N.p[0] & 1 ) == 0 ||
141  ( ctx->E.p[0] & 1 ) == 0 )
143 
144  if( mpi_msb( &ctx->N ) < 128 ||
145  mpi_msb( &ctx->N ) > POLARSSL_MPI_MAX_BITS )
147 
148  if( mpi_msb( &ctx->E ) < 2 ||
149  mpi_msb( &ctx->E ) > 64 )
151 
152  return( 0 );
153 }
154 
155 /*
156  * Check a private RSA key
157  */
158 int rsa_check_privkey( const rsa_context *ctx )
159 {
160  int ret;
161  mpi PQ, DE, P1, Q1, H, I, G, G2, L1, L2;
162 
163  if( ( ret = rsa_check_pubkey( ctx ) ) != 0 )
164  return( ret );
165 
166  if( !ctx->P.p || !ctx->Q.p || !ctx->D.p )
168 
169  mpi_init( &PQ ); mpi_init( &DE ); mpi_init( &P1 ); mpi_init( &Q1 );
170  mpi_init( &H ); mpi_init( &I ); mpi_init( &G ); mpi_init( &G2 );
171  mpi_init( &L1 ); mpi_init( &L2 );
172 
173  MPI_CHK( mpi_mul_mpi( &PQ, &ctx->P, &ctx->Q ) );
174  MPI_CHK( mpi_mul_mpi( &DE, &ctx->D, &ctx->E ) );
175  MPI_CHK( mpi_sub_int( &P1, &ctx->P, 1 ) );
176  MPI_CHK( mpi_sub_int( &Q1, &ctx->Q, 1 ) );
177  MPI_CHK( mpi_mul_mpi( &H, &P1, &Q1 ) );
178  MPI_CHK( mpi_gcd( &G, &ctx->E, &H ) );
179 
180  MPI_CHK( mpi_gcd( &G2, &P1, &Q1 ) );
181  MPI_CHK( mpi_div_mpi( &L1, &L2, &H, &G2 ) );
182  MPI_CHK( mpi_mod_mpi( &I, &DE, &L1 ) );
183 
184  /*
185  * Check for a valid PKCS1v2 private key
186  */
187  if( mpi_cmp_mpi( &PQ, &ctx->N ) != 0 ||
188  mpi_cmp_int( &L2, 0 ) != 0 ||
189  mpi_cmp_int( &I, 1 ) != 0 ||
190  mpi_cmp_int( &G, 1 ) != 0 )
191  {
193  }
194 
195 
196 cleanup:
197 
198  mpi_free( &PQ ); mpi_free( &DE ); mpi_free( &P1 ); mpi_free( &Q1 );
199  mpi_free( &H ); mpi_free( &I ); mpi_free( &G ); mpi_free( &G2 );
200  mpi_free( &L1 ); mpi_free( &L2 );
201 
203  return( ret );
204 
205  if( ret != 0 )
206  return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED + ret );
207 
208  return( 0 );
209 }
210 
211 /*
212  * Do an RSA public key operation
213  */
214 int rsa_public( rsa_context *ctx,
215  const unsigned char *input,
216  unsigned char *output )
217 {
218  int ret;
219  size_t olen;
220  mpi T;
221 
222  mpi_init( &T );
223 
224  MPI_CHK( mpi_read_binary( &T, input, ctx->len ) );
225 
226  if( mpi_cmp_mpi( &T, &ctx->N ) >= 0 )
227  {
228  mpi_free( &T );
230  }
231 
232  olen = ctx->len;
233  MPI_CHK( mpi_exp_mod( &T, &T, &ctx->E, &ctx->N, &ctx->RN ) );
234  MPI_CHK( mpi_write_binary( &T, output, olen ) );
235 
236 cleanup:
237 
238  mpi_free( &T );
239 
240  if( ret != 0 )
241  return( POLARSSL_ERR_RSA_PUBLIC_FAILED + ret );
242 
243  return( 0 );
244 }
245 
246 /*
247  * Do an RSA private key operation
248  */
249 int rsa_private( rsa_context *ctx,
250  const unsigned char *input,
251  unsigned char *output )
252 {
253  int ret;
254  size_t olen;
255  mpi T, T1, T2;
256 
257  mpi_init( &T ); mpi_init( &T1 ); mpi_init( &T2 );
258 
259  MPI_CHK( mpi_read_binary( &T, input, ctx->len ) );
260 
261  if( mpi_cmp_mpi( &T, &ctx->N ) >= 0 )
262  {
263  mpi_free( &T );
265  }
266 
267 #if defined(POLARSSL_RSA_NO_CRT)
268  MPI_CHK( mpi_exp_mod( &T, &T, &ctx->D, &ctx->N, &ctx->RN ) );
269 #else
270  /*
271  * faster decryption using the CRT
272  *
273  * T1 = input ^ dP mod P
274  * T2 = input ^ dQ mod Q
275  */
276  MPI_CHK( mpi_exp_mod( &T1, &T, &ctx->DP, &ctx->P, &ctx->RP ) );
277  MPI_CHK( mpi_exp_mod( &T2, &T, &ctx->DQ, &ctx->Q, &ctx->RQ ) );
278 
279  /*
280  * T = (T1 - T2) * (Q^-1 mod P) mod P
281  */
282  MPI_CHK( mpi_sub_mpi( &T, &T1, &T2 ) );
283  MPI_CHK( mpi_mul_mpi( &T1, &T, &ctx->QP ) );
284  MPI_CHK( mpi_mod_mpi( &T, &T1, &ctx->P ) );
285 
286  /*
287  * output = T2 + T * Q
288  */
289  MPI_CHK( mpi_mul_mpi( &T1, &T, &ctx->Q ) );
290  MPI_CHK( mpi_add_mpi( &T, &T2, &T1 ) );
291 #endif
292 
293  olen = ctx->len;
294  MPI_CHK( mpi_write_binary( &T, output, olen ) );
295 
296 cleanup:
297 
298  mpi_free( &T ); mpi_free( &T1 ); mpi_free( &T2 );
299 
300  if( ret != 0 )
301  return( POLARSSL_ERR_RSA_PRIVATE_FAILED + ret );
302 
303  return( 0 );
304 }
305 
306 #if defined(POLARSSL_PKCS1_V21)
307 
316 static void mgf_mask( unsigned char *dst, size_t dlen, unsigned char *src, size_t slen,
317  md_context_t *md_ctx )
318 {
319  unsigned char mask[POLARSSL_MD_MAX_SIZE];
320  unsigned char counter[4];
321  unsigned char *p;
322  unsigned int hlen;
323  size_t i, use_len;
324 
325  memset( mask, 0, POLARSSL_MD_MAX_SIZE );
326  memset( counter, 0, 4 );
327 
328  hlen = md_ctx->md_info->size;
329 
330  // Generate and apply dbMask
331  //
332  p = dst;
333 
334  while( dlen > 0 )
335  {
336  use_len = hlen;
337  if( dlen < hlen )
338  use_len = dlen;
339 
340  md_starts( md_ctx );
341  md_update( md_ctx, src, slen );
342  md_update( md_ctx, counter, 4 );
343  md_finish( md_ctx, mask );
344 
345  for( i = 0; i < use_len; ++i )
346  *p++ ^= mask[i];
347 
348  counter[3]++;
349 
350  dlen -= use_len;
351  }
352 }
353 #endif
354 
355 /*
356  * Add the message padding, then do an RSA operation
357  */
359  int (*f_rng)(void *, unsigned char *, size_t),
360  void *p_rng,
361  int mode, size_t ilen,
362  const unsigned char *input,
363  unsigned char *output )
364 {
365  size_t nb_pad, olen;
366  int ret;
367  unsigned char *p = output;
368 #if defined(POLARSSL_PKCS1_V21)
369  unsigned int hlen;
370  const md_info_t *md_info;
371  md_context_t md_ctx;
372 #endif
373 
374  olen = ctx->len;
375 
376  if( f_rng == NULL )
378 
379  switch( ctx->padding )
380  {
381  case RSA_PKCS_V15:
382 
383  if( olen < ilen + 11 )
385 
386  nb_pad = olen - 3 - ilen;
387 
388  *p++ = 0;
389  if( mode == RSA_PUBLIC )
390  {
391  *p++ = RSA_CRYPT;
392 
393  while( nb_pad-- > 0 )
394  {
395  int rng_dl = 100;
396 
397  do {
398  ret = f_rng( p_rng, p, 1 );
399  } while( *p == 0 && --rng_dl && ret == 0 );
400 
401  // Check if RNG failed to generate data
402  //
403  if( rng_dl == 0 || ret != 0)
404  return POLARSSL_ERR_RSA_RNG_FAILED + ret;
405 
406  p++;
407  }
408  }
409  else
410  {
411  *p++ = RSA_SIGN;
412 
413  while( nb_pad-- > 0 )
414  *p++ = 0xFF;
415  }
416 
417  *p++ = 0;
418  memcpy( p, input, ilen );
419  break;
420 
421 #if defined(POLARSSL_PKCS1_V21)
422  case RSA_PKCS_V21:
423 
424  md_info = md_info_from_type( ctx->hash_id );
425  if( md_info == NULL )
427 
428  hlen = md_get_size( md_info );
429 
430  if( olen < ilen + 2 * hlen + 2 || f_rng == NULL )
432 
433  memset( output, 0, olen );
434 
435  *p++ = 0;
436 
437  // Generate a random octet string seed
438  //
439  if( ( ret = f_rng( p_rng, p, hlen ) ) != 0 )
440  return( POLARSSL_ERR_RSA_RNG_FAILED + ret );
441 
442  p += hlen;
443 
444  // Construct DB
445  //
446  md( md_info, p, 0, p );
447  p += hlen;
448  p += olen - 2 * hlen - 2 - ilen;
449  *p++ = 1;
450  memcpy( p, input, ilen );
451 
452  md_init_ctx( &md_ctx, md_info );
453 
454  // maskedDB: Apply dbMask to DB
455  //
456  mgf_mask( output + hlen + 1, olen - hlen - 1, output + 1, hlen,
457  &md_ctx );
458 
459  // maskedSeed: Apply seedMask to seed
460  //
461  mgf_mask( output + 1, hlen, output + hlen + 1, olen - hlen - 1,
462  &md_ctx );
463 
464  md_free_ctx( &md_ctx );
465  break;
466 #endif
467 
468  default:
469 
471  }
472 
473  return( ( mode == RSA_PUBLIC )
474  ? rsa_public( ctx, output, output )
475  : rsa_private( ctx, output, output ) );
476 }
477 
478 /*
479  * Do an RSA operation, then remove the message padding
480  */
482  int mode, size_t *olen,
483  const unsigned char *input,
484  unsigned char *output,
485  size_t output_max_len)
486 {
487  int ret;
488  size_t ilen;
489  unsigned char *p;
490  unsigned char bt;
491  unsigned char buf[1024];
492 #if defined(POLARSSL_PKCS1_V21)
493  unsigned char lhash[POLARSSL_MD_MAX_SIZE];
494  unsigned int hlen;
495  const md_info_t *md_info;
496  md_context_t md_ctx;
497 #endif
498 
499  ilen = ctx->len;
500 
501  if( ilen < 16 || ilen > sizeof( buf ) )
503 
504  ret = ( mode == RSA_PUBLIC )
505  ? rsa_public( ctx, input, buf )
506  : rsa_private( ctx, input, buf );
507 
508  if( ret != 0 )
509  return( ret );
510 
511  p = buf;
512 
513  switch( ctx->padding )
514  {
515  case RSA_PKCS_V15:
516 
517  if( *p++ != 0 )
519 
520  bt = *p++;
521  if( ( bt != RSA_CRYPT && mode == RSA_PRIVATE ) ||
522  ( bt != RSA_SIGN && mode == RSA_PUBLIC ) )
523  {
525  }
526 
527  if( bt == RSA_CRYPT )
528  {
529  while( *p != 0 && p < buf + ilen - 1 )
530  p++;
531 
532  if( *p != 0 || p >= buf + ilen - 1 )
534 
535  p++;
536  }
537  else
538  {
539  while( *p == 0xFF && p < buf + ilen - 1 )
540  p++;
541 
542  if( *p != 0 || p >= buf + ilen - 1 )
544 
545  p++;
546  }
547 
548  break;
549 
550 #if defined(POLARSSL_PKCS1_V21)
551  case RSA_PKCS_V21:
552 
553  if( *p++ != 0 )
555 
556  md_info = md_info_from_type( ctx->hash_id );
557  if( md_info == NULL )
559 
560  hlen = md_get_size( md_info );
561 
562  md_init_ctx( &md_ctx, md_info );
563 
564  // Generate lHash
565  //
566  md( md_info, lhash, 0, lhash );
567 
568  // seed: Apply seedMask to maskedSeed
569  //
570  mgf_mask( buf + 1, hlen, buf + hlen + 1, ilen - hlen - 1,
571  &md_ctx );
572 
573  // DB: Apply dbMask to maskedDB
574  //
575  mgf_mask( buf + hlen + 1, ilen - hlen - 1, buf + 1, hlen,
576  &md_ctx );
577 
578  p += hlen;
579  md_free_ctx( &md_ctx );
580 
581  // Check validity
582  //
583  if( memcmp( lhash, p, hlen ) != 0 )
585 
586  p += hlen;
587 
588  while( *p == 0 && p < buf + ilen )
589  p++;
590 
591  if( p == buf + ilen )
593 
594  if( *p++ != 0x01 )
596 
597  break;
598 #endif
599 
600  default:
601 
603  }
604 
605  if (ilen - (p - buf) > output_max_len)
607 
608  *olen = ilen - (p - buf);
609  memcpy( output, p, *olen );
610 
611  return( 0 );
612 }
613 
614 /*
615  * Do an RSA operation to sign the message digest
616  */
617 int rsa_pkcs1_sign( rsa_context *ctx,
618  int (*f_rng)(void *, unsigned char *, size_t),
619  void *p_rng,
620  int mode,
621  int hash_id,
622  unsigned int hashlen,
623  const unsigned char *hash,
624  unsigned char *sig )
625 {
626  size_t nb_pad, olen;
627  unsigned char *p = sig;
628 #if defined(POLARSSL_PKCS1_V21)
629  unsigned char salt[POLARSSL_MD_MAX_SIZE];
630  unsigned int slen, hlen, offset = 0;
631  int ret;
632  size_t msb;
633  const md_info_t *md_info;
634  md_context_t md_ctx;
635 #else
636  (void) f_rng;
637  (void) p_rng;
638 #endif
639 
640  olen = ctx->len;
641 
642  switch( ctx->padding )
643  {
644  case RSA_PKCS_V15:
645 
646  switch( hash_id )
647  {
648  case SIG_RSA_RAW:
649  nb_pad = olen - 3 - hashlen;
650  break;
651 
652  case SIG_RSA_MD2:
653  case SIG_RSA_MD4:
654  case SIG_RSA_MD5:
655  nb_pad = olen - 3 - 34;
656  break;
657 
658  case SIG_RSA_SHA1:
659  nb_pad = olen - 3 - 35;
660  break;
661 
662  case SIG_RSA_SHA224:
663  nb_pad = olen - 3 - 47;
664  break;
665 
666  case SIG_RSA_SHA256:
667  nb_pad = olen - 3 - 51;
668  break;
669 
670  case SIG_RSA_SHA384:
671  nb_pad = olen - 3 - 67;
672  break;
673 
674  case SIG_RSA_SHA512:
675  nb_pad = olen - 3 - 83;
676  break;
677 
678 
679  default:
681  }
682 
683  if( ( nb_pad < 8 ) || ( nb_pad > olen ) )
685 
686  *p++ = 0;
687  *p++ = RSA_SIGN;
688  memset( p, 0xFF, nb_pad );
689  p += nb_pad;
690  *p++ = 0;
691 
692  switch( hash_id )
693  {
694  case SIG_RSA_RAW:
695  memcpy( p, hash, hashlen );
696  break;
697 
698  case SIG_RSA_MD2:
699  memcpy( p, ASN1_HASH_MDX, 18 );
700  memcpy( p + 18, hash, 16 );
701  p[13] = 2; break;
702 
703  case SIG_RSA_MD4:
704  memcpy( p, ASN1_HASH_MDX, 18 );
705  memcpy( p + 18, hash, 16 );
706  p[13] = 4; break;
707 
708  case SIG_RSA_MD5:
709  memcpy( p, ASN1_HASH_MDX, 18 );
710  memcpy( p + 18, hash, 16 );
711  p[13] = 5; break;
712 
713  case SIG_RSA_SHA1:
714  memcpy( p, ASN1_HASH_SHA1, 15 );
715  memcpy( p + 15, hash, 20 );
716  break;
717 
718  case SIG_RSA_SHA224:
719  memcpy( p, ASN1_HASH_SHA2X, 19 );
720  memcpy( p + 19, hash, 28 );
721  p[1] += 28; p[14] = 4; p[18] += 28; break;
722 
723  case SIG_RSA_SHA256:
724  memcpy( p, ASN1_HASH_SHA2X, 19 );
725  memcpy( p + 19, hash, 32 );
726  p[1] += 32; p[14] = 1; p[18] += 32; break;
727 
728  case SIG_RSA_SHA384:
729  memcpy( p, ASN1_HASH_SHA2X, 19 );
730  memcpy( p + 19, hash, 48 );
731  p[1] += 48; p[14] = 2; p[18] += 48; break;
732 
733  case SIG_RSA_SHA512:
734  memcpy( p, ASN1_HASH_SHA2X, 19 );
735  memcpy( p + 19, hash, 64 );
736  p[1] += 64; p[14] = 3; p[18] += 64; break;
737 
738  default:
740  }
741 
742  break;
743 
744 #if defined(POLARSSL_PKCS1_V21)
745  case RSA_PKCS_V21:
746 
747  if( f_rng == NULL )
749 
750  switch( hash_id )
751  {
752  case SIG_RSA_MD2:
753  case SIG_RSA_MD4:
754  case SIG_RSA_MD5:
755  hashlen = 16;
756  break;
757 
758  case SIG_RSA_SHA1:
759  hashlen = 20;
760  break;
761 
762  case SIG_RSA_SHA224:
763  hashlen = 28;
764  break;
765 
766  case SIG_RSA_SHA256:
767  hashlen = 32;
768  break;
769 
770  case SIG_RSA_SHA384:
771  hashlen = 48;
772  break;
773 
774  case SIG_RSA_SHA512:
775  hashlen = 64;
776  break;
777 
778  default:
780  }
781 
782  md_info = md_info_from_type( ctx->hash_id );
783  if( md_info == NULL )
785 
786  hlen = md_get_size( md_info );
787  slen = hlen;
788 
789  if( olen < hlen + slen + 2 )
791 
792  memset( sig, 0, olen );
793 
794  msb = mpi_msb( &ctx->N ) - 1;
795 
796  // Generate salt of length slen
797  //
798  if( ( ret = f_rng( p_rng, salt, slen ) ) != 0 )
799  return( POLARSSL_ERR_RSA_RNG_FAILED + ret );
800 
801  // Note: EMSA-PSS encoding is over the length of N - 1 bits
802  //
803  msb = mpi_msb( &ctx->N ) - 1;
804  p += olen - hlen * 2 - 2;
805  *p++ = 0x01;
806  memcpy( p, salt, slen );
807  p += slen;
808 
809  md_init_ctx( &md_ctx, md_info );
810 
811  // Generate H = Hash( M' )
812  //
813  md_starts( &md_ctx );
814  md_update( &md_ctx, p, 8 );
815  md_update( &md_ctx, hash, hashlen );
816  md_update( &md_ctx, salt, slen );
817  md_finish( &md_ctx, p );
818 
819  // Compensate for boundary condition when applying mask
820  //
821  if( msb % 8 == 0 )
822  offset = 1;
823 
824  // maskedDB: Apply dbMask to DB
825  //
826  mgf_mask( sig + offset, olen - hlen - 1 - offset, p, hlen, &md_ctx );
827 
828  md_free_ctx( &md_ctx );
829 
830  msb = mpi_msb( &ctx->N ) - 1;
831  sig[0] &= 0xFF >> ( olen * 8 - msb );
832 
833  p += hlen;
834  *p++ = 0xBC;
835  break;
836 #endif
837 
838  default:
839 
841  }
842 
843  return( ( mode == RSA_PUBLIC )
844  ? rsa_public( ctx, sig, sig )
845  : rsa_private( ctx, sig, sig ) );
846 }
847 
848 /*
849  * Do an RSA operation and check the message digest
850  */
851 int rsa_pkcs1_verify( rsa_context *ctx,
852  int mode,
853  int hash_id,
854  unsigned int hashlen,
855  const unsigned char *hash,
856  unsigned char *sig )
857 {
858  int ret;
859  size_t len, siglen;
860  unsigned char *p, c;
861  unsigned char buf[1024];
862 #if defined(POLARSSL_PKCS1_V21)
863  unsigned char result[POLARSSL_MD_MAX_SIZE];
864  unsigned char zeros[8];
865  unsigned int hlen;
866  size_t slen, msb;
867  const md_info_t *md_info;
868  md_context_t md_ctx;
869 #endif
870  siglen = ctx->len;
871 
872  if( siglen < 16 || siglen > sizeof( buf ) )
874 
875  ret = ( mode == RSA_PUBLIC )
876  ? rsa_public( ctx, sig, buf )
877  : rsa_private( ctx, sig, buf );
878 
879  if( ret != 0 )
880  return( ret );
881 
882  p = buf;
883 
884  switch( ctx->padding )
885  {
886  case RSA_PKCS_V15:
887 
888  if( *p++ != 0 || *p++ != RSA_SIGN )
890 
891  while( *p != 0 )
892  {
893  if( p >= buf + siglen - 1 || *p != 0xFF )
895  p++;
896  }
897  p++;
898 
899  len = siglen - ( p - buf );
900 
901  if( len == 34 )
902  {
903  c = p[13];
904  p[13] = 0;
905 
906  if( memcmp( p, ASN1_HASH_MDX, 18 ) != 0 )
908 
909  if( ( c == 2 && hash_id == SIG_RSA_MD2 ) ||
910  ( c == 4 && hash_id == SIG_RSA_MD4 ) ||
911  ( c == 5 && hash_id == SIG_RSA_MD5 ) )
912  {
913  if( memcmp( p + 18, hash, 16 ) == 0 )
914  return( 0 );
915  else
917  }
918  }
919 
920  if( len == 35 && hash_id == SIG_RSA_SHA1 )
921  {
922  if( memcmp( p, ASN1_HASH_SHA1, 15 ) == 0 &&
923  memcmp( p + 15, hash, 20 ) == 0 )
924  return( 0 );
925  else
927  }
928  if( ( len == 19 + 28 && p[14] == 4 && hash_id == SIG_RSA_SHA224 ) ||
929  ( len == 19 + 32 && p[14] == 1 && hash_id == SIG_RSA_SHA256 ) ||
930  ( len == 19 + 48 && p[14] == 2 && hash_id == SIG_RSA_SHA384 ) ||
931  ( len == 19 + 64 && p[14] == 3 && hash_id == SIG_RSA_SHA512 ) )
932  {
933  c = p[1] - 17;
934  p[1] = 17;
935  p[14] = 0;
936 
937  if( p[18] == c &&
938  memcmp( p, ASN1_HASH_SHA2X, 18 ) == 0 &&
939  memcmp( p + 19, hash, c ) == 0 )
940  return( 0 );
941  else
943  }
944 
945  if( len == hashlen && hash_id == SIG_RSA_RAW )
946  {
947  if( memcmp( p, hash, hashlen ) == 0 )
948  return( 0 );
949  else
951  }
952 
953  break;
954 
955 #if defined(POLARSSL_PKCS1_V21)
956  case RSA_PKCS_V21:
957 
958  if( buf[siglen - 1] != 0xBC )
960 
961  switch( hash_id )
962  {
963  case SIG_RSA_MD2:
964  case SIG_RSA_MD4:
965  case SIG_RSA_MD5:
966  hashlen = 16;
967  break;
968 
969  case SIG_RSA_SHA1:
970  hashlen = 20;
971  break;
972 
973  case SIG_RSA_SHA224:
974  hashlen = 28;
975  break;
976 
977  case SIG_RSA_SHA256:
978  hashlen = 32;
979  break;
980 
981  case SIG_RSA_SHA384:
982  hashlen = 48;
983  break;
984 
985  case SIG_RSA_SHA512:
986  hashlen = 64;
987  break;
988 
989  default:
991  }
992 
993  md_info = md_info_from_type( ctx->hash_id );
994  if( md_info == NULL )
996 
997  hlen = md_get_size( md_info );
998  slen = siglen - hlen - 1;
999 
1000  memset( zeros, 0, 8 );
1001 
1002  // Note: EMSA-PSS verification is over the length of N - 1 bits
1003  //
1004  msb = mpi_msb( &ctx->N ) - 1;
1005 
1006  // Compensate for boundary condition when applying mask
1007  //
1008  if( msb % 8 == 0 )
1009  {
1010  p++;
1011  siglen -= 1;
1012  }
1013  if( buf[0] >> ( 8 - siglen * 8 + msb ) )
1015 
1016  md_init_ctx( &md_ctx, md_info );
1017 
1018  mgf_mask( p, siglen - hlen - 1, p + siglen - hlen - 1, hlen, &md_ctx );
1019 
1020  buf[0] &= 0xFF >> ( siglen * 8 - msb );
1021 
1022  while( *p == 0 && p < buf + siglen )
1023  p++;
1024 
1025  if( p == buf + siglen ||
1026  *p++ != 0x01 )
1027  {
1028  md_free_ctx( &md_ctx );
1030  }
1031 
1032  slen -= p - buf;
1033 
1034  // Generate H = Hash( M' )
1035  //
1036  md_starts( &md_ctx );
1037  md_update( &md_ctx, zeros, 8 );
1038  md_update( &md_ctx, hash, hashlen );
1039  md_update( &md_ctx, p, slen );
1040  md_finish( &md_ctx, result );
1041 
1042  md_free_ctx( &md_ctx );
1043 
1044  if( memcmp( p + slen, result, hlen ) == 0 )
1045  return( 0 );
1046  else
1048 #endif
1049 
1050  default:
1051 
1053  }
1054 
1056 }
1057 
1058 /*
1059  * Free the components of an RSA key
1060  */
1061 void rsa_free( rsa_context *ctx )
1062 {
1063  mpi_free( &ctx->RQ ); mpi_free( &ctx->RP ); mpi_free( &ctx->RN );
1064  mpi_free( &ctx->QP ); mpi_free( &ctx->DQ ); mpi_free( &ctx->DP );
1065  mpi_free( &ctx->Q ); mpi_free( &ctx->P ); mpi_free( &ctx->D );
1066  mpi_free( &ctx->E ); mpi_free( &ctx->N );
1067 }
1068 
1069 #if defined(POLARSSL_SELF_TEST)
1070 
1071 #include "polarssl/sha1.h"
1072 
1073 /*
1074  * Example RSA-1024 keypair, for test purposes
1075  */
1076 #define KEY_LEN 128
1077 
1078 #define RSA_N "9292758453063D803DD603D5E777D788" \
1079  "8ED1D5BF35786190FA2F23EBC0848AEA" \
1080  "DDA92CA6C3D80B32C4D109BE0F36D6AE" \
1081  "7130B9CED7ACDF54CFC7555AC14EEBAB" \
1082  "93A89813FBF3C4F8066D2D800F7C38A8" \
1083  "1AE31942917403FF4946B0A83D3D3E05" \
1084  "EE57C6F5F5606FB5D4BC6CD34EE0801A" \
1085  "5E94BB77B07507233A0BC7BAC8F90F79"
1086 
1087 #define RSA_E "10001"
1088 
1089 #define RSA_D "24BF6185468786FDD303083D25E64EFC" \
1090  "66CA472BC44D253102F8B4A9D3BFA750" \
1091  "91386C0077937FE33FA3252D28855837" \
1092  "AE1B484A8A9A45F7EE8C0C634F99E8CD" \
1093  "DF79C5CE07EE72C7F123142198164234" \
1094  "CABB724CF78B8173B9F880FC86322407" \
1095  "AF1FEDFDDE2BEB674CA15F3E81A1521E" \
1096  "071513A1E85B5DFA031F21ECAE91A34D"
1097 
1098 #define RSA_P "C36D0EB7FCD285223CFB5AABA5BDA3D8" \
1099  "2C01CAD19EA484A87EA4377637E75500" \
1100  "FCB2005C5C7DD6EC4AC023CDA285D796" \
1101  "C3D9E75E1EFC42488BB4F1D13AC30A57"
1102 
1103 #define RSA_Q "C000DF51A7C77AE8D7C7370C1FF55B69" \
1104  "E211C2B9E5DB1ED0BF61D0D9899620F4" \
1105  "910E4168387E3C30AA1E00C339A79508" \
1106  "8452DD96A9A5EA5D9DCA68DA636032AF"
1107 
1108 #define RSA_DP "C1ACF567564274FB07A0BBAD5D26E298" \
1109  "3C94D22288ACD763FD8E5600ED4A702D" \
1110  "F84198A5F06C2E72236AE490C93F07F8" \
1111  "3CC559CD27BC2D1CA488811730BB5725"
1112 
1113 #define RSA_DQ "4959CBF6F8FEF750AEE6977C155579C7" \
1114  "D8AAEA56749EA28623272E4F7D0592AF" \
1115  "7C1F1313CAC9471B5C523BFE592F517B" \
1116  "407A1BD76C164B93DA2D32A383E58357"
1117 
1118 #define RSA_QP "9AE7FBC99546432DF71896FC239EADAE" \
1119  "F38D18D2B2F0E2DD275AA977E2BF4411" \
1120  "F5A3B2A5D33605AEBBCCBA7FEB9F2D2F" \
1121  "A74206CEC169D74BF5A8C50D6F48EA08"
1122 
1123 #define PT_LEN 24
1124 #define RSA_PT "\xAA\xBB\xCC\x03\x02\x01\x00\xFF\xFF\xFF\xFF\xFF" \
1125  "\x11\x22\x33\x0A\x0B\x0C\xCC\xDD\xDD\xDD\xDD\xDD"
1126 
1127 static int myrand( void *rng_state, unsigned char *output, size_t len )
1128 {
1129  size_t i;
1130 
1131  if( rng_state != NULL )
1132  rng_state = NULL;
1133 
1134  for( i = 0; i < len; ++i )
1135  output[i] = rand();
1136 
1137  return( 0 );
1138 }
1139 
1140 /*
1141  * Checkup routine
1142  */
1143 int rsa_self_test( int verbose )
1144 {
1145  size_t len;
1146  rsa_context rsa;
1147  unsigned char rsa_plaintext[PT_LEN];
1148  unsigned char rsa_decrypted[PT_LEN];
1149  unsigned char rsa_ciphertext[KEY_LEN];
1150 #if defined(POLARSSL_SHA1_C)
1151  unsigned char sha1sum[20];
1152 #endif
1153 
1154  rsa_init( &rsa, RSA_PKCS_V15, 0 );
1155 
1156  rsa.len = KEY_LEN;
1157  mpi_read_string( &rsa.N , 16, RSA_N );
1158  mpi_read_string( &rsa.E , 16, RSA_E );
1159  mpi_read_string( &rsa.D , 16, RSA_D );
1160  mpi_read_string( &rsa.P , 16, RSA_P );
1161  mpi_read_string( &rsa.Q , 16, RSA_Q );
1162  mpi_read_string( &rsa.DP, 16, RSA_DP );
1163  mpi_read_string( &rsa.DQ, 16, RSA_DQ );
1164  mpi_read_string( &rsa.QP, 16, RSA_QP );
1165 
1166  if( verbose != 0 )
1167  printf( " RSA key validation: " );
1168 
1169  if( rsa_check_pubkey( &rsa ) != 0 ||
1170  rsa_check_privkey( &rsa ) != 0 )
1171  {
1172  if( verbose != 0 )
1173  printf( "failed\n" );
1174 
1175  return( 1 );
1176  }
1177 
1178  if( verbose != 0 )
1179  printf( "passed\n PKCS#1 encryption : " );
1180 
1181  memcpy( rsa_plaintext, RSA_PT, PT_LEN );
1182 
1183  if( rsa_pkcs1_encrypt( &rsa, &myrand, NULL, RSA_PUBLIC, PT_LEN,
1184  rsa_plaintext, rsa_ciphertext ) != 0 )
1185  {
1186  if( verbose != 0 )
1187  printf( "failed\n" );
1188 
1189  return( 1 );
1190  }
1191 
1192  if( verbose != 0 )
1193  printf( "passed\n PKCS#1 decryption : " );
1194 
1195  if( rsa_pkcs1_decrypt( &rsa, RSA_PRIVATE, &len,
1196  rsa_ciphertext, rsa_decrypted,
1197  sizeof(rsa_decrypted) ) != 0 )
1198  {
1199  if( verbose != 0 )
1200  printf( "failed\n" );
1201 
1202  return( 1 );
1203  }
1204 
1205  if( memcmp( rsa_decrypted, rsa_plaintext, len ) != 0 )
1206  {
1207  if( verbose != 0 )
1208  printf( "failed\n" );
1209 
1210  return( 1 );
1211  }
1212 
1213 #if defined(POLARSSL_SHA1_C)
1214  if( verbose != 0 )
1215  printf( "passed\n PKCS#1 data sign : " );
1216 
1217  sha1( rsa_plaintext, PT_LEN, sha1sum );
1218 
1219  if( rsa_pkcs1_sign( &rsa, NULL, NULL, RSA_PRIVATE, SIG_RSA_SHA1, 20,
1220  sha1sum, rsa_ciphertext ) != 0 )
1221  {
1222  if( verbose != 0 )
1223  printf( "failed\n" );
1224 
1225  return( 1 );
1226  }
1227 
1228  if( verbose != 0 )
1229  printf( "passed\n PKCS#1 sig. verify: " );
1230 
1231  if( rsa_pkcs1_verify( &rsa, RSA_PUBLIC, SIG_RSA_SHA1, 20,
1232  sha1sum, rsa_ciphertext ) != 0 )
1233  {
1234  if( verbose != 0 )
1235  printf( "failed\n" );
1236 
1237  return( 1 );
1238  }
1239 
1240  if( verbose != 0 )
1241  printf( "passed\n\n" );
1242 #endif /* POLARSSL_SHA1_C */
1243 
1244  rsa_free( &rsa );
1245 
1246  return( 0 );
1247 }
1248 
1249 #endif
1250 
1251 #endif