2 * The RSA public-key cryptosystem
4 * Copyright (C) 2006-2010, Brainspark B.V.
6 * This file is part of PolarSSL (http://www.polarssl.org)
7 * Lead Maintainer: Paul Bakker <polarssl_maintainer at polarssl.org>
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.
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.
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.
26 * RSA was designed by Ron Rivest, Adi Shamir and Len Adleman.
28 * http://theory.lcs.mit.edu/~rivest/rsapaper.pdf
29 * http://www.cacr.math.uwaterloo.ca/hac/about/chap8.pdf
32 #include "polarssl/config.h"
34 #if defined(POLARSSL_RSA_C)
36 #include "polarssl/rsa.h"
43 * Initialize an RSA context
45 void rsa_init( rsa_context *ctx,
49 memset( ctx, 0, sizeof( rsa_context ) );
51 ctx->padding = padding;
52 ctx->hash_id = hash_id;
55 #if defined(POLARSSL_GENPRIME)
58 * Generate an RSA keypair
60 int rsa_gen_key( rsa_context *ctx,
63 int nbits, int exponent )
68 if( f_rng == NULL || nbits < 128 || exponent < 3 )
69 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
71 mpi_init( &P1, &Q1, &H, &G, NULL );
74 * find primes P and Q with Q < P so that:
75 * GCD( E, (P-1)*(Q-1) ) == 1
77 MPI_CHK( mpi_lset( &ctx->E, exponent ) );
81 MPI_CHK( mpi_gen_prime( &ctx->P, ( nbits + 1 ) >> 1, 0,
84 MPI_CHK( mpi_gen_prime( &ctx->Q, ( nbits + 1 ) >> 1, 0,
87 if( mpi_cmp_mpi( &ctx->P, &ctx->Q ) < 0 )
88 mpi_swap( &ctx->P, &ctx->Q );
90 if( mpi_cmp_mpi( &ctx->P, &ctx->Q ) == 0 )
93 MPI_CHK( mpi_mul_mpi( &ctx->N, &ctx->P, &ctx->Q ) );
94 if( mpi_msb( &ctx->N ) != nbits )
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 ) );
102 while( mpi_cmp_int( &G, 1 ) != 0 );
105 * D = E^-1 mod ((P-1)*(Q-1))
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 ) );
115 ctx->len = ( mpi_msb( &ctx->N ) + 7 ) >> 3;
119 mpi_free( &G, &H, &Q1, &P1, NULL );
124 return( POLARSSL_ERR_RSA_KEY_GEN_FAILED | ret );
133 * Check a public RSA key
135 int rsa_check_pubkey( const rsa_context *ctx )
137 if( !ctx->N.p || !ctx->E.p )
138 return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED );
140 if( ( ctx->N.p[0] & 1 ) == 0 ||
141 ( ctx->E.p[0] & 1 ) == 0 )
142 return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED );
144 if( mpi_msb( &ctx->N ) < 128 ||
145 mpi_msb( &ctx->N ) > 4096 )
146 return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED );
148 if( mpi_msb( &ctx->E ) < 2 ||
149 mpi_msb( &ctx->E ) > 64 )
150 return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED );
156 * Check a private RSA key
158 int rsa_check_privkey( const rsa_context *ctx )
161 mpi PQ, DE, P1, Q1, H, I, G, G2, L1, L2;
163 if( ( ret = rsa_check_pubkey( ctx ) ) != 0 )
166 if( !ctx->P.p || !ctx->Q.p || !ctx->D.p )
167 return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED );
169 mpi_init( &PQ, &DE, &P1, &Q1, &H, &I, &G, &G2, &L1, &L2, NULL );
171 MPI_CHK( mpi_mul_mpi( &PQ, &ctx->P, &ctx->Q ) );
172 MPI_CHK( mpi_mul_mpi( &DE, &ctx->D, &ctx->E ) );
173 MPI_CHK( mpi_sub_int( &P1, &ctx->P, 1 ) );
174 MPI_CHK( mpi_sub_int( &Q1, &ctx->Q, 1 ) );
175 MPI_CHK( mpi_mul_mpi( &H, &P1, &Q1 ) );
176 MPI_CHK( mpi_gcd( &G, &ctx->E, &H ) );
178 MPI_CHK( mpi_gcd( &G2, &P1, &Q1 ) );
179 MPI_CHK( mpi_div_mpi( &L1, &L2, &H, &G2 ) );
180 MPI_CHK( mpi_mod_mpi( &I, &DE, &L1 ) );
183 * Check for a valid PKCS1v2 private key
185 if( mpi_cmp_mpi( &PQ, &ctx->N ) == 0 &&
186 mpi_cmp_int( &L2, 0 ) == 0 &&
187 mpi_cmp_int( &I, 1 ) == 0 &&
188 mpi_cmp_int( &G, 1 ) == 0 )
190 mpi_free( &G, &I, &H, &Q1, &P1, &DE, &PQ, &G2, &L1, &L2, NULL );
197 mpi_free( &G, &I, &H, &Q1, &P1, &DE, &PQ, &G2, &L1, &L2, NULL );
198 return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED | ret );
202 * Do an RSA public key operation
204 int rsa_public( rsa_context *ctx,
205 const unsigned char *input,
206 unsigned char *output )
211 mpi_init( &T, NULL );
213 MPI_CHK( mpi_read_binary( &T, input, ctx->len ) );
215 if( mpi_cmp_mpi( &T, &ctx->N ) >= 0 )
217 mpi_free( &T, NULL );
218 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
222 MPI_CHK( mpi_exp_mod( &T, &T, &ctx->E, &ctx->N, &ctx->RN ) );
223 MPI_CHK( mpi_write_binary( &T, output, olen ) );
227 mpi_free( &T, NULL );
230 return( POLARSSL_ERR_RSA_PUBLIC_FAILED | ret );
236 * Do an RSA private key operation
238 int rsa_private( rsa_context *ctx,
239 const unsigned char *input,
240 unsigned char *output )
245 mpi_init( &T, &T1, &T2, NULL );
247 MPI_CHK( mpi_read_binary( &T, input, ctx->len ) );
249 if( mpi_cmp_mpi( &T, &ctx->N ) >= 0 )
251 mpi_free( &T, NULL );
252 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
256 MPI_CHK( mpi_exp_mod( &T, &T, &ctx->D, &ctx->N, &ctx->RN ) );
259 * faster decryption using the CRT
261 * T1 = input ^ dP mod P
262 * T2 = input ^ dQ mod Q
264 MPI_CHK( mpi_exp_mod( &T1, &T, &ctx->DP, &ctx->P, &ctx->RP ) );
265 MPI_CHK( mpi_exp_mod( &T2, &T, &ctx->DQ, &ctx->Q, &ctx->RQ ) );
268 * T = (T1 - T2) * (Q^-1 mod P) mod P
270 MPI_CHK( mpi_sub_mpi( &T, &T1, &T2 ) );
271 MPI_CHK( mpi_mul_mpi( &T1, &T, &ctx->QP ) );
272 MPI_CHK( mpi_mod_mpi( &T, &T1, &ctx->P ) );
275 * output = T2 + T * Q
277 MPI_CHK( mpi_mul_mpi( &T1, &T, &ctx->Q ) );
278 MPI_CHK( mpi_add_mpi( &T, &T2, &T1 ) );
282 MPI_CHK( mpi_write_binary( &T, output, olen ) );
286 mpi_free( &T, &T1, &T2, NULL );
289 return( POLARSSL_ERR_RSA_PRIVATE_FAILED | ret );
295 * Add the message padding, then do an RSA operation
297 int rsa_pkcs1_encrypt( rsa_context *ctx,
298 int (*f_rng)(void *),
301 const unsigned char *input,
302 unsigned char *output )
305 unsigned char *p = output;
309 switch( ctx->padding )
313 if( ilen < 0 || olen < ilen + 11 || f_rng == NULL )
314 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
316 nb_pad = olen - 3 - ilen;
321 while( nb_pad-- > 0 )
326 *p = (unsigned char) f_rng( p_rng );
327 } while( *p == 0 && --rng_dl );
329 // Check if RNG failed to generate data
332 return POLARSSL_ERR_RSA_RNG_FAILED;
337 memcpy( p, input, ilen );
342 return( POLARSSL_ERR_RSA_INVALID_PADDING );
345 return( ( mode == RSA_PUBLIC )
346 ? rsa_public( ctx, output, output )
347 : rsa_private( ctx, output, output ) );
351 * Do an RSA operation, then remove the message padding
353 int rsa_pkcs1_decrypt( rsa_context *ctx,
355 const unsigned char *input,
356 unsigned char *output,
361 unsigned char buf[1024];
365 if( ilen < 16 || ilen > (int) sizeof( buf ) )
366 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
368 ret = ( mode == RSA_PUBLIC )
369 ? rsa_public( ctx, input, buf )
370 : rsa_private( ctx, input, buf );
377 switch( ctx->padding )
381 if( *p++ != 0 || *p++ != RSA_CRYPT )
382 return( POLARSSL_ERR_RSA_INVALID_PADDING );
386 if( p >= buf + ilen - 1 )
387 return( POLARSSL_ERR_RSA_INVALID_PADDING );
395 return( POLARSSL_ERR_RSA_INVALID_PADDING );
398 if (ilen - (int)(p - buf) > output_max_len)
399 return( POLARSSL_ERR_RSA_OUTPUT_TOO_LARGE );
401 *olen = ilen - (int)(p - buf);
402 memcpy( output, p, *olen );
408 * Do an RSA operation to sign the message digest
410 int rsa_pkcs1_sign( rsa_context *ctx,
414 const unsigned char *hash,
418 unsigned char *p = sig;
422 switch( ctx->padding )
429 nb_pad = olen - 3 - hashlen;
435 nb_pad = olen - 3 - 34;
439 nb_pad = olen - 3 - 35;
443 nb_pad = olen - 3 - 47;
447 nb_pad = olen - 3 - 51;
451 nb_pad = olen - 3 - 67;
455 nb_pad = olen - 3 - 83;
460 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
464 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
468 memset( p, 0xFF, nb_pad );
475 return( POLARSSL_ERR_RSA_INVALID_PADDING );
481 memcpy( p, hash, hashlen );
485 memcpy( p, ASN1_HASH_MDX, 18 );
486 memcpy( p + 18, hash, 16 );
490 memcpy( p, ASN1_HASH_MDX, 18 );
491 memcpy( p + 18, hash, 16 );
495 memcpy( p, ASN1_HASH_MDX, 18 );
496 memcpy( p + 18, hash, 16 );
500 memcpy( p, ASN1_HASH_SHA1, 15 );
501 memcpy( p + 15, hash, 20 );
505 memcpy( p, ASN1_HASH_SHA2X, 19 );
506 memcpy( p + 19, hash, 28 );
507 p[1] += 28; p[14] = 4; p[18] += 28; break;
510 memcpy( p, ASN1_HASH_SHA2X, 19 );
511 memcpy( p + 19, hash, 32 );
512 p[1] += 32; p[14] = 1; p[18] += 32; break;
515 memcpy( p, ASN1_HASH_SHA2X, 19 );
516 memcpy( p + 19, hash, 48 );
517 p[1] += 48; p[14] = 2; p[18] += 48; break;
520 memcpy( p, ASN1_HASH_SHA2X, 19 );
521 memcpy( p + 19, hash, 64 );
522 p[1] += 64; p[14] = 3; p[18] += 64; break;
525 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
528 return( ( mode == RSA_PUBLIC )
529 ? rsa_public( ctx, sig, sig )
530 : rsa_private( ctx, sig, sig ) );
534 * Do an RSA operation and check the message digest
536 int rsa_pkcs1_verify( rsa_context *ctx,
540 const unsigned char *hash,
543 int ret, len, siglen;
545 unsigned char buf[1024];
549 if( siglen < 16 || siglen > (int) sizeof( buf ) )
550 return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
552 ret = ( mode == RSA_PUBLIC )
553 ? rsa_public( ctx, sig, buf )
554 : rsa_private( ctx, sig, buf );
561 switch( ctx->padding )
565 if( *p++ != 0 || *p++ != RSA_SIGN )
566 return( POLARSSL_ERR_RSA_INVALID_PADDING );
570 if( p >= buf + siglen - 1 || *p != 0xFF )
571 return( POLARSSL_ERR_RSA_INVALID_PADDING );
579 return( POLARSSL_ERR_RSA_INVALID_PADDING );
582 len = siglen - (int)( p - buf );
589 if( memcmp( p, ASN1_HASH_MDX, 18 ) != 0 )
590 return( POLARSSL_ERR_RSA_VERIFY_FAILED );
592 if( ( c == 2 && hash_id == SIG_RSA_MD2 ) ||
593 ( c == 4 && hash_id == SIG_RSA_MD4 ) ||
594 ( c == 5 && hash_id == SIG_RSA_MD5 ) )
596 if( memcmp( p + 18, hash, 16 ) == 0 )
599 return( POLARSSL_ERR_RSA_VERIFY_FAILED );
603 if( len == 35 && hash_id == SIG_RSA_SHA1 )
605 if( memcmp( p, ASN1_HASH_SHA1, 15 ) == 0 &&
606 memcmp( p + 15, hash, 20 ) == 0 )
609 return( POLARSSL_ERR_RSA_VERIFY_FAILED );
611 if( ( len == 19 + 28 && p[14] == 4 && hash_id == SIG_RSA_SHA224 ) ||
612 ( len == 19 + 32 && p[14] == 1 && hash_id == SIG_RSA_SHA256 ) ||
613 ( len == 19 + 48 && p[14] == 2 && hash_id == SIG_RSA_SHA384 ) ||
614 ( len == 19 + 64 && p[14] == 3 && hash_id == SIG_RSA_SHA512 ) )
621 memcmp( p, ASN1_HASH_SHA2X, 18 ) == 0 &&
622 memcmp( p + 19, hash, c ) == 0 )
625 return( POLARSSL_ERR_RSA_VERIFY_FAILED );
628 if( len == hashlen && hash_id == SIG_RSA_RAW )
630 if( memcmp( p, hash, hashlen ) == 0 )
633 return( POLARSSL_ERR_RSA_VERIFY_FAILED );
636 return( POLARSSL_ERR_RSA_INVALID_PADDING );
640 * Free the components of an RSA key
642 void rsa_free( rsa_context *ctx )
644 mpi_free( &ctx->RQ, &ctx->RP, &ctx->RN,
645 &ctx->QP, &ctx->DQ, &ctx->DP,
646 &ctx->Q, &ctx->P, &ctx->D,
647 &ctx->E, &ctx->N, NULL );
650 #if defined(POLARSSL_SELF_TEST)
652 #include "polarssl/sha1.h"
655 * Example RSA-1024 keypair, for test purposes
659 #define RSA_N "9292758453063D803DD603D5E777D788" \
660 "8ED1D5BF35786190FA2F23EBC0848AEA" \
661 "DDA92CA6C3D80B32C4D109BE0F36D6AE" \
662 "7130B9CED7ACDF54CFC7555AC14EEBAB" \
663 "93A89813FBF3C4F8066D2D800F7C38A8" \
664 "1AE31942917403FF4946B0A83D3D3E05" \
665 "EE57C6F5F5606FB5D4BC6CD34EE0801A" \
666 "5E94BB77B07507233A0BC7BAC8F90F79"
668 #define RSA_E "10001"
670 #define RSA_D "24BF6185468786FDD303083D25E64EFC" \
671 "66CA472BC44D253102F8B4A9D3BFA750" \
672 "91386C0077937FE33FA3252D28855837" \
673 "AE1B484A8A9A45F7EE8C0C634F99E8CD" \
674 "DF79C5CE07EE72C7F123142198164234" \
675 "CABB724CF78B8173B9F880FC86322407" \
676 "AF1FEDFDDE2BEB674CA15F3E81A1521E" \
677 "071513A1E85B5DFA031F21ECAE91A34D"
679 #define RSA_P "C36D0EB7FCD285223CFB5AABA5BDA3D8" \
680 "2C01CAD19EA484A87EA4377637E75500" \
681 "FCB2005C5C7DD6EC4AC023CDA285D796" \
682 "C3D9E75E1EFC42488BB4F1D13AC30A57"
684 #define RSA_Q "C000DF51A7C77AE8D7C7370C1FF55B69" \
685 "E211C2B9E5DB1ED0BF61D0D9899620F4" \
686 "910E4168387E3C30AA1E00C339A79508" \
687 "8452DD96A9A5EA5D9DCA68DA636032AF"
689 #define RSA_DP "C1ACF567564274FB07A0BBAD5D26E298" \
690 "3C94D22288ACD763FD8E5600ED4A702D" \
691 "F84198A5F06C2E72236AE490C93F07F8" \
692 "3CC559CD27BC2D1CA488811730BB5725"
694 #define RSA_DQ "4959CBF6F8FEF750AEE6977C155579C7" \
695 "D8AAEA56749EA28623272E4F7D0592AF" \
696 "7C1F1313CAC9471B5C523BFE592F517B" \
697 "407A1BD76C164B93DA2D32A383E58357"
699 #define RSA_QP "9AE7FBC99546432DF71896FC239EADAE" \
700 "F38D18D2B2F0E2DD275AA977E2BF4411" \
701 "F5A3B2A5D33605AEBBCCBA7FEB9F2D2F" \
702 "A74206CEC169D74BF5A8C50D6F48EA08"
705 #define RSA_PT "\xAA\xBB\xCC\x03\x02\x01\x00\xFF\xFF\xFF\xFF\xFF" \
706 "\x11\x22\x33\x0A\x0B\x0C\xCC\xDD\xDD\xDD\xDD\xDD"
708 static int myrand( void *rng_state )
710 if( rng_state != NULL )
719 int rsa_self_test( int verbose )
723 unsigned char sha1sum[20];
724 unsigned char rsa_plaintext[PT_LEN];
725 unsigned char rsa_decrypted[PT_LEN];
726 unsigned char rsa_ciphertext[KEY_LEN];
728 rsa_init( &rsa, RSA_PKCS_V15, 0 );
731 mpi_read_string( &rsa.N , 16, RSA_N );
732 mpi_read_string( &rsa.E , 16, RSA_E );
733 mpi_read_string( &rsa.D , 16, RSA_D );
734 mpi_read_string( &rsa.P , 16, RSA_P );
735 mpi_read_string( &rsa.Q , 16, RSA_Q );
736 mpi_read_string( &rsa.DP, 16, RSA_DP );
737 mpi_read_string( &rsa.DQ, 16, RSA_DQ );
738 mpi_read_string( &rsa.QP, 16, RSA_QP );
741 printf( " RSA key validation: " );
743 if( rsa_check_pubkey( &rsa ) != 0 ||
744 rsa_check_privkey( &rsa ) != 0 )
747 printf( "failed\n" );
753 printf( "passed\n PKCS#1 encryption : " );
755 memcpy( rsa_plaintext, RSA_PT, PT_LEN );
757 if( rsa_pkcs1_encrypt( &rsa, &myrand, NULL, RSA_PUBLIC, PT_LEN,
758 rsa_plaintext, rsa_ciphertext ) != 0 )
761 printf( "failed\n" );
767 printf( "passed\n PKCS#1 decryption : " );
769 if( rsa_pkcs1_decrypt( &rsa, RSA_PRIVATE, &len,
770 rsa_ciphertext, rsa_decrypted,
771 sizeof(rsa_decrypted) ) != 0 )
774 printf( "failed\n" );
779 if( memcmp( rsa_decrypted, rsa_plaintext, len ) != 0 )
782 printf( "failed\n" );
788 printf( "passed\n PKCS#1 data sign : " );
790 sha1( rsa_plaintext, PT_LEN, sha1sum );
792 if( rsa_pkcs1_sign( &rsa, RSA_PRIVATE, SIG_RSA_SHA1, 20,
793 sha1sum, rsa_ciphertext ) != 0 )
796 printf( "failed\n" );
802 printf( "passed\n PKCS#1 sig. verify: " );
804 if( rsa_pkcs1_verify( &rsa, RSA_PUBLIC, SIG_RSA_SHA1, 20,
805 sha1sum, rsa_ciphertext ) != 0 )
808 printf( "failed\n" );
814 printf( "passed\n\n" );