![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to prime.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [rsaref] / rsaref / source|
Return to prime.c CVS log | Up to [rsaref] / rsaref / source |
1.1 root 1: /* PRIME.C - primality-testing routines
2: */
3:
4: /* Copyright (C) 1991-2 RSA Laboratories, a division of RSA Data
5: Security, Inc. All rights reserved.
6: */
7:
8: #include "global.h"
9: #include "rsaref.h"
10: #include "nn.h"
11: #include "prime.h"
12:
13: static unsigned int SMALL_PRIMES[] = { 3, 5, 7, 11 };
14: #define SMALL_PRIME_COUNT 4
15:
16: static int RSAPrime PROTO_LIST
17: ((NN_DIGIT *, unsigned int, NN_DIGIT *, unsigned int));
18: static int ProbablePrime PROTO_LIST ((NN_DIGIT *, unsigned int));
19: static int SmallFactor PROTO_LIST ((NN_DIGIT *, unsigned int));
20: static int FermatTest PROTO_LIST ((NN_DIGIT *, unsigned int));
21: static int RelativelyPrime PROTO_LIST
22: ((NN_DIGIT *, unsigned int, NN_DIGIT *, unsigned int));
23:
24: /* Find a probable prime a between 3*2^(b-2) and 2^b-1, starting at
25: 3*2^(b-2) + (c mod 2^(b-2)), such that gcd (a-1, d) = 1.
26:
27: Lengths: a[cDigits], c[cDigits], d[dDigits].
28: Assumes b > 2, b < cDigits * NN_DIGIT_BITS, d is odd,
29: cDigits < MAX_NN_DIGITS, dDigits < MAX_NN_DIGITS, and a
30: probable prime can be found.
31: */
32: void FindRSAPrime (a, b, c, cDigits, d, dDigits)
33: NN_DIGIT *a, *c, *d;
34: unsigned int b, cDigits, dDigits;
35: {
36: NN_DIGIT t[MAX_NN_DIGITS], u[MAX_NN_DIGITS], v[MAX_NN_DIGITS],
37: w[MAX_NN_DIGITS];
38:
39: /* Compute t = 2^(b-2), u = 3*2^(b-2).
40: */
41: NN_Assign2Exp (t, b-2, cDigits);
42: NN_Assign2Exp (u, b-1, cDigits);
43: NN_Add (u, u, t, cDigits);
44:
45: /* Compute v = 3*2^(b-2) + (c mod 2^(b-2)); add one if even.
46: */
47: NN_Mod (v, c, cDigits, t, cDigits);
48: NN_Add (v, v, u, cDigits);
49: if (NN_EVEN (v, cDigits)) {
50: NN_ASSIGN_DIGIT (w, 1, cDigits);
51: NN_Add (v, v, w, cDigits);
52: }
53:
54: /* Compute w = 2, u = 2^b - 2.
55: */
56: NN_ASSIGN_DIGIT (w, 2, cDigits);
57: NN_Sub (u, u, w, cDigits);
58: NN_Add (u, u, t, cDigits);
59:
60: /* Search to 2^b-1 from starting point, then from 3*2^(b-2)+1.
61: */
62: while (! RSAPrime (v, cDigits, d, dDigits)) {
63: if (NN_Cmp (v, u, cDigits) > 0)
64: NN_Sub (v, v, t, cDigits);
65: NN_Add (v, v, w, cDigits);
66: }
67:
68: NN_Assign (a, v, cDigits);
69:
70: /* Zeroize sensitive information.
71: */
72: R_memset ((POINTER)v, 0, sizeof (v));
73: }
74:
75: /* Returns nonzero iff a is a probable prime and GCD (a-1, b) = 1.
76:
77: Lengths: a[aDigits], b[bDigits].
78: Assumes aDigits < MAX_NN_DIGITS, bDigits < MAX_NN_DIGITS.
79: */
80: static int RSAPrime (a, aDigits, b, bDigits)
81: NN_DIGIT *a, *b;
82: unsigned int aDigits, bDigits;
83: {
84: int status;
85: NN_DIGIT aMinus1[MAX_NN_DIGITS], t[MAX_NN_DIGITS];
86:
87: NN_ASSIGN_DIGIT (t, 1, aDigits);
88: NN_Sub (aMinus1, a, t, aDigits);
89:
90: status = ProbablePrime (a, aDigits) &&
91: RelativelyPrime (aMinus1, aDigits, b, bDigits);
92:
93: /* Zeroize sensitive information.
94: */
95: R_memset ((POINTER)aMinus1, 0, sizeof (aMinus1));
96:
97: return (status);
98: }
99:
100: /* Returns nonzero iff a is a probable prime.
101:
102: Lengths: a[aDigits].
103: Assumes aDigits < MAX_NN_DIGITS.
104: */
105: static int ProbablePrime (a, aDigits)
106: NN_DIGIT *a;
107: unsigned int aDigits;
108: {
109: return (! SmallFactor (a, aDigits) && FermatTest (a, aDigits));
110: }
111:
112: /* Returns nonzero iff a has a prime factor in SMALL_PRIMES.
113:
114: Lengths: a[aDigits].
115: Assumes aDigits < MAX_NN_DIGITS.
116: */
117: static int SmallFactor (a, aDigits)
118: NN_DIGIT *a;
119: unsigned int aDigits;
120: {
121: int status;
122: NN_DIGIT t[1];
123: unsigned int i;
124:
125: status = 0;
126:
127: for (i = 0; i < SMALL_PRIME_COUNT; i++) {
128: NN_ASSIGN_DIGIT (t, SMALL_PRIMES[i], 1);
129: NN_Mod (t, a, aDigits, t, 1);
130: if (NN_Zero (t, 1)) {
131: status = 1;
132: break;
133: }
134: }
135:
136: /* Zeroize sensitive information.
137: */
138: i = 0;
139: R_memset ((POINTER)t, 0, sizeof (t));
140:
141: return (status);
142: }
143:
144: /* Returns nonzero iff a passes Fermat's test for witness 2.
145: (All primes pass the test, and nearly all composites fail.)
146:
147: Lengths: a[aDigits].
148: Assumes aDigits < MAX_NN_DIGITS.
149: */
150: static int FermatTest (a, aDigits)
151: NN_DIGIT *a;
152: unsigned int aDigits;
153: {
154: int status;
155: NN_DIGIT t[MAX_NN_DIGITS], u[MAX_NN_DIGITS];
156:
157: NN_ASSIGN_DIGIT (t, 2, aDigits);
158: NN_ModExp (u, t, a, aDigits, a, aDigits);
159:
160: status = NN_EQUAL (t, u, aDigits);
161:
162: /* Zeroize sensitive information.
163: */
164: R_memset ((POINTER)u, 0, sizeof (u));
165:
166: return (status);
167: }
168:
169: /* Returns nonzero iff a and b are relatively prime.
170:
171: Lengths: a[aDigits], b[bDigits].
172: Assumes aDigits >= bDigits, aDigits < MAX_NN_DIGITS.
173: */
174: static int RelativelyPrime (a, aDigits, b, bDigits)
175: NN_DIGIT *a, *b;
176: unsigned int aDigits, bDigits;
177: {
178: int status;
179: NN_DIGIT t[MAX_NN_DIGITS], u[MAX_NN_DIGITS];
180:
181: NN_AssignZero (t, aDigits);
182: NN_Assign (t, b, bDigits);
183: NN_Gcd (t, a, t, aDigits);
184: NN_ASSIGN_DIGIT (u, 1, aDigits);
185:
186: status = NN_EQUAL (t, u, aDigits);
187:
188: /* Zeroize sensitive information.
189: */
190: R_memset ((POINTER)t, 0, sizeof (t));
191:
192: return (status);
193: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.