diff options
Diffstat (limited to 'frozen_deps/Cryptodome/Math')
| -rw-r--r-- | frozen_deps/Cryptodome/Math/Numbers.py | 42 | ||||
| -rw-r--r-- | frozen_deps/Cryptodome/Math/Numbers.pyi | 4 | ||||
| -rw-r--r-- | frozen_deps/Cryptodome/Math/Primality.py | 368 | ||||
| -rw-r--r-- | frozen_deps/Cryptodome/Math/Primality.pyi | 18 | ||||
| -rw-r--r-- | frozen_deps/Cryptodome/Math/_IntegerBase.py | 392 | ||||
| -rw-r--r-- | frozen_deps/Cryptodome/Math/_IntegerBase.pyi | 61 | ||||
| -rw-r--r-- | frozen_deps/Cryptodome/Math/_IntegerCustom.py | 111 | ||||
| -rw-r--r-- | frozen_deps/Cryptodome/Math/_IntegerCustom.pyi | 8 | ||||
| -rw-r--r-- | frozen_deps/Cryptodome/Math/_IntegerGMP.py | 708 | ||||
| -rw-r--r-- | frozen_deps/Cryptodome/Math/_IntegerGMP.pyi | 3 | ||||
| -rw-r--r-- | frozen_deps/Cryptodome/Math/_IntegerNative.py | 380 | ||||
| -rw-r--r-- | frozen_deps/Cryptodome/Math/_IntegerNative.pyi | 3 | ||||
| -rw-r--r-- | frozen_deps/Cryptodome/Math/__init__.py | 0 | ||||
| -rwxr-xr-x | frozen_deps/Cryptodome/Math/_modexp.cpython-38-x86_64-linux-gnu.so | bin | 0 -> 207274 bytes |
14 files changed, 2098 insertions, 0 deletions
diff --git a/frozen_deps/Cryptodome/Math/Numbers.py b/frozen_deps/Cryptodome/Math/Numbers.py new file mode 100644 index 0000000..c9ff848 --- /dev/null +++ b/frozen_deps/Cryptodome/Math/Numbers.py @@ -0,0 +1,42 @@ +# =================================================================== +# +# Copyright (c) 2014, Legrandin <[email protected]> +# 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. +# =================================================================== + +__all__ = ["Integer"] + +try: + from Cryptodome.Math._IntegerGMP import IntegerGMP as Integer + from Cryptodome.Math._IntegerGMP import implementation as _implementation +except (ImportError, OSError, AttributeError): + try: + from Cryptodome.Math._IntegerCustom import IntegerCustom as Integer + from Cryptodome.Math._IntegerCustom import implementation as _implementation + except (ImportError, OSError): + from Cryptodome.Math._IntegerNative import IntegerNative as Integer + _implementation = {} diff --git a/frozen_deps/Cryptodome/Math/Numbers.pyi b/frozen_deps/Cryptodome/Math/Numbers.pyi new file mode 100644 index 0000000..2285a3b --- /dev/null +++ b/frozen_deps/Cryptodome/Math/Numbers.pyi @@ -0,0 +1,4 @@ +from Cryptodome.Math._IntegerBase import IntegerBase + +class Integer(IntegerBase): + pass diff --git a/frozen_deps/Cryptodome/Math/Primality.py b/frozen_deps/Cryptodome/Math/Primality.py new file mode 100644 index 0000000..08ea3ff --- /dev/null +++ b/frozen_deps/Cryptodome/Math/Primality.py @@ -0,0 +1,368 @@ +# =================================================================== +# +# Copyright (c) 2014, Legrandin <[email protected]> +# 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. +# =================================================================== + +"""Functions to create and test prime numbers. + +:undocumented: __package__ +""" + +from Cryptodome import Random +from Cryptodome.Math.Numbers import Integer + +from Cryptodome.Util.py3compat import iter_range + +COMPOSITE = 0 +PROBABLY_PRIME = 1 + + +def miller_rabin_test(candidate, iterations, randfunc=None): + """Perform a Miller-Rabin primality test on an integer. + + The test is specified in Section C.3.1 of `FIPS PUB 186-4`__. + + :Parameters: + candidate : integer + The number to test for primality. + iterations : integer + The maximum number of iterations to perform before + declaring a candidate a probable prime. + randfunc : callable + An RNG function where bases are taken from. + + :Returns: + ``Primality.COMPOSITE`` or ``Primality.PROBABLY_PRIME``. + + .. __: http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf + """ + + if not isinstance(candidate, Integer): + candidate = Integer(candidate) + + if candidate in (1, 2, 3, 5): + return PROBABLY_PRIME + + if candidate.is_even(): + return COMPOSITE + + one = Integer(1) + minus_one = Integer(candidate - 1) + + if randfunc is None: + randfunc = Random.new().read + + # Step 1 and 2 + m = Integer(minus_one) + a = 0 + while m.is_even(): + m >>= 1 + a += 1 + + # Skip step 3 + + # Step 4 + for i in iter_range(iterations): + + # Step 4.1-2 + base = 1 + while base in (one, minus_one): + base = Integer.random_range(min_inclusive=2, + max_inclusive=candidate - 2) + assert(2 <= base <= candidate - 2) + + # Step 4.3-4.4 + z = pow(base, m, candidate) + if z in (one, minus_one): + continue + + # Step 4.5 + for j in iter_range(1, a): + z = pow(z, 2, candidate) + if z == minus_one: + break + if z == one: + return COMPOSITE + else: + return COMPOSITE + + # Step 5 + return PROBABLY_PRIME + + +def lucas_test(candidate): + """Perform a Lucas primality test on an integer. + + The test is specified in Section C.3.3 of `FIPS PUB 186-4`__. + + :Parameters: + candidate : integer + The number to test for primality. + + :Returns: + ``Primality.COMPOSITE`` or ``Primality.PROBABLY_PRIME``. + + .. __: http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf + """ + + if not isinstance(candidate, Integer): + candidate = Integer(candidate) + + # Step 1 + if candidate in (1, 2, 3, 5): + return PROBABLY_PRIME + if candidate.is_even() or candidate.is_perfect_square(): + return COMPOSITE + + # Step 2 + def alternate(): + value = 5 + while True: + yield value + if value > 0: + value += 2 + else: + value -= 2 + value = -value + + for D in alternate(): + if candidate in (D, -D): + continue + js = Integer.jacobi_symbol(D, candidate) + if js == 0: + return COMPOSITE + if js == -1: + break + # Found D. P=1 and Q=(1-D)/4 (note that Q is guaranteed to be an integer) + + # Step 3 + # This is \delta(n) = n - jacobi(D/n) + K = candidate + 1 + # Step 4 + r = K.size_in_bits() - 1 + # Step 5 + # U_1=1 and V_1=P + U_i = Integer(1) + V_i = Integer(1) + U_temp = Integer(0) + V_temp = Integer(0) + # Step 6 + for i in iter_range(r - 1, -1, -1): + # Square + # U_temp = U_i * V_i % candidate + U_temp.set(U_i) + U_temp *= V_i + U_temp %= candidate + # V_temp = (((V_i ** 2 + (U_i ** 2 * D)) * K) >> 1) % candidate + V_temp.set(U_i) + V_temp *= U_i + V_temp *= D + V_temp.multiply_accumulate(V_i, V_i) + if V_temp.is_odd(): + V_temp += candidate + V_temp >>= 1 + V_temp %= candidate + # Multiply + if K.get_bit(i): + # U_i = (((U_temp + V_temp) * K) >> 1) % candidate + U_i.set(U_temp) + U_i += V_temp + if U_i.is_odd(): + U_i += candidate + U_i >>= 1 + U_i %= candidate + # V_i = (((V_temp + U_temp * D) * K) >> 1) % candidate + V_i.set(V_temp) + V_i.multiply_accumulate(U_temp, D) + if V_i.is_odd(): + V_i += candidate + V_i >>= 1 + V_i %= candidate + else: + U_i.set(U_temp) + V_i.set(V_temp) + # Step 7 + if U_i == 0: + return PROBABLY_PRIME + return COMPOSITE + + +from Cryptodome.Util.number import sieve_base as _sieve_base_large +## The optimal number of small primes to use for the sieve +## is probably dependent on the platform and the candidate size +_sieve_base = set(_sieve_base_large[:100]) + + +def test_probable_prime(candidate, randfunc=None): + """Test if a number is prime. + + A number is qualified as prime if it passes a certain + number of Miller-Rabin tests (dependent on the size + of the number, but such that probability of a false + positive is less than 10^-30) and a single Lucas test. + + For instance, a 1024-bit candidate will need to pass + 4 Miller-Rabin tests. + + :Parameters: + candidate : integer + The number to test for primality. + randfunc : callable + The routine to draw random bytes from to select Miller-Rabin bases. + :Returns: + ``PROBABLE_PRIME`` if the number if prime with very high probability. + ``COMPOSITE`` if the number is a composite. + For efficiency reasons, ``COMPOSITE`` is also returned for small primes. + """ + + if randfunc is None: + randfunc = Random.new().read + + if not isinstance(candidate, Integer): + candidate = Integer(candidate) + + # First, check trial division by the smallest primes + if int(candidate) in _sieve_base: + return PROBABLY_PRIME + try: + map(candidate.fail_if_divisible_by, _sieve_base) + except ValueError: + return COMPOSITE + + # These are the number of Miller-Rabin iterations s.t. p(k, t) < 1E-30, + # with p(k, t) being the probability that a randomly chosen k-bit number + # is composite but still survives t MR iterations. + mr_ranges = ((220, 30), (280, 20), (390, 15), (512, 10), + (620, 7), (740, 6), (890, 5), (1200, 4), + (1700, 3), (3700, 2)) + + bit_size = candidate.size_in_bits() + try: + mr_iterations = list(filter(lambda x: bit_size < x[0], + mr_ranges))[0][1] + except IndexError: + mr_iterations = 1 + + if miller_rabin_test(candidate, mr_iterations, + randfunc=randfunc) == COMPOSITE: + return COMPOSITE + if lucas_test(candidate) == COMPOSITE: + return COMPOSITE + return PROBABLY_PRIME + + +def generate_probable_prime(**kwargs): + """Generate a random probable prime. + + The prime will not have any specific properties + (e.g. it will not be a *strong* prime). + + Random numbers are evaluated for primality until one + passes all tests, consisting of a certain number of + Miller-Rabin tests with random bases followed by + a single Lucas test. + + The number of Miller-Rabin iterations is chosen such that + the probability that the output number is a non-prime is + less than 1E-30 (roughly 2^{-100}). + + This approach is compliant to `FIPS PUB 186-4`__. + + :Keywords: + exact_bits : integer + The desired size in bits of the probable prime. + It must be at least 160. + randfunc : callable + An RNG function where candidate primes are taken from. + prime_filter : callable + A function that takes an Integer as parameter and returns + True if the number can be passed to further primality tests, + False if it should be immediately discarded. + + :Return: + A probable prime in the range 2^exact_bits > p > 2^(exact_bits-1). + + .. __: http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf + """ + + exact_bits = kwargs.pop("exact_bits", None) + randfunc = kwargs.pop("randfunc", None) + prime_filter = kwargs.pop("prime_filter", lambda x: True) + if kwargs: + raise ValueError("Unknown parameters: " + kwargs.keys()) + + if exact_bits is None: + raise ValueError("Missing exact_bits parameter") + if exact_bits < 160: + raise ValueError("Prime number is not big enough.") + + if randfunc is None: + randfunc = Random.new().read + + result = COMPOSITE + while result == COMPOSITE: + candidate = Integer.random(exact_bits=exact_bits, + randfunc=randfunc) | 1 + if not prime_filter(candidate): + continue + result = test_probable_prime(candidate, randfunc) + return candidate + + +def generate_probable_safe_prime(**kwargs): + """Generate a random, probable safe prime. + + Note this operation is much slower than generating a simple prime. + + :Keywords: + exact_bits : integer + The desired size in bits of the probable safe prime. + randfunc : callable + An RNG function where candidate primes are taken from. + + :Return: + A probable safe prime in the range + 2^exact_bits > p > 2^(exact_bits-1). + """ + + exact_bits = kwargs.pop("exact_bits", None) + randfunc = kwargs.pop("randfunc", None) + if kwargs: + raise ValueError("Unknown parameters: " + kwargs.keys()) + + if randfunc is None: + randfunc = Random.new().read + + result = COMPOSITE + while result == COMPOSITE: + q = generate_probable_prime(exact_bits=exact_bits - 1, randfunc=randfunc) + candidate = q * 2 + 1 + if candidate.size_in_bits() != exact_bits: + continue + result = test_probable_prime(candidate, randfunc=randfunc) + return candidate diff --git a/frozen_deps/Cryptodome/Math/Primality.pyi b/frozen_deps/Cryptodome/Math/Primality.pyi new file mode 100644 index 0000000..7813483 --- /dev/null +++ b/frozen_deps/Cryptodome/Math/Primality.pyi @@ -0,0 +1,18 @@ +from typing import Callable, Optional, Union, Set + +PrimeResult = int + +COMPOSITE: PrimeResult +PROBABLY_PRIME: PrimeResult + +def miller_rabin_test(candidate: int, iterations: int, randfunc: Optional[Callable[[int],bytes]]=None) -> PrimeResult: ... +def lucas_test(candidate: int) -> PrimeResult: ... +_sieve_base: Set[int] +def test_probable_prime(candidate: int, randfunc: Optional[Callable[[int],bytes]]=None) -> PrimeResult: ... +def generate_probable_prime(*, + exact_bits: int = ..., + randfunc: Callable[[int],bytes] = ..., + prime_filter: Callable[[int],bool] = ...) -> int: ... +def generate_probable_safe_prime(*, + exact_bits: int = ..., + randfunc: Callable[[int],bytes] = ...) -> int: ... 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 <[email protected]> +# 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 + diff --git a/frozen_deps/Cryptodome/Math/_IntegerBase.pyi b/frozen_deps/Cryptodome/Math/_IntegerBase.pyi new file mode 100644 index 0000000..3f534db --- /dev/null +++ b/frozen_deps/Cryptodome/Math/_IntegerBase.pyi @@ -0,0 +1,61 @@ +from typing import Optional, Union, Callable + +RandFunc = Callable[[int],int] + +class IntegerBase: + + def __int__(self) -> int: ... + def __str__(self) -> str: ... + def __repr__(self) -> str: ... + def to_bytes(self, block_size: Optional[int]=0) -> bytes: ... + @staticmethod + def from_bytes(byte_string: bytes) -> IntegerBase: ... + def __eq__(self, term: object) -> bool: ... + def __ne__(self, term: object) -> bool: ... + def __lt__(self, term: Union[IntegerBase, int]) -> bool: ... + def __le__(self, term: Union[IntegerBase, int]) -> bool: ... + def __gt__(self, term: Union[IntegerBase, int]) -> bool: ... + def __ge__(self, term: Union[IntegerBase, int]) -> bool: ... + def __nonzero__(self) -> bool: ... + def is_negative(self) -> bool: ... + def __add__(self, term: Union[IntegerBase, int]) -> IntegerBase: ... + def __sub__(self, term: Union[IntegerBase, int]) -> IntegerBase: ... + def __mul__(self, term: Union[IntegerBase, int]) -> IntegerBase: ... + def __floordiv__(self, divisor: Union[IntegerBase, int]) -> IntegerBase: ... + def __mod__(self, divisor: Union[IntegerBase, int]) -> IntegerBase: ... + def inplace_pow(self, exponent: int, modulus: Optional[Union[IntegerBase, int]]=None) -> IntegerBase: ... + def __pow__(self, exponent: int, modulus: Optional[int]) -> IntegerBase: ... + def __abs__(self) -> IntegerBase: ... + def sqrt(self, modulus: Optional[int]) -> IntegerBase: ... + def __iadd__(self, term: Union[IntegerBase, int]) -> IntegerBase: ... + def __isub__(self, term: Union[IntegerBase, int]) -> IntegerBase: ... + def __imul__(self, term: Union[IntegerBase, int]) -> IntegerBase: ... + def __imod__(self, divisor: Union[IntegerBase, int]) -> IntegerBase: ... + def __and__(self, term: Union[IntegerBase, int]) -> IntegerBase: ... + def __or__(self, term: Union[IntegerBase, int]) -> IntegerBase: ... + def __rshift__(self, pos: Union[IntegerBase, int]) -> IntegerBase: ... + def __irshift__(self, pos: Union[IntegerBase, int]) -> IntegerBase: ... + def __lshift__(self, pos: Union[IntegerBase, int]) -> IntegerBase: ... + def __ilshift__(self, pos: Union[IntegerBase, int]) -> IntegerBase: ... + def get_bit(self, n: int) -> bool: ... + def is_odd(self) -> bool: ... + def is_even(self) -> bool: ... + def size_in_bits(self) -> int: ... + def size_in_bytes(self) -> int: ... + def is_perfect_square(self) -> bool: ... + def fail_if_divisible_by(self, small_prime: Union[IntegerBase, int]) -> None: ... + def multiply_accumulate(self, a: Union[IntegerBase, int], b: Union[IntegerBase, int]) -> IntegerBase: ... + def set(self, source: Union[IntegerBase, int]) -> IntegerBase: ... + def inplace_inverse(self, modulus: Union[IntegerBase, int]) -> IntegerBase: ... + def inverse(self, modulus: Union[IntegerBase, int]) -> IntegerBase: ... + def gcd(self, term: Union[IntegerBase, int]) -> IntegerBase: ... + def lcm(self, term: Union[IntegerBase, int]) -> IntegerBase: ... + @staticmethod + def jacobi_symbol(a: Union[IntegerBase, int], n: Union[IntegerBase, int]) -> IntegerBase: ... + @staticmethod + def _tonelli_shanks(n: Union[IntegerBase, int], p: Union[IntegerBase, int]) -> IntegerBase : ... + @classmethod + def random(cls, **kwargs: Union[int,RandFunc]) -> IntegerBase : ... + @classmethod + def random_range(cls, **kwargs: Union[int,RandFunc]) -> IntegerBase : ... + diff --git a/frozen_deps/Cryptodome/Math/_IntegerCustom.py b/frozen_deps/Cryptodome/Math/_IntegerCustom.py new file mode 100644 index 0000000..b626014 --- /dev/null +++ b/frozen_deps/Cryptodome/Math/_IntegerCustom.py @@ -0,0 +1,111 @@ +# =================================================================== +# +# Copyright (c) 2018, Helder Eijs <[email protected]> +# 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. +# =================================================================== + +from ._IntegerNative import IntegerNative + +from Cryptodome.Util.number import long_to_bytes, bytes_to_long + +from Cryptodome.Util._raw_api import (load_pycryptodome_raw_lib, + create_string_buffer, + get_raw_buffer, backend, + c_size_t, c_ulonglong) + + +from Cryptodome.Random.random import getrandbits + +c_defs = """ +int monty_pow(const uint8_t *base, + const uint8_t *exp, + const uint8_t *modulus, + uint8_t *out, + size_t len, + uint64_t seed); +""" + + +_raw_montgomery = load_pycryptodome_raw_lib("Cryptodome.Math._modexp", c_defs) +implementation = {"library": "custom", "api": backend} + + +class IntegerCustom(IntegerNative): + + @staticmethod + def from_bytes(byte_string): + return IntegerCustom(bytes_to_long(byte_string)) + + def inplace_pow(self, exponent, modulus=None): + exp_value = int(exponent) + if exp_value < 0: + raise ValueError("Exponent must not be negative") + + # No modular reduction + if modulus is None: + self._value = pow(self._value, exp_value) + return self + + # With modular reduction + mod_value = int(modulus) + if mod_value < 0: + raise ValueError("Modulus must be positive") + if mod_value == 0: + raise ZeroDivisionError("Modulus cannot be zero") + + # C extension only works with odd moduli + if (mod_value & 1) == 0: + self._value = pow(self._value, exp_value, mod_value) + return self + + # C extension only works with bases smaller than modulus + if self._value >= mod_value: + self._value %= mod_value + + max_len = len(long_to_bytes(max(self._value, exp_value, mod_value))) + + base_b = long_to_bytes(self._value, max_len) + exp_b = long_to_bytes(exp_value, max_len) + modulus_b = long_to_bytes(mod_value, max_len) + + out = create_string_buffer(max_len) + + error = _raw_montgomery.monty_pow( + out, + base_b, + exp_b, + modulus_b, + c_size_t(max_len), + c_ulonglong(getrandbits(64)) + ) + + if error: + raise ValueError("monty_pow failed with error: %d" % error) + + result = bytes_to_long(get_raw_buffer(out)) + self._value = result + return self diff --git a/frozen_deps/Cryptodome/Math/_IntegerCustom.pyi b/frozen_deps/Cryptodome/Math/_IntegerCustom.pyi new file mode 100644 index 0000000..2dd75c7 --- /dev/null +++ b/frozen_deps/Cryptodome/Math/_IntegerCustom.pyi @@ -0,0 +1,8 @@ +from typing import Any + +from ._IntegerNative import IntegerNative + +_raw_montgomery = Any + +class IntegerCustom(IntegerNative): + pass diff --git a/frozen_deps/Cryptodome/Math/_IntegerGMP.py b/frozen_deps/Cryptodome/Math/_IntegerGMP.py new file mode 100644 index 0000000..c860020 --- /dev/null +++ b/frozen_deps/Cryptodome/Math/_IntegerGMP.py @@ -0,0 +1,708 @@ +# =================================================================== +# +# Copyright (c) 2014, Legrandin <[email protected]> +# 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 sys + +from Cryptodome.Util.py3compat import tobytes, is_native_int + +from Cryptodome.Util._raw_api import (backend, load_lib, + get_raw_buffer, get_c_string, + null_pointer, create_string_buffer, + c_ulong, c_size_t) + +from ._IntegerBase import IntegerBase + +gmp_defs = """typedef unsigned long UNIX_ULONG; + typedef struct { int a; int b; void *c; } MPZ; + typedef MPZ mpz_t[1]; + typedef UNIX_ULONG mp_bitcnt_t; + void __gmpz_init (mpz_t x); + void __gmpz_init_set (mpz_t rop, const mpz_t op); + void __gmpz_init_set_ui (mpz_t rop, UNIX_ULONG op); + int __gmp_sscanf (const char *s, const char *fmt, ...); + void __gmpz_set (mpz_t rop, const mpz_t op); + int __gmp_snprintf (uint8_t *buf, size_t size, const char *fmt, ...); + void __gmpz_add (mpz_t rop, const mpz_t op1, const mpz_t op2); + void __gmpz_add_ui (mpz_t rop, const mpz_t op1, UNIX_ULONG op2); + void __gmpz_sub_ui (mpz_t rop, const mpz_t op1, UNIX_ULONG op2); + void __gmpz_addmul (mpz_t rop, const mpz_t op1, const mpz_t op2); + void __gmpz_addmul_ui (mpz_t rop, const mpz_t op1, UNIX_ULONG op2); + void __gmpz_submul_ui (mpz_t rop, const mpz_t op1, UNIX_ULONG op2); + void __gmpz_import (mpz_t rop, size_t count, int order, size_t size, + int endian, size_t nails, const void *op); + void * __gmpz_export (void *rop, size_t *countp, int order, + size_t size, + int endian, size_t nails, const mpz_t op); + size_t __gmpz_sizeinbase (const mpz_t op, int base); + void __gmpz_sub (mpz_t rop, const mpz_t op1, const mpz_t op2); + void __gmpz_mul (mpz_t rop, const mpz_t op1, const mpz_t op2); + void __gmpz_mul_ui (mpz_t rop, const mpz_t op1, UNIX_ULONG op2); + int __gmpz_cmp (const mpz_t op1, const mpz_t op2); + void __gmpz_powm (mpz_t rop, const mpz_t base, const mpz_t exp, const + mpz_t mod); + void __gmpz_powm_ui (mpz_t rop, const mpz_t base, UNIX_ULONG exp, + const mpz_t mod); + void __gmpz_pow_ui (mpz_t rop, const mpz_t base, UNIX_ULONG exp); + void __gmpz_sqrt(mpz_t rop, const mpz_t op); + void __gmpz_mod (mpz_t r, const mpz_t n, const mpz_t d); + void __gmpz_neg (mpz_t rop, const mpz_t op); + void __gmpz_abs (mpz_t rop, const mpz_t op); + void __gmpz_and (mpz_t rop, const mpz_t op1, const mpz_t op2); + void __gmpz_ior (mpz_t rop, const mpz_t op1, const mpz_t op2); + void __gmpz_clear (mpz_t x); + void __gmpz_tdiv_q_2exp (mpz_t q, const mpz_t n, mp_bitcnt_t b); + void __gmpz_fdiv_q (mpz_t q, const mpz_t n, const mpz_t d); + void __gmpz_mul_2exp (mpz_t rop, const mpz_t op1, mp_bitcnt_t op2); + int __gmpz_tstbit (const mpz_t op, mp_bitcnt_t bit_index); + int __gmpz_perfect_square_p (const mpz_t op); + int __gmpz_jacobi (const mpz_t a, const mpz_t b); + void __gmpz_gcd (mpz_t rop, const mpz_t op1, const mpz_t op2); + UNIX_ULONG __gmpz_gcd_ui (mpz_t rop, const mpz_t op1, + UNIX_ULONG op2); + void __gmpz_lcm (mpz_t rop, const mpz_t op1, const mpz_t op2); + int __gmpz_invert (mpz_t rop, const mpz_t op1, const mpz_t op2); + int __gmpz_divisible_p (const mpz_t n, const mpz_t d); + int __gmpz_divisible_ui_p (const mpz_t n, UNIX_ULONG d); + """ + +if sys.platform == "win32": + raise ImportError("Not using GMP on Windows") + +lib = load_lib("gmp", gmp_defs) +implementation = {"library": "gmp", "api": backend} + +if hasattr(lib, "__mpir_version"): + raise ImportError("MPIR library detected") + +# In order to create a function that returns a pointer to +# a new MPZ structure, we need to break the abstraction +# and know exactly what ffi backend we have +if implementation["api"] == "ctypes": + from ctypes import Structure, c_int, c_void_p, byref + + class _MPZ(Structure): + _fields_ = [('_mp_alloc', c_int), + ('_mp_size', c_int), + ('_mp_d', c_void_p)] + + def new_mpz(): + return byref(_MPZ()) + +else: + # We are using CFFI + from Cryptodome.Util._raw_api import ffi + + def new_mpz(): + return ffi.new("MPZ*") + + +# Lazy creation of GMP methods +class _GMP(object): + + def __getattr__(self, name): + if name.startswith("mpz_"): + func_name = "__gmpz_" + name[4:] + elif name.startswith("gmp_"): + func_name = "__gmp_" + name[4:] + else: + raise AttributeError("Attribute %s is invalid" % name) + func = getattr(lib, func_name) + setattr(self, name, func) + return func + + +_gmp = _GMP() + + +class IntegerGMP(IntegerBase): + """A fast, arbitrary precision integer""" + + _zero_mpz_p = new_mpz() + _gmp.mpz_init_set_ui(_zero_mpz_p, c_ulong(0)) + + def __init__(self, value): + """Initialize the integer to the given value.""" + + self._mpz_p = new_mpz() + self._initialized = False + + if isinstance(value, float): + raise ValueError("A floating point type is not a natural number") + + self._initialized = True + + if is_native_int(value): + _gmp.mpz_init(self._mpz_p) + result = _gmp.gmp_sscanf(tobytes(str(value)), b"%Zd", self._mpz_p) + if result != 1: + raise ValueError("Error converting '%d'" % value) + elif isinstance(value, IntegerGMP): + _gmp.mpz_init_set(self._mpz_p, value._mpz_p) + else: + raise NotImplementedError + + # Conversions + def __int__(self): + # buf will contain the integer encoded in decimal plus the trailing + # zero, and possibly the negative sign. + # dig10(x) < log10(x) + 1 = log2(x)/log2(10) + 1 < log2(x)/3 + 1 + buf_len = _gmp.mpz_sizeinbase(self._mpz_p, 2) // 3 + 3 + buf = create_string_buffer(buf_len) + + _gmp.gmp_snprintf(buf, c_size_t(buf_len), b"%Zd", self._mpz_p) + return int(get_c_string(buf)) + + def __str__(self): + return str(int(self)) + + def __repr__(self): + return "Integer(%s)" % str(self) + + # Only Python 2.x + def __hex__(self): + return hex(int(self)) + + # Only Python 3.x + def __index__(self): + return int(self) + + def to_bytes(self, block_size=0): + """Convert the number into a byte string. + + This method encodes the number in network order and prepends + as many zero bytes as required. It only works for non-negative + values. + + :Parameters: + block_size : integer + The exact size the output byte string must have. + If zero, the string has the minimal length. + :Returns: + A byte string. + :Raise ValueError: + If the value is negative or if ``block_size`` is + provided and the length of the byte string would exceed it. + """ + + if self < 0: + raise ValueError("Conversion only valid for non-negative numbers") + + buf_len = (_gmp.mpz_sizeinbase(self._mpz_p, 2) + 7) // 8 + if buf_len > block_size > 0: + raise ValueError("Number is too big to convert to byte string" + "of prescribed length") + buf = create_string_buffer(buf_len) + + _gmp.mpz_export( + buf, + null_pointer, # Ignore countp + 1, # Big endian + c_size_t(1), # Each word is 1 byte long + 0, # Endianess within a word - not relevant + c_size_t(0), # No nails + self._mpz_p) + + return b'\x00' * max(0, block_size - buf_len) + get_raw_buffer(buf) + + @staticmethod + def from_bytes(byte_string): + """Convert a byte string into a number. + + :Parameters: + byte_string : byte string + The input number, encoded in network order. + It can only be non-negative. + :Return: + The ``Integer`` object carrying the same value as the input. + """ + result = IntegerGMP(0) + _gmp.mpz_import( + result._mpz_p, + c_size_t(len(byte_string)), # Amount of words to read + 1, # Big endian + c_size_t(1), # Each word is 1 byte long + 0, # Endianess within a word - not relevant + c_size_t(0), # No nails + byte_string) + return result + + # Relations + def _apply_and_return(self, func, term): + if not isinstance(term, IntegerGMP): + term = IntegerGMP(term) + return func(self._mpz_p, term._mpz_p) + + def __eq__(self, term): + if not (isinstance(term, IntegerGMP) or is_native_int(term)): + return False + return self._apply_and_return(_gmp.mpz_cmp, term) == 0 + + def __ne__(self, term): + if not (isinstance(term, IntegerGMP) or is_native_int(term)): + return True + return self._apply_and_return(_gmp.mpz_cmp, term) != 0 + + def __lt__(self, term): + return self._apply_and_return(_gmp.mpz_cmp, term) < 0 + + def __le__(self, term): + return self._apply_and_return(_gmp.mpz_cmp, term) <= 0 + + def __gt__(self, term): + return self._apply_and_return(_gmp.mpz_cmp, term) > 0 + + def __ge__(self, term): + return self._apply_and_return(_gmp.mpz_cmp, term) >= 0 + + def __nonzero__(self): + return _gmp.mpz_cmp(self._mpz_p, self._zero_mpz_p) != 0 + __bool__ = __nonzero__ + + def is_negative(self): + return _gmp.mpz_cmp(self._mpz_p, self._zero_mpz_p) < 0 + + # Arithmetic operations + def __add__(self, term): + result = IntegerGMP(0) + if not isinstance(term, IntegerGMP): + try: + term = IntegerGMP(term) + except NotImplementedError: + return NotImplemented + _gmp.mpz_add(result._mpz_p, + self._mpz_p, + term._mpz_p) + return result + + def __sub__(self, term): + result = IntegerGMP(0) + if not isinstance(term, IntegerGMP): + try: + term = IntegerGMP(term) + except NotImplementedError: + return NotImplemented + _gmp.mpz_sub(result._mpz_p, + self._mpz_p, + term._mpz_p) + return result + + def __mul__(self, term): + result = IntegerGMP(0) + if not isinstance(term, IntegerGMP): + try: + term = IntegerGMP(term) + except NotImplementedError: + return NotImplemented + _gmp.mpz_mul(result._mpz_p, + self._mpz_p, + term._mpz_p) + return result + + def __floordiv__(self, divisor): + if not isinstance(divisor, IntegerGMP): + divisor = IntegerGMP(divisor) + if _gmp.mpz_cmp(divisor._mpz_p, + self._zero_mpz_p) == 0: + raise ZeroDivisionError("Division by zero") + result = IntegerGMP(0) + _gmp.mpz_fdiv_q(result._mpz_p, + self._mpz_p, + divisor._mpz_p) + return result + + def __mod__(self, divisor): + if not isinstance(divisor, IntegerGMP): + divisor = IntegerGMP(divisor) + comp = _gmp.mpz_cmp(divisor._mpz_p, + self._zero_mpz_p) + if comp == 0: + raise ZeroDivisionError("Division by zero") + if comp < 0: + raise ValueError("Modulus must be positive") + result = IntegerGMP(0) + _gmp.mpz_mod(result._mpz_p, + self._mpz_p, + divisor._mpz_p) + return result + + def inplace_pow(self, exponent, modulus=None): + + if modulus is None: + if exponent < 0: + raise ValueError("Exponent must not be negative") + + # Normal exponentiation + if exponent > 256: + raise ValueError("Exponent is too big") + _gmp.mpz_pow_ui(self._mpz_p, + self._mpz_p, # Base + c_ulong(int(exponent)) + ) + else: + # Modular exponentiation + if not isinstance(modulus, IntegerGMP): + modulus = IntegerGMP(modulus) + if not modulus: + raise ZeroDivisionError("Division by zero") + if modulus.is_negative(): + raise ValueError("Modulus must be positive") + if is_native_int(exponent): + if exponent < 0: + raise ValueError("Exponent must not be negative") + if exponent < 65536: + _gmp.mpz_powm_ui(self._mpz_p, + self._mpz_p, + c_ulong(exponent), + modulus._mpz_p) + return self + exponent = IntegerGMP(exponent) + elif exponent.is_negative(): + raise ValueError("Exponent must not be negative") + _gmp.mpz_powm(self._mpz_p, + self._mpz_p, + exponent._mpz_p, + modulus._mpz_p) + return self + + def __pow__(self, exponent, modulus=None): + result = IntegerGMP(self) + return result.inplace_pow(exponent, modulus) + + def __abs__(self): + result = IntegerGMP(0) + _gmp.mpz_abs(result._mpz_p, self._mpz_p) + return result + + def sqrt(self, modulus=None): + """Return the largest Integer that does not + exceed the square root""" + + if modulus is None: + if self < 0: + raise ValueError("Square root of negative value") + result = IntegerGMP(0) + _gmp.mpz_sqrt(result._mpz_p, + self._mpz_p) + else: + if modulus <= 0: + raise ValueError("Modulus must be positive") + modulus = int(modulus) + result = IntegerGMP(self._tonelli_shanks(int(self) % modulus, modulus)) + + return result + + def __iadd__(self, term): + if is_native_int(term): + if 0 <= term < 65536: + _gmp.mpz_add_ui(self._mpz_p, + self._mpz_p, + c_ulong(term)) + return self + if -65535 < term < 0: + _gmp.mpz_sub_ui(self._mpz_p, + self._mpz_p, + c_ulong(-term)) + return self + term = IntegerGMP(term) + _gmp.mpz_add(self._mpz_p, + self._mpz_p, + term._mpz_p) + return self + + def __isub__(self, term): + if is_native_int(term): + if 0 <= term < 65536: + _gmp.mpz_sub_ui(self._mpz_p, + self._mpz_p, + c_ulong(term)) + return self + if -65535 < term < 0: + _gmp.mpz_add_ui(self._mpz_p, + self._mpz_p, + c_ulong(-term)) + return self + term = IntegerGMP(term) + _gmp.mpz_sub(self._mpz_p, + self._mpz_p, + term._mpz_p) + return self + + def __imul__(self, term): + if is_native_int(term): + if 0 <= term < 65536: + _gmp.mpz_mul_ui(self._mpz_p, + self._mpz_p, + c_ulong(term)) + return self + if -65535 < term < 0: + _gmp.mpz_mul_ui(self._mpz_p, + self._mpz_p, + c_ulong(-term)) + _gmp.mpz_neg(self._mpz_p, self._mpz_p) + return self + term = IntegerGMP(term) + _gmp.mpz_mul(self._mpz_p, + self._mpz_p, + term._mpz_p) + return self + + def __imod__(self, divisor): + if not isinstance(divisor, IntegerGMP): + divisor = IntegerGMP(divisor) + comp = _gmp.mpz_cmp(divisor._mpz_p, + divisor._zero_mpz_p) + if comp == 0: + raise ZeroDivisionError("Division by zero") + if comp < 0: + raise ValueError("Modulus must be positive") + _gmp.mpz_mod(self._mpz_p, + self._mpz_p, + divisor._mpz_p) + return self + + # Boolean/bit operations + def __and__(self, term): + result = IntegerGMP(0) + if not isinstance(term, IntegerGMP): + term = IntegerGMP(term) + _gmp.mpz_and(result._mpz_p, + self._mpz_p, + term._mpz_p) + return result + + def __or__(self, term): + result = IntegerGMP(0) + if not isinstance(term, IntegerGMP): + term = IntegerGMP(term) + _gmp.mpz_ior(result._mpz_p, + self._mpz_p, + term._mpz_p) + return result + + def __rshift__(self, pos): + result = IntegerGMP(0) + if pos < 0: + raise ValueError("negative shift count") + if pos > 65536: + if self < 0: + return -1 + else: + return 0 + _gmp.mpz_tdiv_q_2exp(result._mpz_p, + self._mpz_p, + c_ulong(int(pos))) + return result + + def __irshift__(self, pos): + if pos < 0: + raise ValueError("negative shift count") + if pos > 65536: + if self < 0: + return -1 + else: + return 0 + _gmp.mpz_tdiv_q_2exp(self._mpz_p, + self._mpz_p, + c_ulong(int(pos))) + return self + + def __lshift__(self, pos): + result = IntegerGMP(0) + if not 0 <= pos < 65536: + raise ValueError("Incorrect shift count") + _gmp.mpz_mul_2exp(result._mpz_p, + self._mpz_p, + c_ulong(int(pos))) + return result + + def __ilshift__(self, pos): + if not 0 <= pos < 65536: + raise ValueError("Incorrect shift count") + _gmp.mpz_mul_2exp(self._mpz_p, + self._mpz_p, + c_ulong(int(pos))) + return self + + def get_bit(self, n): + """Return True if the n-th bit is set to 1. + Bit 0 is the least significant.""" + + if self < 0: + raise ValueError("no bit representation for negative values") + if n < 0: + raise ValueError("negative bit count") + if n > 65536: + return 0 + return bool(_gmp.mpz_tstbit(self._mpz_p, + c_ulong(int(n)))) + + # Extra + def is_odd(self): + return _gmp.mpz_tstbit(self._mpz_p, 0) == 1 + + def is_even(self): + return _gmp.mpz_tstbit(self._mpz_p, 0) == 0 + + def size_in_bits(self): + """Return the minimum number of bits that can encode the number.""" + + if self < 0: + raise ValueError("Conversion only valid for non-negative numbers") + return _gmp.mpz_sizeinbase(self._mpz_p, 2) + + def size_in_bytes(self): + """Return the minimum number of bytes that can encode the number.""" + return (self.size_in_bits() - 1) // 8 + 1 + + def is_perfect_square(self): + return _gmp.mpz_perfect_square_p(self._mpz_p) != 0 + + def fail_if_divisible_by(self, small_prime): + """Raise an exception if the small prime is a divisor.""" + + if is_native_int(small_prime): + if 0 < small_prime < 65536: + if _gmp.mpz_divisible_ui_p(self._mpz_p, + c_ulong(small_prime)): + raise ValueError("The value is composite") + return + small_prime = IntegerGMP(small_prime) + if _gmp.mpz_divisible_p(self._mpz_p, + small_prime._mpz_p): + raise ValueError("The value is composite") + + def multiply_accumulate(self, a, b): + """Increment the number by the product of a and b.""" + + if not isinstance(a, IntegerGMP): + a = IntegerGMP(a) + if is_native_int(b): + if 0 < b < 65536: + _gmp.mpz_addmul_ui(self._mpz_p, + a._mpz_p, + c_ulong(b)) + return self + if -65535 < b < 0: + _gmp.mpz_submul_ui(self._mpz_p, + a._mpz_p, + c_ulong(-b)) + return self + b = IntegerGMP(b) + _gmp.mpz_addmul(self._mpz_p, + a._mpz_p, + b._mpz_p) + return self + + def set(self, source): + """Set the Integer to have the given value""" + + if not isinstance(source, IntegerGMP): + source = IntegerGMP(source) + _gmp.mpz_set(self._mpz_p, + source._mpz_p) + return self + + def inplace_inverse(self, modulus): + """Compute the inverse of this number in the ring of + modulo integers. + + Raise an exception if no inverse exists. + """ + + if not isinstance(modulus, IntegerGMP): + modulus = IntegerGMP(modulus) + + comp = _gmp.mpz_cmp(modulus._mpz_p, + self._zero_mpz_p) + if comp == 0: + raise ZeroDivisionError("Modulus cannot be zero") + if comp < 0: + raise ValueError("Modulus must be positive") + + result = _gmp.mpz_invert(self._mpz_p, + self._mpz_p, + modulus._mpz_p) + if not result: + raise ValueError("No inverse value can be computed") + return self + + def inverse(self, modulus): + result = IntegerGMP(self) + result.inplace_inverse(modulus) + return result + + def gcd(self, term): + """Compute the greatest common denominator between this + number and another term.""" + + result = IntegerGMP(0) + if is_native_int(term): + if 0 < term < 65535: + _gmp.mpz_gcd_ui(result._mpz_p, + self._mpz_p, + c_ulong(term)) + return result + term = IntegerGMP(term) + _gmp.mpz_gcd(result._mpz_p, self._mpz_p, term._mpz_p) + return result + + def lcm(self, term): + """Compute the least common multiplier between this + number and another term.""" + + result = IntegerGMP(0) + if not isinstance(term, IntegerGMP): + term = IntegerGMP(term) + _gmp.mpz_lcm(result._mpz_p, self._mpz_p, term._mpz_p) + return result + + @staticmethod + def jacobi_symbol(a, n): + """Compute the Jacobi symbol""" + + if not isinstance(a, IntegerGMP): + a = IntegerGMP(a) + if not isinstance(n, IntegerGMP): + n = IntegerGMP(n) + if n <= 0 or n.is_even(): + raise ValueError("n must be positive even for the Jacobi symbol") + return _gmp.mpz_jacobi(a._mpz_p, n._mpz_p) + + # Clean-up + def __del__(self): + + try: + if self._mpz_p is not None: + if self._initialized: + _gmp.mpz_clear(self._mpz_p) + + self._mpz_p = None + except AttributeError: + pass diff --git a/frozen_deps/Cryptodome/Math/_IntegerGMP.pyi b/frozen_deps/Cryptodome/Math/_IntegerGMP.pyi new file mode 100644 index 0000000..2181b47 --- /dev/null +++ b/frozen_deps/Cryptodome/Math/_IntegerGMP.pyi @@ -0,0 +1,3 @@ +from ._IntegerBase import IntegerBase +class IntegerGMP(IntegerBase): + pass diff --git a/frozen_deps/Cryptodome/Math/_IntegerNative.py b/frozen_deps/Cryptodome/Math/_IntegerNative.py new file mode 100644 index 0000000..896107f --- /dev/null +++ b/frozen_deps/Cryptodome/Math/_IntegerNative.py @@ -0,0 +1,380 @@ +# =================================================================== +# +# Copyright (c) 2014, Legrandin <[email protected]> +# 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. +# =================================================================== + +from ._IntegerBase import IntegerBase + +from Cryptodome.Util.number import long_to_bytes, bytes_to_long + + +class IntegerNative(IntegerBase): + """A class to model a natural integer (including zero)""" + + def __init__(self, value): + if isinstance(value, float): + raise ValueError("A floating point type is not a natural number") + try: + self._value = value._value + except AttributeError: + self._value = value + + # Conversions + def __int__(self): + return self._value + + def __str__(self): + return str(int(self)) + + def __repr__(self): + return "Integer(%s)" % str(self) + + # Only Python 2.x + def __hex__(self): + return hex(self._value) + + # Only Python 3.x + def __index__(self): + return int(self._value) + + def to_bytes(self, block_size=0): + if self._value < 0: + raise ValueError("Conversion only valid for non-negative numbers") + result = long_to_bytes(self._value, block_size) + if len(result) > block_size > 0: + raise ValueError("Value too large to encode") + return result + + @classmethod + def from_bytes(cls, byte_string): + return cls(bytes_to_long(byte_string)) + + # Relations + def __eq__(self, term): + if term is None: + return False + return self._value == int(term) + + def __ne__(self, term): + return not self.__eq__(term) + + def __lt__(self, term): + return self._value < int(term) + + def __le__(self, term): + return self.__lt__(term) or self.__eq__(term) + + def __gt__(self, term): + return not self.__le__(term) + + def __ge__(self, term): + return not self.__lt__(term) + + def __nonzero__(self): + return self._value != 0 + __bool__ = __nonzero__ + + def is_negative(self): + return self._value < 0 + + # Arithmetic operations + def __add__(self, term): + try: + return self.__class__(self._value + int(term)) + except (ValueError, AttributeError, TypeError): + return NotImplemented + + def __sub__(self, term): + try: + return self.__class__(self._value - int(term)) + except (ValueError, AttributeError, TypeError): + return NotImplemented + + def __mul__(self, factor): + try: + return self.__class__(self._value * int(factor)) + except (ValueError, AttributeError, TypeError): + return NotImplemented + + def __floordiv__(self, divisor): + return self.__class__(self._value // int(divisor)) + + def __mod__(self, divisor): + divisor_value = int(divisor) + if divisor_value < 0: + raise ValueError("Modulus must be positive") + return self.__class__(self._value % divisor_value) + + def inplace_pow(self, exponent, modulus=None): + exp_value = int(exponent) + if exp_value < 0: + raise ValueError("Exponent must not be negative") + + if modulus is not None: + mod_value = int(modulus) + if mod_value < 0: + raise ValueError("Modulus must be positive") + if mod_value == 0: + raise ZeroDivisionError("Modulus cannot be zero") + else: + mod_value = None + self._value = pow(self._value, exp_value, mod_value) + return self + + def __pow__(self, exponent, modulus=None): + result = self.__class__(self) + return result.inplace_pow(exponent, modulus) + + def __abs__(self): + return abs(self._value) + + def sqrt(self, modulus=None): + + value = self._value + if modulus is None: + if value < 0: + raise ValueError("Square root of negative value") + # http://stackoverflow.com/questions/15390807/integer-square-root-in-python + + x = value + y = (x + 1) // 2 + while y < x: + x = y + y = (x + value // x) // 2 + result = x + else: + if modulus <= 0: + raise ValueError("Modulus must be positive") + result = self._tonelli_shanks(self % modulus, modulus) + + return self.__class__(result) + + def __iadd__(self, term): + self._value += int(term) + return self + + def __isub__(self, term): + self._value -= int(term) + return self + + def __imul__(self, term): + self._value *= int(term) + return self + + def __imod__(self, term): + modulus = int(term) + if modulus == 0: + raise ZeroDivisionError("Division by zero") + if modulus < 0: + raise ValueError("Modulus must be positive") + self._value %= modulus + return self + + # Boolean/bit operations + def __and__(self, term): + return self.__class__(self._value & int(term)) + + def __or__(self, term): + return self.__class__(self._value | int(term)) + + def __rshift__(self, pos): + try: + return self.__class__(self._value >> int(pos)) + except OverflowError: + if self._value >= 0: + return 0 + else: + return -1 + + def __irshift__(self, pos): + try: + self._value >>= int(pos) + except OverflowError: + if self._value >= 0: + return 0 + else: + return -1 + return self + + def __lshift__(self, pos): + try: + return self.__class__(self._value << int(pos)) + except OverflowError: + raise ValueError("Incorrect shift count") + + def __ilshift__(self, pos): + try: + self._value <<= int(pos) + except OverflowError: + raise ValueError("Incorrect shift count") + return self + + def get_bit(self, n): + if self._value < 0: + raise ValueError("no bit representation for negative values") + try: + try: + result = (self._value >> n._value) & 1 + if n._value < 0: + raise ValueError("negative bit count") + except AttributeError: + result = (self._value >> n) & 1 + if n < 0: + raise ValueError("negative bit count") + except OverflowError: + result = 0 + return result + + # Extra + def is_odd(self): + return (self._value & 1) == 1 + + def is_even(self): + return (self._value & 1) == 0 + + def size_in_bits(self): + + if self._value < 0: + raise ValueError("Conversion only valid for non-negative numbers") + + if self._value == 0: + return 1 + + bit_size = 0 + tmp = self._value + while tmp: + tmp >>= 1 + bit_size += 1 + + return bit_size + + def size_in_bytes(self): + return (self.size_in_bits() - 1) // 8 + 1 + + def is_perfect_square(self): + if self._value < 0: + return False + if self._value in (0, 1): + return True + + x = self._value // 2 + square_x = x ** 2 + + while square_x > self._value: + x = (square_x + self._value) // (2 * x) + square_x = x ** 2 + + return self._value == x ** 2 + + def fail_if_divisible_by(self, small_prime): + if (self._value % int(small_prime)) == 0: + raise ValueError("Value is composite") + + def multiply_accumulate(self, a, b): + self._value += int(a) * int(b) + return self + + def set(self, source): + self._value = int(source) + + def inplace_inverse(self, modulus): + modulus = int(modulus) + if modulus == 0: + raise ZeroDivisionError("Modulus cannot be zero") + if modulus < 0: + raise ValueError("Modulus cannot be negative") + r_p, r_n = self._value, modulus + s_p, s_n = 1, 0 + while r_n > 0: + q = r_p // r_n + r_p, r_n = r_n, r_p - q * r_n + s_p, s_n = s_n, s_p - q * s_n + if r_p != 1: + raise ValueError("No inverse value can be computed" + str(r_p)) + while s_p < 0: + s_p += modulus + self._value = s_p + return self + + def inverse(self, modulus): + result = self.__class__(self) + result.inplace_inverse(modulus) + return result + + def gcd(self, term): + r_p, r_n = abs(self._value), abs(int(term)) + while r_n > 0: + q = r_p // r_n + r_p, r_n = r_n, r_p - q * r_n + return self.__class__(r_p) + + def lcm(self, term): + term = int(term) + if self._value == 0 or term == 0: + return self.__class__(0) + return self.__class__(abs((self._value * term) // self.gcd(term)._value)) + + @staticmethod + def jacobi_symbol(a, n): + a = int(a) + n = int(n) + + if n <= 0: + raise ValueError("n must be a positive integer") + + if (n & 1) == 0: + raise ValueError("n must be even for the Jacobi symbol") + + # Step 1 + a = a % n + # Step 2 + if a == 1 or n == 1: + return 1 + # Step 3 + if a == 0: + return 0 + # Step 4 + e = 0 + a1 = a + while (a1 & 1) == 0: + a1 >>= 1 + e += 1 + # Step 5 + if (e & 1) == 0: + s = 1 + elif n % 8 in (1, 7): + s = 1 + else: + s = -1 + # Step 6 + if n % 4 == 3 and a1 % 4 == 3: + s = -s + # Step 7 + n1 = n % a1 + # Step 8 + return s * IntegerNative.jacobi_symbol(n1, a1) diff --git a/frozen_deps/Cryptodome/Math/_IntegerNative.pyi b/frozen_deps/Cryptodome/Math/_IntegerNative.pyi new file mode 100644 index 0000000..3f65a39 --- /dev/null +++ b/frozen_deps/Cryptodome/Math/_IntegerNative.pyi @@ -0,0 +1,3 @@ +from ._IntegerBase import IntegerBase +class IntegerNative(IntegerBase): + pass diff --git a/frozen_deps/Cryptodome/Math/__init__.py b/frozen_deps/Cryptodome/Math/__init__.py new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/frozen_deps/Cryptodome/Math/__init__.py diff --git a/frozen_deps/Cryptodome/Math/_modexp.cpython-38-x86_64-linux-gnu.so b/frozen_deps/Cryptodome/Math/_modexp.cpython-38-x86_64-linux-gnu.so Binary files differnew file mode 100755 index 0000000..9b8cd0a --- /dev/null +++ b/frozen_deps/Cryptodome/Math/_modexp.cpython-38-x86_64-linux-gnu.so |