util/rsaref/prime.c

   1 /* PRIME.C - primality-testing routines
   2  */
   3
   4 /* Copyright (C) RSA Laboratories, a division of RSA Data Security,
   5      Inc., created 1991. All rights reserved.
   6  */
   7
   8 #include "global.h"
   9 #include "rsaref.h"
  10 #include "r_random.h"
  11 #include "nn.h"
  12 #include "prime.h"
  13
  14 static unsigned int SMALL_PRIMES[] = { 3, 5, 7, 11 };
  15 #define SMALL_PRIME_COUNT 4
  16
  17 static int ProbablePrime PROTO_LIST ((NN_DIGIT *, unsigned int));
  18 static int SmallFactor PROTO_LIST ((NN_DIGIT *, unsigned int));
  19 static int FermatTest PROTO_LIST ((NN_DIGIT *, unsigned int));
  20
  21 /* Generates a probable prime a between b and c such that a-1 is
  22    divisible by d.
  23
  24    Lengths: a[digits], b[digits], c[digits], d[digits].
  25    Assumes b < c, digits < MAX_NN_DIGITS.
  26
  27    Returns RE_NEED_RANDOM if randomStruct not seeded, RE_DATA if
  28    unsuccessful.
  29  */
  30 int GeneratePrime (a, b, c, d, digits, randomStruct)
  31 NN_DIGIT *a, *b, *c, *d;
  32 unsigned int digits;
  33 R_RANDOM_STRUCT *randomStruct;
  34 {
  35   int status;
  36   unsigned char block[MAX_NN_DIGITS * NN_DIGIT_LEN];
  37   NN_DIGIT t[MAX_NN_DIGITS], u[MAX_NN_DIGITS];
  38
  39   /* Generate random number between b and c.
  40    */
  41   if (status = R_GenerateBytes (block, digits * NN_DIGIT_LEN, randomStruct))
  42     return (status);
  43   NN_Decode (a, digits, block, digits * NN_DIGIT_LEN);
  44   NN_Sub (t, c, b, digits);
  45   NN_ASSIGN_DIGIT (u, 1, digits);
  46   NN_Add (t, t, u, digits);
  47   NN_Mod (a, a, digits, t, digits);
  48   NN_Add (a, a, b, digits);
  49
  50   /* Adjust so that a-1 is divisible by d.
  51    */
  52   NN_Mod (t, a, digits, d, digits);
  53   NN_Sub (a, a, t, digits);
  54   NN_Add (a, a, u, digits);
  55   if (NN_Cmp (a, b, digits) < 0)
  56     NN_Add (a, a, d, digits);
  57   if (NN_Cmp (a, c, digits) > 0)
  58     NN_Sub (a, a, d, digits);
  59
  60   /* Search to c in steps of d.
  61    */
  62   NN_Assign (t, c, digits);
  63   NN_Sub (t, t, d, digits);
  64
  65   while (! ProbablePrime (a, digits)) {
  66     if (NN_Cmp (a, t, digits) > 0)
  67       return (RE_DATA);
  68     NN_Add (a, a, d, digits);
  69   }
  70
  71   return (0);
  72 }
  73
  74 /* Returns nonzero iff a is a probable prime.
  75
  76    Lengths: a[aDigits].
  77    Assumes aDigits < MAX_NN_DIGITS.
  78  */
  79 static int ProbablePrime (a, aDigits)
  80 NN_DIGIT *a;
  81 unsigned int aDigits;
  82 {
  83   return (! SmallFactor (a, aDigits) && FermatTest (a, aDigits));
  84 }
  85
  86 /* Returns nonzero iff a has a prime factor in SMALL_PRIMES.
  87
  88    Lengths: a[aDigits].
  89    Assumes aDigits < MAX_NN_DIGITS.
  90  */
  91 static int SmallFactor (a, aDigits)
  92 NN_DIGIT *a;
  93 unsigned int aDigits;
  94 {
  95   int status;
  96   NN_DIGIT t[1];
  97   unsigned int i;
  98
  99   status = 0;
 100
 101   for (i = 0; i < SMALL_PRIME_COUNT; i++) {
 102     NN_ASSIGN_DIGIT (t, SMALL_PRIMES[i], 1);
 103     if ((aDigits == 1) && ! NN_Cmp (a, t, 1))
 104       break;
 105     NN_Mod (t, a, aDigits, t, 1);
 106     if (NN_Zero (t, 1)) {
 107       status = 1;
 108       break;
 109     }
 110   }
 111
 112   /* Zeroize sensitive information.
 113    */
 114   i = 0;
 115   R_memset ((POINTER)t, 0, sizeof (t));
 116
 117   return (status);
 118 }
 119
 120 /* Returns nonzero iff a passes Fermat's test for witness 2.
 121    (All primes pass the test, and nearly all composites fail.)
 122
 123    Lengths: a[aDigits].
 124    Assumes aDigits < MAX_NN_DIGITS.
 125  */
 126 static int FermatTest (a, aDigits)
 127 NN_DIGIT *a;
 128 unsigned int aDigits;
 129 {
 130   int status;
 131   NN_DIGIT t[MAX_NN_DIGITS], u[MAX_NN_DIGITS];
 132
 133   NN_ASSIGN_DIGIT (t, 2, aDigits);
 134   NN_ModExp (u, t, a, aDigits, a, aDigits);
 135
 136   status = NN_EQUAL (t, u, aDigits);
 137
 138   /* Zeroize sensitive information.
 139    */
 140   R_memset ((POINTER)u, 0, sizeof (u));
 141
 142   return (status);
 143 }