aboutsummaryrefslogtreecommitdiff
path: root/frozen_deps/Cryptodome/Math
diff options
context:
space:
mode:
Diffstat (limited to 'frozen_deps/Cryptodome/Math')
-rw-r--r--frozen_deps/Cryptodome/Math/Numbers.pyi6
-rw-r--r--frozen_deps/Cryptodome/Math/Primality.py5
-rw-r--r--frozen_deps/Cryptodome/Math/_IntegerBase.py26
-rw-r--r--frozen_deps/Cryptodome/Math/_IntegerBase.pyi10
-rw-r--r--frozen_deps/Cryptodome/Math/_IntegerCustom.py65
-rw-r--r--frozen_deps/Cryptodome/Math/_IntegerGMP.py116
-rw-r--r--frozen_deps/Cryptodome/Math/_IntegerNative.py66
-rwxr-xr-xfrozen_deps/Cryptodome/Math/_modexp.abi3.sobin0 -> 213552 bytes
-rwxr-xr-xfrozen_deps/Cryptodome/Math/_modexp.cpython-38-x86_64-linux-gnu.sobin207274 -> 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
new file mode 100755
index 0000000..d11de72
--- /dev/null
+++ b/frozen_deps/Cryptodome/Math/_modexp.abi3.so
Binary files differ
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
deleted file mode 100755
index 9b8cd0a..0000000
--- a/frozen_deps/Cryptodome/Math/_modexp.cpython-38-x86_64-linux-gnu.so
+++ /dev/null
Binary files differ