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