paramiko.primes

47 "returns a random # from 0 to N-1" + 48 bits = util.bit_length(n-1) + 49 bytes = (bits + 7) // 8 + 50 hbyte_mask = pow(2, bits % 8) - 1 + 51 + 52 # so here's the plan: + 53 # we fetch as many random bits as we'd need to fit N-1, and if the + 54 # generated number is >= N, we try again. in the worst case (N-1 is a + 55 # power of 2), we have slightly better than 50% odds of getting one that + 56 # fits, so i can't guarantee that this loop will ever finish, but the odds + 57 # of it looping forever should be infinitesimal. + 58 while True: + 59 x = rpool.get_bytes(bytes) + 60 if hbyte_mask > 0: + 61 x = chr(ord(x[0]) & hbyte_mask) + x[1:] + 62 num = util.inflate_long(x, 1) + 63 if num < n: + 64 break + 65 return num +

69 """ + 70 convenience object for holding the contents of the /etc/ssh/moduli file, + 71 on systems that have such a file. + 72 """ + 73 +

74 - def __init__(self, rpool): +

75 # pack is a hash of: bits -> [ (generator, modulus) ... ] + 76 self.pack = {} + 77 self.discarded = [] + 78 self.randpool = rpool +

79 +

80 - def _parse_modulus(self, line): +

81 timestamp, mod_type, tests, tries, size, generator, modulus = line.split() + 82 mod_type = int(mod_type) + 83 tests = int(tests) + 84 tries = int(tries) + 85 size = int(size) + 86 generator = int(generator) + 87 modulus = long(modulus, 16) + 88 + 89 # weed out primes that aren't at least: + 90 # type 2 (meets basic structural requirements) + 91 # test 4 (more than just a small-prime sieve) + 92 # tries < 100 if test & 4 (at least 100 tries of miller-rabin) + 93 if (mod_type < 2) or (tests < 4) or ((tests & 4) and (tests < 8) and (tries < 100)): + 94 self.discarded.append((modulus, 'does not meet basic requirements')) + 95 return + 96 if generator == 0: + 97 generator = 2 + 98 + 99 # there's a bug in the ssh "moduli" file (yeah, i know: shock! dismay! +100 # call cnn!) where it understates the bit lengths of these primes by 1. +101 # this is okay. +102 bl = util.bit_length(modulus) +103 if (bl != size) and (bl != size + 1): +104 self.discarded.append((modulus, 'incorrectly reported bit length %d' % size)) +105 return +106 if bl not in self.pack: +107 self.pack[bl] = [] +108 self.pack[bl].append((generator, modulus)) +

109 +

110 - def read_file(self, filename): +

111 """ +112 @raise IOError: passed from any file operations that fail. +113 """ +114 self.pack = {} +115 f = open(filename, 'r') +116 for line in f: +117 line = line.strip() +118 if (len(line) == 0) or (line[0] == '#'): +119 continue +120 try: +121 self._parse_modulus(line) +122 except: +123 continue +124 f.close() +

125 +

126 - def get_modulus(self, min, prefer, max): +

127 bitsizes = self.pack.keys() +128 bitsizes.sort() +129 if len(bitsizes) == 0: +130 raise SSHException('no moduli available') +131 good = -1 +132 # find nearest bitsize >= preferred +133 for b in bitsizes: +134 if (b >= prefer) and (b < max) and ((b < good) or (good == -1)): +135 good = b +136 # if that failed, find greatest bitsize >= min +137 if good == -1: +138 for b in bitsizes: +139 if (b >= min) and (b < max) and (b > good): +140 good = b +141 if good == -1: +142 # their entire (min, max) range has no intersection with our range. +143 # if their range is below ours, pick the smallest. otherwise pick +144 # the largest. it'll be out of their range requirement either way, +145 # but we'll be sending them the closest one we have. +146 good = bitsizes[0] +147 if min > good: +148 good = bitsizes[-1] +149 # now pick a random modulus of this bitsize +150 n = _roll_random(self.randpool, len(self.pack[good])) +151 return self.pack[good][n] +

Source Code for Module paramiko.primes