cryptlib  3.4.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Macros
kg_prime.c
Go to the documentation of this file.
1 /****************************************************************************
2 * *
3 * cryptlib Prime Generation/Checking Routines *
4 * Copyright Peter Gutmann 1997-2009 *
5 * *
6 ****************************************************************************/
7 
8 /* The Usenet Oracle has pondered your question deeply.
9  Your question was:
10 
11  > O Oracle Most Wise,
12  >
13  > What is the largest prime number?
14 
15  And in response, thus spake the Oracle:
16 
17  } This is a question which has stumped some of the best minds in
18  } mathematics, but I will explain it so that even you can understand it.
19  } The first prime is 2, and the binary representation of 2 is 10.
20  } Consider the following series:
21  }
22  } Prime Decimal Representation Representation in its own base
23  } 1st 2 10
24  } 2nd 3 10
25  } 3rd 5 10
26  } 4th 7 10
27  } 5th 11 10
28  } 6th 13 10
29  } 7th 17 10
30  }
31  } From this demonstration you can see that there is only one prime, and
32  } it is ten. Therefore, the largest prime is ten.
33  -- The Usenet Oracle */
34 
35 #define PKC_CONTEXT /* Indicate that we're working with PKC contexts */
36 #if defined( INC_ALL )
37  #include "crypt.h"
38  #include "context.h"
39  #include "keygen.h"
40 #else
41  #include "crypt.h"
42  #include "context/context.h"
43  #include "context/keygen.h"
44 #endif /* Compiler-specific includes */
45 
46 /****************************************************************************
47 * *
48 * Fast Prime Sieve *
49 * *
50 ****************************************************************************/
51 
52 /* #include 4k of EAY copyright */
53 
54 /* The following define is necessary in memory-starved environments. It
55  controls the size of the table used for the sieving */
56 
57 #if defined( CONFIG_CONSERVE_MEMORY )
58  #define EIGHT_BIT
59 #endif /* CONFIG_CONSERVE_MEMORY */
60 
61 /* Pull in the table of primes */
62 
63 #if defined( INC_ALL )
64  #include "bn_prime.h"
65 #else
66  #include "bn/bn_prime.h"
67 #endif /* Compiler-specific includes */
68 
69 /* The number of primes in the sieve (and their values) that result in a
70  given number of candidates remaining from 40,000. Even the first 100
71  primes weed out 91% of all the candidates, and after 500 you're only
72  removing a handful for each 100 extra primes.
73 
74  Number Prime Candidates left
75  Values from 40,000
76  -------- --------- ---------------
77  0- 99 0- 541 3564
78  100-199 541-1223 3175
79  200-299 1223-1987 2969
80  300-399 1987-2741 2845
81  400-499 2741-3571 2755
82  500-599 3571-4409 2688
83  600-699 4409-5279 2629
84  700-799 5279-6133 2593
85  800-899 6133-6997 2555
86  900-999 6997-7919 2521
87 
88  There is in fact an even faster prime tester due to Dan Piponi that uses
89  C++ templates as a universal computer and performs the primality test at
90  compile time, however this requires the use of a fairly advanced C++
91  compiler and isn't amenable to generating different primes */
92 
93 /* Enable the following to cross-check the Miller-Rabin test using a Fermat
94  test and an alternative form of the Miller-Rabin test that merges the
95  test loop and the modexp at the start. Note that this displays
96  diagnostic timing output and expects to use Pentium performance counters
97  for timing so it's only (optionally) enabled for Win32 debug */
98 
99 #if defined( __WIN32__ ) && !defined( NDEBUG ) && 0
100  #define CHECK_PRIMETEST
101 #endif /* Win32 debug */
102 
103 /* The size of the sieve array, 1 memory page (on most CPUs) = 4K candidate
104  values. When changing this value the LFSR parameters need to be adjusted
105  to match */
106 
107 #define SIEVE_SIZE 4096
108 
109 /* When we're doing a sieve of a singleton candidate we don't run through
110  the whole range of sieve values since we run into the law of diminishing
111  returns after a certain point. The following value sieves with every
112  prime under 1000 */
113 
114 #if NUMPRIMES < ( 21 * 8 )
115  #define FAST_SIEVE_NUMPRIMES NUMPRIMES
116 #else
117  #define FAST_SIEVE_NUMPRIMES ( 21 * 8 )
118 #endif /* Small prime table */
119 
120 /* Set up the sieve array for the number. Every position that contains
121  a zero is non-divisible by all of the small primes */
122 
123 STDC_NONNULL_ARG( ( 1, 3 ) ) \
124 static void initSieve( IN_ARRAY( sieveSize ) BOOLEAN *sieveArray,
125  IN_LENGTH_FIXED( SIEVE_SIZE ) const int sieveSize,
126  const BIGNUM *candidate )
127  {
128  int i;
129 
130  assert( isWritePtr( sieveArray, sieveSize * sizeof( BOOLEAN ) ) );
131  assert( isReadPtr( candidate, sizeof( BIGNUM ) ) );
132 
133  REQUIRES_V( sieveSize == SIEVE_SIZE );
134 
135  memset( sieveArray, 0, sieveSize * sizeof( BOOLEAN ) );
136 
137  /* Walk down the list of primes marking the appropriate position in the
138  array as divisible by the prime. We start at index 1 because the
139  candidate will never be divisible by 2 (== primes[ 0 ]) */
140  for( i = 1; i < NUMPRIMES; i++ )
141  {
142  unsigned int step = primes[ i ];
143  BN_ULONG sieveIndex = BN_mod_word( candidate, step );
144 
145  /* Determine the correct start index for this value */
146  if( sieveIndex & 1 )
147  sieveIndex = ( step - sieveIndex ) / 2;
148  else
149  {
150  if( sieveIndex > 0 )
151  sieveIndex = ( ( step * 2 ) - sieveIndex ) / 2;
152  }
153 
154  /* Mark each multiple of the divisor as being divisible */
155  while( sieveIndex >= 0 && sieveIndex < sieveSize )
156  {
157  sieveArray[ sieveIndex ] = 1;
158  sieveIndex += step;
159  }
160  }
161  }
162 
163 /* An LFSR to step through each entry in the sieve array. This isn't a true
164  pseudorandom selection since all that it's really doing is going through
165  the numbers in a linear order with a different starting point, but it's
166  good enough as a randomiser */
167 
168 #define LFSR_POLYNOMIAL 0x1053
169 #define LFSR_MASK 0x1000
170 
171 CHECK_RETVAL \
172 static int nextEntry( IN_INT_SHORT int value )
173  {
174  static_assert( LFSR_MASK == SIEVE_SIZE, "LFSR size" );
175 
176  REQUIRES( value > 0 && value < SIEVE_SIZE );
177 
178  /* Get the next value: Multiply by x and reduce by the polynomial */
179  value <<= 1;
180  if( value & LFSR_MASK )
181  value ^= LFSR_POLYNOMIAL;
182  return( value );
183  }
184 
185 /* A one-off sieve check for when we're testing a singleton rather than
186  running over a range of values */
187 
188 CHECK_RETVAL_BOOL STDC_NONNULL_ARG( ( 1 ) ) \
189 BOOLEAN primeSieve( const BIGNUM *candidate )
190  {
191  int i;
192 
193  assert( isReadPtr( candidate, sizeof( BIGNUM ) ) );
194 
195  /* If we're checking a small value then we can use a direct machine
196  instruction for the check, this is both faster and avoids false
197  positives when the value being checked is small enough to be
198  present in the sieve */
199  if( BN_num_bytes( candidate ) < sizeof( int ) - 1 )
200  {
201  const BN_ULONG candidateWord = BN_get_word( candidate );
202 
203  for( i = 1; i < FAST_SIEVE_NUMPRIMES && \
204  primes[ i ] < candidateWord; i++ )
205  {
206  if( candidateWord % primes[ i ] == 0 )
207  return( FALSE );
208  }
209 
210  return( TRUE );
211  }
212 
213  for( i = 1; i < FAST_SIEVE_NUMPRIMES; i++ )
214  {
215  if( BN_mod_word( candidate, primes[ i ] ) == 0 )
216  return( FALSE );
217  }
218 
219  return( TRUE );
220  }
221 
222 /****************************************************************************
223 * *
224 * Generate a Prime Number *
225 * *
226 ****************************************************************************/
227 
228 #ifdef CHECK_PRIMETEST
229 
230 /* Witness function, modified from original BN code as found at a UFO crash
231  site. This looks nothing like a standard Miller-Rabin test because it
232  merges the modexp that usually needs to be performed as the first
233  portion of the test process and the remainder of the checking. Destroys
234  param6 + 7 */
235 
236 CHECK_RETVAL STDC_NONNULL_ARG( ( 1, 2, 3, 4, 5, 6, 7 ) ) \
237 static int witnessOld( INOUT PKC_INFO *pkcInfo, INOUT BIGNUM *a,
238  INOUT BIGNUM *n, INOUT BIGNUM *n1,
239  INOUT BIGNUM *mont_n1, INOUT BIGNUM *mont_1,
240  INOUT BN_MONT_CTX *montCTX_n )
241  {
242  BIGNUM *y = &pkcInfo->param6;
243  BIGNUM *yPrime = &pkcInfo->param7; /* Safe to destroy */
244  BN_CTX *ctx = pkcInfo->bnCTX;
245  BIGNUM *mont_a = &ctx->bn[ ctx->tos++ ];
246  const int k = BN_num_bits( n1 );
247  int i, bnStatus = BN_STATUS;
248 
249  assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
250  assert( isWritePtr( a, sizeof( BIGNUM ) ) );
251  assert( isWritePtr( n, sizeof( BIGNUM ) ) );
252  assert( isWritePtr( n1, sizeof( BIGNUM ) ) );
253  assert( isWritePtr( mont_n1, sizeof( BIGNUM ) ) );
254  assert( isWritePtr( mont_1, sizeof( BIGNUM ) ) );
255  assert( isWritePtr( montCTX_n, sizeof( BN_MONT_CTX ) ) );
256 
257  /* All values are manipulated in their Montgomery form so before we
258  begin we have to convert a to this form as well */
259  if( !BN_to_montgomery( mont_a, a, montCTX_n, pkcInfo->bnCTX ) )
260  {
261  ctx->tos--;
262  return( CRYPT_ERROR_FAILED );
263  }
264 
265  CKPTR( BN_copy( y, mont_1 ) );
266  for ( i = k - 1; i >= 0; i-- )
267  {
268  /* Perform the y^2 mod n check. yPrime = y^2 mod n, if yPrime == 1
269  it's composite (this condition is virtually never met) */
270  CK( BN_mod_mul_montgomery( yPrime, y, y, montCTX_n,
271  pkcInfo->bnCTX ) );
272  if( bnStatusError( bnStatus ) || \
273  ( !BN_cmp( yPrime, mont_1 ) && \
274  BN_cmp( y, mont_1 ) && BN_cmp( y, mont_n1 ) ) )
275  {
276  ctx->tos--;
277  return( TRUE );
278  }
279 
280  /* Perform another step of the modexp */
281  if( BN_is_bit_set( n1, i ) )
282  {
283  CK( BN_mod_mul_montgomery( y, yPrime, mont_a, montCTX_n,
284  pkcInfo->bnCTX ) );
285  }
286  else
287  {
288  BIGNUM *tmp;
289 
290  /* Input and output to modmult can't be the same, so we have to
291  swap the pointers */
292  tmp = y; y = yPrime; yPrime = tmp;
293  }
294  }
295  ctx->tos--;
296 
297  /* Finally we have y = a^u mod n. If y == 1 (mod n) it's prime,
298  otherwise it's composite */
299  return( BN_cmp( y, mont_1 ) ? TRUE : FALSE );
300  }
301 
302 /* Perform noChecks iterations of the Miller-Rabin probabilistic primality
303  test. Destroys param8, tmp1-3, mont1 */
304 
305 CHECK_RETVAL STDC_NONNULL_ARG( ( 1, 2 ) ) \
306 static int primeProbableOld( INOUT PKC_INFO *pkcInfo,
307  INOUT BIGNUM *candidate,
308  IN_RANGE( 1, 100 ) const int noChecks )
309  {
310  BIGNUM *check = &pkcInfo->tmp1;
311  BIGNUM *candidate_1 = &pkcInfo->tmp2;
312  BIGNUM *mont_candidate_1 = &pkcInfo->tmp3;
313  BIGNUM *mont_1 = &pkcInfo->param8; /* Safe to destroy */
314  BN_MONT_CTX *montCTX_candidate = &pkcInfo->montCTX1;
315  int i, bnStatus = BN_STATUS, status;
316 
317  assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
318  assert( isWritePtr( candidate, sizeof( BIGNUM ) ) );
319 
320  REQUIRES( noChecks >= 1 && noChecks <= 100 );
321 
322  /* Set up various values */
323  CK( BN_MONT_CTX_set( montCTX_candidate, candidate, pkcInfo->bnCTX ) );
324  if( bnStatusError( bnStatus ) )
325  return( getBnStatus( bnStatus ) );
326  CK( BN_to_montgomery( mont_1, BN_value_one(), montCTX_candidate,
327  pkcInfo->bnCTX ) );
328  CKPTR( BN_copy( candidate_1, candidate ) );
329  CK( BN_sub_word( candidate_1, 1 ) );
330  CK( BN_to_montgomery( mont_candidate_1, candidate_1, montCTX_candidate,
331  pkcInfo->bnCTX ) );
332  if( bnStatusError( bnStatus ) )
333  return( getBnStatus( bnStatus ) );
334 
335  /* Perform n iterations of Miller-Rabin */
336  for( i = 0; i < noChecks; i++ )
337  {
338  /* Instead of using a bignum for the Miller-Rabin check we use a
339  series of small primes. The reason for this is that if bases a1
340  and a2 are strong liars for n then their product a1*a2 is also
341  very likely to be a strong liar so using a composite base
342  doesn't give us any great advantage. In addition an initial test
343  with a=2 is beneficial since most composite numbers will fail
344  Miller-Rabin with a=2, and exponentiation with base 2 is faster
345  than general-purpose exponentiation. Finally, using small values
346  instead of random bignums is both significantly more efficient
347  and much easier on the RNG. In theory in order to use the first
348  noChecks small primes as the base instead of using random bignum
349  bases we would have to assume that the extended Riemann
350  hypothesis holds (without this, which allows us to use values
351  1 < check < 2 * log( candidate )^2, we'd have to pick random
352  check values as required for Monte Carlo algorithms), however the
353  requirement for random bases assumes that the candidates could be
354  chosen maliciously to be pseudoprime to any reasonable list of
355  bases, thus requiring random bases to evade the problem.
356  Obviously we're not going to do this so one base is as good as
357  another, and small primes work well (even a single Fermat test
358  has a failure probability of around 10e-44 for 512-bit primes if
359  you're not trying to cook the primes, this is why Fermat works as
360  a verification of the Miller-Rabin test in generatePrime()) */
361  BN_set_word( check, primes[ i ] );
362  status = witnessOld( pkcInfo, check, candidate, candidate_1,
363  mont_candidate_1, mont_1, montCTX_candidate );
364  if( cryptStatusError( status ) )
365  return( status );
366  if( status )
367  return( FALSE ); /* It's not a prime */
368  }
369 
370  /* It's prime */
371  return( TRUE );
372  }
373 #endif /* CHECK_PRIMETEST */
374 
375 /* Less unconventional witness function, which follows the normal pattern:
376 
377  x(0) = a^u mod n
378  if x(0) = 1 || x(0) = n - 1
379  return "probably-prime"
380 
381  for i = 1 to k
382  x(i) = x(i-1)^2 mod n
383  if x(i) = n - 1
384  return "probably-prime"
385  if x(i) = 1
386  return "composite";
387  return "composite"
388 
389  Since it's a yes-biased Monte Carlo algorithm this witness function can
390  only answer "probably-prime" so we reduce the uncertainty by iterating
391  for the Miller-Rabin test */
392 
393 CHECK_RETVAL STDC_NONNULL_ARG( ( 1, 2, 3, 4, 5, 7 ) ) \
394 static int witness( INOUT PKC_INFO *pkcInfo, INOUT BIGNUM *a,
395  const BIGNUM *n, const BIGNUM *n_1, const BIGNUM *u,
396  IN_LENGTH_SHORT const int k,
397  INOUT BN_MONT_CTX *montCTX_n )
398  {
399  int i, bnStatus = BN_STATUS;
400 
401  assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
402  assert( isWritePtr( a, sizeof( BIGNUM ) ) );
403  assert( isReadPtr( n, sizeof( BIGNUM ) ) );
404  assert( isReadPtr( n_1, sizeof( BIGNUM ) ) );
405  assert( isReadPtr( u, sizeof( BIGNUM ) ) );
406  assert( isReadPtr( montCTX_n, sizeof( BN_MONT_CTX ) ) );
407 
408  REQUIRES( k >= 1 && k <= bytesToBits( CRYPT_MAX_PKCSIZE ) );
409 
410  /* x(0) = a^u mod n. If x(0) == 1 || x(0) == n - 1 it's probably
411  prime */
412  CK( BN_mod_exp_mont( a, a, u, n, pkcInfo->bnCTX, montCTX_n ) );
413  if( bnStatusError( bnStatus ) )
414  return( getBnStatus( bnStatus ) );
415  if( BN_is_one( a ) || !BN_cmp( a, n_1 ) )
416  return( FALSE ); /* Probably prime */
417 
418  for( i = 1; i < k; i++ )
419  {
420  /* x(i) = x(i-1)^2 mod n */
421  CK( BN_mod_mul( a, a, a, n, pkcInfo->bnCTX ) );
422  if( bnStatusError( bnStatus ) )
423  return( getBnStatus( bnStatus ) );
424  if( !BN_cmp( a, n_1 ) )
425  return( FALSE ); /* Probably prime */
426  if( BN_is_one( a ) )
427  return( TRUE ); /* Composite */
428  }
429 
430  return( TRUE );
431  }
432 
433 /* Perform noChecks iterations of the Miller-Rabin probabilistic primality
434  test (n = candidate prime, a = randomly-chosen check value):
435 
436  evaluate u s.t. n - 1 = 2^k * u, u odd
437 
438  for i = 1 to noChecks
439  if witness( a, n, n-1, u, k )
440  return "composite"
441 
442  return "prime"
443 
444  Destroys tmp1-3, mont1 */
445 
446 CHECK_RETVAL STDC_NONNULL_ARG( ( 1, 2 ) ) \
447 int primeProbable( INOUT PKC_INFO *pkcInfo,
448  INOUT BIGNUM *n,
449  IN_RANGE( 1, 100 ) const int noChecks )
450  {
451  BIGNUM *a = &pkcInfo->tmp1, *n_1 = &pkcInfo->tmp2, *u = &pkcInfo->tmp3;
452  int i, k, iterationCount, bnStatus = BN_STATUS, status;
453 
454  assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
455  assert( isWritePtr( n, sizeof( BIGNUM ) ) );
456 
457  REQUIRES( noChecks >= 1 && noChecks <= 100 );
458 
459  /* Set up various values */
460  CK( BN_MONT_CTX_set( &pkcInfo->montCTX1, n, pkcInfo->bnCTX ) );
461  if( bnStatusError( bnStatus ) )
462  return( getBnStatus( bnStatus ) );
463 
464  /* Evaluate u as n - 1 = 2^k * u. Obviously the less one bits in the
465  LSBs of n the more efficient this test becomes, however with a
466  randomly-chosen n value we get an exponentially-decreasing chance
467  of losing any bits after the first one, which will always be zero
468  since n starts out being odd */
469  CKPTR( BN_copy( n_1, n ) );
470  CK( BN_sub_word( n_1, 1 ) );
471  if( bnStatusError( bnStatus ) )
472  return( getBnStatus( bnStatus ) );
473  for( k = 1, iterationCount = 0;
474  !BN_is_bit_set( n_1, k ) && \
475  iterationCount < FAILSAFE_ITERATIONS_MAX;
476  k++, iterationCount++ );
477  ENSURES( iterationCount < FAILSAFE_ITERATIONS_MAX );
478  CK( BN_rshift( u, n_1, k ) );
479  if( bnStatusError( bnStatus ) )
480  return( getBnStatus( bnStatus ) );
481 
482  /* Perform n iterations of Miller-Rabin */
483  for( i = 0; i < noChecks; i++ )
484  {
485  /* Instead of using a bignum for the Miller-Rabin check we use a
486  series of small primes. The reason for this is that if bases a1
487  and a2 are strong liars for n then their product a1*a2 is also
488  very likely to be a strong liar so using a composite base
489  doesn't give us any great advantage. In addition an initial test
490  with a=2 is beneficial since most composite numbers will fail
491  Miller-Rabin with a=2, and exponentiation with base 2 is faster
492  than general-purpose exponentiation. Finally, using small values
493  instead of random bignums is both significantly more efficient
494  and much easier on the RNG. In theory in order to use the first
495  noChecks small primes as the base instead of using random bignum
496  bases we would have to assume that the extended Riemann
497  hypothesis holds (without this, which allows us to use values
498  1 < check < 2 * log( candidate )^2, we'd have to pick random
499  check values as required for Monte Carlo algorithms), however the
500  requirement for random bases assumes that the candidates could be
501  chosen maliciously to be pseudoprime to any reasonable list of
502  bases, thus requiring random bases to evade the problem.
503  Obviously we're not going to do this so one base is as good as
504  another, and small primes work well (even a single Fermat test
505  has a failure probability of around 10e-44 for 512-bit primes if
506  you're not trying to cook the primes, this is why Fermat works as
507  a verification of the Miller-Rabin test in generatePrime()) */
508  CK( BN_set_word( a, primes[ i ] ) );
509  if( bnStatusError( bnStatus ) )
510  return( getBnStatus( bnStatus ) );
511  status = witness( pkcInfo, a, n, n_1, u, k, &pkcInfo->montCTX1 );
512  if( cryptStatusError( status ) )
513  return( status );
514  if( status )
515  return( FALSE ); /* It's not a prime */
516  }
517 
518  /* It's prime */
519  return( TRUE );
520  }
521 
522 /* Generate a prime. If the exponent is present this will also verify that
523  gcd( (p - 1)(q - 1), exponent ) = 1, which is required for RSA */
524 
525 CHECK_RETVAL STDC_NONNULL_ARG( ( 1, 2 ) ) \
526 int generatePrime( INOUT PKC_INFO *pkcInfo,
527  INOUT BIGNUM *candidate,
528  IN_LENGTH_SHORT_MIN( 120 ) const int noBits,
529  IN_INT_OPT const long exponent )
530  {
531  MESSAGE_DATA msgData;
532  const int noChecks = getNoPrimeChecks( noBits );
533  BOOLEAN *sieveArray, primeFound = FALSE;
534  int offset, oldOffset = 0, startPoint, iterationCount;
535  int bnStatus = BN_STATUS, status;
536 
537  assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
538  assert( isWritePtr( candidate, sizeof( BIGNUM ) ) );
539 
540  REQUIRES( noBits >= 120 && noBits <= bytesToBits( CRYPT_MAX_PKCSIZE ) );
541  /* The value of 120 doesn't correspond to any key size but is
542  the minimal value for a prime that we'd generate using the
543  Lim-Lee algorithm */
544  REQUIRES( exponent == CRYPT_UNUSED || \
545  ( exponent >= 17 && exponent < INT_MAX - 1000 ) );
546 
547  /* Start with a cryptographically strong odd random number ("There is a
548  divinity in odd numbers", William Shakespeare, "Merry Wives of
549  Windsor"). We set the two high bits so that (when generating RSA
550  keys) pq will end up exactly 2n bits long */
551  status = generateBignum( candidate, noBits, 0xC0, 0x1 );
552  if( cryptStatusError( status ) )
553  return( status );
554 
555  /* Allocate the array */
556  if( ( sieveArray = clAlloc( "generatePrime", \
557  SIEVE_SIZE * sizeof( BOOLEAN ) ) ) == NULL )
558  return( CRYPT_ERROR_MEMORY );
559 
560  for( iterationCount = 0;
561  !primeFound && iterationCount < FAILSAFE_ITERATIONS_MAX;
562  iterationCount++ )
563  {
564  int innerIterationCount;
565 
566  /* Set up the sieve array for the number and pick a random starting
567  point */
568  initSieve( sieveArray, SIEVE_SIZE, candidate );
569  setMessageData( &msgData, &startPoint, sizeof( int ) );
570  status = krnlSendMessage( SYSTEM_OBJECT_HANDLE,
571  IMESSAGE_GETATTRIBUTE_S, &msgData,
572  CRYPT_IATTRIBUTE_RANDOM );
573  if( cryptStatusError( status ) )
574  break;
575  startPoint &= SIEVE_SIZE - 1;
576  if( startPoint <= 0 )
577  startPoint = 1; /* Avoid getting stuck on zero */
578 
579  /* Perform a random-probing search for a prime (poli, poli, di
580  umbuendo). "On generation of probably primes by incremental
581  search" by J�rgen Brandt and Ivan Damg�rd, Proceedings of
582  Crypto'92, (LNCS Vol.740), p.358, shows that for an n-bit
583  number we'll find a prime after O( n ) steps by incrementing
584  the start value by 2 each time */
585  for( offset = nextEntry( startPoint ), innerIterationCount = 0; \
586  offset != startPoint && innerIterationCount < SIEVE_SIZE + 1; \
587  offset = nextEntry( offset ), innerIterationCount++ )
588  {
589 #ifdef CHECK_PRIMETEST
590  LARGE_INTEGER tStart, tStop;
591  BOOLEAN passedFermat, passedOldPrimeTest;
592  int oldTicks, newTicks, ratio;
593 #endif /* CHECK_PRIMETEST */
594  long remainder;
595 
596  ENSURES( offset > 0 && offset < SIEVE_SIZE );
597  ENSURES( offset != oldOffset );
598 
599  /* If this candidate is divisible by anything, continue */
600  if( sieveArray[ offset ] != 0 )
601  continue;
602 
603  /* Adjust the candidate by the number of nonprimes that we've
604  skipped */
605  if( offset > oldOffset )
606  CK( BN_add_word( candidate, ( offset - oldOffset ) * 2 ) );
607  else
608  CK( BN_sub_word( candidate, ( oldOffset - offset ) * 2 ) );
609  oldOffset = offset;
610  if( bnStatusError( bnStatus ) )
611  {
612  status = getBnStatus( bnStatus );
613  break;
614  }
615 
616 #if defined( CHECK_PRIMETEST )
617  /* Perform a Fermat test to the base 2 (Fermat = a^p-1 mod p == 1
618  -> a^p mod p == a, for all a), which isn't as reliable as
619  Miller-Rabin but may be quicker if a fast base 2 modexp is
620  available (currently it provides no improvement at all over
621  the use of straight Miller-Rabin). At the moment it's only
622  used to sanity-check the MR test but if a faster version is
623  ever made available it can be used as a filter to weed out
624  most pseudoprimes */
625  CK( BN_MONT_CTX_set( &pkcInfo->montCTX1, candidate,
626  pkcInfo->bnCTX ) );
627  CK( BN_set_word( &pkcInfo->tmp1, 2 ) );
628  CK( BN_mod_exp_mont( &pkcInfo->tmp2, &pkcInfo->tmp1, candidate,
629  candidate, pkcInfo->bnCTX,
630  &pkcInfo->montCTX1 ) );
631  passedFermat = ( bnStatusOK( bnStatus ) && \
632  BN_is_word( &pkcInfo->tmp2, 2 ) ) ? TRUE : FALSE;
633 
634  /* Perform the older probabalistic test */
635  QueryPerformanceCounter( &tStart );
636  status = primeProbableOld( pkcInfo, candidate, noChecks );
637  QueryPerformanceCounter( &tStop );
638  assert( tStart.HighPart == tStop.HighPart );
639  oldTicks = tStop.LowPart - tStart.LowPart;
640  if( cryptStatusError( status ) )
641  break;
642  passedOldPrimeTest = status;
643 
644  /* Perform the probabalistic test */
645  QueryPerformanceCounter( &tStart );
646  status = primeProbable( pkcInfo, candidate, noChecks );
647  QueryPerformanceCounter( &tStop );
648  assert( tStart.HighPart == tStop.HighPart );
649  newTicks = tStop.LowPart - tStart.LowPart;
650  ratio = ( oldTicks * 100 ) / newTicks;
651  printf( "%4d bits, old MR = %6d ticks, new MR = %6d ticks, "
652  "ratio = %d.%d\n", noBits, oldTicks, newTicks,
653  ratio / 100, ratio % 100 );
654  if( status != passedFermat || status != passedOldPrimeTest )
655  {
656  printf( "Fermat reports %d, old Miller-Rabin reports %d, "
657  "new Miller-Rabin reports %d.\n",
658  passedFermat, passedOldPrimeTest, status );
659  getchar();
660  }
661 #else
662  status = primeProbable( pkcInfo, candidate, noChecks );
663 #endif /* CHECK_PRIMETEST */
664  if( cryptStatusError( status ) )
665  break;
666  if( status == FALSE )
667  continue; /* It's not a prime */
668 
669  ENSURES( status == TRUE ); /* It's prime */
670 
671  /* If it's not for RSA use, we've found our candidate */
672  if( exponent == CRYPT_UNUSED )
673  {
674  /* status == TRUE from above */
675  primeFound = TRUE;
676  break;
677  }
678 
679  /* It's for use with RSA, check the RSA condition that
680  gcd( p - 1, exp ) == 1. Since exp is a small prime we can do
681  this efficiently by checking that ( p - 1 ) mod exp != 0 */
682  CK( BN_sub_word( candidate, 1 ) );
683  remainder = BN_mod_word( candidate, exponent );
684  CK( BN_add_word( candidate, 1 ) );
685  if( bnStatusError( bnStatus ) )
686  {
687  status = getBnStatus( bnStatus );
688  break;
689  }
690  if( remainder > 0 )
691  {
692  /* status == TRUE from above */
693  primeFound = TRUE;
694  break;
695  }
696  }
697  ENSURES( innerIterationCount < SIEVE_SIZE + 1 );
698  }
699  ENSURES( iterationCount < FAILSAFE_ITERATIONS_MAX );
700  ENSURES( cryptStatusError( status ) || primeFound );
701 
702  /* Clean up */
703  zeroise( sieveArray, SIEVE_SIZE * sizeof( BOOLEAN ) );
704  clFree( "generatePrime", sieveArray );
705  return( cryptStatusError( status ) ? status : CRYPT_OK );
706  }
707 
708 /****************************************************************************
709 * *
710 * Generate a Random Bignum *
711 * *
712 ****************************************************************************/
713 
714 /* Generate a bignum of a specified length with the given high and low 8
715  bits. 'high' is merged into the high 8 bits of the number (set it to 0x80
716  to ensure that the number is exactly 'bits' bits long, i.e. 2^(bits-1) <=
717  bn < 2^bits), 'low' is merged into the low 8 bits (set it to 1 to ensure
718  that the number is odd). In almost all cases used in cryptlib, 'high' is
719  set to 0xC0 and low is set to 0x01.
720 
721  We don't need to pagelock the bignum buffer that we're using because it's
722  being accessed continuously while there's data in it so there's little
723  chance that it'll be swapped unless the system is already thrashing */
724 
725 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
726 int generateBignum( OUT BIGNUM *bn,
727  IN_LENGTH_SHORT_MIN( 120 ) const int noBits,
728  IN_BYTE const int high, IN_BYTE const int low )
729  {
730  MESSAGE_DATA msgData;
731  BYTE buffer[ CRYPT_MAX_PKCSIZE + DLP_OVERFLOW_SIZE + 8 ];
732  int noBytes = bitsToBytes( noBits ), status;
733 
734  assert( isWritePtr( bn, sizeof( BIGNUM ) ) );
735 
736  REQUIRES( noBits >= 120 && \
737  noBits <= bytesToBits( CRYPT_MAX_PKCSIZE + DLP_OVERFLOW_SIZE ) );
738  /* The value of 120 doesn't correspond to any key size but is
739  the minimal value for a prime that we'd generate using the
740  Lim-Lee algorithm. The extra 32 bits added to
741  CRYPT_MAX_PKCSIZE are for DLP algorithms where we reduce
742  the bignum mod p or q and use a few extra bits to avoid the
743  resulting value being biased, see the DLP code for
744  details */
745  REQUIRES( high > 0 && high <= 0xFF );
746  REQUIRES( low >= 0 && low <= 0xFF );
747  /* The lower bound may be zero if we're generating e.g. a
748  blinding value or some similar non-key-data value */
749 
750  /* Clear the return value */
751  BN_zero( bn );
752 
753  /* Load the random data into the bignum buffer */
754  setMessageData( &msgData, buffer, noBytes );
755  status = krnlSendMessage( SYSTEM_OBJECT_HANDLE, IMESSAGE_GETATTRIBUTE_S,
756  &msgData, CRYPT_IATTRIBUTE_RANDOM );
757  if( cryptStatusError( status ) )
758  {
759  zeroise( buffer, noBytes );
760  return( status );
761  }
762 
763  /* Merge in the specified low bits, mask off any excess high bits, and
764  merge in the specified high bits. This is a bit more complex than
765  just masking in the byte values because the bignum may not be a
766  multiple of 8 bytes long */
767  buffer[ noBytes - 1 ] |= low;
768  buffer[ 0 ] &= 0xFF >> ( -noBits & 7 );
769  buffer[ 0 ] |= high >> ( -noBits & 7 );
770  if( noBits & 7 )
771  buffer[ 1 ] |= ( high << ( noBits & 7 ) ) & 0xFF;
772 
773  /* Turn the contents of the buffer into a bignum */
774  if( noBytes > CRYPT_MAX_PKCSIZE )
775  {
776  /* We've created an oversize bignum for use in a DLP algorithm, the
777  upper bound is somewhat larger than CRYPT_MAX_PKCSIZE */
778  status = importBignum( bn, buffer, noBytes, max( noBytes - 8, 1 ),
779  CRYPT_MAX_PKCSIZE + DLP_OVERFLOW_SIZE, NULL,
780  KEYSIZE_CHECK_SPECIAL );
781  }
782  else
783  {
784  status = importBignum( bn, buffer, noBytes, max( noBytes - 8, 1 ),
785  CRYPT_MAX_PKCSIZE, NULL, KEYSIZE_CHECK_NONE );
786  }
787  zeroise( buffer, noBytes );
788  return( status );
789  }
Generated on Thu Jan 10 2013 10:00:45 for cryptlib by   doxygen 1.8.2