Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/rsa/prime.py: 17%

1# Copyright 2011 Sybren A. Stüvel <sybren@stuvel.eu> 

2# 

3# Licensed under the Apache License, Version 2.0 (the "License"); 

4# you may not use this file except in compliance with the License. 

5# You may obtain a copy of the License at 

6# 

7# https://www.apache.org/licenses/LICENSE-2.0 

8# 

9# Unless required by applicable law or agreed to in writing, software 

10# distributed under the License is distributed on an "AS IS" BASIS, 

11# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 

12# See the License for the specific language governing permissions and 

13# limitations under the License. 

14 

15"""Numerical functions related to primes. 

16 

17Implementation based on the book Algorithm Design by Michael T. Goodrich and 

18Roberto Tamassia, 2002. 

19""" 

20 

21import rsa.common 

22import rsa.randnum 

23 

24__all__ = ["getprime", "are_relatively_prime"] 

25 

26 

27def gcd(p: int, q: int) -> int: 

28 """Returns the greatest common divisor of p and q 

29 

30 >>> gcd(48, 180) 

31 12 

32 """ 

33 

34 while q != 0: 

35 (p, q) = (q, p % q) 

36 return p 

37 

38 

39def get_primality_testing_rounds(number: int) -> int: 

40 """Returns minimum number of rounds for Miller-Rabing primality testing, 

41 based on number bitsize. 

42 

43 According to NIST FIPS 186-4, Appendix C, Table C.3, minimum number of 

44 rounds of M-R testing, using an error probability of 2 ** (-100), for 

45 different p, q bitsizes are: 

46 * p, q bitsize: 512; rounds: 7 

47 * p, q bitsize: 1024; rounds: 4 

48 * p, q bitsize: 1536; rounds: 3 

49 See: http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf 

50 """ 

51 

52 # Calculate number bitsize. 

53 bitsize = rsa.common.bit_size(number) 

54 # Set number of rounds. 

55 if bitsize >= 1536: 

56 return 3 

57 if bitsize >= 1024: 

58 return 4 

59 if bitsize >= 512: 

60 return 7 

61 # For smaller bitsizes, set arbitrary number of rounds. 

62 return 10 

63 

64 

65def miller_rabin_primality_testing(n: int, k: int) -> bool: 

66 """Calculates whether n is composite (which is always correct) or prime 

67 (which theoretically is incorrect with error probability 4**-k), by 

68 applying Miller-Rabin primality testing. 

69 

70 For reference and implementation example, see: 

71 https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test 

72 

73 :param n: Integer to be tested for primality. 

74 :type n: int 

75 :param k: Number of rounds (witnesses) of Miller-Rabin testing. 

76 :type k: int 

77 :return: False if the number is composite, True if it's probably prime. 

78 :rtype: bool 

79 """ 

80 

81 # prevent potential infinite loop when d = 0 

82 if n < 2: 

83 return False 

84 

85 # Decompose (n - 1) to write it as (2 ** r) * d 

86 # While d is even, divide it by 2 and increase the exponent. 

87 d = n - 1 

88 r = 0 

89 

90 while not (d & 1): 

91 r += 1 

92 d >>= 1 

93 

94 # Test k witnesses. 

95 for _ in range(k): 

96 # Generate random integer a, where 2 <= a <= (n - 2) 

97 a = rsa.randnum.randint(n - 3) + 1 

98 

99 x = pow(a, d, n) 

100 if x == 1 or x == n - 1: 

101 continue 

102 

103 for _ in range(r - 1): 

104 x = pow(x, 2, n) 

105 if x == 1: 

106 # n is composite. 

107 return False 

108 if x == n - 1: 

109 # Exit inner loop and continue with next witness. 

110 break 

111 else: 

112 # If loop doesn't break, n is composite. 

113 return False 

114 

115 return True 

116 

117 

118def is_prime(number: int) -> bool: 

119 """Returns True if the number is prime, and False otherwise. 

120 

121 >>> is_prime(2) 

122 True 

123 >>> is_prime(42) 

124 False 

125 >>> is_prime(41) 

126 True 

127 """ 

128 

129 # Check for small numbers. 

130 if number < 10: 

131 return number in {2, 3, 5, 7} 

132 

133 # Check for even numbers. 

134 if not (number & 1): 

135 return False 

136 

137 # Calculate minimum number of rounds. 

138 k = get_primality_testing_rounds(number) 

139 

140 # Run primality testing with (minimum + 1) rounds. 

141 return miller_rabin_primality_testing(number, k + 1) 

142 

143 

144def getprime(nbits: int) -> int: 

145 """Returns a prime number that can be stored in 'nbits' bits. 

146 

147 >>> p = getprime(128) 

148 >>> is_prime(p-1) 

149 False 

150 >>> is_prime(p) 

151 True 

152 >>> is_prime(p+1) 

153 False 

154 

155 >>> from rsa import common 

156 >>> common.bit_size(p) == 128 

157 True 

158 """ 

159 

160 assert nbits > 3 # the loop will hang on too small numbers 

161 

162 while True: 

163 integer = rsa.randnum.read_random_odd_int(nbits) 

164 

165 # Test for primeness 

166 if is_prime(integer): 

167 return integer 

168 

169 # Retry if not prime 

170 

171 

172def are_relatively_prime(a: int, b: int) -> bool: 

173 """Returns True if a and b are relatively prime, and False if they 

174 are not. 

175 

176 >>> are_relatively_prime(2, 3) 

177 True 

178 >>> are_relatively_prime(2, 4) 

179 False 

180 """ 

181 

182 d = gcd(a, b) 

183 return d == 1 

184 

185 

186if __name__ == "__main__": 

187 print("Running doctests 1000x or until failure") 

188 import doctest 

189 

190 for count in range(1000): 

191 (failures, tests) = doctest.testmod() 

192 if failures: 

193 break 

194 

195 if count % 100 == 0 and count: 

196 print("%i times" % count) 

197 

198 print("Doctests done")