source: trunk/third/moira/util/rsaref/prime.c @ 23095

Revision 23095, 3.3 KB checked in by ghudson, 16 years ago (diff)
Import the moira package from SIPB Debathena.
RevLine 
[23095]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
14static unsigned int SMALL_PRIMES[] = { 3, 5, 7, 11 };
15#define SMALL_PRIME_COUNT 4
16
17static int ProbablePrime PROTO_LIST ((NN_DIGIT *, unsigned int));
18static int SmallFactor PROTO_LIST ((NN_DIGIT *, unsigned int));
19static 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 */
30int GeneratePrime (a, b, c, d, digits, randomStruct)
31NN_DIGIT *a, *b, *c, *d;
32unsigned int digits;
33R_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 */
79static int ProbablePrime (a, aDigits)
80NN_DIGIT *a;
81unsigned 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 */
91static int SmallFactor (a, aDigits)
92NN_DIGIT *a;
93unsigned 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 */
126static int FermatTest (a, aDigits)
127NN_DIGIT *a;
128unsigned 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}
Note: See TracBrowser for help on using the repository browser.