]>
Commit | Line | Data |
---|---|---|
bd940221 | 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 | } |