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