Package paramiko :: Module primes |
[frames] | no frames]

# Source Code for Module paramiko.primes

      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 distrubuted 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  # 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA.
     18
     19  """
     20  Utility functions for dealing with primes.
     21  """
     22
     23  from Crypto.Util import number
     24
     25  from paramiko import util
     26  from paramiko.ssh_exception import SSHException
     27
     28
     29 -def _generate_prime(bits, randpool):
     30      "primtive attempt at prime generation"
     31      hbyte_mask = pow(2, bits % 8) - 1
     32      while True:
     33          # loop catches the case where we increment n into a higher bit-range
     34          x = randpool.get_bytes((bits+7) // 8)
     35          if hbyte_mask > 0:
     36              x = chr(ord(x[0]) & hbyte_mask) + x[1:]
     37          n = util.inflate_long(x, 1)
     38          n |= 1
     39          n |= (1 << (bits - 1))
     40          while not number.isPrime(n):
     41              n += 2
     42          if util.bit_length(n) == bits:
     43              break
     44      return n
     45
     46 -def _roll_random(rpool, n):
     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
     66
     67
     68 -class ModulusPack (object):
     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]
    152