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, rng):
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 = rng.read((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(rng, 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 = rng.read(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.rng = 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.rng, len(self.pack[good])) 151 return self.pack[good][n]
152