codekingpro/portable-devtools

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 the6# terms of the GNU Lesser General Public License as published by the Free7# 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 ANY11# WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR12# A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more13# details.14#15# You should have received a copy of the GNU Lesser General Public License16# 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 os24 25from paramiko import util26from paramiko.common import byte_mask27from paramiko.ssh_exception import SSHException28 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) // 834    hbyte_mask = pow(2, bits % 8) - 135 36    # so here's the plan:37    # we fetch as many random bits as we'd need to fit N-1, and if the38    # generated number is >= N, we try again.  in the worst case (N-1 is a39    # power of 2), we have slightly better than 50% odds of getting one that40    # fits, so i can't guarantee that this loop will ever finish, but the odds41    # 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            break49    return num50 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 < 286            or tests < 487            or (tests & 4 and tests < 8 and tries < 100)88        ):89            self.discarded.append(90                (modulus, "does not meet basic requirements")91            )92            return93        if generator == 0:94            generator = 295 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            return105        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                    continue119                try:120                    self._parse_modulus(line)121                except:122                    continue123 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 = -1129        # find nearest bitsize >= preferred130        for b in bitsizes:131            if (b >= prefer) and (b <= max) and (b < good or good == -1):132                good = b133        # if that failed, find greatest bitsize >= min134        if good == -1:135            for b in bitsizes:136                if (b >= min) and (b <= max) and (b > good):137                    good = b138        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 pick141            # 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 bitsize147        n = _roll_random(len(self.pack[good]))148        return self.pack[good][n]149