diff options
Diffstat (limited to 'frozen_deps/Cryptodome/Math')
| -rw-r--r-- | frozen_deps/Cryptodome/Math/Numbers.pyi | 6 | ||||
| -rw-r--r-- | frozen_deps/Cryptodome/Math/Primality.py | 5 | ||||
| -rw-r--r-- | frozen_deps/Cryptodome/Math/_IntegerBase.py | 26 | ||||
| -rw-r--r-- | frozen_deps/Cryptodome/Math/_IntegerBase.pyi | 10 | ||||
| -rw-r--r-- | frozen_deps/Cryptodome/Math/_IntegerCustom.py | 65 | ||||
| -rw-r--r-- | frozen_deps/Cryptodome/Math/_IntegerGMP.py | 116 | ||||
| -rw-r--r-- | frozen_deps/Cryptodome/Math/_IntegerNative.py | 66 | ||||
| -rwxr-xr-x | frozen_deps/Cryptodome/Math/_modexp.abi3.so | bin | 0 -> 213552 bytes | |||
| -rwxr-xr-x | frozen_deps/Cryptodome/Math/_modexp.cpython-38-x86_64-linux-gnu.so | bin | 207274 -> 0 bytes |
9 files changed, 223 insertions, 71 deletions
diff --git a/frozen_deps/Cryptodome/Math/Numbers.pyi b/frozen_deps/Cryptodome/Math/Numbers.pyi index 2285a3b..b0206ca 100644 --- a/frozen_deps/Cryptodome/Math/Numbers.pyi +++ b/frozen_deps/Cryptodome/Math/Numbers.pyi @@ -1,4 +1,2 @@ -from Cryptodome.Math._IntegerBase import IntegerBase - -class Integer(IntegerBase): - pass +from Cryptodome.Math._IntegerBase import IntegerBase as Integer +__all__ = ['Integer'] diff --git a/frozen_deps/Cryptodome/Math/Primality.py b/frozen_deps/Cryptodome/Math/Primality.py index 08ea3ff..33814fa 100644 --- a/frozen_deps/Cryptodome/Math/Primality.py +++ b/frozen_deps/Cryptodome/Math/Primality.py @@ -67,7 +67,7 @@ def miller_rabin_test(candidate, iterations, randfunc=None): if candidate in (1, 2, 3, 5): return PROBABLY_PRIME - + if candidate.is_even(): return COMPOSITE @@ -93,7 +93,8 @@ def miller_rabin_test(candidate, iterations, randfunc=None): base = 1 while base in (one, minus_one): base = Integer.random_range(min_inclusive=2, - max_inclusive=candidate - 2) + max_inclusive=candidate - 2, + randfunc=randfunc) assert(2 <= base <= candidate - 2) # Step 4.3-4.4 diff --git a/frozen_deps/Cryptodome/Math/_IntegerBase.py b/frozen_deps/Cryptodome/Math/_IntegerBase.py index f8cf333..03dd591 100644 --- a/frozen_deps/Cryptodome/Math/_IntegerBase.py +++ b/frozen_deps/Cryptodome/Math/_IntegerBase.py @@ -51,12 +51,12 @@ class IntegerBase(ABC): pass @abc.abstractmethod - def to_bytes(self, block_size=0): + def to_bytes(self, block_size=0, byteorder='big'): pass @staticmethod @abc.abstractmethod - def from_bytes(byte_string): + def from_bytes(byte_string, byteorder='big'): pass # Relations @@ -228,7 +228,7 @@ class IntegerBase(ABC): @abc.abstractmethod def jacobi_symbol(a, n): pass - + @staticmethod def _tonelli_shanks(n, p): """Tonelli-shanks algorithm for computing the square root @@ -390,3 +390,23 @@ class IntegerBase(ABC): ) return norm_candidate + min_inclusive + @staticmethod + @abc.abstractmethod + def _mult_modulo_bytes(term1, term2, modulus): + """Multiply two integers, take the modulo, and encode as big endian. + This specialized method is used for RSA decryption. + + Args: + term1 : integer + The first term of the multiplication, non-negative. + term2 : integer + The second term of the multiplication, non-negative. + modulus: integer + The modulus, a positive odd number. + :Returns: + A byte string, with the result of the modular multiplication + encoded in big endian mode. + It is as long as the modulus would be, with zero padding + on the left if needed. + """ + pass diff --git a/frozen_deps/Cryptodome/Math/_IntegerBase.pyi b/frozen_deps/Cryptodome/Math/_IntegerBase.pyi index 3f534db..ea23532 100644 --- a/frozen_deps/Cryptodome/Math/_IntegerBase.pyi +++ b/frozen_deps/Cryptodome/Math/_IntegerBase.pyi @@ -4,12 +4,14 @@ RandFunc = Callable[[int],int] class IntegerBase: + def __init__(self, value: Union[IntegerBase, int]): ... + def __int__(self) -> int: ... def __str__(self) -> str: ... def __repr__(self) -> str: ... - def to_bytes(self, block_size: Optional[int]=0) -> bytes: ... + def to_bytes(self, block_size: Optional[int]=0, byteorder: str= ...) -> bytes: ... @staticmethod - def from_bytes(byte_string: bytes) -> IntegerBase: ... + def from_bytes(byte_string: bytes, byteorder: Optional[str] = ...) -> IntegerBase: ... def __eq__(self, term: object) -> bool: ... def __ne__(self, term: object) -> bool: ... def __lt__(self, term: Union[IntegerBase, int]) -> bool: ... @@ -58,4 +60,8 @@ class IntegerBase: def random(cls, **kwargs: Union[int,RandFunc]) -> IntegerBase : ... @classmethod def random_range(cls, **kwargs: Union[int,RandFunc]) -> IntegerBase : ... + @staticmethod + def _mult_modulo_bytes(term1: Union[IntegerBase, int], + term2: Union[IntegerBase, int], + modulus: Union[IntegerBase, int]) -> bytes: ... diff --git a/frozen_deps/Cryptodome/Math/_IntegerCustom.py b/frozen_deps/Cryptodome/Math/_IntegerCustom.py index b626014..20eadca 100644 --- a/frozen_deps/Cryptodome/Math/_IntegerCustom.py +++ b/frozen_deps/Cryptodome/Math/_IntegerCustom.py @@ -41,12 +41,18 @@ from Cryptodome.Util._raw_api import (load_pycryptodome_raw_lib, 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); +int monty_pow(uint8_t *out, + const uint8_t *base, + const uint8_t *exp, + const uint8_t *modulus, + size_t len, + uint64_t seed); + +int monty_multiply(uint8_t *out, + const uint8_t *term1, + const uint8_t *term2, + const uint8_t *modulus, + size_t len); """ @@ -57,7 +63,14 @@ implementation = {"library": "custom", "api": backend} class IntegerCustom(IntegerNative): @staticmethod - def from_bytes(byte_string): + def from_bytes(byte_string, byteorder='big'): + if byteorder == 'big': + pass + elif byteorder == 'little': + byte_string = bytearray(byte_string) + byte_string.reverse() + else: + raise ValueError("Incorrect byteorder") return IntegerCustom(bytes_to_long(byte_string)) def inplace_pow(self, exponent, modulus=None): @@ -109,3 +122,41 @@ class IntegerCustom(IntegerNative): result = bytes_to_long(get_raw_buffer(out)) self._value = result return self + + @staticmethod + def _mult_modulo_bytes(term1, term2, modulus): + + # 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: + raise ValueError("Odd modulus is required") + + # C extension only works with non-negative terms smaller than modulus + if term1 >= mod_value or term1 < 0: + term1 %= mod_value + if term2 >= mod_value or term2 < 0: + term2 %= mod_value + + modulus_b = long_to_bytes(mod_value) + numbers_len = len(modulus_b) + term1_b = long_to_bytes(term1, numbers_len) + term2_b = long_to_bytes(term2, numbers_len) + out = create_string_buffer(numbers_len) + + error = _raw_montgomery.monty_multiply( + out, + term1_b, + term2_b, + modulus_b, + c_size_t(numbers_len) + ) + if error: + raise ValueError("monty_multiply failed with error: %d" % error) + + return get_raw_buffer(out) diff --git a/frozen_deps/Cryptodome/Math/_IntegerGMP.py b/frozen_deps/Cryptodome/Math/_IntegerGMP.py index c860020..f58f044 100644 --- a/frozen_deps/Cryptodome/Math/_IntegerGMP.py +++ b/frozen_deps/Cryptodome/Math/_IntegerGMP.py @@ -35,7 +35,7 @@ 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) + c_ulong, c_size_t, c_uint8_ptr) from ._IntegerBase import IntegerBase @@ -43,12 +43,14 @@ 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, ...); + + UNIX_ULONG __gmpz_get_ui (const mpz_t op); void __gmpz_set (mpz_t rop, const mpz_t op); - int __gmp_snprintf (uint8_t *buf, size_t size, const char *fmt, ...); + void __gmpz_set_ui (mpz_t rop, UNIX_ULONG op); 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); @@ -156,28 +158,58 @@ class IntegerGMP(IntegerBase): 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) + self._initialized = True + if value == 0: + return + + tmp = new_mpz() + _gmp.mpz_init(tmp) + + try: + positive = value >= 0 + reduce = abs(value) + slots = (reduce.bit_length() - 1) // 32 + 1 + + while slots > 0: + slots = slots - 1 + _gmp.mpz_set_ui(tmp, + c_ulong(0xFFFFFFFF & (reduce >> (slots * 32)))) + _gmp.mpz_mul_2exp(tmp, tmp, c_ulong(slots * 32)) + _gmp.mpz_add(self._mpz_p, self._mpz_p, tmp) + finally: + _gmp.mpz_clear(tmp) + + if not positive: + _gmp.mpz_neg(self._mpz_p, self._mpz_p) + elif isinstance(value, IntegerGMP): _gmp.mpz_init_set(self._mpz_p, value._mpz_p) + self._initialized = True 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) + tmp = new_mpz() + _gmp.mpz_init_set(tmp, self._mpz_p) - _gmp.gmp_snprintf(buf, c_size_t(buf_len), b"%Zd", self._mpz_p) - return int(get_c_string(buf)) + try: + value = 0 + slot = 0 + while _gmp.mpz_cmp(tmp, self._zero_mpz_p) != 0: + lsb = _gmp.mpz_get_ui(tmp) & 0xFFFFFFFF + value |= lsb << (slot * 32) + _gmp.mpz_tdiv_q_2exp(tmp, tmp, c_ulong(32)) + slot = slot + 1 + finally: + _gmp.mpz_clear(tmp) + + if self < 0: + value = -value + return int(value) def __str__(self): return str(int(self)) @@ -193,7 +225,7 @@ class IntegerGMP(IntegerBase): def __index__(self): return int(self) - def to_bytes(self, block_size=0): + def to_bytes(self, block_size=0, byteorder='big'): """Convert the number into a byte string. This method encodes the number in network order and prepends @@ -204,6 +236,8 @@ class IntegerGMP(IntegerBase): block_size : integer The exact size the output byte string must have. If zero, the string has the minimal length. + byteorder : string + 'big' for big-endian integers (default), 'little' for litte-endian. :Returns: A byte string. :Raise ValueError: @@ -217,9 +251,10 @@ class IntegerGMP(IntegerBase): 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") + " of prescribed length") buf = create_string_buffer(buf_len) + _gmp.mpz_export( buf, null_pointer, # Ignore countp @@ -229,20 +264,39 @@ class IntegerGMP(IntegerBase): c_size_t(0), # No nails self._mpz_p) - return b'\x00' * max(0, block_size - buf_len) + get_raw_buffer(buf) + result = b'\x00' * max(0, block_size - buf_len) + get_raw_buffer(buf) + if byteorder == 'big': + pass + elif byteorder == 'little': + result = bytearray(result) + result.reverse() + result = bytes(result) + else: + raise ValueError("Incorrect byteorder") + return result @staticmethod - def from_bytes(byte_string): + def from_bytes(byte_string, byteorder='big'): """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. + byteorder : string + 'big' for big-endian integers (default), 'little' for litte-endian. + :Return: The ``Integer`` object carrying the same value as the input. """ result = IntegerGMP(0) + if byteorder == 'big': + pass + elif byteorder == 'little': + byte_string = bytearray(byte_string) + byte_string.reverse() + else: + raise ValueError("Incorrect byteorder") _gmp.mpz_import( result._mpz_p, c_size_t(len(byte_string)), # Amount of words to read @@ -250,7 +304,7 @@ class IntegerGMP(IntegerBase): 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) + c_uint8_ptr(byte_string)) return result # Relations @@ -692,9 +746,29 @@ class IntegerGMP(IntegerBase): 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") + raise ValueError("n must be positive odd for the Jacobi symbol") return _gmp.mpz_jacobi(a._mpz_p, n._mpz_p) + @staticmethod + def _mult_modulo_bytes(term1, term2, modulus): + if not isinstance(term1, IntegerGMP): + term1 = IntegerGMP(term1) + if not isinstance(term2, IntegerGMP): + term2 = IntegerGMP(term2) + if not isinstance(modulus, IntegerGMP): + modulus = IntegerGMP(modulus) + + if modulus < 0: + raise ValueError("Modulus must be positive") + if modulus == 0: + raise ZeroDivisionError("Modulus cannot be zero") + if (modulus & 1) == 0: + raise ValueError("Odd modulus is required") + + numbers_len = len(modulus.to_bytes()) + result = ((term1 * term2) % modulus).to_bytes(numbers_len) + return result + # Clean-up def __del__(self): diff --git a/frozen_deps/Cryptodome/Math/_IntegerNative.py b/frozen_deps/Cryptodome/Math/_IntegerNative.py index 896107f..5f768e2 100644 --- a/frozen_deps/Cryptodome/Math/_IntegerNative.py +++ b/frozen_deps/Cryptodome/Math/_IntegerNative.py @@ -30,7 +30,7 @@ from ._IntegerBase import IntegerBase -from Cryptodome.Util.number import long_to_bytes, bytes_to_long +from Cryptodome.Util.number import long_to_bytes, bytes_to_long, inverse, GCD class IntegerNative(IntegerBase): @@ -62,16 +62,31 @@ class IntegerNative(IntegerBase): def __index__(self): return int(self._value) - def to_bytes(self, block_size=0): + def to_bytes(self, block_size=0, byteorder='big'): 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") + if byteorder == 'big': + pass + elif byteorder == 'little': + result = bytearray(result) + result.reverse() + result = bytes(result) + else: + raise ValueError("Incorrect byteorder") return result @classmethod - def from_bytes(cls, byte_string): + def from_bytes(cls, byte_string, byteorder='big'): + if byteorder == 'big': + pass + elif byteorder == 'little': + byte_string = bytearray(byte_string) + byte_string.reverse() + else: + raise ValueError("Incorrect byteorder") return cls(bytes_to_long(byte_string)) # Relations @@ -265,13 +280,7 @@ class IntegerNative(IntegerBase): if self._value == 0: return 1 - bit_size = 0 - tmp = self._value - while tmp: - tmp >>= 1 - bit_size += 1 - - return bit_size + return self._value.bit_length() def size_in_bytes(self): return (self.size_in_bits() - 1) // 8 + 1 @@ -303,22 +312,7 @@ class IntegerNative(IntegerBase): 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 + self._value = inverse(self._value, int(modulus)) return self def inverse(self, modulus): @@ -327,11 +321,7 @@ class IntegerNative(IntegerBase): 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) + return self.__class__(GCD(abs(self._value), abs(int(term)))) def lcm(self, term): term = int(term) @@ -348,7 +338,7 @@ class IntegerNative(IntegerBase): raise ValueError("n must be a positive integer") if (n & 1) == 0: - raise ValueError("n must be even for the Jacobi symbol") + raise ValueError("n must be odd for the Jacobi symbol") # Step 1 a = a % n @@ -378,3 +368,15 @@ class IntegerNative(IntegerBase): n1 = n % a1 # Step 8 return s * IntegerNative.jacobi_symbol(n1, a1) + + @staticmethod + def _mult_modulo_bytes(term1, term2, modulus): + if modulus < 0: + raise ValueError("Modulus must be positive") + if modulus == 0: + raise ZeroDivisionError("Modulus cannot be zero") + if (modulus & 1) == 0: + raise ValueError("Odd modulus is required") + + number_len = len(long_to_bytes(modulus)) + return long_to_bytes((term1 * term2) % modulus, number_len) diff --git a/frozen_deps/Cryptodome/Math/_modexp.abi3.so b/frozen_deps/Cryptodome/Math/_modexp.abi3.so Binary files differnew file mode 100755 index 0000000..d11de72 --- /dev/null +++ b/frozen_deps/Cryptodome/Math/_modexp.abi3.so 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 differdeleted file mode 100755 index 9b8cd0a..0000000 --- a/frozen_deps/Cryptodome/Math/_modexp.cpython-38-x86_64-linux-gnu.so +++ /dev/null |