![[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:
1.1.1.2 ! root 4: /* Copyright (C) RSA Laboratories, a division of RSA Data Security,
! 5: Inc., created 1991. All rights reserved.
1.1 root 6: */
7:
8: #include "global.h"
9: #include "rsaref.h"
1.1.1.2 ! root 10: #include "r_random.h"
1.1 root 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:
1.1.1.2 ! root 21: /* Generates a probable prime a between b and c such that a-1 is
! 22: divisible by d.
1.1 root 23:
1.1.1.2 ! root 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;
1.1 root 34: {
1.1.1.2 ! root 35: int status;
! 36: unsigned char block[MAX_NN_DIGITS * NN_DIGIT_LEN];
! 37: NN_DIGIT t[MAX_NN_DIGITS], u[MAX_NN_DIGITS];
1.1 root 38:
1.1.1.2 ! root 39: /* Generate random number between b and c.
1.1 root 40: */
1.1.1.2 ! root 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);
1.1 root 69: }
70:
1.1.1.2 ! root 71: return (0);
1.1 root 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);
1.1.1.2 ! root 103: if ((aDigits == 1) && ! NN_Cmp (a, t, 1))
! 104: break;
1.1 root 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: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.