Coverage for /pythoncovmergedfiles/medio/medio/src/paramiko/paramiko/primes.py: 15%

1# Copyright (C) 2003-2007 Robey Pointer <robeypointer@gmail.com> 

2# 

3# This file is part of paramiko. 

4# 

5# Paramiko is free software; you can redistribute it and/or modify it under the 

6# terms of the GNU Lesser General Public License as published by the Free 

7# Software Foundation; either version 2.1 of the License, or (at your option) 

8# any later version. 

9# 

10# Paramiko is distributed in the hope that it will be useful, but WITHOUT ANY 

11# WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR 

12# A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more 

13# details. 

14# 

15# You should have received a copy of the GNU Lesser General Public License 

16# along with Paramiko; if not, write to the Free Software Foundation, Inc., 

17# 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 

18 

19""" 

20Utility functions for dealing with primes. 

21""" 

22 

23import os 

24 

25from paramiko import util 

26from paramiko.common import byte_mask 

27from paramiko.ssh_exception import SSHException 

28 

29 

30def _roll_random(n): 

31 """returns a random # from 0 to N-1""" 

32 bits = util.bit_length(n - 1) 

33 byte_count = (bits + 7) // 8 

34 hbyte_mask = pow(2, bits % 8) - 1 

35 

36 # so here's the plan: 

37 # we fetch as many random bits as we'd need to fit N-1, and if the 

38 # generated number is >= N, we try again. in the worst case (N-1 is a 

39 # power of 2), we have slightly better than 50% odds of getting one that 

40 # fits, so i can't guarantee that this loop will ever finish, but the odds 

41 # of it looping forever should be infinitesimal. 

42 while True: 

43 x = os.urandom(byte_count) 

44 if hbyte_mask > 0: 

45 x = byte_mask(x[0], hbyte_mask) + x[1:] 

46 num = util.inflate_long(x, 1) 

47 if num < n: 

48 break 

49 return num 

50 

51 

52class ModulusPack: 

53 """ 

54 convenience object for holding the contents of the /etc/ssh/moduli file, 

55 on systems that have such a file. 

56 """ 

57 

58 def __init__(self): 

59 # pack is a hash of: bits -> [ (generator, modulus) ... ] 

60 self.pack = {} 

61 self.discarded = [] 

62 

63 def _parse_modulus(self, line): 

64 ( 

65 timestamp, 

66 mod_type, 

67 tests, 

68 tries, 

69 size, 

70 generator, 

71 modulus, 

72 ) = line.split() 

73 mod_type = int(mod_type) 

74 tests = int(tests) 

75 tries = int(tries) 

76 size = int(size) 

77 generator = int(generator) 

78 modulus = int(modulus, 16) 

79 

80 # weed out primes that aren't at least: 

81 # type 2 (meets basic structural requirements) 

82 # test 4 (more than just a small-prime sieve) 

83 # tries < 100 if test & 4 (at least 100 tries of miller-rabin) 

84 if ( 

85 mod_type < 2 

86 or tests < 4 

87 or (tests & 4 and tests < 8 and tries < 100) 

88 ): 

89 self.discarded.append( 

90 (modulus, "does not meet basic requirements") 

91 ) 

92 return 

93 if generator == 0: 

94 generator = 2 

95 

96 # there's a bug in the ssh "moduli" file (yeah, i know: shock! dismay! 

97 # call cnn!) where it understates the bit lengths of these primes by 1. 

98 # this is okay. 

99 bl = util.bit_length(modulus) 

100 if (bl != size) and (bl != size + 1): 

101 self.discarded.append( 

102 (modulus, "incorrectly reported bit length {}".format(size)) 

103 ) 

104 return 

105 if bl not in self.pack: 

106 self.pack[bl] = [] 

107 self.pack[bl].append((generator, modulus)) 

108 

109 def read_file(self, filename): 

110 """ 

111 :raises IOError: passed from any file operations that fail. 

112 """ 

113 self.pack = {} 

114 with open(filename, "r") as f: 

115 for line in f: 

116 line = line.strip() 

117 if (len(line) == 0) or (line[0] == "#"): 

118 continue 

119 try: 

120 self._parse_modulus(line) 

121 except: 

122 continue 

123 

124 def get_modulus(self, min, prefer, max): 

125 bitsizes = sorted(self.pack.keys()) 

126 if len(bitsizes) == 0: 

127 raise SSHException("no moduli available") 

128 good = -1 

129 # find nearest bitsize >= preferred 

130 for b in bitsizes: 

131 if (b >= prefer) and (b <= max) and (b < good or good == -1): 

132 good = b 

133 # if that failed, find greatest bitsize >= min 

134 if good == -1: 

135 for b in bitsizes: 

136 if (b >= min) and (b <= max) and (b > good): 

137 good = b 

138 if good == -1: 

139 # their entire (min, max) range has no intersection with our range. 

140 # if their range is below ours, pick the smallest. otherwise pick 

141 # the largest. it'll be out of their range requirement either way, 

142 # but we'll be sending them the closest one we have. 

143 good = bitsizes[0] 

144 if min > good: 

145 good = bitsizes[-1] 

146 # now pick a random modulus of this bitsize 

147 n = _roll_random(len(self.pack[good])) 

148 return self.pack[good][n]