13832902924

Committed 13 Mar 2025 10:54AM UTC coverage: 99.579% (+0.001%) from 99.578%

Build # 13832902924

Build Type

Pull #359

github

Committed by

web-flow

Commit Message

Merge 658ddc81b into 3c5df06ae

Pull Request Pull Request #359: add release notes for 0.19.1 release

Run Details

2560 of 2571 branches covered (99.57%)

Branch coverage included in aggregate %.

6663 of 6691 relevant lines covered (99.58%)

19.18 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

98.24

/src/ecdsa/numbertheory.py

#! /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

1	#! /usr/bin/env python
2	#
3	# Provide some simple capabilities from number theory.
4	#
5	# Version of 2008.11.14.
6	#
7	# Written in 2005 and 2006 by Peter Pearson and placed in the public domain.
8	# Revision history:
9	# 2008.11.14: Use pow(base, exponent, modulus) for modular_exp.
10	# Make gcd and lcm accept arbitrarily many arguments.
11
12	from __future__ import division	20✔
13
14	import sys	20✔
15	from six import integer_types, PY2	20✔
16	from six.moves import reduce	20✔
17
18	try:	20✔
19	xrange	20✔
20	except NameError:	12✔
21	xrange = range	12✔
22	try:	20✔
23	from gmpy2 import powmod, mpz	20✔
24
25	GMPY2 = True	3✔
26	GMPY = False	3✔
27	except ImportError: # pragma: no branch	17✔
28	GMPY2 = False	17✔
29	try:	17✔
30	from gmpy import mpz	17✔
31
32	GMPY = True	3✔
33	except ImportError:	14✔
34	GMPY = False	14✔
35
36
37	if GMPY2 or GMPY: # pragma: no branch	20✔
38	integer_types = tuple(integer_types + (type(mpz(1)),))	6✔
39
40
41	import math	20✔
42	import warnings	20✔
43	import random	20✔
44	from .util import bit_length	20✔
45
46
47	class Error(Exception):	20✔
48	"""Base class for exceptions in this module."""
49
50	pass	20✔
51
52
53	class JacobiError(Error):	20✔
54	pass	20✔
55
56
57	class SquareRootError(Error):	20✔
58	pass	20✔
59
60
61	class NegativeExponentError(Error):	20✔
62	pass	20✔
63
64
65	def modular_exp(base, exponent, modulus): # pragma: no cover
66	"""Raise base to exponent, reducing by modulus"""
67	# deprecated in 0.14
68	warnings.warn(
69	"Function is unused in library code. If you use this code, "
70	"change to pow() builtin.",
71	DeprecationWarning,
72	)
73	if exponent < 0:
74	raise NegativeExponentError(
75	"Negative exponents (%d) not allowed" % exponent
76	)
77	return pow(base, exponent, modulus)
78
79
80	def polynomial_reduce_mod(poly, polymod, p):	20✔
81	"""Reduce poly by polymod, integer arithmetic modulo p.
82
83	Polynomials are represented as lists of coefficients
84	of increasing powers of x."""
85
86	# This module has been tested only by extensive use
87	# in calculating modular square roots.
88
89	# Just to make this easy, require a monic polynomial:
90	assert polymod[-1] == 1	20✔
91
92	assert len(polymod) > 1	20✔
93
94	while len(poly) >= len(polymod):	20✔
95	if poly[-1] != 0:	20✔
96	for i in xrange(2, len(polymod) + 1):	20✔
97	poly[-i] = (poly[-i] - poly[-1] * polymod[-i]) % p	20✔
98	poly = poly[0:-1]	20✔
99
100	return poly	20✔
101
102
103	def polynomial_multiply_mod(m1, m2, polymod, p):	20✔
104	"""Polynomial multiplication modulo a polynomial over ints mod p.
105
106	Polynomials are represented as lists of coefficients
107	of increasing powers of x."""
108
109	# This is just a seat-of-the-pants implementation.
110
111	# This module has been tested only by extensive use
112	# in calculating modular square roots.
113
114	# Initialize the product to zero:
115
116	prod = (len(m1) + len(m2) - 1) * [0]	20✔
117
118	# Add together all the cross-terms:
119
120	for i in xrange(len(m1)):	20✔
121	for j in xrange(len(m2)):	20✔
122	prod[i + j] = (prod[i + j] + m1[i] * m2[j]) % p	20✔
123
124	return polynomial_reduce_mod(prod, polymod, p)	20✔
125
126
127	def polynomial_exp_mod(base, exponent, polymod, p):	20✔
128	"""Polynomial exponentiation modulo a polynomial over ints mod p.
129
130	Polynomials are represented as lists of coefficients
131	of increasing powers of x."""
132
133	# Based on the Handbook of Applied Cryptography, algorithm 2.227.
134
135	# This module has been tested only by extensive use
136	# in calculating modular square roots.
137
138	assert exponent < p	20✔
139
140	if exponent == 0:	20!
141	return [1]	×
142
143	G = base	20✔
144	k = exponent	20✔
145	if k % 2 == 1:	20!
146	s = G	20✔
147	else:
148	s = [1]	×
149
150	while k > 1:	20✔
151	k = k // 2	20✔
152	G = polynomial_multiply_mod(G, G, polymod, p)	20✔
153	if k % 2 == 1:	20✔
154	s = polynomial_multiply_mod(G, s, polymod, p)	20✔
155
156	return s	20✔
157
158
159	def jacobi(a, n):	20✔
160	"""Jacobi symbol"""
161
162	# Based on the Handbook of Applied Cryptography (HAC), algorithm 2.149.
163
164	# This function has been tested by comparison with a small
165	# table printed in HAC, and by extensive use in calculating
166	# modular square roots.
167
168	if not n >= 3:	20!
169	raise JacobiError("n must be larger than 2")	×
170	if not n % 2 == 1:	20✔
171	raise JacobiError("n must be odd")	20✔
172	a = a % n	20✔
173	if a == 0:	20✔
174	return 0	20✔
175	if a == 1:	20✔
176	return 1	20✔
177	a1, e = a, 0	20✔
178	while a1 % 2 == 0:	20✔
179	a1, e = a1 // 2, e + 1	20✔
180	if e % 2 == 0 or n % 8 == 1 or n % 8 == 7:	20✔
181	s = 1	20✔
182	else:
183	s = -1	20✔
184	if a1 == 1:	20✔
185	return s	20✔
186	if n % 4 == 3 and a1 % 4 == 3:	20✔
187	s = -s	20✔
188	return s * jacobi(n % a1, a1)	20✔
189
190
191	def square_root_mod_prime(a, p):	20✔
192	"""Modular square root of a, mod p, p prime."""
193
194	# Based on the Handbook of Applied Cryptography, algorithms 3.34 to 3.39.
195
196	# This module has been tested for all values in [0,p-1] for
197	# every prime p from 3 to 1229.
198
199	assert 0 <= a < p	20✔
200	assert 1 < p	20✔
201
202	if a == 0:	20✔
203	return 0	20✔
204	if p == 2:	20✔
205	return a	20✔
206
207	jac = jacobi(a, p)	20✔
208	if jac == -1:	20✔
209	raise SquareRootError("%d has no square root modulo %d" % (a, p))	20✔
210
211	if p % 4 == 3:	20✔
212	return pow(a, (p + 1) // 4, p)	20✔
213
214	if p % 8 == 5:	20✔
215	d = pow(a, (p - 1) // 4, p)	20✔
216	if d == 1:	20✔
217	return pow(a, (p + 3) // 8, p)	20✔
218	assert d == p - 1	20✔
219	return (2 * a * pow(4 * a, (p - 5) // 8, p)) % p	20✔
220
221	if PY2:	20✔
222	# xrange on python2 can take integers representable as C long only
223	range_top = min(0x7FFFFFFF, p)	8✔
224	else:
225	range_top = p	12✔
226	for b in xrange(2, range_top): # pragma: no branch	20✔
227	if jacobi(b * b - 4 * a, p) == -1:	20✔
228	f = (a, -b, 1)	20✔
229	ff = polynomial_exp_mod((0, 1), (p + 1) // 2, f, p)	20✔
230	if ff[1]:	20✔
231	raise SquareRootError("p is not prime")	20✔
232	return ff[0]	20✔
233	# just an assertion
234	raise RuntimeError("No b found.") # pragma: no cover
235
236
237	# because all the inverse_mod code is arch/environment specific, and coveralls
238	# expects it to execute equal number of times, we need to waive it by
239	# adding the "no branch" pragma to all branches
240	if GMPY2: # pragma: no branch	20✔
241
242	def inverse_mod(a, m):	3✔
243	"""Inverse of a mod m."""
244	if a == 0: # pragma: no branch	3✔
245	return 0	3✔
246	return powmod(a, -1, m)	3✔
247
248	elif GMPY: # pragma: no branch	17✔
249
250	def inverse_mod(a, m):	3✔
251	"""Inverse of a mod m."""
252	# while libgmp does support inverses modulo, it is accessible
253	# only using the native `pow()` function, and `pow()` in gmpy sanity
254	# checks the parameters before passing them on to underlying
255	# implementation
256	if a == 0: # pragma: no branch	3✔
257	return 0	3✔
258	a = mpz(a)	3✔
259	m = mpz(m)	3✔
260
261	lm, hm = mpz(1), mpz(0)	3✔
262	low, high = a % m, m	3✔
263	while low > 1: # pragma: no branch	3✔
264	r = high // low	3✔
265	lm, low, hm, high = hm - lm * r, high - low * r, lm, low	3✔
266
267	return lm % m	3✔
268
269	elif sys.version_info >= (3, 8): # pragma: no branch	14✔
270
271	def inverse_mod(a, m):	7✔
272	"""Inverse of a mod m."""
273	if a == 0: # pragma: no branch	7✔
274	return 0	7✔
275	return pow(a, -1, m)	7✔
276
277	else: # pragma: no branch
278
279	def inverse_mod(a, m):	7✔
280	"""Inverse of a mod m."""
281
282	if a == 0: # pragma: no branch	7✔
283	return 0	7✔
284
285	lm, hm = 1, 0	7✔
286	low, high = a % m, m	7✔
287	while low > 1: # pragma: no branch	7✔
288	r = high // low	7✔
289	lm, low, hm, high = hm - lm * r, high - low * r, lm, low	7✔
290
291	return lm % m	7✔
292
293
294	try:	20✔
295	gcd2 = math.gcd	20✔
296	except AttributeError:	8✔
297
298	def gcd2(a, b):	8✔
299	"""Greatest common divisor using Euclid's algorithm."""
300	while a:	8✔
301	a, b = b % a, a	8✔
302	return b	8✔
303
304
305	def gcd(*a):	20✔
306	"""Greatest common divisor.
307
308	Usage: gcd([ 2, 4, 6 ])
309	or: gcd(2, 4, 6)
310	"""
311
312	if len(a) > 1:	20✔
313	return reduce(gcd2, a)	20✔
314	if hasattr(a[0], "__iter__"):	20✔
315	return reduce(gcd2, a[0])	20✔
316	return a[0]	20✔
317
318
319	def lcm2(a, b):	20✔
320	"""Least common multiple of two integers."""
321
322	return (a * b) // gcd(a, b)	20✔
323
324
325	def lcm(*a):	20✔
326	"""Least common multiple.
327
328	Usage: lcm([ 3, 4, 5 ])
329	or: lcm(3, 4, 5)
330	"""
331
332	if len(a) > 1:	20✔
333	return reduce(lcm2, a)	20✔
334	if hasattr(a[0], "__iter__"):	20✔
335	return reduce(lcm2, a[0])	20✔
336	return a[0]	20✔
337
338
339	def factorization(n):	20✔
340	"""Decompose n into a list of (prime,exponent) pairs."""
341
342	assert isinstance(n, integer_types)	20✔
343
344	if n < 2:	20✔
345	return []	19✔
346
347	result = []	20✔
348
349	# Test the small primes:
350
351	for d in smallprimes:	20✔
352	if d > n:	20✔
353	break	20✔
354	q, r = divmod(n, d)	20✔
355	if r == 0:	20✔
356	count = 1	20✔
357	while d <= n: # pragma: no branch	20✔
358	n = q	20✔
359	q, r = divmod(n, d)	20✔
360	if r != 0:	20✔
361	break	20✔
362	count = count + 1	20✔
363	result.append((d, count))	20✔
364
365	# If n is still greater than the last of our small primes,
366	# it may require further work:
367
368	if n > smallprimes[-1]:	20✔
369	if is_prime(n): # If what's left is prime, it's easy:	20✔
370	result.append((n, 1))	20✔
371	else: # Ugh. Search stupidly for a divisor:
372	d = smallprimes[-1]	20✔
373	while 1:	18✔
374	d = d + 2 # Try the next divisor.	20✔
375	q, r = divmod(n, d)	20✔
376	if q < d: # n < d*d means we're done, n = 1 or prime.	20✔
377	break	20✔
378	if r == 0: # d divides n. How many times?	20✔
379	count = 1	20✔
380	n = q	20✔
381	# As long as d might still divide n,
382	while d <= n: # pragma: no branch	20✔
383	q, r = divmod(n, d) # see if it does.	20✔
384	if r != 0:	20✔
385	break	20✔
386	n = q # It does. Reduce n, increase count.	20✔
387	count = count + 1	20✔
388	result.append((d, count))	20✔
389	if n > 1:	20!
390	result.append((n, 1))	20✔
391
392	return result	20✔
393
394
395	def phi(n): # pragma: no cover
396	"""Return the Euler totient function of n."""
397	# deprecated in 0.14
398	warnings.warn(
399	"Function is unused by library code. If you use this code, "
400	"please open an issue in "
401	"https://github.com/tlsfuzzer/python-ecdsa",
402	DeprecationWarning,
403	)
404
405	assert isinstance(n, integer_types)
406
407	if n < 3:
408	return 1
409
410	result = 1
411	ff = factorization(n)
412	for f in ff:
413	e = f[1]
414	if e > 1:
415	result = result * f[0] ** (e - 1) * (f[0] - 1)
416	else:
417	result = result * (f[0] - 1)
418	return result
419
420
421	def carmichael(n): # pragma: no cover
422	"""Return Carmichael function of n.
423
424	Carmichael(n) is the smallest integer x such that
425	m**x = 1 mod n for all m relatively prime to n.
426	"""
427	# deprecated in 0.14
428	warnings.warn(
429	"Function is unused by library code. If you use this code, "
430	"please open an issue in "
431	"https://github.com/tlsfuzzer/python-ecdsa",
432	DeprecationWarning,
433	)
434
435	return carmichael_of_factorized(factorization(n))
436
437
438	def carmichael_of_factorized(f_list): # pragma: no cover
439	"""Return the Carmichael function of a number that is
440	represented as a list of (prime,exponent) pairs.
441	"""
442	# deprecated in 0.14
443	warnings.warn(
444	"Function is unused by library code. If you use this code, "
445	"please open an issue in "
446	"https://github.com/tlsfuzzer/python-ecdsa",
447	DeprecationWarning,
448	)
449
450	if len(f_list) < 1:
451	return 1
452
453	result = carmichael_of_ppower(f_list[0])
454	for i in xrange(1, len(f_list)):
455	result = lcm(result, carmichael_of_ppower(f_list[i]))
456
457	return result
458
459
460	def carmichael_of_ppower(pp): # pragma: no cover
461	"""Carmichael function of the given power of the given prime."""
462	# deprecated in 0.14
463	warnings.warn(
464	"Function is unused by library code. If you use this code, "
465	"please open an issue in "
466	"https://github.com/tlsfuzzer/python-ecdsa",
467	DeprecationWarning,
468	)
469
470	p, a = pp
471	if p == 2 and a > 2:
472	return 2 ** (a - 2)
473	else:
474	return (p - 1) * p ** (a - 1)
475
476
477	def order_mod(x, m): # pragma: no cover
478	"""Return the order of x in the multiplicative group mod m."""
479	# deprecated in 0.14
480	warnings.warn(
481	"Function is unused by library code. If you use this code, "
482	"please open an issue in "
483	"https://github.com/tlsfuzzer/python-ecdsa",
484	DeprecationWarning,
485	)
486
487	# Warning: this implementation is not very clever, and will
488	# take a long time if m is very large.
489
490	if m <= 1:
491	return 0
492
493	assert gcd(x, m) == 1
494
495	z = x
496	result = 1
497	while z != 1:
498	z = (z * x) % m
499	result = result + 1
500	return result
501
502
503	def largest_factor_relatively_prime(a, b): # pragma: no cover
504	"""Return the largest factor of a relatively prime to b."""
505	# deprecated in 0.14
506	warnings.warn(
507	"Function is unused by library code. If you use this code, "
508	"please open an issue in "
509	"https://github.com/tlsfuzzer/python-ecdsa",
510	DeprecationWarning,
511	)
512
513	while 1:
514	d = gcd(a, b)
515	if d <= 1:
516	break
517	b = d
518	while 1:
519	q, r = divmod(a, d)
520	if r > 0:
521	break
522	a = q
523	return a
524
525
526	def kinda_order_mod(x, m): # pragma: no cover
527	"""Return the order of x in the multiplicative group mod m',
528	where m' is the largest factor of m relatively prime to x.
529	"""
530	# deprecated in 0.14
531	warnings.warn(
532	"Function is unused by library code. If you use this code, "
533	"please open an issue in "
534	"https://github.com/tlsfuzzer/python-ecdsa",
535	DeprecationWarning,
536	)
537
538	return order_mod(x, largest_factor_relatively_prime(m, x))
539
540
541	def is_prime(n):	20✔
542	"""Return True if x is prime, False otherwise.
543
544	We use the Miller-Rabin test, as given in Menezes et al. p. 138.
545	This test is not exact: there are composite values n for which
546	it returns True.
547
548	In testing the odd numbers from 10000001 to 19999999,
549	about 66 composites got past the first test,
550	5 got past the second test, and none got past the third.
551	Since factors of 2, 3, 5, 7, and 11 were detected during
552	preliminary screening, the number of numbers tested by
553	Miller-Rabin was (19999999 - 10000001)(2/3)(4/5)*(6/7)
554	= 4.57 million.
555	"""
556
557	# (This is used to study the risk of false positives:)
558	global miller_rabin_test_count
559
560	miller_rabin_test_count = 0	20✔
561
562	if n <= smallprimes[-1]:	20✔
563	if n in smallprimes:	20✔
564	return True	20✔
565	else:
566	return False	20✔
567	# 2310 = 2 * 3 * 5 * 7 * 11
568	if gcd(n, 2310) != 1:	20✔
569	return False	20✔
570
571	# Choose a number of iterations sufficient to reduce the
572	# probability of accepting a composite below 2**-80
573	# (from Menezes et al. Table 4.4):
574
575	t = 40	20✔
576	n_bits = 1 + bit_length(n)	20✔
577	assert 11 <= n_bits <= 16384	20✔
578	for k, tt in (	20✔
579	(100, 27),
580	(150, 18),
581	(200, 15),
582	(250, 12),
583	(300, 9),
584	(350, 8),
585	(400, 7),
586	(450, 6),
587	(550, 5),
588	(650, 4),
589	(850, 3),
590	(1300, 2),
591	):
592	if n_bits < k:	20✔
593	break	20✔
594	t = tt	20✔
595
596	# Run the test t times:
597
598	s = 0	20✔
599	r = n - 1	20✔
600	while (r % 2) == 0:	20✔
601	s = s + 1	20✔
602	r = r // 2	20✔
603	for i in xrange(t):	20✔
604	a = random.choice(smallprimes)	20✔
605	y = pow(a, r, n)	20✔
606	if y != 1 and y != n - 1:	20✔
607	j = 1	20✔
608	while j <= s - 1 and y != n - 1:	20✔
609	y = pow(y, 2, n)	20✔
610	if y == 1:	20✔
611	miller_rabin_test_count = i + 1	4✔
612	return False	4✔
613	j = j + 1	20✔
614	if y != n - 1:	20✔
615	miller_rabin_test_count = i + 1	20✔
616	return False	20✔
617	return True	20✔
618
619
620	def next_prime(starting_value):	20✔
621	"""Return the smallest prime larger than the starting value."""
622
623	if starting_value < 2:	20✔
624	return 2	20✔
625	result = (starting_value + 1) \| 1	20✔
626	while not is_prime(result):	20✔
627	result = result + 2	20✔
628	return result	20✔
629
630
631	smallprimes = [	20✔
632	2,
633	3,
634	5,
635	7,
636	11,
637	13,
638	17,
639	19,
640	23,
641	29,
642	31,
643	37,
644	41,
645	43,
646	47,
647	53,
648	59,
649	61,
650	67,
651	71,
652	73,
653	79,
654	83,
655	89,
656	97,
657	101,
658	103,
659	107,
660	109,
661	113,
662	127,
663	131,
664	137,
665	139,
666	149,
667	151,
668	157,
669	163,
670	167,
671	173,
672	179,
673	181,
674	191,
675	193,
676	197,
677	199,
678	211,
679	223,
680	227,
681	229,
682	233,
683	239,
684	241,
685	251,
686	257,
687	263,
688	269,
689	271,
690	277,
691	281,
692	283,
693	293,
694	307,
695	311,
696	313,
697	317,
698	331,
699	337,
700	347,
701	349,
702	353,
703	359,
704	367,
705	373,
706	379,
707	383,
708	389,
709	397,
710	401,
711	409,
712	419,
713	421,
714	431,
715	433,
716	439,
717	443,
718	449,
719	457,
720	461,
721	463,
722	467,
723	479,
724	487,
725	491,
726	499,
727	503,
728	509,
729	521,
730	523,
731	541,
732	547,
733	557,
734	563,
735	569,
736	571,
737	577,
738	587,
739	593,
740	599,
741	601,
742	607,
743	613,
744	617,
745	619,
746	631,
747	641,
748	643,
749	647,
750	653,
751	659,
752	661,
753	673,
754	677,
755	683,
756	691,
757	701,
758	709,
759	719,
760	727,
761	733,
762	739,
763	743,
764	751,
765	757,
766	761,
767	769,
768	773,
769	787,
770	797,
771	809,
772	811,
773	821,
774	823,
775	827,
776	829,
777	839,
778	853,
779	857,
780	859,
781	863,
782	877,
783	881,
784	883,
785	887,
786	907,
787	911,
788	919,
789	929,
790	937,
791	941,
792	947,
793	953,
794	967,
795	971,
796	977,
797	983,
798	991,
799	997,
800	1009,
801	1013,
802	1019,
803	1021,
804	1031,
805	1033,
806	1039,
807	1049,
808	1051,
809	1061,
810	1063,
811	1069,
812	1087,
813	1091,
814	1093,
815	1097,
816	1103,
817	1109,
818	1117,
819	1123,
820	1129,
821	1151,
822	1153,
823	1163,
824	1171,
825	1181,
826	1187,
827	1193,
828	1201,
829	1213,
830	1217,
831	1223,
832	1229,
833	]
834
835	miller_rabin_test_count = 0	20✔

tlsfuzzer / python-ecdsa / 13832902924

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous