1 /****************************************************************************
2 * *
3 * cryptlib RSA Key Generation/Checking Routines *
4 * Copyright Peter Gutmann 1997-2014 *
5 * *
6 ****************************************************************************/
7
8 #define PKC_CONTEXT /* Indicate that we're working with PKC contexts */
9 #if defined( INC_ALL )
10 #include "crypt.h"
11 #include "context.h"
12 #include "keygen.h"
13 #else
14 #include "crypt.h"
15 #include "context/context.h"
16 #include "context/keygen.h"
17 #endif /* Compiler-specific includes */
18
19 /* We use F4 as the default public exponent e unless the user chooses to
20 override this with some other value:
21
22 Fn = 2^(2^n) + 1, n = 0...4.
23
24 F0 = 3, F1 = 5, F2 = 17, F3 = 257, F4 = 65537.
25
26 The older (X.509v1) recommended value of 3 is insecure for general use
27 and more recent work indicates that values like 17 (used by PGP) are also
28 insecure against the Hastad attack. We could work around this by using
29 41 or 257 as the exponent, however current best practice favours F4
30 unless you're doing banking standards, in which case you set e=2 (EMV)
31 and use raw, unpadded RSA (HBCI) to make it easier for students to break
32 your banking security as a homework exercise.
33
34 Since some systems may be using 16-bit bignum component values we use an
35 exponent of 257 for these cases to ensure that it fits in a single
36 component value */
37
38 #ifndef RSA_PUBLIC_EXPONENT
39 #ifdef SIXTEEN_BIT
40 #define RSA_PUBLIC_EXPONENT 257
41 #else
42 #define RSA_PUBLIC_EXPONENT 65537L
43 #endif /* 16-bit bignum components */
44 #endif /* RSA_PUBLIC_EXPONENT */
45
46 /* The minimum allowed public exponent. In theory this could go as low as 3,
47 however there are all manner of obscure corner cases that have to be
48 checked if this exponent is used and in general the necessary checking
49 presents a more or less intractable problem. To avoid this minefield we
50 require a minimum exponent of at 17, the next generally-used value above
51 3. However even this is only used by PGP 2.x, the next minimum is 33 (a
52 weird value used by OpenSSH until mid-2010, see the comment further
53 down), 41 (another weird value used by GPG until mid-2006), and then 257
54 or (in practice) F4 / 65537 by everything else */
55
56 #if defined( USE_PGP ) || defined( USE_PGPKEYS )
57 #define MIN_PUBLIC_EXPONENT 17
58 #elif defined( USE_SSH )
59 #define MIN_PUBLIC_EXPONENT 33
60 #else
61 #define MIN_PUBLIC_EXPONENT 257
62 #endif /* Smallest exponents used by various crypto protocols */
63 #if ( MIN_PUBLIC_EXPONENT <= 0xFF && RSAPARAM_MIN_E > 1 ) || \
64 ( MIN_PUBLIC_EXPONENT <= 0xFFFF && RSAPARAM_MIN_E > 2 )
65 #error RSAPARAM_MIN_E is too large for MIN_PUBLIC_EXPONENT
66 #endif /* MIN_PUBLIC_EXPONENT size > RSAPARAM_MIN_E value */
67
68 /****************************************************************************
69 * *
70 * Utility Functions *
71 * *
72 ****************************************************************************/
73
74 /* Enable various side-channel protection mechanisms */
75
76 #if defined( __WINCE__ ) && defined( ARMV4 ) && defined( NDEBUG )
77 #pragma optimize( "g", off )
78 #endif /* eVC++ 4.0 ARMv4 optimiser bug */
79
80 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
enableSidechannelProtection(INOUT PKC_INFO * pkcInfo,const BOOLEAN isPrivateKey)81 static int enableSidechannelProtection( INOUT PKC_INFO *pkcInfo,
82 const BOOLEAN isPrivateKey )
83 {
84 BIGNUM *n = &pkcInfo->rsaParam_n, *e = &pkcInfo->rsaParam_e;
85 BIGNUM *k = &pkcInfo->rsaParam_blind_k;
86 BIGNUM *kInv = &pkcInfo->rsaParam_blind_kInv;
87 MESSAGE_DATA msgData;
88 BYTE buffer[ CRYPT_MAX_PKCSIZE + 8 ];
89 int noBytes = bitsToBytes( pkcInfo->keySizeBits );
90 int bnStatus = BN_STATUS, status;
91
92 assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
93
94 REQUIRES( sanityCheckPKCInfo( pkcInfo ) );
95
96 /* Generate a random bignum for blinding. Since this merely has to be
97 unpredictable to an outsider but not cryptographically strong, and to
98 avoid having more crypto RNG output than necessary sitting around in
99 memory, we get it from the nonce PRNG rather than the crypto one. In
100 addition we don't have to perform a range check on import to see if
101 it's larger than 'n' since we're about to reduce it mod n in the next
102 step, and doing so would give false positives */
103 setMessageData( &msgData, buffer, noBytes );
104 status = krnlSendMessage( SYSTEM_OBJECT_HANDLE, IMESSAGE_GETATTRIBUTE_S,
105 &msgData, CRYPT_IATTRIBUTE_RANDOM_NONCE );
106 if( cryptStatusOK( status ) )
107 {
108 buffer[ 0 ] &= 0xFF >> ( -pkcInfo->keySizeBits & 7 );
109 status = importBignum( k, buffer, noBytes, MIN_PKCSIZE - 8,
110 CRYPT_MAX_PKCSIZE, NULL,
111 KEYSIZE_CHECK_NONE );
112 }
113 zeroise( buffer, noBytes );
114 if( cryptStatusError( status ) )
115 return( status );
116
117 /* Set up the blinding and unblinding values */
118 CK( BN_mod( k, k, n, &pkcInfo->bnCTX ) ); /* k = rand() mod n */
119 CKPTR( BN_mod_inverse( kInv, k, n, &pkcInfo->bnCTX ) );
120 /* kInv = k^-1 mod n */
121 CK( BN_mod_exp_mont( k, k, e, n, &pkcInfo->bnCTX,
122 &pkcInfo->rsaParam_mont_n ) );
123 /* k = k^e mod n */
124 if( bnStatusError( bnStatus ) )
125 return( getBnStatus( bnStatus ) );
126
127 /* Use constant-time modexp() to protect the private key from timing
128 channels if required */
129 if( isPrivateKey )
130 {
131 BN_set_flags( &pkcInfo->rsaParam_exponent1, BN_FLG_CONSTTIME );
132 BN_set_flags( &pkcInfo->rsaParam_exponent2, BN_FLG_CONSTTIME );
133 }
134
135 ENSURES( sanityCheckPKCInfo( pkcInfo ) );
136
137 return( CRYPT_OK );
138 }
139
140 #if defined( __WINCE__ ) && defined( ARMV4 ) && defined( NDEBUG )
141 #pragma optimize( "g", on )
142 #endif /* eVC++ 4.0 ARMv4 optimiser bug */
143
144 /* Adjust p and q if necessary to ensure that the CRT decrypt works */
145
146 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
fixCRTvalues(INOUT PKC_INFO * pkcInfo,const BOOLEAN fixPKCSvalues)147 static int fixCRTvalues( INOUT PKC_INFO *pkcInfo,
148 const BOOLEAN fixPKCSvalues )
149 {
150 BIGNUM *p = &pkcInfo->rsaParam_p, *q = &pkcInfo->rsaParam_q;
151 int bnStatus = BN_STATUS;
152
153 assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
154
155 REQUIRES( sanityCheckPKCInfo( pkcInfo ) );
156
157 /* Make sure that p > q, which is required for the CRT decrypt */
158 if( BN_cmp( p, q ) >= 0 )
159 return( CRYPT_OK );
160
161 /* Swap the values p and q and, if necessary, the PKCS parameters e1
162 and e2 that depend on them (e1 = d mod (p - 1) and
163 e2 = d mod (q - 1)), and recompute u = qInv mod p */
164 BN_swap( p, q );
165 if( !fixPKCSvalues )
166 return( CRYPT_OK );
167 BN_swap( &pkcInfo->rsaParam_exponent1, &pkcInfo->rsaParam_exponent2 );
168 CKPTR( BN_mod_inverse( &pkcInfo->rsaParam_u, q, p,
169 &pkcInfo->bnCTX ) );
170 if( bnStatusError( bnStatus ) )
171 return( getBnStatus( bnStatus ) );
172
173 ENSURES( sanityCheckPKCInfo( pkcInfo ) );
174
175 return( CRYPT_OK );
176 }
177
178 /* Evaluate the Montgomery forms for public and private components */
179
180 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
getRSAMontgomery(INOUT PKC_INFO * pkcInfo,const BOOLEAN isPrivateKey)181 static int getRSAMontgomery( INOUT PKC_INFO *pkcInfo,
182 const BOOLEAN isPrivateKey )
183 {
184 int bnStatus = BN_STATUS;
185
186 assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
187
188 REQUIRES( sanityCheckPKCInfo( pkcInfo ) );
189
190 REQUIRES( sanityCheckPKCInfo( pkcInfo ) );
191
192 /* Evaluate the public value */
193 if( !BN_MONT_CTX_set( &pkcInfo->rsaParam_mont_n, &pkcInfo->rsaParam_n,
194 &pkcInfo->bnCTX ) )
195 return( CRYPT_ERROR_FAILED );
196 if( !isPrivateKey )
197 return( CRYPT_OK );
198
199 /* Evaluate the private values */
200 CK( BN_MONT_CTX_set( &pkcInfo->rsaParam_mont_p, &pkcInfo->rsaParam_p,
201 &pkcInfo->bnCTX ) );
202 CK( BN_MONT_CTX_set( &pkcInfo->rsaParam_mont_q, &pkcInfo->rsaParam_q,
203 &pkcInfo->bnCTX ) );
204 if( bnStatusError( bnStatus ) )
205 return( getBnStatus( bnStatus ) );
206
207 ENSURES( sanityCheckPKCInfo( pkcInfo ) );
208
209 return( CRYPT_OK );
210 }
211
212 /****************************************************************************
213 * *
214 * Check an RSA Key *
215 * *
216 ****************************************************************************/
217
218 /* Perform validity checks on the public key. We have to make the PKC_INFO
219 data non-const because the bignum code wants to modify some of the values
220 as it's working with them */
221
222 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
checkRSAPublicKeyComponents(INOUT PKC_INFO * pkcInfo)223 static int checkRSAPublicKeyComponents( INOUT PKC_INFO *pkcInfo )
224 {
225 BIGNUM *n = &pkcInfo->rsaParam_n, *e = &pkcInfo->rsaParam_e;
226 const BN_ULONG eWord = BN_get_word( e );
227 const int eLen = BN_num_bits( e );
228 int length;
229
230 assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
231
232 REQUIRES( sanityCheckPKCInfo( pkcInfo ) );
233 REQUIRES( eLen > 0 && eLen <= bytesToBits( CRYPT_MAX_PKCSIZE ) );
234
235 /* Verify that nLen >= RSAPARAM_MIN_N (= MIN_PKCSIZE),
236 nLen <= RSAPARAM_MAX_N (= CRYPT_MAX_PKCSIZE) */
237 length = BN_num_bytes( n );
238 if( isShortPKCKey( length ) )
239 {
240 /* Special-case handling for insecure-sized public keys */
241 return( CRYPT_ERROR_NOSECURE );
242 }
243 if( length < RSAPARAM_MIN_N || length > RSAPARAM_MAX_N )
244 return( CRYPT_ARGERROR_STR1 );
245
246 /* Verify that n is not (obviously) composite */
247 if( !primeSieve( n ) )
248 return( CRYPT_ARGERROR_STR1 );
249
250 /* Verify that e >= MIN_PUBLIC_EXPONENT, eLen <= RSAPARAM_MAX_E
251 (= 32 bits). The latter check is to preclude DoS attacks due to
252 ridiculously large e values. BN_get_word() works even on 16-bit
253 systems because it returns BN_MASK2 (== UINT_MAX) if the value
254 can't be represented in a machine word */
255 if( eWord < MIN_PUBLIC_EXPONENT || bitsToBytes( eLen ) > RSAPARAM_MAX_E )
256 return( CRYPT_ARGERROR_STR1 );
257
258 /* Perform a second check to make sure that e will fit into a signed
259 integer. This isn't strictly required since a BN_ULONG is unsigned
260 but it's unlikely that anyone would consciously use a full 32-bit e
261 value (well, except for the German RegTP, who do all sorts of other
262 bizarre things as well) so we weed out any attempts to use one here */
263 if( eLen >= bytesToBits( sizeof( int ) ) )
264 return( CRYPT_ARGERROR_STR1 );
265
266 /* Verify that e is a small prime. The easiest way to do this would be
267 to compare it to a set of standard values but there'll always be some
268 wierdo implementation that uses a nonstandard value and that would
269 therefore fail the test so we perform a quick check that just tries
270 dividing by all primes below 1000. In addition since in almost all
271 cases e will be one of a standard set of values we don't bother with
272 the trial division unless it's an unusual value. This test isn't
273 perfect but it'll catch obvious non-primes */
274 if( eWord != 17 && eWord != 257 && eWord != 65537L && !primeSieve( e ) )
275 {
276 /* OpenSSH versions up to 5.4 (released in 2010) hardcoded e = 35,
277 which is both a suboptimal exponent (it's less efficient that a
278 safer value like 257 or F4) and non-prime. The reason for this
279 was that the original SSH used an e relatively prime to
280 (p-1)(q-1), choosing odd (in both senses of the word)
281 numbers > 31. 33 or 35 probably ended up being chosen frequently
282 so it was hardcoded into OpenSSH for cargo-cult reasons, finally
283 being fixed after more than a decade to use F4. In order to use
284 pre-5.4 OpenSSH keys that use this odd value we make a special-
285 case exception for SSH use */
286 #ifdef USE_SSH
287 if( eWord == 33 || eWord == 35 )
288 return( CRYPT_OK );
289 #endif /* USE_SSH */
290
291 return( CRYPT_ARGERROR_STR1 );
292 }
293
294 return( CRYPT_OK );
295 }
296
297 /* Perform validity checks on the private key. We have to make the PKC_INFO
298 data non-const because the bignum code wants to modify some of the values
299 as it's working with them */
300
301 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
checkRSAPrivateKeyComponents(INOUT PKC_INFO * pkcInfo)302 static int checkRSAPrivateKeyComponents( INOUT PKC_INFO *pkcInfo )
303 {
304 BIGNUM *n = &pkcInfo->rsaParam_n, *e = &pkcInfo->rsaParam_e;
305 BIGNUM *d = &pkcInfo->rsaParam_d, *p = &pkcInfo->rsaParam_p;
306 BIGNUM *q = &pkcInfo->rsaParam_q;
307 BIGNUM *p1 = &pkcInfo->tmp1, *q1 = &pkcInfo->tmp2, *tmp = &pkcInfo->tmp3;
308 const BN_ULONG eWord = BN_get_word( e );
309 int bnStatus = BN_STATUS, status;
310
311 assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
312
313 REQUIRES( sanityCheckPKCInfo( pkcInfo ) );
314 REQUIRES( eWord > 0 && eWord < INT_MAX );
315 /* Already checked in checkRSAPublicKeyComponents() */
316
317 /* Verify that p, q aren't (obviously) composite. Note that we can't
318 use primeProbable() because this updates the Montgomery CTX data,
319 it's OK to use it early in the keygen process before everything is
320 set up but not after the pkcInfo is fully initialised so we use
321 primeProbablyFermat() instead */
322 if( !primeSieve( p ) || !primeSieve( q ) )
323 return( CRYPT_ARGERROR_STR1 );
324 status = primeProbableFermat( pkcInfo, p, &pkcInfo->rsaParam_mont_p );
325 if( cryptStatusError( status ) )
326 return( status );
327 if( status != TRUE )
328 return( CRYPT_ARGERROR_STR1 );
329 status = primeProbableFermat( pkcInfo, q, &pkcInfo->rsaParam_mont_q );
330 if( cryptStatusError( status ) )
331 return( status );
332 if( status != TRUE )
333 return( CRYPT_ARGERROR_STR1 );
334
335 /* Verify that |p-q| > 128 bits. We know that p >= q because this is a
336 precondition for the CRT decrypt to work. FIPS 186-3 requires only
337 100 bits, this check is slightly more conservative but in any case
338 both values are somewhat arbitrary and are merely meant to delimit
339 "not too close".
340
341 There's a second more obscure check that we could in theory perform
342 to make sure that p and q don't have the least significant nLen / 4
343 bits the same (which would still lead to |p-q| > 128), this would
344 make the Boneh/Durfee attack marginally less improbable (result by
345 Zhao and Qi). Since the chance of them having 256 LSB bits the same
346 is vanishingly small and the Boneh/Dufree attack requires special
347 properties for d (see the comment in generateRSAkey()) we don't
348 bother with this check */
349 ENSURES( BN_cmp( p, q ) >= 0 );
350 CKPTR( BN_copy( tmp, p ) );
351 CK( BN_sub( tmp, tmp, q ) );
352 if( bnStatusError( bnStatus ) || \
353 BN_num_bits( tmp ) < 128 )
354 return( CRYPT_ARGERROR_STR1 );
355
356 /* Calculate p - 1, q - 1 */
357 CKPTR( BN_copy( p1, p ) );
358 CK( BN_sub_word( p1, 1 ) );
359 CKPTR( BN_copy( q1, q ) );
360 CK( BN_sub_word( q1, 1 ) );
361 if( bnStatusError( bnStatus ) )
362 return( CRYPT_ARGERROR_STR1 );
363
364 /* Verify that n = p * q */
365 CK( BN_mul( tmp, p, q, &pkcInfo->bnCTX ) );
366 if( bnStatusError( bnStatus ) || BN_cmp( n, tmp ) != 0 )
367 return( CRYPT_ARGERROR_STR1 );
368
369 /* Verify that:
370
371 p, q < d
372 ( d * e ) mod p-1 == 1
373 ( d * e ) mod q-1 == 1
374
375 Some implementations don't store d since it's not needed when the CRT
376 shortcut is used so we can only perform this check if d is present */
377 if( !BN_is_zero( d ) )
378 {
379 if( BN_cmp( p, d ) >= 0 || BN_cmp( q, d ) >= 0 )
380 return( CRYPT_ARGERROR_STR1 );
381 CK( BN_mod_mul( tmp, d, e, p1, &pkcInfo->bnCTX ) );
382 if( bnStatusError( bnStatus ) || !BN_is_one( tmp ) )
383 return( CRYPT_ARGERROR_STR1 );
384 CK( BN_mod_mul( tmp, d, e, q1, &pkcInfo->bnCTX ) );
385 if( bnStatusError( bnStatus ) || !BN_is_one( tmp ) )
386 return( CRYPT_ARGERROR_STR1 );
387 }
388
389 #ifdef USE_FIPS140
390 /* Verify that sizeof( d ) > sizeof( p ) / 2, a weird requirement set by
391 FIPS 186-3. This is one of those things where the probability of the
392 check going wrong in some way outweighs the probability of the
393 situation actually occurring by about two dozen orders of magnitude
394 so we only do this when we have to. The fact that this parameter is
395 never even used makes the check even less meaningful.
396
397 (This check possibly has something to do with defending against
398 Wiener's continued-fraction attack, which requires d < n^(1/4) in
399 order to succeed, later extended into the range d < n^(0.29) by
400 Boneh and Durfee/Bloemer and May and d < 1/2 n^(1/2) by Maitra and
401 Sarkar) */
402 if( !BN_is_zero( d ) && BN_num_bits( d ) <= pkcInfo->keySizeBits )
403 return( CRYPT_ARGERROR_STR1 );
404 #endif /* USE_FIPS140 */
405
406 /* Verify that ( q * u ) mod p == 1 */
407 CK( BN_mod_mul( tmp, q, &pkcInfo->rsaParam_u, p, &pkcInfo->bnCTX ) );
408 if( bnStatusError( bnStatus ) || !BN_is_one( tmp ) )
409 return( CRYPT_ARGERROR_STR1 );
410
411 /* Verify that e1 < p, e2 < q */
412 if( BN_cmp( &pkcInfo->rsaParam_exponent1, p ) >= 0 || \
413 BN_cmp( &pkcInfo->rsaParam_exponent2, q ) >= 0 )
414 return( CRYPT_ARGERROR_STR1 );
415
416 /* Verify that u < p, where u was calculated as q^-1 mod p */
417 if( BN_cmp( &pkcInfo->rsaParam_u, p ) >= 0 )
418 return( CRYPT_ARGERROR_STR1 );
419
420 /* A very small number of systems/compilers can't handle 32 * 32 -> 64
421 ops which means that we have to use 16-bit bignum components. For
422 the common case where e = F4 the value won't fit into a 16-bit bignum
423 component so we have to use the full BN_mod() form of the checks that
424 are carried out further on */
425 #ifdef SIXTEEN_BIT
426 CK( BN_mod( tmp, p1, e, &pkcInfo->bnCTX ) );
427 if( bnStatusError( bnStatus ) || BN_is_zero( tmp ) )
428 return( CRYPT_ARGERROR_STR1 );
429 CK( BN_mod( tmp, q1, e, &pkcInfo->bnCTX ) );
430 if( bnStatusError( bnStatus ) || BN_is_zero( tmp ) )
431 return( CRYPT_ARGERROR_STR1 );
432 return( CRYPT_OK );
433 #endif /* Systems without 32 * 32 -> 64 ops */
434
435 /* Verify that gcd( ( p - 1 )( q - 1), e ) == 1
436
437 Since e is a small prime we can do this much more efficiently by
438 checking that:
439
440 ( p - 1 ) mod e != 0
441 ( q - 1 ) mod e != 0 */
442 if( BN_mod_word( p1, eWord ) == 0 || BN_mod_word( q1, eWord ) == 0 )
443 return( CRYPT_ARGERROR_STR1 );
444
445 return( CRYPT_OK );
446 }
447
448 /****************************************************************************
449 * *
450 * Initialise/Check an RSA Key *
451 * *
452 ****************************************************************************/
453
454 /* Generate an RSA key pair into an encryption context. For FIPS 140
455 purposes the keygen method used here complies with FIPS 186-3 Appendix
456 B.3, "IFC Key Pair Generation", specifically method B.3.3, "Generation of
457 Random Primes that are Probably Prime". Note that FIPS 186-3 provides a
458 range of key-generation methods and allows implementations to select one
459 that's appropriate, this implementation provides the one in B.3.3, with
460 the exception that it allows keys in the range MIN_PKC_SIZE ...
461 CRYPT_MAX_PKCSIZE to be generated. FIPS 186-3 is rather confusing in
462 that it discusses conditions and requirements for generating pairs from
463 512 ... 3072 bits and then gives different lengths and restrictions on
464 lengths depending on which portion of text you consult. Because of this
465 confusion, and the fact that telling users that they can't generate the
466 key that they want because of some obscure document that they've never
467 even heard of will cause friction, we leave it as a policy decision to
468 define the appropriate key size to use */
469
470 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
471 int generateRSAkey( INOUT CONTEXT_INFO *contextInfoPtr,
472 IN_LENGTH_SHORT_MIN( MIN_PKCSIZE * 8 ) const int keyBits )
473 {
474 PKC_INFO *pkcInfo = contextInfoPtr->ctxPKC;
475 BIGNUM *d = &pkcInfo->rsaParam_d, *p = &pkcInfo->rsaParam_p;
476 BIGNUM *q = &pkcInfo->rsaParam_q;
477 BIGNUM *tmp = &pkcInfo->tmp1;
478 int pBits, qBits, bnStatus, status;
479
480 assert( isWritePtr( contextInfoPtr, sizeof( CONTEXT_INFO ) ) );
481
482 REQUIRES( sanityCheckPKCInfo( pkcInfo ) );
483 REQUIRES( keyBits >= bytesToBits( MIN_PKCSIZE ) && \
484 keyBits <= bytesToBits( CRYPT_MAX_PKCSIZE ) );
485
486 /* Determine how many bits to give to each of p and q */
487 pBits = ( keyBits + 1 ) / 2;
488 qBits = keyBits - pBits;
489 pkcInfo->keySizeBits = pBits + qBits;
490
491 /* Generate the primes p and q and set them up so that the CRT decrypt
492 will work. FIPS 186-3 requires that they be in the range
493 sqr(2) * 2^(keyBits-1) ... 2^keyBits (so that pq will be exactly
494 keyBits long), but this is guaranteed by the way that generatePrime()
495 selects its prime values so we don't have to check explicitly for it
496 here */
497 bnStatus = BN_set_word( &pkcInfo->rsaParam_e, RSA_PUBLIC_EXPONENT );
498 ENSURES( bnStatusOK( bnStatus ) );
499 status = generatePrime( pkcInfo, p, pBits, RSA_PUBLIC_EXPONENT );
500 if( cryptStatusOK( status ) )
501 status = generatePrime( pkcInfo, q, qBits, RSA_PUBLIC_EXPONENT );
502 if( cryptStatusOK( status ) )
503 status = fixCRTvalues( pkcInfo, FALSE );
504 if( cryptStatusError( status ) )
505 return( status );
506
507 /* Compute d = eInv mod (p - 1)(q - 1) */
508 CK( BN_sub_word( p, 1 ) );
509 CK( BN_sub_word( q, 1 ) );
510 CK( BN_mul( tmp, p, q, &pkcInfo->bnCTX ) );
511 CKPTR( BN_mod_inverse( d, &pkcInfo->rsaParam_e, tmp, &pkcInfo->bnCTX ) );
512 if( bnStatusError( bnStatus ) )
513 return( getBnStatus( bnStatus ) );
514
515 #ifdef USE_FIPS140
516 /* Check that sizeof( d ) > sizeof( p ) / 2, a weird requirement set by
517 FIPS 186-3. This is one of those things where the probability of the
518 check going wrong in some way outweighs the probability of the
519 situation actually occurring by about two dozen orders of magnitude
520 so we only do this when we have to. The fact that this parameter is
521 never even used makes the check even less meaningful.
522
523 (This check possibly has something to do with defending against
524 Wiener's continued-fraction attack, which requires d < n^(1/4) in
525 order to succeed, later extended into the range d < n^(0.29) by
526 Boneh and Durfee/Bloemer and May and d < 1/2 n^(1/2) by Maitra and
527 Sarkar) */
528 if( BN_num_bits( d ) <= pkcInfo->keySizeBits / 2 )
529 return( CRYPT_ERROR_FAILED );
530 #endif /* USE_FIPS140 */
531
532 /* Compute e1 = d mod (p - 1), e2 = d mod (q - 1) */
533 CK( BN_mod( &pkcInfo->rsaParam_exponent1, d,
534 p, &pkcInfo->bnCTX ) );
535 CK( BN_mod( &pkcInfo->rsaParam_exponent2, d, q, &pkcInfo->bnCTX ) );
536 CK( BN_add_word( p, 1 ) );
537 CK( BN_add_word( q, 1 ) );
538 if( bnStatusError( bnStatus ) )
539 return( getBnStatus( bnStatus ) );
540
541 /* Compute n = pq, u = qInv mod p */
542 CK( BN_mul( &pkcInfo->rsaParam_n, p, q, &pkcInfo->bnCTX ) );
543 CKPTR( BN_mod_inverse( &pkcInfo->rsaParam_u, q, p, &pkcInfo->bnCTX ) );
544 if( bnStatusError( bnStatus ) )
545 return( getBnStatus( bnStatus ) );
546
547 /* Since the keygen is randomised it may occur that the final size of
548 the public value that determines its nominal size is slightly smaller
549 than the requested nominal size. To handle this we recalculate the
550 effective key size after we've finished generating the public value
551 that determines its nominal size */
552 pkcInfo->keySizeBits = BN_num_bits( &pkcInfo->rsaParam_n );
553 ENSURES( pkcInfo->keySizeBits >= bytesToBits( MIN_PKCSIZE ) && \
554 pkcInfo->keySizeBits <= bytesToBits( CRYPT_MAX_PKCSIZE ) );
555
556 /* Evaluate the Montgomery forms */
557 status = getRSAMontgomery( pkcInfo, TRUE );
558 if( cryptStatusError( status ) )
559 return( status );
560
561 /* Make sure that the generated values are valid */
562 status = checkRSAPublicKeyComponents( pkcInfo );
563 if( cryptStatusOK( status ) )
564 status = checkRSAPrivateKeyComponents( pkcInfo );
565 if( cryptStatusError( status ) )
566 return( status );
567
568 /* Enable side-channel protection if required */
569 if( contextInfoPtr->flags & CONTEXT_FLAG_SIDECHANNELPROTECTION )
570 {
571 status = enableSidechannelProtection( pkcInfo, TRUE );
572 if( cryptStatusError( status ) )
573 return( status );
574 }
575
576 /* Checksum the bignums to try and detect fault attacks. Since we're
577 setting the checksum at this point there's no need to check the
578 return value */
579 ( void ) checksumContextData( pkcInfo, CRYPT_ALGO_RSA, TRUE );
580
581 ENSURES( sanityCheckPKCInfo( pkcInfo ) );
582
583 return( CRYPT_OK );
584 }
585
586 /* Initialise and check an RSA key */
587
588 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
initCheckRSAkey(INOUT CONTEXT_INFO * contextInfoPtr)589 int initCheckRSAkey( INOUT CONTEXT_INFO *contextInfoPtr )
590 {
591 PKC_INFO *pkcInfo = contextInfoPtr->ctxPKC;
592 BIGNUM *n = &pkcInfo->rsaParam_n, *e = &pkcInfo->rsaParam_e;
593 BIGNUM *d = &pkcInfo->rsaParam_d, *p = &pkcInfo->rsaParam_p;
594 BIGNUM *q = &pkcInfo->rsaParam_q;
595 const BOOLEAN isPrivateKey = \
596 ( contextInfoPtr->flags & CONTEXT_FLAG_ISPUBLICKEY ) ? FALSE : TRUE;
597 int bnStatus = BN_STATUS, status = CRYPT_OK;
598
599 assert( isWritePtr( contextInfoPtr, sizeof( CONTEXT_INFO ) ) );
600
601 REQUIRES( sanityCheckPKCInfo( pkcInfo ) );
602
603 /* Make sure that the necessary key parameters have been initialised */
604 if( BN_is_zero( n ) || BN_is_zero( e ) )
605 return( CRYPT_ARGERROR_STR1 );
606 if( isPrivateKey )
607 {
608 if( BN_is_zero( p ) || BN_is_zero( q ) )
609 return( CRYPT_ARGERROR_STR1 );
610 if( BN_is_zero( d ) && \
611 ( BN_is_zero( &pkcInfo->rsaParam_exponent1 ) || \
612 BN_is_zero( &pkcInfo->rsaParam_exponent2 ) ) )
613 {
614 /* Either d or e1+e2 must be present, d isn't needed if we have
615 e1+e2 and e1+e2 can be reconstructed from d */
616 return( CRYPT_ARGERROR_STR1 );
617 }
618 }
619
620 /* Make sure that the public key parameters are valid */
621 status = checkRSAPublicKeyComponents( pkcInfo );
622 if( cryptStatusError( status ) )
623 return( status );
624
625 /* If it's a public key, we're done */
626 if( !isPrivateKey )
627 {
628 /* Precompute the Montgomery forms of required values */
629 status = getRSAMontgomery( pkcInfo, FALSE );
630 if( cryptStatusError( status ) )
631 return( status );
632 pkcInfo->keySizeBits = BN_num_bits( &pkcInfo->rsaParam_n );
633 ENSURES( pkcInfo->keySizeBits >= bytesToBits( MIN_PKCSIZE ) && \
634 pkcInfo->keySizeBits <= bytesToBits( CRYPT_MAX_PKCSIZE ) );
635
636 /* Enable side-channel protection if required */
637 if( contextInfoPtr->flags & CONTEXT_FLAG_SIDECHANNELPROTECTION )
638 {
639 status = enableSidechannelProtection( pkcInfo, TRUE );
640 if( cryptStatusError( status ) )
641 return( status );
642 }
643
644 /* Checksum the bignums to try and detect fault attacks. Since
645 we're setting the checksum at this point there's no need to check
646 the return value */
647 ( void ) checksumContextData( pkcInfo, CRYPT_ALGO_RSA, FALSE );
648
649 return( CRYPT_OK );
650 }
651
652 /* If we're not using PKCS keys that have exponent1 = d mod ( p - 1 )
653 and exponent2 = d mod ( q - 1 ) precalculated, evaluate them now
654 (this only ever occurs for PGP keys). If there's no u precalculated,
655 evaluate it now (this should never occur with any normal source of
656 keys) */
657 if( BN_is_zero( &pkcInfo->rsaParam_exponent1 ) )
658 {
659 BIGNUM *exponent1 = &pkcInfo->rsaParam_exponent1;
660 BIGNUM *exponent2 = &pkcInfo->rsaParam_exponent2;
661
662 REQUIRES( !BN_is_zero( d ) );
663
664 /* exponent1 = d mod ( p - 1 ) ) */
665 CKPTR( BN_copy( exponent1, p ) );
666 CK( BN_sub_word( exponent1, 1 ) );
667 CK( BN_mod( exponent1, d, exponent1, &pkcInfo->bnCTX ) );
668 if( bnStatusError( bnStatus ) )
669 return( getBnStatus( bnStatus ) );
670
671 /* exponent2 = d mod ( q - 1 ) ) */
672 CKPTR( BN_copy( exponent2, q ) );
673 CK( BN_sub_word( exponent2, 1 ) );
674 CK( BN_mod( exponent2, d, exponent2, &pkcInfo->bnCTX ) );
675 if( bnStatusError( bnStatus ) )
676 return( getBnStatus( bnStatus ) );
677 }
678 if( BN_is_zero( &pkcInfo->rsaParam_u ) )
679 {
680 CKPTR( BN_mod_inverse( &pkcInfo->rsaParam_u, q, p,
681 &pkcInfo->bnCTX ) );
682 if( bnStatusError( bnStatus ) )
683 return( getBnStatus( bnStatus ) );
684 }
685
686 /* Make sure that p and q are set up correctly for the CRT decryption */
687 status = fixCRTvalues( pkcInfo, TRUE );
688 if( cryptStatusError( status ) )
689 return( status );
690
691 /* Precompute the Montgomery forms of required values */
692 status = getRSAMontgomery( pkcInfo, TRUE );
693 if( cryptStatusError( status ) )
694 return( status );
695 pkcInfo->keySizeBits = BN_num_bits( &pkcInfo->rsaParam_n );
696 ENSURES( pkcInfo->keySizeBits >= bytesToBits( MIN_PKCSIZE ) && \
697 pkcInfo->keySizeBits <= bytesToBits( CRYPT_MAX_PKCSIZE ) );
698
699 /* We've got the remaining components set up, perform further validity
700 checks on the private key */
701 status = checkRSAPrivateKeyComponents( pkcInfo );
702 if( cryptStatusError( status ) )
703 return( status );
704
705 /* Enable side-channel protection if required */
706 if( contextInfoPtr->flags & CONTEXT_FLAG_SIDECHANNELPROTECTION )
707 {
708 status = enableSidechannelProtection( pkcInfo, TRUE );
709 if( cryptStatusError( status ) )
710 return( status );
711 }
712
713 /* Checksum the bignums to try and detect fault attacks. Since we're
714 setting the checksum at this point there's no need to check the
715 return value */
716 ( void ) checksumContextData( pkcInfo, CRYPT_ALGO_RSA, TRUE );
717
718 ENSURES( sanityCheckPKCInfo( pkcInfo ) );
719
720 return( CRYPT_OK );
721 }
722