aboutsummaryrefslogtreecommitdiff
path: root/frozen_deps/ecdsa/numbertheory.py
diff options
context:
space:
mode:
Diffstat (limited to 'frozen_deps/ecdsa/numbertheory.py')
-rw-r--r--frozen_deps/ecdsa/numbertheory.py101
1 files changed, 63 insertions, 38 deletions
diff --git a/frozen_deps/ecdsa/numbertheory.py b/frozen_deps/ecdsa/numbertheory.py
index e5cc888..fe974f8 100644
--- a/frozen_deps/ecdsa/numbertheory.py
+++ b/frozen_deps/ecdsa/numbertheory.py
@@ -7,10 +7,11 @@
# Written in 2005 and 2006 by Peter Pearson and placed in the public domain.
# Revision history:
# 2008.11.14: Use pow(base, exponent, modulus) for modular_exp.
-# Make gcd and lcm accept arbitrarly many arguments.
+# Make gcd and lcm accept arbitrarily many arguments.
from __future__ import division
+import sys
from six import integer_types, PY2
from six.moves import reduce
@@ -19,11 +20,11 @@ try:
except NameError:
xrange = range
try:
- from gmpy2 import powmod
+ from gmpy2 import powmod, mpz
GMPY2 = True
GMPY = False
-except ImportError:
+except ImportError: # pragma: no branch
GMPY2 = False
try:
from gmpy import mpz
@@ -32,8 +33,15 @@ except ImportError:
except ImportError:
GMPY = False
+
+if GMPY2 or GMPY: # pragma: no branch
+ integer_types = tuple(integer_types + (type(mpz(1)),))
+
+
import math
import warnings
+import random
+from .util import bit_length
class Error(Exception):
@@ -42,6 +50,10 @@ class Error(Exception):
pass
+class JacobiError(Error):
+ pass
+
+
class SquareRootError(Error):
pass
@@ -153,8 +165,10 @@ def jacobi(a, n):
# table printed in HAC, and by extensive use in calculating
# modular square roots.
- assert n >= 3
- assert n % 2 == 1
+ if not n >= 3:
+ raise JacobiError("n must be larger than 2")
+ if not n % 2 == 1:
+ raise JacobiError("n must be odd")
a = a % n
if a == 0:
return 0
@@ -201,66 +215,76 @@ def square_root_mod_prime(a, p):
d = pow(a, (p - 1) // 4, p)
if d == 1:
return pow(a, (p + 3) // 8, p)
- if d == p - 1:
- return (2 * a * pow(4 * a, (p - 5) // 8, p)) % p
- raise RuntimeError("Shouldn't get here.")
+ assert d == p - 1
+ return (2 * a * pow(4 * a, (p - 5) // 8, p)) % p
if PY2:
# xrange on python2 can take integers representable as C long only
range_top = min(0x7FFFFFFF, p)
else:
range_top = p
- for b in xrange(2, range_top):
+ for b in xrange(2, range_top): # pragma: no branch
if jacobi(b * b - 4 * a, p) == -1:
f = (a, -b, 1)
ff = polynomial_exp_mod((0, 1), (p + 1) // 2, f, p)
- assert ff[1] == 0
+ if ff[1]:
+ raise SquareRootError("p is not prime")
return ff[0]
- raise RuntimeError("No b found.")
+ # just an assertion
+ raise RuntimeError("No b found.") # pragma: no cover
-if GMPY2:
+# because all the inverse_mod code is arch/environment specific, and coveralls
+# expects it to execute equal number of times, we need to waive it by
+# adding the "no branch" pragma to all branches
+if GMPY2: # pragma: no branch
def inverse_mod(a, m):
"""Inverse of a mod m."""
- if a == 0:
+ if a == 0: # pragma: no branch
return 0
return powmod(a, -1, m)
-
-elif GMPY:
+elif GMPY: # pragma: no branch
def inverse_mod(a, m):
"""Inverse of a mod m."""
- # while libgmp likely does support inverses modulo, it is accessible
- # only using the native `pow()` function, and `pow()` sanity checks
- # the parameters before passing them on to underlying implementation
- # on Python2
- if a == 0:
+ # while libgmp does support inverses modulo, it is accessible
+ # only using the native `pow()` function, and `pow()` in gmpy sanity
+ # checks the parameters before passing them on to underlying
+ # implementation
+ if a == 0: # pragma: no branch
return 0
a = mpz(a)
m = mpz(m)
lm, hm = mpz(1), mpz(0)
low, high = a % m, m
- while low > 1:
+ while low > 1: # pragma: no branch
r = high // low
lm, low, hm, high = hm - lm * r, high - low * r, lm, low
return lm % m
+elif sys.version_info >= (3, 8): # pragma: no branch
+
+ def inverse_mod(a, m):
+ """Inverse of a mod m."""
+ if a == 0: # pragma: no branch
+ return 0
+ return pow(a, -1, m)
-else:
+else: # pragma: no branch
def inverse_mod(a, m):
"""Inverse of a mod m."""
- if a == 0:
+ if a == 0: # pragma: no branch
return 0
lm, hm = 1, 0
low, high = a % m, m
- while low > 1:
+ while low > 1: # pragma: no branch
r = high // low
lm, low, hm, high = hm - lm * r, high - low * r, lm, low
@@ -321,7 +345,6 @@ def factorization(n):
return []
result = []
- d = 2
# Test the small primes:
@@ -331,7 +354,7 @@ def factorization(n):
q, r = divmod(n, d)
if r == 0:
count = 1
- while d <= n:
+ while d <= n: # pragma: no branch
n = q
q, r = divmod(n, d)
if r != 0:
@@ -355,7 +378,8 @@ def factorization(n):
if r == 0: # d divides n. How many times?
count = 1
n = q
- while d <= n: # As long as d might still divide n,
+ # As long as d might still divide n,
+ while d <= n: # pragma: no branch
q, r = divmod(n, d) # see if it does.
if r != 0:
break
@@ -374,7 +398,7 @@ def phi(n): # pragma: no cover
warnings.warn(
"Function is unused by library code. If you use this code, "
"please open an issue in "
- "https://github.com/warner/python-ecdsa",
+ "https://github.com/tlsfuzzer/python-ecdsa",
DeprecationWarning,
)
@@ -404,7 +428,7 @@ def carmichael(n): # pragma: no cover
warnings.warn(
"Function is unused by library code. If you use this code, "
"please open an issue in "
- "https://github.com/warner/python-ecdsa",
+ "https://github.com/tlsfuzzer/python-ecdsa",
DeprecationWarning,
)
@@ -419,7 +443,7 @@ def carmichael_of_factorized(f_list): # pragma: no cover
warnings.warn(
"Function is unused by library code. If you use this code, "
"please open an issue in "
- "https://github.com/warner/python-ecdsa",
+ "https://github.com/tlsfuzzer/python-ecdsa",
DeprecationWarning,
)
@@ -439,7 +463,7 @@ def carmichael_of_ppower(pp): # pragma: no cover
warnings.warn(
"Function is unused by library code. If you use this code, "
"please open an issue in "
- "https://github.com/warner/python-ecdsa",
+ "https://github.com/tlsfuzzer/python-ecdsa",
DeprecationWarning,
)
@@ -456,7 +480,7 @@ def order_mod(x, m): # pragma: no cover
warnings.warn(
"Function is unused by library code. If you use this code, "
"please open an issue in "
- "https://github.com/warner/python-ecdsa",
+ "https://github.com/tlsfuzzer/python-ecdsa",
DeprecationWarning,
)
@@ -482,7 +506,7 @@ def largest_factor_relatively_prime(a, b): # pragma: no cover
warnings.warn(
"Function is unused by library code. If you use this code, "
"please open an issue in "
- "https://github.com/warner/python-ecdsa",
+ "https://github.com/tlsfuzzer/python-ecdsa",
DeprecationWarning,
)
@@ -507,7 +531,7 @@ def kinda_order_mod(x, m): # pragma: no cover
warnings.warn(
"Function is unused by library code. If you use this code, "
"please open an issue in "
- "https://github.com/warner/python-ecdsa",
+ "https://github.com/tlsfuzzer/python-ecdsa",
DeprecationWarning,
)
@@ -540,8 +564,8 @@ def is_prime(n):
return True
else:
return False
-
- if gcd(n, 2 * 3 * 5 * 7 * 11) != 1:
+ # 2310 = 2 * 3 * 5 * 7 * 11
+ if gcd(n, 2310) != 1:
return False
# Choose a number of iterations sufficient to reduce the
@@ -549,7 +573,8 @@ def is_prime(n):
# (from Menezes et al. Table 4.4):
t = 40
- n_bits = 1 + int(math.log(n, 2))
+ n_bits = 1 + bit_length(n)
+ assert 11 <= n_bits <= 16384
for k, tt in (
(100, 27),
(150, 18),
@@ -576,7 +601,7 @@ def is_prime(n):
s = s + 1
r = r // 2
for i in xrange(t):
- a = smallprimes[i]
+ a = random.choice(smallprimes)
y = pow(a, r, n)
if y != 1 and y != n - 1:
j = 1