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

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

Line | |
---|---|

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.