diff options
Diffstat (limited to 'frozen_deps/Cryptodome/Math/_IntegerBase.py')
| -rw-r--r-- | frozen_deps/Cryptodome/Math/_IntegerBase.py | 392 |
1 files changed, 392 insertions, 0 deletions
diff --git a/frozen_deps/Cryptodome/Math/_IntegerBase.py b/frozen_deps/Cryptodome/Math/_IntegerBase.py new file mode 100644 index 0000000..f8cf333 --- /dev/null +++ b/frozen_deps/Cryptodome/Math/_IntegerBase.py @@ -0,0 +1,392 @@ +# =================================================================== +# +# Copyright (c) 2018, Helder Eijs <helderijs@gmail.com> +# All rights reserved. +# +# Redistribution and use in source and binary forms, with or without +# modification, are permitted provided that the following conditions +# are met: +# +# 1. Redistributions of source code must retain the above copyright +# notice, this list of conditions and the following disclaimer. +# 2. Redistributions in binary form must reproduce the above copyright +# notice, this list of conditions and the following disclaimer in +# the documentation and/or other materials provided with the +# distribution. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS +# FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE +# COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, +# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, +# BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; +# LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER +# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +# LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN +# ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +# POSSIBILITY OF SUCH DAMAGE. +# =================================================================== + +import abc + +from Cryptodome.Util.py3compat import iter_range, bord, bchr, ABC + +from Cryptodome import Random + + +class IntegerBase(ABC): + + # Conversions + @abc.abstractmethod + def __int__(self): + pass + + @abc.abstractmethod + def __str__(self): + pass + + @abc.abstractmethod + def __repr__(self): + pass + + @abc.abstractmethod + def to_bytes(self, block_size=0): + pass + + @staticmethod + @abc.abstractmethod + def from_bytes(byte_string): + pass + + # Relations + @abc.abstractmethod + def __eq__(self, term): + pass + + @abc.abstractmethod + def __ne__(self, term): + pass + + @abc.abstractmethod + def __lt__(self, term): + pass + + @abc.abstractmethod + def __le__(self, term): + pass + + @abc.abstractmethod + def __gt__(self, term): + pass + + @abc.abstractmethod + def __ge__(self, term): + pass + + @abc.abstractmethod + def __nonzero__(self): + pass + __bool__ = __nonzero__ + + @abc.abstractmethod + def is_negative(self): + pass + + # Arithmetic operations + @abc.abstractmethod + def __add__(self, term): + pass + + @abc.abstractmethod + def __sub__(self, term): + pass + + @abc.abstractmethod + def __mul__(self, factor): + pass + + @abc.abstractmethod + def __floordiv__(self, divisor): + pass + + @abc.abstractmethod + def __mod__(self, divisor): + pass + + @abc.abstractmethod + def inplace_pow(self, exponent, modulus=None): + pass + + @abc.abstractmethod + def __pow__(self, exponent, modulus=None): + pass + + @abc.abstractmethod + def __abs__(self): + pass + + @abc.abstractmethod + def sqrt(self, modulus=None): + pass + + @abc.abstractmethod + def __iadd__(self, term): + pass + + @abc.abstractmethod + def __isub__(self, term): + pass + + @abc.abstractmethod + def __imul__(self, term): + pass + + @abc.abstractmethod + def __imod__(self, term): + pass + + # Boolean/bit operations + @abc.abstractmethod + def __and__(self, term): + pass + + @abc.abstractmethod + def __or__(self, term): + pass + + @abc.abstractmethod + def __rshift__(self, pos): + pass + + @abc.abstractmethod + def __irshift__(self, pos): + pass + + @abc.abstractmethod + def __lshift__(self, pos): + pass + + @abc.abstractmethod + def __ilshift__(self, pos): + pass + + @abc.abstractmethod + def get_bit(self, n): + pass + + # Extra + @abc.abstractmethod + def is_odd(self): + pass + + @abc.abstractmethod + def is_even(self): + pass + + @abc.abstractmethod + def size_in_bits(self): + pass + + @abc.abstractmethod + def size_in_bytes(self): + pass + + @abc.abstractmethod + def is_perfect_square(self): + pass + + @abc.abstractmethod + def fail_if_divisible_by(self, small_prime): + pass + + @abc.abstractmethod + def multiply_accumulate(self, a, b): + pass + + @abc.abstractmethod + def set(self, source): + pass + + @abc.abstractmethod + def inplace_inverse(self, modulus): + pass + + @abc.abstractmethod + def inverse(self, modulus): + pass + + @abc.abstractmethod + def gcd(self, term): + pass + + @abc.abstractmethod + def lcm(self, term): + pass + + @staticmethod + @abc.abstractmethod + def jacobi_symbol(a, n): + pass + + @staticmethod + def _tonelli_shanks(n, p): + """Tonelli-shanks algorithm for computing the square root + of n modulo a prime p. + + n must be in the range [0..p-1]. + p must be at least even. + + The return value r is the square root of modulo p. If non-zero, + another solution will also exist (p-r). + + Note we cannot assume that p is really a prime: if it's not, + we can either raise an exception or return the correct value. + """ + + # See https://rosettacode.org/wiki/Tonelli-Shanks_algorithm + + if n in (0, 1): + return n + + if p % 4 == 3: + root = pow(n, (p + 1) // 4, p) + if pow(root, 2, p) != n: + raise ValueError("Cannot compute square root") + return root + + s = 1 + q = (p - 1) // 2 + while not (q & 1): + s += 1 + q >>= 1 + + z = n.__class__(2) + while True: + euler = pow(z, (p - 1) // 2, p) + if euler == 1: + z += 1 + continue + if euler == p - 1: + break + # Most probably p is not a prime + raise ValueError("Cannot compute square root") + + m = s + c = pow(z, q, p) + t = pow(n, q, p) + r = pow(n, (q + 1) // 2, p) + + while t != 1: + for i in iter_range(0, m): + if pow(t, 2**i, p) == 1: + break + if i == m: + raise ValueError("Cannot compute square root of %d mod %d" % (n, p)) + b = pow(c, 2**(m - i - 1), p) + m = i + c = b**2 % p + t = (t * b**2) % p + r = (r * b) % p + + if pow(r, 2, p) != n: + raise ValueError("Cannot compute square root") + + return r + + @classmethod + def random(cls, **kwargs): + """Generate a random natural integer of a certain size. + + :Keywords: + exact_bits : positive integer + The length in bits of the resulting random Integer number. + The number is guaranteed to fulfil the relation: + + 2^bits > result >= 2^(bits - 1) + + max_bits : positive integer + The maximum length in bits of the resulting random Integer number. + The number is guaranteed to fulfil the relation: + + 2^bits > result >=0 + + randfunc : callable + A function that returns a random byte string. The length of the + byte string is passed as parameter. Optional. + If not provided (or ``None``), randomness is read from the system RNG. + + :Return: a Integer object + """ + + exact_bits = kwargs.pop("exact_bits", None) + max_bits = kwargs.pop("max_bits", None) + randfunc = kwargs.pop("randfunc", None) + + if randfunc is None: + randfunc = Random.new().read + + if exact_bits is None and max_bits is None: + raise ValueError("Either 'exact_bits' or 'max_bits' must be specified") + + if exact_bits is not None and max_bits is not None: + raise ValueError("'exact_bits' and 'max_bits' are mutually exclusive") + + bits = exact_bits or max_bits + bytes_needed = ((bits - 1) // 8) + 1 + significant_bits_msb = 8 - (bytes_needed * 8 - bits) + msb = bord(randfunc(1)[0]) + if exact_bits is not None: + msb |= 1 << (significant_bits_msb - 1) + msb &= (1 << significant_bits_msb) - 1 + + return cls.from_bytes(bchr(msb) + randfunc(bytes_needed - 1)) + + @classmethod + def random_range(cls, **kwargs): + """Generate a random integer within a given internal. + + :Keywords: + min_inclusive : integer + The lower end of the interval (inclusive). + max_inclusive : integer + The higher end of the interval (inclusive). + max_exclusive : integer + The higher end of the interval (exclusive). + randfunc : callable + A function that returns a random byte string. The length of the + byte string is passed as parameter. Optional. + If not provided (or ``None``), randomness is read from the system RNG. + :Returns: + An Integer randomly taken in the given interval. + """ + + min_inclusive = kwargs.pop("min_inclusive", None) + max_inclusive = kwargs.pop("max_inclusive", None) + max_exclusive = kwargs.pop("max_exclusive", None) + randfunc = kwargs.pop("randfunc", None) + + if kwargs: + raise ValueError("Unknown keywords: " + str(kwargs.keys)) + if None not in (max_inclusive, max_exclusive): + raise ValueError("max_inclusive and max_exclusive cannot be both" + " specified") + if max_exclusive is not None: + max_inclusive = max_exclusive - 1 + if None in (min_inclusive, max_inclusive): + raise ValueError("Missing keyword to identify the interval") + + if randfunc is None: + randfunc = Random.new().read + + norm_maximum = max_inclusive - min_inclusive + bits_needed = cls(norm_maximum).size_in_bits() + + norm_candidate = -1 + while not 0 <= norm_candidate <= norm_maximum: + norm_candidate = cls.random( + max_bits=bits_needed, + randfunc=randfunc + ) + return norm_candidate + min_inclusive + |