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

Revision 23095, 3.3 KB checked in by ghudson, 16 years ago (diff) |
---|

Rev | Line | |
---|---|---|

[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 | ||

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 | } |

**Note:**See TracBrowser for help on using the repository browser.