#! /usr/bin/env python
#
# Provide some simple capabilities from number theory.
#
# Version of 2008.11.14.
#
# 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 arbitrarily many arguments.
from __future__ import division
import sys
from six import integer_types, PY2
from six.moves import reduce
try:
xrange
except NameError:
xrange = range
try:
from gmpy2 import powmod, mpz
GMPY2 = True
GMPY = False
except ImportError: # pragma: no branch
GMPY2 = False
try:
from gmpy import mpz
GMPY = True
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):
"""Base class for exceptions in this module."""
pass
class JacobiError(Error):
pass
class SquareRootError(Error):
pass
class NegativeExponentError(Error):
pass
def modular_exp(base, exponent, modulus): # pragma: no cover
"""Raise base to exponent, reducing by modulus"""
# deprecated in 0.14
warnings.warn(
"Function is unused in library code. If you use this code, "
"change to pow() builtin.",
DeprecationWarning,
)
if exponent < 0:
raise NegativeExponentError(
"Negative exponents (%d) not allowed" % exponent
)
return pow(base, exponent, modulus)
def polynomial_reduce_mod(poly, polymod, p):
"""Reduce poly by polymod, integer arithmetic modulo p.
Polynomials are represented as lists of coefficients
of increasing powers of x."""
# This module has been tested only by extensive use
# in calculating modular square roots.
# Just to make this easy, require a monic polynomial:
assert polymod[-1] == 1
assert len(polymod) > 1
while len(poly) >= len(polymod):
if poly[-1] != 0:
for i in xrange(2, len(polymod) + 1):
poly[-i] = (poly[-i] - poly[-1] * polymod[-i]) % p
poly = poly[0:-1]
return poly
def polynomial_multiply_mod(m1, m2, polymod, p):
"""Polynomial multiplication modulo a polynomial over ints mod p.
Polynomials are represented as lists of coefficients
of increasing powers of x."""
# This is just a seat-of-the-pants implementation.
# This module has been tested only by extensive use
# in calculating modular square roots.
# Initialize the product to zero:
prod = (len(m1) + len(m2) - 1) * [0]
# Add together all the cross-terms:
for i in xrange(len(m1)):
for j in xrange(len(m2)):
prod[i + j] = (prod[i + j] + m1[i] * m2[j]) % p
return polynomial_reduce_mod(prod, polymod, p)
def polynomial_exp_mod(base, exponent, polymod, p):
"""Polynomial exponentiation modulo a polynomial over ints mod p.
Polynomials are represented as lists of coefficients
of increasing powers of x."""
# Based on the Handbook of Applied Cryptography, algorithm 2.227.
# This module has been tested only by extensive use
# in calculating modular square roots.
assert exponent < p
if exponent == 0:
return [1]
G = base
k = exponent
if k % 2 == 1:
s = G
else:
s = [1]
while k > 1:
k = k // 2
G = polynomial_multiply_mod(G, G, polymod, p)
if k % 2 == 1:
s = polynomial_multiply_mod(G, s, polymod, p)
return s
def jacobi(a, n):
"""Jacobi symbol"""
# Based on the Handbook of Applied Cryptography (HAC), algorithm 2.149.
# This function has been tested by comparison with a small
# table printed in HAC, and by extensive use in calculating
# modular square roots.
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
if a == 1:
return 1
a1, e = a, 0
while a1 % 2 == 0:
a1, e = a1 // 2, e + 1
if e % 2 == 0 or n % 8 == 1 or n % 8 == 7:
s = 1
else:
s = -1
if a1 == 1:
return s
if n % 4 == 3 and a1 % 4 == 3:
s = -s
return s * jacobi(n % a1, a1)
def square_root_mod_prime(a, p):
"""Modular square root of a, mod p, p prime."""
# Based on the Handbook of Applied Cryptography, algorithms 3.34 to 3.39.
# This module has been tested for all values in [0,p-1] for
# every prime p from 3 to 1229.
assert 0 <= a < p
assert 1 < p
if a == 0:
return 0
if p == 2:
return a
jac = jacobi(a, p)
if jac == -1:
raise SquareRootError("%d has no square root modulo %d" % (a, p))
if p % 4 == 3:
return pow(a, (p + 1) // 4, p)
if p % 8 == 5:
d = pow(a, (p - 1) // 4, p)
if d == 1:
return pow(a, (p + 3) // 8, p)
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): # 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)
if ff[1]:
raise SquareRootError("p is not prime")
return ff[0]
# just an assertion
raise RuntimeError("No b found.") # pragma: no cover
# 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: # pragma: no branch
return 0
return powmod(a, -1, m)
elif GMPY: # pragma: no branch
def inverse_mod(a, m):
"""Inverse of a mod m."""
# 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: # 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: # pragma: no branch
def inverse_mod(a, m):
"""Inverse of a mod m."""
if a == 0: # pragma: no branch
return 0
lm, hm = 1, 0
low, high = a % m, m
while low > 1: # pragma: no branch
r = high // low
lm, low, hm, high = hm - lm * r, high - low * r, lm, low
return lm % m
try:
gcd2 = math.gcd
except AttributeError:
def gcd2(a, b):
"""Greatest common divisor using Euclid's algorithm."""
while a:
a, b = b % a, a
return b
def gcd(*a):
"""Greatest common divisor.
Usage: gcd([ 2, 4, 6 ])
or: gcd(2, 4, 6)
"""
if len(a) > 1:
return reduce(gcd2, a)
if hasattr(a[0], "__iter__"):
return reduce(gcd2, a[0])
return a[0]
def lcm2(a, b):
"""Least common multiple of two integers."""
return (a * b) // gcd(a, b)
def lcm(*a):
"""Least common multiple.
Usage: lcm([ 3, 4, 5 ])
or: lcm(3, 4, 5)
"""
if len(a) > 1:
return reduce(lcm2, a)
if hasattr(a[0], "__iter__"):
return reduce(lcm2, a[0])
return a[0]
def factorization(n):
"""Decompose n into a list of (prime,exponent) pairs."""
assert isinstance(n, integer_types)
if n < 2:
return []
result = []
# Test the small primes:
for d in smallprimes:
if d > n:
break
q, r = divmod(n, d)
if r == 0:
count = 1
while d <= n: # pragma: no branch
n = q
q, r = divmod(n, d)
if r != 0:
break
count = count + 1
result.append((d, count))
# If n is still greater than the last of our small primes,
# it may require further work:
if n > smallprimes[-1]:
if is_prime(n): # If what's left is prime, it's easy:
result.append((n, 1))
else: # Ugh. Search stupidly for a divisor:
d = smallprimes[-1]
while 1:
d = d + 2 # Try the next divisor.
q, r = divmod(n, d)
if q < d: # n < d*d means we're done, n = 1 or prime.
break
if r == 0: # d divides n. How many times?
count = 1
n = q
# 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
n = q # It does. Reduce n, increase count.
count = count + 1
result.append((d, count))
if n > 1:
result.append((n, 1))
return result
def phi(n): # pragma: no cover
"""Return the Euler totient function of n."""
# deprecated in 0.14
warnings.warn(
"Function is unused by library code. If you use this code, "
"please open an issue in "
"https://github.com/tlsfuzzer/python-ecdsa",
DeprecationWarning,
)
assert isinstance(n, integer_types)
if n < 3:
return 1
result = 1
ff = factorization(n)
for f in ff:
e = f[1]
if e > 1:
result = result * f[0] ** (e - 1) * (f[0] - 1)
else:
result = result * (f[0] - 1)
return result
def carmichael(n): # pragma: no cover
"""Return Carmichael function of n.
Carmichael(n) is the smallest integer x such that
m**x = 1 mod n for all m relatively prime to n.
"""
# deprecated in 0.14
warnings.warn(
"Function is unused by library code. If you use this code, "
"please open an issue in "
"https://github.com/tlsfuzzer/python-ecdsa",
DeprecationWarning,
)
return carmichael_of_factorized(factorization(n))
def carmichael_of_factorized(f_list): # pragma: no cover
"""Return the Carmichael function of a number that is
represented as a list of (prime,exponent) pairs.
"""
# deprecated in 0.14
warnings.warn(
"Function is unused by library code. If you use this code, "
"please open an issue in "
"https://github.com/tlsfuzzer/python-ecdsa",
DeprecationWarning,
)
if len(f_list) < 1:
return 1
result = carmichael_of_ppower(f_list[0])
for i in xrange(1, len(f_list)):
result = lcm(result, carmichael_of_ppower(f_list[i]))
return result
def carmichael_of_ppower(pp): # pragma: no cover
"""Carmichael function of the given power of the given prime."""
# deprecated in 0.14
warnings.warn(
"Function is unused by library code. If you use this code, "
"please open an issue in "
"https://github.com/tlsfuzzer/python-ecdsa",
DeprecationWarning,
)
p, a = pp
if p == 2 and a > 2:
return 2 ** (a - 2)
else:
return (p - 1) * p ** (a - 1)
def order_mod(x, m): # pragma: no cover
"""Return the order of x in the multiplicative group mod m."""
# deprecated in 0.14
warnings.warn(
"Function is unused by library code. If you use this code, "
"please open an issue in "
"https://github.com/tlsfuzzer/python-ecdsa",
DeprecationWarning,
)
# Warning: this implementation is not very clever, and will
# take a long time if m is very large.
if m <= 1:
return 0
assert gcd(x, m) == 1
z = x
result = 1
while z != 1:
z = (z * x) % m
result = result + 1
return result
def largest_factor_relatively_prime(a, b): # pragma: no cover
"""Return the largest factor of a relatively prime to b."""
# deprecated in 0.14
warnings.warn(
"Function is unused by library code. If you use this code, "
"please open an issue in "
"https://github.com/tlsfuzzer/python-ecdsa",
DeprecationWarning,
)
while 1:
d = gcd(a, b)
if d <= 1:
break
b = d
while 1:
q, r = divmod(a, d)
if r > 0:
break
a = q
return a
def kinda_order_mod(x, m): # pragma: no cover
"""Return the order of x in the multiplicative group mod m',
where m' is the largest factor of m relatively prime to x.
"""
# deprecated in 0.14
warnings.warn(
"Function is unused by library code. If you use this code, "
"please open an issue in "
"https://github.com/tlsfuzzer/python-ecdsa",
DeprecationWarning,
)
return order_mod(x, largest_factor_relatively_prime(m, x))
def is_prime(n):
"""Return True if x is prime, False otherwise.
We use the Miller-Rabin test, as given in Menezes et al. p. 138.
This test is not exact: there are composite values n for which
it returns True.
In testing the odd numbers from 10000001 to 19999999,
about 66 composites got past the first test,
5 got past the second test, and none got past the third.
Since factors of 2, 3, 5, 7, and 11 were detected during
preliminary screening, the number of numbers tested by
Miller-Rabin was (19999999 - 10000001)*(2/3)*(4/5)*(6/7)
= 4.57 million.
"""
# (This is used to study the risk of false positives:)
global miller_rabin_test_count
miller_rabin_test_count = 0
if n <= smallprimes[-1]:
if n in smallprimes:
return True
else:
return False
# 2310 = 2 * 3 * 5 * 7 * 11
if gcd(n, 2310) != 1:
return False
# Choose a number of iterations sufficient to reduce the
# probability of accepting a composite below 2**-80
# (from Menezes et al. Table 4.4):
t = 40
n_bits = 1 + bit_length(n)
assert 11 <= n_bits <= 16384
for k, tt in (
(100, 27),
(150, 18),
(200, 15),
(250, 12),
(300, 9),
(350, 8),
(400, 7),
(450, 6),
(550, 5),
(650, 4),
(850, 3),
(1300, 2),
):
if n_bits < k:
break
t = tt
# Run the test t times:
s = 0
r = n - 1
while (r % 2) == 0:
s = s + 1
r = r // 2
for i in xrange(t):
a = random.choice(smallprimes)
y = pow(a, r, n)
if y != 1 and y != n - 1:
j = 1
while j <= s - 1 and y != n - 1:
y = pow(y, 2, n)
if y == 1:
miller_rabin_test_count = i + 1
return False
j = j + 1
if y != n - 1:
miller_rabin_test_count = i + 1
return False
return True
def next_prime(starting_value):
"""Return the smallest prime larger than the starting value."""
if starting_value < 2:
return 2
result = (starting_value + 1) | 1
while not is_prime(result):
result = result + 2
return result
smallprimes = [
2,
3,
5,
7,
11,
13,
17,
19,
23,
29,
31,
37,
41,
43,
47,
53,
59,
61,
67,
71,
73,
79,
83,
89,
97,
101,
103,
107,
109,
113,
127,
131,
137,
139,
149,
151,
157,
163,
167,
173,
179,
181,
191,
193,
197,
199,
211,
223,
227,
229,
233,
239,
241,
251,
257,
263,
269,
271,
277,
281,
283,
293,
307,
311,
313,
317,
331,
337,
347,
349,
353,
359,
367,
373,
379,
383,
389,
397,
401,
409,
419,
421,
431,
433,
439,
443,
449,
457,
461,
463,
467,
479,
487,
491,
499,
503,
509,
521,
523,
541,
547,
557,
563,
569,
571,
577,
587,
593,
599,
601,
607,
613,
617,
619,
631,
641,
643,
647,
653,
659,
661,
673,
677,
683,
691,
701,
709,
719,
727,
733,
739,
743,
751,
757,
761,
769,
773,
787,
797,
809,
811,
821,
823,
827,
829,
839,
853,
857,
859,
863,
877,
881,
883,
887,
907,
911,
919,
929,
937,
941,
947,
953,
967,
971,
977,
983,
991,
997,
1009,
1013,
1019,
1021,
1031,
1033,
1039,
1049,
1051,
1061,
1063,
1069,
1087,
1091,
1093,
1097,
1103,
1109,
1117,
1123,
1129,
1151,
1153,
1163,
1171,
1181,
1187,
1193,
1201,
1213,
1217,
1223,
1229,
]
miller_rabin_test_count = 0