rsa_source/rsa/randnum.py

   1 # -*- coding: utf-8 -*-
   2 #
   3 #  Copyright 2011 Sybren A. Stüvel <sybren@stuvel.eu>
   4 #
   5 #  Licensed under the Apache License, Version 2.0 (the "License");
   6 #  you may not use this file except in compliance with the License.
   7 #  You may obtain a copy of the License at
   8 #
   9 #      http://www.apache.org/licenses/LICENSE-2.0
  10 #
  11 #  Unless required by applicable law or agreed to in writing, software
  12 #  distributed under the License is distributed on an "AS IS" BASIS,
  13 #  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14 #  See the License for the specific language governing permissions and
  15 #  limitations under the License.
  16
  17 '''Functions for generating random numbers.'''
  18
  19 # Source inspired by code by Yesudeep Mangalapilly <yesudeep@gmail.com>
  20
  21 import os
  22
  23 from rsa import common, transform
  24
  25 def read_random_bits(nbits):
  26     '''Reads 'nbits' random bits.
  27
  28     If nbits isn't a whole number of bytes, an extra byte will be appended with
  29     only the lower bits set.
  30     '''
  31
  32     nbytes, rbits = divmod(nbits, 8)
  33
  34     # Get the random bytes
  35     randomdata = os.urandom(nbytes)
  36
  37     # Add the remaining random bits
  38     if rbits > 0:
  39         randomvalue = ord(os.urandom(1))
  40         randomvalue >>= (8 - rbits)
  41         randomdata = chr(randomvalue) + randomdata
  42
  43     return randomdata
  44
  45
  46 def read_random_int(nbits):
  47     """Reads a random integer of approximately nbits bits.
  48     """
  49
  50     randomdata = read_random_bits(nbits)
  51     value = transform.bytes2int(randomdata)
  52
  53     # Ensure that the number is large enough to just fill out the required
  54     # number of bits.
  55     value |= 1 << (nbits - 1)
  56
  57     return value
  58
  59 def randint(maxvalue):
  60     """Returns a random integer x with 1 <= x <= maxvalue
  61
  62     May take a very long time in specific situations. If maxvalue needs N bits
  63     to store, the closer maxvalue is to (2 ** N) - 1, the faster this function
  64     is.
  65     """
  66
  67     bit_size = common.bit_size(maxvalue)
  68
  69     tries = 0
  70     while True:
  71         value = read_random_int(bit_size)
  72         if value <= maxvalue:
  73             break
  74
  75         if tries and tries % 10 == 0:
  76             # After a lot of tries to get the right number of bits but still
  77             # smaller than maxvalue, decrease the number of bits by 1. That'll
  78             # dramatically increase the chances to get a large enough number.
  79             bit_size -= 1
  80         tries += 1
  81
  82     return value
  83
  84