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