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 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  # 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA. 
 18   
 19  """ 
 20  Utility functions for dealing with primes. 
 21  """ 
 22   
 23  import os 
 24   
 25  from paramiko import util 
 26  from paramiko.py3compat import byte_mask, long 
 27  from paramiko.ssh_exception import SSHException 
 28   
 29   
30 -def _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
52 -class ModulusPack (object):
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 timestamp, mod_type, tests, tries, size, generator, modulus = line.split() 65 mod_type = int(mod_type) 66 tests = int(tests) 67 tries = int(tries) 68 size = int(size) 69 generator = int(generator) 70 modulus = long(modulus, 16) 71 72 # weed out primes that aren't at least: 73 # type 2 (meets basic structural requirements) 74 # test 4 (more than just a small-prime sieve) 75 # tries < 100 if test & 4 (at least 100 tries of miller-rabin) 76 if (mod_type < 2) or (tests < 4) or ((tests & 4) and (tests < 8) and (tries < 100)): 77 self.discarded.append((modulus, 'does not meet basic requirements')) 78 return 79 if generator == 0: 80 generator = 2 81 82 # there's a bug in the ssh "moduli" file (yeah, i know: shock! dismay! 83 # call cnn!) where it understates the bit lengths of these primes by 1. 84 # this is okay. 85 bl = util.bit_length(modulus) 86 if (bl != size) and (bl != size + 1): 87 self.discarded.append((modulus, 'incorrectly reported bit length %d' % size)) 88 return 89 if bl not in self.pack: 90 self.pack[bl] = [] 91 self.pack[bl].append((generator, modulus))
92
93 - def read_file(self, filename):
94 """ 95 :raises IOError: passed from any file operations that fail. 96 """ 97 self.pack = {} 98 with open(filename, 'r') as f: 99 for line in f: 100 line = line.strip() 101 if (len(line) == 0) or (line[0] == '#'): 102 continue 103 try: 104 self._parse_modulus(line) 105 except: 106 continue
107
108 - def get_modulus(self, min, prefer, max):
109 bitsizes = sorted(self.pack.keys()) 110 if len(bitsizes) == 0: 111 raise SSHException('no moduli available') 112 good = -1 113 # find nearest bitsize >= preferred 114 for b in bitsizes: 115 if (b >= prefer) and (b < max) and (b < good or good == -1): 116 good = b 117 # if that failed, find greatest bitsize >= min 118 if good == -1: 119 for b in bitsizes: 120 if (b >= min) and (b < max) and (b > good): 121 good = b 122 if good == -1: 123 # their entire (min, max) range has no intersection with our range. 124 # if their range is below ours, pick the smallest. otherwise pick 125 # the largest. it'll be out of their range requirement either way, 126 # but we'll be sending them the closest one we have. 127 good = bitsizes[0] 128 if min > good: 129 good = bitsizes[-1] 130 # now pick a random modulus of this bitsize 131 n = _roll_random(len(self.pack[good])) 132 return self.pack[good][n]
133