Add google-endpoints to third_party/.

third_party/google-endpoints/rsa/randnum.py

+# -*- coding: utf-8 -*-
+#
+#  Copyright 2011 Sybren A. Stüvel <sybren@stuvel.eu>
+#
+#  Licensed under the Apache License, Version 2.0 (the "License");
+#  you may not use this file except in compliance with the License.
+#  You may obtain a copy of the License at
+#
+#      https://www.apache.org/licenses/LICENSE-2.0
+#
+#  Unless required by applicable law or agreed to in writing, software
+#  distributed under the License is distributed on an "AS IS" BASIS,
+#  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+#  See the License for the specific language governing permissions and
+#  limitations under the License.
+
+"""Functions for generating random numbers."""
+
+# Source inspired by code by Yesudeep Mangalapilly <yesudeep@gmail.com>
+
+import os
+
+from rsa import common, transform
+from rsa._compat import byte
+
+
+def read_random_bits(nbits):
+    """Reads 'nbits' random bits.
+
+    If nbits isn't a whole number of bytes, an extra byte will be appended with
+    only the lower bits set.
+    """
+
+    nbytes, rbits = divmod(nbits, 8)
+
+    # Get the random bytes
+    randomdata = os.urandom(nbytes)
+
+    # Add the remaining random bits
+    if rbits > 0:
+        randomvalue = ord(os.urandom(1))
+        randomvalue >>= (8 - rbits)
+        randomdata = byte(randomvalue) + randomdata
+
+    return randomdata
+
+
+def read_random_int(nbits):
+    """Reads a random integer of approximately nbits bits.
+    """
+
+    randomdata = read_random_bits(nbits)
+    value = transform.bytes2int(randomdata)
+
+    # Ensure that the number is large enough to just fill out the required
+    # number of bits.
+    value |= 1 << (nbits - 1)
+
+    return value
+
+
+def read_random_odd_int(nbits):
+    """Reads a random odd integer of approximately nbits bits.
+
+    >>> read_random_odd_int(512) & 1
+    1
+    """
+
+    value = read_random_int(nbits)
+
+    # Make sure it's odd
+    return value | 1
+
+
+def randint(maxvalue):
+    """Returns a random integer x with 1 <= x <= maxvalue
+
+    May take a very long time in specific situations. If maxvalue needs N bits
+    to store, the closer maxvalue is to (2 ** N) - 1, the faster this function
+    is.
+    """
+
+    bit_size = common.bit_size(maxvalue)
+
+    tries = 0
+    while True:
+        value = read_random_int(bit_size)
+        if value <= maxvalue:
+            break
+
+        if tries and tries % 10 == 0:
+            # After a lot of tries to get the right number of bits but still
+            # smaller than maxvalue, decrease the number of bits by 1. That'll
+            # dramatically increase the chances to get a large enough number.
+            bit_size -= 1
+        tries += 1
+
+    return value