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 polarssl_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" );