Home | History | Annotate | Download | only in rsa 
      1 # -*- coding: utf-8 -*-
      2 #
      3 #  Copyright 2011 Sybren A. Stvel <sybren (at] 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 #      https://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 (at] gmail.com>
     20 
     21 import os
     22 
     23 from rsa import common, transform
     24 from rsa._compat import byte
     25 
     26 
     27 def read_random_bits(nbits):
     28     """Reads 'nbits' random bits.
     29 
     30     If nbits isn't a whole number of bytes, an extra byte will be appended with
     31     only the lower bits set.
     32     """
     33 
     34     nbytes, rbits = divmod(nbits, 8)
     35 
     36     # Get the random bytes
     37     randomdata = os.urandom(nbytes)
     38 
     39     # Add the remaining random bits
     40     if rbits > 0:
     41         randomvalue = ord(os.urandom(1))
     42         randomvalue >>= (8 - rbits)
     43         randomdata = byte(randomvalue) + randomdata
     44 
     45     return randomdata
     46 
     47 
     48 def read_random_int(nbits):
     49     """Reads a random integer of approximately nbits bits.
     50     """
     51 
     52     randomdata = read_random_bits(nbits)
     53     value = transform.bytes2int(randomdata)
     54 
     55     # Ensure that the number is large enough to just fill out the required
     56     # number of bits.
     57     value |= 1 << (nbits - 1)
     58 
     59     return value
     60 
     61 
     62 def read_random_odd_int(nbits):
     63     """Reads a random odd integer of approximately nbits bits.
     64 
     65     >>> read_random_odd_int(512) & 1
     66     1
     67     """
     68 
     69     value = read_random_int(nbits)
     70 
     71     # Make sure it's odd
     72     return value | 1
     73 
     74 
     75 def randint(maxvalue):
     76     """Returns a random integer x with 1 <= x <= maxvalue
     77 
     78     May take a very long time in specific situations. If maxvalue needs N bits
     79     to store, the closer maxvalue is to (2 ** N) - 1, the faster this function
     80     is.
     81     """
     82 
     83     bit_size = common.bit_size(maxvalue)
     84 
     85     tries = 0
     86     while True:
     87         value = read_random_int(bit_size)
     88         if value <= maxvalue:
     89             break
     90 
     91         if tries % 10 == 0 and tries:
     92             # After a lot of tries to get the right number of bits but still
     93             # smaller than maxvalue, decrease the number of bits by 1. That'll
     94             # dramatically increase the chances to get a large enough number.
     95             bit_size -= 1
     96         tries += 1
     97 
     98     return value
     99