PolarSSL v1.1.4
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  *p++ = RSA_CRYPT;
390 
391  while( nb_pad-- > 0 )
392  {
393  int rng_dl = 100;
394 
395  do {
396  ret = f_rng( p_rng, p, 1 );
397  } while( *p == 0 && --rng_dl && ret == 0 );
398 
399  // Check if RNG failed to generate data
400  //
401  if( rng_dl == 0 || ret != 0)
402  return POLARSSL_ERR_RSA_RNG_FAILED + ret;
403 
404  p++;
405  }
406  *p++ = 0;
407  memcpy( p, input, ilen );
408  break;
409 
410 #if defined(POLARSSL_PKCS1_V21)
411  case RSA_PKCS_V21:
412 
413  md_info = md_info_from_type( ctx->hash_id );
414  if( md_info == NULL )
416 
417  hlen = md_get_size( md_info );
418 
419  if( olen < ilen + 2 * hlen + 2 || f_rng == NULL )
421 
422  memset( output, 0, olen );
423  memset( &md_ctx, 0, sizeof( md_context_t ) );
424 
425  md_init_ctx( &md_ctx, md_info );
426 
427  *p++ = 0;
428 
429  // Generate a random octet string seed
430  //
431  if( ( ret = f_rng( p_rng, p, hlen ) ) != 0 )
432  return( POLARSSL_ERR_RSA_RNG_FAILED + ret );
433 
434  p += hlen;
435 
436  // Construct DB
437  //
438  md( md_info, p, 0, p );
439  p += hlen;
440  p += olen - 2 * hlen - 2 - ilen;
441  *p++ = 1;
442  memcpy( p, input, ilen );
443 
444  // maskedDB: Apply dbMask to DB
445  //
446  mgf_mask( output + hlen + 1, olen - hlen - 1, output + 1, hlen,
447  &md_ctx );
448 
449  // maskedSeed: Apply seedMask to seed
450  //
451  mgf_mask( output + 1, hlen, output + hlen + 1, olen - hlen - 1,
452  &md_ctx );
453  break;
454 #endif
455 
456  default:
457 
459  }
460 
461  return( ( mode == RSA_PUBLIC )
462  ? rsa_public( ctx, output, output )
463  : rsa_private( ctx, output, output ) );
464 }
465 
466 /*
467  * Do an RSA operation, then remove the message padding
468  */
470  int mode, size_t *olen,
471  const unsigned char *input,
472  unsigned char *output,
473  size_t output_max_len)
474 {
475  int ret;
476  size_t ilen;
477  unsigned char *p;
478  unsigned char buf[1024];
479 #if defined(POLARSSL_PKCS1_V21)
480  unsigned char lhash[POLARSSL_MD_MAX_SIZE];
481  unsigned int hlen;
482  const md_info_t *md_info;
483  md_context_t md_ctx;
484 #endif
485 
486  ilen = ctx->len;
487 
488  if( ilen < 16 || ilen > sizeof( buf ) )
490 
491  ret = ( mode == RSA_PUBLIC )
492  ? rsa_public( ctx, input, buf )
493  : rsa_private( ctx, input, buf );
494 
495  if( ret != 0 )
496  return( ret );
497 
498  p = buf;
499 
500  switch( ctx->padding )
501  {
502  case RSA_PKCS_V15:
503 
504  if( *p++ != 0 || *p++ != RSA_CRYPT )
506 
507  while( *p != 0 )
508  {
509  if( p >= buf + ilen - 1 )
511  p++;
512  }
513  p++;
514  break;
515 
516 #if defined(POLARSSL_PKCS1_V21)
517  case RSA_PKCS_V21:
518 
519  if( *p++ != 0 )
521 
522  md_info = md_info_from_type( ctx->hash_id );
523  if( md_info == NULL )
525 
526  hlen = md_get_size( md_info );
527  memset( &md_ctx, 0, sizeof( md_context_t ) );
528 
529  md_init_ctx( &md_ctx, md_info );
530 
531  // Generate lHash
532  //
533  md( md_info, lhash, 0, lhash );
534 
535  // seed: Apply seedMask to maskedSeed
536  //
537  mgf_mask( buf + 1, hlen, buf + hlen + 1, ilen - hlen - 1,
538  &md_ctx );
539 
540  // DB: Apply dbMask to maskedDB
541  //
542  mgf_mask( buf + hlen + 1, ilen - hlen - 1, buf + 1, hlen,
543  &md_ctx );
544 
545  p += hlen;
546 
547  // Check validity
548  //
549  if( memcmp( lhash, p, hlen ) != 0 )
551 
552  p += hlen;
553 
554  while( *p == 0 && p < buf + ilen )
555  p++;
556 
557  if( p == buf + ilen )
559 
560  if( *p++ != 0x01 )
562 
563  break;
564 #endif
565 
566  default:
567 
569  }
570 
571  if (ilen - (p - buf) > output_max_len)
573 
574  *olen = ilen - (p - buf);
575  memcpy( output, p, *olen );
576 
577  return( 0 );
578 }
579 
580 /*
581  * Do an RSA operation to sign the message digest
582  */
583 int rsa_pkcs1_sign( rsa_context *ctx,
584  int (*f_rng)(void *, unsigned char *, size_t),
585  void *p_rng,
586  int mode,
587  int hash_id,
588  unsigned int hashlen,
589  const unsigned char *hash,
590  unsigned char *sig )
591 {
592  size_t nb_pad, olen;
593  unsigned char *p = sig;
594 #if defined(POLARSSL_PKCS1_V21)
595  unsigned char salt[POLARSSL_MD_MAX_SIZE];
596  unsigned int slen, hlen, offset = 0;
597  int ret;
598  size_t msb;
599  const md_info_t *md_info;
600  md_context_t md_ctx;
601 #else
602  (void) f_rng;
603  (void) p_rng;
604 #endif
605 
606  olen = ctx->len;
607 
608  switch( ctx->padding )
609  {
610  case RSA_PKCS_V15:
611 
612  switch( hash_id )
613  {
614  case SIG_RSA_RAW:
615  nb_pad = olen - 3 - hashlen;
616  break;
617 
618  case SIG_RSA_MD2:
619  case SIG_RSA_MD4:
620  case SIG_RSA_MD5:
621  nb_pad = olen - 3 - 34;
622  break;
623 
624  case SIG_RSA_SHA1:
625  nb_pad = olen - 3 - 35;
626  break;
627 
628  case SIG_RSA_SHA224:
629  nb_pad = olen - 3 - 47;
630  break;
631 
632  case SIG_RSA_SHA256:
633  nb_pad = olen - 3 - 51;
634  break;
635 
636  case SIG_RSA_SHA384:
637  nb_pad = olen - 3 - 67;
638  break;
639 
640  case SIG_RSA_SHA512:
641  nb_pad = olen - 3 - 83;
642  break;
643 
644 
645  default:
647  }
648 
649  if( nb_pad < 8 )
651 
652  *p++ = 0;
653  *p++ = RSA_SIGN;
654  memset( p, 0xFF, nb_pad );
655  p += nb_pad;
656  *p++ = 0;
657 
658  switch( hash_id )
659  {
660  case SIG_RSA_RAW:
661  memcpy( p, hash, hashlen );
662  break;
663 
664  case SIG_RSA_MD2:
665  memcpy( p, ASN1_HASH_MDX, 18 );
666  memcpy( p + 18, hash, 16 );
667  p[13] = 2; break;
668 
669  case SIG_RSA_MD4:
670  memcpy( p, ASN1_HASH_MDX, 18 );
671  memcpy( p + 18, hash, 16 );
672  p[13] = 4; break;
673 
674  case SIG_RSA_MD5:
675  memcpy( p, ASN1_HASH_MDX, 18 );
676  memcpy( p + 18, hash, 16 );
677  p[13] = 5; break;
678 
679  case SIG_RSA_SHA1:
680  memcpy( p, ASN1_HASH_SHA1, 15 );
681  memcpy( p + 15, hash, 20 );
682  break;
683 
684  case SIG_RSA_SHA224:
685  memcpy( p, ASN1_HASH_SHA2X, 19 );
686  memcpy( p + 19, hash, 28 );
687  p[1] += 28; p[14] = 4; p[18] += 28; break;
688 
689  case SIG_RSA_SHA256:
690  memcpy( p, ASN1_HASH_SHA2X, 19 );
691  memcpy( p + 19, hash, 32 );
692  p[1] += 32; p[14] = 1; p[18] += 32; break;
693 
694  case SIG_RSA_SHA384:
695  memcpy( p, ASN1_HASH_SHA2X, 19 );
696  memcpy( p + 19, hash, 48 );
697  p[1] += 48; p[14] = 2; p[18] += 48; break;
698 
699  case SIG_RSA_SHA512:
700  memcpy( p, ASN1_HASH_SHA2X, 19 );
701  memcpy( p + 19, hash, 64 );
702  p[1] += 64; p[14] = 3; p[18] += 64; break;
703 
704  default:
706  }
707 
708  break;
709 
710 #if defined(POLARSSL_PKCS1_V21)
711  case RSA_PKCS_V21:
712 
713  if( f_rng == NULL )
715 
716  switch( hash_id )
717  {
718  case SIG_RSA_MD2:
719  case SIG_RSA_MD4:
720  case SIG_RSA_MD5:
721  hashlen = 16;
722  break;
723 
724  case SIG_RSA_SHA1:
725  hashlen = 20;
726  break;
727 
728  case SIG_RSA_SHA224:
729  hashlen = 28;
730  break;
731 
732  case SIG_RSA_SHA256:
733  hashlen = 32;
734  break;
735 
736  case SIG_RSA_SHA384:
737  hashlen = 48;
738  break;
739 
740  case SIG_RSA_SHA512:
741  hashlen = 64;
742  break;
743 
744  default:
746  }
747 
748  md_info = md_info_from_type( ctx->hash_id );
749  if( md_info == NULL )
751 
752  hlen = md_get_size( md_info );
753  slen = hlen;
754 
755  memset( sig, 0, olen );
756  memset( &md_ctx, 0, sizeof( md_context_t ) );
757 
758  md_init_ctx( &md_ctx, md_info );
759 
760  msb = mpi_msb( &ctx->N ) - 1;
761 
762  // Generate salt of length slen
763  //
764  if( ( ret = f_rng( p_rng, salt, slen ) ) != 0 )
765  return( POLARSSL_ERR_RSA_RNG_FAILED + ret );
766 
767  // Note: EMSA-PSS encoding is over the length of N - 1 bits
768  //
769  msb = mpi_msb( &ctx->N ) - 1;
770  p += olen - hlen * 2 - 2;
771  *p++ = 0x01;
772  memcpy( p, salt, slen );
773  p += slen;
774 
775  // Generate H = Hash( M' )
776  //
777  md_starts( &md_ctx );
778  md_update( &md_ctx, p, 8 );
779  md_update( &md_ctx, hash, hashlen );
780  md_update( &md_ctx, salt, slen );
781  md_finish( &md_ctx, p );
782 
783  // Compensate for boundary condition when applying mask
784  //
785  if( msb % 8 == 0 )
786  offset = 1;
787 
788  // maskedDB: Apply dbMask to DB
789  //
790  mgf_mask( sig + offset, olen - hlen - 1 - offset, p, hlen, &md_ctx );
791 
792  msb = mpi_msb( &ctx->N ) - 1;
793  sig[0] &= 0xFF >> ( olen * 8 - msb );
794 
795  p += hlen;
796  *p++ = 0xBC;
797  break;
798 #endif
799 
800  default:
801 
803  }
804 
805  return( ( mode == RSA_PUBLIC )
806  ? rsa_public( ctx, sig, sig )
807  : rsa_private( ctx, sig, sig ) );
808 }
809 
810 /*
811  * Do an RSA operation and check the message digest
812  */
813 int rsa_pkcs1_verify( rsa_context *ctx,
814  int mode,
815  int hash_id,
816  unsigned int hashlen,
817  const unsigned char *hash,
818  unsigned char *sig )
819 {
820  int ret;
821  size_t len, siglen;
822  unsigned char *p, c;
823  unsigned char buf[1024];
824 #if defined(POLARSSL_PKCS1_V21)
825  unsigned char result[POLARSSL_MD_MAX_SIZE];
826  unsigned char zeros[8];
827  unsigned int hlen;
828  size_t slen, msb;
829  const md_info_t *md_info;
830  md_context_t md_ctx;
831 #endif
832  siglen = ctx->len;
833 
834  if( siglen < 16 || siglen > sizeof( buf ) )
836 
837  ret = ( mode == RSA_PUBLIC )
838  ? rsa_public( ctx, sig, buf )
839  : rsa_private( ctx, sig, buf );
840 
841  if( ret != 0 )
842  return( ret );
843 
844  p = buf;
845 
846  switch( ctx->padding )
847  {
848  case RSA_PKCS_V15:
849 
850  if( *p++ != 0 || *p++ != RSA_SIGN )
852 
853  while( *p != 0 )
854  {
855  if( p >= buf + siglen - 1 || *p != 0xFF )
857  p++;
858  }
859  p++;
860 
861  len = siglen - ( p - buf );
862 
863  if( len == 34 )
864  {
865  c = p[13];
866  p[13] = 0;
867 
868  if( memcmp( p, ASN1_HASH_MDX, 18 ) != 0 )
870 
871  if( ( c == 2 && hash_id == SIG_RSA_MD2 ) ||
872  ( c == 4 && hash_id == SIG_RSA_MD4 ) ||
873  ( c == 5 && hash_id == SIG_RSA_MD5 ) )
874  {
875  if( memcmp( p + 18, hash, 16 ) == 0 )
876  return( 0 );
877  else
879  }
880  }
881 
882  if( len == 35 && hash_id == SIG_RSA_SHA1 )
883  {
884  if( memcmp( p, ASN1_HASH_SHA1, 15 ) == 0 &&
885  memcmp( p + 15, hash, 20 ) == 0 )
886  return( 0 );
887  else
889  }
890  if( ( len == 19 + 28 && p[14] == 4 && hash_id == SIG_RSA_SHA224 ) ||
891  ( len == 19 + 32 && p[14] == 1 && hash_id == SIG_RSA_SHA256 ) ||
892  ( len == 19 + 48 && p[14] == 2 && hash_id == SIG_RSA_SHA384 ) ||
893  ( len == 19 + 64 && p[14] == 3 && hash_id == SIG_RSA_SHA512 ) )
894  {
895  c = p[1] - 17;
896  p[1] = 17;
897  p[14] = 0;
898 
899  if( p[18] == c &&
900  memcmp( p, ASN1_HASH_SHA2X, 18 ) == 0 &&
901  memcmp( p + 19, hash, c ) == 0 )
902  return( 0 );
903  else
905  }
906 
907  if( len == hashlen && hash_id == SIG_RSA_RAW )
908  {
909  if( memcmp( p, hash, hashlen ) == 0 )
910  return( 0 );
911  else
913  }
914 
915  break;
916 
917 #if defined(POLARSSL_PKCS1_V21)
918  case RSA_PKCS_V21:
919 
920  if( buf[siglen - 1] != 0xBC )
922 
923  switch( hash_id )
924  {
925  case SIG_RSA_MD2:
926  case SIG_RSA_MD4:
927  case SIG_RSA_MD5:
928  hashlen = 16;
929  break;
930 
931  case SIG_RSA_SHA1:
932  hashlen = 20;
933  break;
934 
935  case SIG_RSA_SHA224:
936  hashlen = 28;
937  break;
938 
939  case SIG_RSA_SHA256:
940  hashlen = 32;
941  break;
942 
943  case SIG_RSA_SHA384:
944  hashlen = 48;
945  break;
946 
947  case SIG_RSA_SHA512:
948  hashlen = 64;
949  break;
950 
951  default:
953  }
954 
955  md_info = md_info_from_type( ctx->hash_id );
956  if( md_info == NULL )
958 
959  hlen = md_get_size( md_info );
960  slen = siglen - hlen - 1;
961 
962  memset( &md_ctx, 0, sizeof( md_context_t ) );
963  memset( zeros, 0, 8 );
964 
965  md_init_ctx( &md_ctx, md_info );
966 
967  // Note: EMSA-PSS verification is over the length of N - 1 bits
968  //
969  msb = mpi_msb( &ctx->N ) - 1;
970 
971  // Compensate for boundary condition when applying mask
972  //
973  if( msb % 8 == 0 )
974  {
975  p++;
976  siglen -= 1;
977  }
978  if( buf[0] >> ( 8 - siglen * 8 + msb ) )
980 
981  mgf_mask( p, siglen - hlen - 1, p + siglen - hlen - 1, hlen, &md_ctx );
982 
983  buf[0] &= 0xFF >> ( siglen * 8 - msb );
984 
985  while( *p == 0 && p < buf + siglen )
986  p++;
987 
988  if( p == buf + siglen )
990 
991  if( *p++ != 0x01 )
993 
994  slen -= p - buf;
995 
996  // Generate H = Hash( M' )
997  //
998  md_starts( &md_ctx );
999  md_update( &md_ctx, zeros, 8 );
1000  md_update( &md_ctx, hash, hashlen );
1001  md_update( &md_ctx, p, slen );
1002  md_finish( &md_ctx, result );
1003 
1004  if( memcmp( p + slen, result, hlen ) == 0 )
1005  return( 0 );
1006  else
1008 #endif
1009 
1010  default:
1011 
1013  }
1014 
1016 }
1017 
1018 /*
1019  * Free the components of an RSA key
1020  */
1021 void rsa_free( rsa_context *ctx )
1022 {
1023  mpi_free( &ctx->RQ ); mpi_free( &ctx->RP ); mpi_free( &ctx->RN );
1024  mpi_free( &ctx->QP ); mpi_free( &ctx->DQ ); mpi_free( &ctx->DP );
1025  mpi_free( &ctx->Q ); mpi_free( &ctx->P ); mpi_free( &ctx->D );
1026  mpi_free( &ctx->E ); mpi_free( &ctx->N );
1027 }
1028 
1029 #if defined(POLARSSL_SELF_TEST)
1030 
1031 #include "polarssl/sha1.h"
1032 
1033 /*
1034  * Example RSA-1024 keypair, for test purposes
1035  */
1036 #define KEY_LEN 128
1037 
1038 #define RSA_N "9292758453063D803DD603D5E777D788" \
1039  "8ED1D5BF35786190FA2F23EBC0848AEA" \
1040  "DDA92CA6C3D80B32C4D109BE0F36D6AE" \
1041  "7130B9CED7ACDF54CFC7555AC14EEBAB" \
1042  "93A89813FBF3C4F8066D2D800F7C38A8" \
1043  "1AE31942917403FF4946B0A83D3D3E05" \
1044  "EE57C6F5F5606FB5D4BC6CD34EE0801A" \
1045  "5E94BB77B07507233A0BC7BAC8F90F79"
1046 
1047 #define RSA_E "10001"
1048 
1049 #define RSA_D "24BF6185468786FDD303083D25E64EFC" \
1050  "66CA472BC44D253102F8B4A9D3BFA750" \
1051  "91386C0077937FE33FA3252D28855837" \
1052  "AE1B484A8A9A45F7EE8C0C634F99E8CD" \
1053  "DF79C5CE07EE72C7F123142198164234" \
1054  "CABB724CF78B8173B9F880FC86322407" \
1055  "AF1FEDFDDE2BEB674CA15F3E81A1521E" \
1056  "071513A1E85B5DFA031F21ECAE91A34D"
1057 
1058 #define RSA_P "C36D0EB7FCD285223CFB5AABA5BDA3D8" \
1059  "2C01CAD19EA484A87EA4377637E75500" \
1060  "FCB2005C5C7DD6EC4AC023CDA285D796" \
1061  "C3D9E75E1EFC42488BB4F1D13AC30A57"
1062 
1063 #define RSA_Q "C000DF51A7C77AE8D7C7370C1FF55B69" \
1064  "E211C2B9E5DB1ED0BF61D0D9899620F4" \
1065  "910E4168387E3C30AA1E00C339A79508" \
1066  "8452DD96A9A5EA5D9DCA68DA636032AF"
1067 
1068 #define RSA_DP "C1ACF567564274FB07A0BBAD5D26E298" \
1069  "3C94D22288ACD763FD8E5600ED4A702D" \
1070  "F84198A5F06C2E72236AE490C93F07F8" \
1071  "3CC559CD27BC2D1CA488811730BB5725"
1072 
1073 #define RSA_DQ "4959CBF6F8FEF750AEE6977C155579C7" \
1074  "D8AAEA56749EA28623272E4F7D0592AF" \
1075  "7C1F1313CAC9471B5C523BFE592F517B" \
1076  "407A1BD76C164B93DA2D32A383E58357"
1077 
1078 #define RSA_QP "9AE7FBC99546432DF71896FC239EADAE" \
1079  "F38D18D2B2F0E2DD275AA977E2BF4411" \
1080  "F5A3B2A5D33605AEBBCCBA7FEB9F2D2F" \
1081  "A74206CEC169D74BF5A8C50D6F48EA08"
1082 
1083 #define PT_LEN 24
1084 #define RSA_PT "\xAA\xBB\xCC\x03\x02\x01\x00\xFF\xFF\xFF\xFF\xFF" \
1085  "\x11\x22\x33\x0A\x0B\x0C\xCC\xDD\xDD\xDD\xDD\xDD"
1086 
1087 static int myrand( void *rng_state, unsigned char *output, size_t len )
1088 {
1089  size_t i;
1090 
1091  if( rng_state != NULL )
1092  rng_state = NULL;
1093 
1094  for( i = 0; i < len; ++i )
1095  output[i] = rand();
1096 
1097  return( 0 );
1098 }
1099 
1100 /*
1101  * Checkup routine
1102  */
1103 int rsa_self_test( int verbose )
1104 {
1105  size_t len;
1106  rsa_context rsa;
1107  unsigned char rsa_plaintext[PT_LEN];
1108  unsigned char rsa_decrypted[PT_LEN];
1109  unsigned char rsa_ciphertext[KEY_LEN];
1110 #if defined(POLARSSL_SHA1_C)
1111  unsigned char sha1sum[20];
1112 #endif
1113 
1114  rsa_init( &rsa, RSA_PKCS_V15, 0 );
1115 
1116  rsa.len = KEY_LEN;
1117  mpi_read_string( &rsa.N , 16, RSA_N );
1118  mpi_read_string( &rsa.E , 16, RSA_E );
1119  mpi_read_string( &rsa.D , 16, RSA_D );
1120  mpi_read_string( &rsa.P , 16, RSA_P );
1121  mpi_read_string( &rsa.Q , 16, RSA_Q );
1122  mpi_read_string( &rsa.DP, 16, RSA_DP );
1123  mpi_read_string( &rsa.DQ, 16, RSA_DQ );
1124  mpi_read_string( &rsa.QP, 16, RSA_QP );
1125 
1126  if( verbose != 0 )
1127  printf( " RSA key validation: " );
1128 
1129  if( rsa_check_pubkey( &rsa ) != 0 ||
1130  rsa_check_privkey( &rsa ) != 0 )
1131  {
1132  if( verbose != 0 )
1133  printf( "failed\n" );
1134 
1135  return( 1 );
1136  }
1137 
1138  if( verbose != 0 )
1139  printf( "passed\n PKCS#1 encryption : " );
1140 
1141  memcpy( rsa_plaintext, RSA_PT, PT_LEN );
1142 
1143  if( rsa_pkcs1_encrypt( &rsa, &myrand, NULL, RSA_PUBLIC, PT_LEN,
1144  rsa_plaintext, rsa_ciphertext ) != 0 )
1145  {
1146  if( verbose != 0 )
1147  printf( "failed\n" );
1148 
1149  return( 1 );
1150  }
1151 
1152  if( verbose != 0 )
1153  printf( "passed\n PKCS#1 decryption : " );
1154 
1155  if( rsa_pkcs1_decrypt( &rsa, RSA_PRIVATE, &len,
1156  rsa_ciphertext, rsa_decrypted,
1157  sizeof(rsa_decrypted) ) != 0 )
1158  {
1159  if( verbose != 0 )
1160  printf( "failed\n" );
1161 
1162  return( 1 );
1163  }
1164 
1165  if( memcmp( rsa_decrypted, rsa_plaintext, len ) != 0 )
1166  {
1167  if( verbose != 0 )
1168  printf( "failed\n" );
1169 
1170  return( 1 );
1171  }
1172 
1173 #if defined(POLARSSL_SHA1_C)
1174  if( verbose != 0 )
1175  printf( "passed\n PKCS#1 data sign : " );
1176 
1177  sha1( rsa_plaintext, PT_LEN, sha1sum );
1178 
1179  if( rsa_pkcs1_sign( &rsa, NULL, NULL, RSA_PRIVATE, SIG_RSA_SHA1, 20,
1180  sha1sum, rsa_ciphertext ) != 0 )
1181  {
1182  if( verbose != 0 )
1183  printf( "failed\n" );
1184 
1185  return( 1 );
1186  }
1187 
1188  if( verbose != 0 )
1189  printf( "passed\n PKCS#1 sig. verify: " );
1190 
1191  if( rsa_pkcs1_verify( &rsa, RSA_PUBLIC, SIG_RSA_SHA1, 20,
1192  sha1sum, rsa_ciphertext ) != 0 )
1193  {
1194  if( verbose != 0 )
1195  printf( "failed\n" );
1196 
1197  return( 1 );
1198  }
1199 
1200  if( verbose != 0 )
1201  printf( "passed\n\n" );
1202 #endif /* POLARSSL_SHA1_C */
1203 
1204  rsa_free( &rsa );
1205 
1206  return( 0 );
1207 }
1208 
1209 #endif
1210 
1211 #endif