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