btclib-org / btclib / 754

Committed 1 Sep 2020 - 15:27 coverage: 99.89% (-0.1%) from 99.987%

Build # 754

Build Type

Pull #44

travis-ci

Committed by

web-flow

Commit Message

Merge fd61e71d4 into f9e283887

Pull Request Pull Request #44: Assorted elliptic curve point multiplication

Run Details

762 of 770 new or added lines in 34 files covered. (98.96%)

8142 of 8151 relevant lines covered (99.89%)

1.0 hits per line

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

97.12

/btclib/tests/test_curve.py

#!/usr/bin/env python3

# Copyright (C) 2017-2020 The btclib developers
#
# This file is part of btclib. It is subject to the license terms in the
# LICENSE file found in the top-level directory of this distribution.
#
# No part of btclib including this file, may be copied, modified, propagated,
# or distributed except according to the terms contained in the LICENSE file.

"Tests for `btclib.curve` module."

import secrets
from typing import Dict

import pytest

from btclib.alias import INF, INFJ
from btclib.curve import CURVES, Curve, double_mult, mult, multi_mult, secp256k1
from btclib.curvegroup import _jac_from_aff
from btclib.numbertheory import mod_sqrt
from btclib.pedersen import second_generator

# FIXME Curve repr should use "dedbeef 00000000", not "0xdedbeef00000000"
# FIXME test curves when n>p

# test curves: very low cardinality
low_card_curves: Dict[str, Curve] = {}
# 13 % 4 = 1; 13 % 8 = 5
low_card_curves["ec13_11"] = Curve(13, 7, 6, (1, 1), 11, 1, False)
low_card_curves["ec13_19"] = Curve(13, 0, 2, (1, 9), 19, 1, False)
# 17 % 4 = 1; 17 % 8 = 1
low_card_curves["ec17_13"] = Curve(17, 6, 8, (0, 12), 13, 2, False)
low_card_curves["ec17_23"] = Curve(17, 3, 5, (1, 14), 23, 1, False)
# 19 % 4 = 3; 19 % 8 = 3
low_card_curves["ec19_13"] = Curve(19, 0, 2, (4, 16), 13, 2, False)
low_card_curves["ec19_23"] = Curve(19, 2, 9, (0, 16), 23, 1, False)
# 23 % 4 = 3; 23 % 8 = 7
low_card_curves["ec23_19"] = Curve(23, 9, 7, (5, 4), 19, 1, False)
low_card_curves["ec23_31"] = Curve(23, 5, 1, (0, 1), 31, 1, False)

all_curves: Dict[str, Curve] = {}
all_curves.update(low_card_curves)
all_curves.update(CURVES)

ec23_31 = low_card_curves["ec23_31"]


def test_exceptions() -> None:

    # good curve
    Curve(13, 0, 2, (1, 9), 19, 1, False)

    with pytest.raises(ValueError, match="p is not prime: "):
        Curve(15, 0, 2, (1, 9), 19, 1, False)

    with pytest.raises(ValueError, match="negative a: "):
        Curve(13, -1, 2, (1, 9), 19, 1, False)

    with pytest.raises(ValueError, match="p <= a: "):
        Curve(13, 13, 2, (1, 9), 19, 1, False)

    with pytest.raises(ValueError, match="negative b: "):
        Curve(13, 0, -2, (1, 9), 19, 1, False)

    with pytest.raises(ValueError, match="p <= b: "):
        Curve(13, 0, 13, (1, 9), 19, 1, False)

    with pytest.raises(ValueError, match="zero discriminant"):
        Curve(11, 7, 7, (1, 9), 19, 1, False)

    err_msg = "Generator must a be a sequence\\[int, int\\]"
    with pytest.raises(ValueError, match=err_msg):
        Curve(13, 0, 2, (1, 9, 1), 19, 1, False)  # type: ignore

    with pytest.raises(ValueError, match="Generator is not on the curve"):
        Curve(13, 0, 2, (2, 9), 19, 1, False)

    with pytest.raises(ValueError, match="n is not prime: "):
        Curve(13, 0, 2, (1, 9), 20, 1, False)

    with pytest.raises(ValueError, match="n not in "):
        Curve(13, 0, 2, (1, 9), 71, 1, False)

    with pytest.raises(ValueError, match="INF point cannot be a generator"):
        Curve(13, 0, 2, INF, 19, 1, False)

    with pytest.raises(ValueError, match="n is not the group order: "):
        Curve(13, 0, 2, (1, 9), 17, 1, False)

    with pytest.raises(ValueError, match="invalid h: "):
        Curve(13, 0, 2, (1, 9), 19, 2, False)

    # n=p -> weak curve
    # missing

    with pytest.raises(UserWarning, match="weak curve"):
        Curve(11, 2, 7, (6, 9), 7, 2, True)


def test_aff_jac_conversions() -> None:
    for ec in all_curves.values():

        # just a random point, not INF
        q = 1 + secrets.randbelow(ec.n - 1)
        Q = mult(q, ec.G, ec)
        QJ = _jac_from_aff(Q)
        assert Q == ec._aff_from_jac(QJ)
        x_Q = ec._x_aff_from_jac(QJ)
        assert Q[0] == x_Q

        assert INF == ec._aff_from_jac(_jac_from_aff(INF))

        # relevant for BIP340-Schnorr signature verification
        assert not ec.has_square_y(INF)
        with pytest.raises(ValueError, match="infinity point has no x-coordinate"):
            ec._x_aff_from_jac(INFJ)
        with pytest.raises(TypeError, match="not a point"):
            ec.has_square_y("notapoint")  # type: ignore


def test_add_double_aff() -> None:
    "Test self-consistency of add and double in affine coordinates."
    for ec in all_curves.values():

        # add G and the infinity point
        assert ec._add_aff(ec.G, INF) == ec.G
        assert ec._add_aff(INF, ec.G) == ec.G

        # double G
        G2 = ec._add_aff(ec.G, ec.G)
        assert G2 == ec._double_aff(ec.G)

        # double INF
        assert ec._add_aff(INF, INF) == INF
        assert ec._double_aff(INF) == INF

        # add G and minus G
        assert ec._add_aff(ec.G, ec.negate(ec.G)) == INF

        # add INF and "minus" INF
        assert ec._add_aff(INF, ec.negate(INF)) == INF


def test_add_double_jac() -> None:
    "Test self-consistency of add and double in Jacobian coordinates."
    for ec in all_curves.values():

        # add G and the infinity point
        assert ec._jac_equality(ec._add_jac(ec.GJ, INFJ), ec.GJ)
        assert ec._jac_equality(ec._add_jac(INFJ, ec.GJ), ec.GJ)

        # double G
        GJ2 = ec._add_jac(ec.GJ, ec.GJ)
        assert ec._jac_equality(GJ2, ec._double_jac(ec.GJ))

        # double INF
        assert ec._jac_equality(ec._add_jac(INFJ, INFJ), INFJ)
        assert ec._jac_equality(ec._double_jac(INFJ), INFJ)

        # add G and minus G
        assert ec._jac_equality(ec._add_jac(ec.GJ, ec.negate_jac(ec.GJ)), INFJ)

        # add INF and "minus" INF
        assert ec._jac_equality(ec._add_jac(INFJ, ec.negate_jac(INFJ)), INFJ)


def test_add_double_aff_jac() -> None:
    "Test consistency between affine and Jacobian add/double methods."
    for ec in all_curves.values():

        # just a random point, not INF
        q = 1 + secrets.randbelow(ec.n - 1)
        Q = mult(q, ec.G, ec)
        QJ = _jac_from_aff(Q)

        # add Q and G
        R = ec._add_aff(Q, ec.G)
        RJ = ec._add_jac(QJ, ec.GJ)
        assert R == ec._aff_from_jac(RJ)

        # double Q
        R = ec._double_aff(Q)
        RJ = ec._double_jac(QJ)
        assert R == ec._aff_from_jac(RJ)
        assert R == ec._add_aff(Q, Q)
        assert ec._jac_equality(RJ, ec._add_jac(QJ, QJ))


def test_ec_repr() -> None:
    for ec in all_curves.values():
        ec_repr = repr(ec)
        if ec in low_card_curves.values() or ec.psize < 24:
            ec_repr = ec_repr[:-1] + ", False)"
        ec2 = eval(ec_repr)
        assert str(ec) == str(ec2)


def test_is_on_curve() -> None:
    for ec in all_curves.values():

        with pytest.raises(ValueError, match="point must be a tuple"):
            ec.is_on_curve("not a point")  # type: ignore

        with pytest.raises(ValueError, match="x-coordinate not in 0..p-1: "):
            ec.y(ec.p)

        # just a random point, not INF
        q = 1 + secrets.randbelow(ec.n - 1)
        Q = mult(q, ec.G, ec)
        with pytest.raises(ValueError, match="y-coordinate not in 1..p-1: "):
            ec.is_on_curve((Q[0], ec.p))


def test_negate() -> None:
    for ec in all_curves.values():

        # just a random point, not INF
        q = 1 + secrets.randbelow(ec.n - 1)
        Q = mult(q, ec.G, ec)
        minus_Q = ec.negate(Q)
        assert ec.add(Q, minus_Q) == INF

        # Jacobian coordinates
        QJ = _jac_from_aff(Q)
        minus_QJ = ec.negate_jac(QJ)
        assert ec._jac_equality(ec._add_jac(QJ, minus_QJ), INFJ)

        # negate of INF is INF
        minus_INF = ec.negate(INF)
        assert minus_INF == INF

        # negate of INFJ is INFJ
        minus_INFJ = ec.negate_jac(INFJ)
        assert ec._jac_equality(minus_INFJ, INFJ)

    with pytest.raises(TypeError, match="not a point"):
        ec.negate(ec.GJ)  # type: ignore

    with pytest.raises(TypeError, match="not a Jacobian point"):
        ec.negate_jac(ec.G)  # type: ignore


def test_symmetry() -> None:
    """Methods to break simmetry: quadratic residue, odd/even, low/high"""
    for ec in low_card_curves.values():

        # just a random point, not INF
        q = 1 + secrets.randbelow(ec.n - 1)
        Q = mult(q, ec.G, ec)
        x_Q = Q[0]

        y_odd = ec.y_odd(x_Q)
        assert y_odd % 2 == 1
        y_even = ec.y_odd(x_Q, False)
        assert y_even % 2 == 0
        assert y_even == ec.p - y_odd

        y_low = ec.y_low(x_Q)
        y_high = ec.y_low(x_Q, False)
        assert y_low < y_high
        assert y_high == ec.p - y_low

        # compute quadratic residues
        hasRoot = {1}
        for i in range(2, ec.p):
            hasRoot.add(i * i % ec.p)

        if ec.p % 4 == 3:
            quad_res = ec.y_quadratic_residue(x_Q)
            not_quad_res = ec.y_quadratic_residue(x_Q, False)

            # in this case only quad_res is a quadratic residue
            assert quad_res in hasRoot
            root = mod_sqrt(quad_res, ec.p)
            assert quad_res == (root * root) % ec.p
            root = ec.p - root
            assert quad_res == (root * root) % ec.p

            assert not_quad_res == ec.p - quad_res
            assert not_quad_res not in hasRoot
            with pytest.raises(ValueError, match="no root for "):
                mod_sqrt(not_quad_res, ec.p)
        else:
            assert ec.p % 4 == 1
            # cannot use y_quadratic_residue in this case
            err_msg = "field prime is not equal to 3 mod 4: "
            with pytest.raises(ValueError, match=err_msg):
                ec.y_quadratic_residue(x_Q)
            with pytest.raises(ValueError, match=err_msg):
                ec.y_quadratic_residue(x_Q, False)

            # in this case neither or both y_Q are quadratic residues
            neither = y_odd not in hasRoot and y_even not in hasRoot
            both = y_odd in hasRoot and y_even in hasRoot
            assert neither or both
            if y_odd in hasRoot:  # both have roots
                root = mod_sqrt(y_odd, ec.p)
                assert y_odd == (root * root) % ec.p
                root = ec.p - root
                assert y_odd == (root * root) % ec.p
                root = mod_sqrt(y_even, ec.p)
                assert y_even == (root * root) % ec.p
                root = ec.p - root
                assert y_even == (root * root) % ec.p
            else:
                err_msg = "no root for "
                with pytest.raises(ValueError, match=err_msg):
                    mod_sqrt(y_odd, ec.p)
                with pytest.raises(ValueError, match=err_msg):
                    mod_sqrt(y_even, ec.p)

    # with the last curve
    with pytest.raises(ValueError, match="low1high0 must be bool or 1/0"):
        ec.y_low(x_Q, 2)
    with pytest.raises(ValueError, match="odd1even0 must be bool or 1/0"):
        ec.y_odd(x_Q, 2)
    with pytest.raises(ValueError, match="quad_res must be bool or 1/0"):
        ec.y_quadratic_residue(x_Q, 2)


@pytest.mark.fourth
def test_assorted_mult() -> None:
    ec = ec23_31
    H = second_generator(ec)
    for k1 in range(-ec.n + 1, ec.n):
        K1 = mult(k1, ec.G, ec)
        for k2 in range(ec.n):
            K2 = mult(k2, H, ec)

            shamir = double_mult(k1, ec.G, k2, ec.G, ec)
            assert shamir == mult(k1 + k2, ec.G, ec)

            shamir = double_mult(k1, INF, k2, H, ec)
            assert ec.is_on_curve(shamir)
            assert shamir == K2

            shamir = double_mult(k1, ec.G, k2, INF, ec)
            assert ec.is_on_curve(shamir)
            assert shamir == K1

            shamir = double_mult(k1, ec.G, k2, H, ec)
            assert ec.is_on_curve(shamir)
            K1K2 = ec.add(K1, K2)
            assert K1K2 == shamir

            k3 = 1 + secrets.randbelow(ec.n - 1)
            K3 = mult(k3, ec.G, ec)
            K1K2K3 = ec.add(K1K2, K3)
            assert ec.is_on_curve(K1K2K3)
            boscoster = multi_mult([k1, k2, k3], [ec.G, H, ec.G], ec)
            assert ec.is_on_curve(boscoster)
            assert K1K2K3 == boscoster, k3

            k4 = 1 + secrets.randbelow(ec.n - 1)
            K4 = mult(k4, H, ec)
            K1K2K3K4 = ec.add(K1K2K3, K4)
            assert ec.is_on_curve(K1K2K3K4)
            points = [ec.G, H, ec.G, H]
            boscoster = multi_mult([k1, k2, k3, k4], points, ec)
            assert ec.is_on_curve(boscoster)
            assert K1K2K3K4 == boscoster, k4
            assert K1K2K3 == multi_mult([k1, k2, k3, 0], points, ec)
            assert K1K2 == multi_mult([k1, k2, 0, 0], points, ec)
            assert K1 == multi_mult([k1, 0, 0, 0], points, ec)
            assert INF == multi_mult([0, 0, 0, 0], points, ec)

    err_msg = "mismatch between number of scalars and points: "
    with pytest.raises(ValueError, match=err_msg):
        multi_mult([k1, k2, k3, k4], [ec.G, H, ec.G], ec)


def test_double_mult() -> None:
    H = second_generator(secp256k1)
    G = secp256k1.G

    # 0*G + 1*H
    T = double_mult(1, H, 0, G)
    assert T == H
    T = multi_mult([1, 0], [H, G])
    assert T == H

    # 0*G + 2*H
    exp = mult(2, H)
    T = double_mult(2, H, 0, G)
    assert T == exp
    T = multi_mult([2, 0], [H, G])
    assert T == exp

    # 0*G + 3*H
    exp = mult(3, H)
    T = double_mult(3, H, 0, G)
    assert T == exp
    T = multi_mult([3, 0], [H, G])
    assert T == exp

    # 1*G + 0*H
    T = double_mult(0, H, 1, G)
    assert T == G
    T = multi_mult([0, 1], [H, G])
    assert T == G

    # 2*G + 0*H
    exp = mult(2, G)
    T = double_mult(0, H, 2, G)
    assert T == exp
    T = multi_mult([0, 2], [H, G])
    assert T == exp

    # 3*G + 0*H
    exp = mult(3, G)
    T = double_mult(0, H, 3, G)
    assert T == exp
    T = multi_mult([0, 3], [H, G])
    assert T == exp

    # 0*G + 5*H
    exp = mult(5, H)
    T = double_mult(5, H, 0, G)
    assert T == exp
    T = multi_mult([5, 0], [H, G])
    assert T == exp

    # 0*G - 5*H
    exp = mult(-5, H)
    T = double_mult(-5, H, 0, G)
    assert T == exp
    T = multi_mult([-5, 0], [H, G])
    assert T == exp

    # 1*G - 5*H
    exp = secp256k1.add(G, T)
    T = double_mult(-5, H, 1, G)
    assert T == exp
    # FIXME
    # T = multi_mult([-5, 1], [H, G])
    # assert T == exp

1	#!/usr/bin/env python3
2
3	# Copyright (C) 2017-2020 The btclib developers
4	#
5	# This file is part of btclib. It is subject to the license terms in the
6	# LICENSE file found in the top-level directory of this distribution.
7	#
8	# No part of btclib including this file, may be copied, modified, propagated,
9	# or distributed except according to the terms contained in the LICENSE file.
10
11	"Tests for `btclib.curve` module."	1×
12
13	import secrets	1×
14	from typing import Dict	1×
15
16	import pytest	1×
17
18	from btclib.alias import INF, INFJ	1×
19	from btclib.curve import CURVES, Curve, double_mult, mult, multi_mult, secp256k1	1×
20	from btclib.curvegroup import _jac_from_aff	1×
21	from btclib.numbertheory import mod_sqrt	1×
22	from btclib.pedersen import second_generator	1×
23
24	# FIXME Curve repr should use "dedbeef 00000000", not "0xdedbeef00000000"
25	# FIXME test curves when n>p
26
27	# test curves: very low cardinality
28	low_card_curves: Dict[str, Curve] = {}	1×
29	# 13 % 4 = 1; 13 % 8 = 5
30	low_card_curves["ec13_11"] = Curve(13, 7, 6, (1, 1), 11, 1, False)	1×
31	low_card_curves["ec13_19"] = Curve(13, 0, 2, (1, 9), 19, 1, False)	1×
32	# 17 % 4 = 1; 17 % 8 = 1
33	low_card_curves["ec17_13"] = Curve(17, 6, 8, (0, 12), 13, 2, False)	1×
34	low_card_curves["ec17_23"] = Curve(17, 3, 5, (1, 14), 23, 1, False)	1×
35	# 19 % 4 = 3; 19 % 8 = 3
36	low_card_curves["ec19_13"] = Curve(19, 0, 2, (4, 16), 13, 2, False)	1×
37	low_card_curves["ec19_23"] = Curve(19, 2, 9, (0, 16), 23, 1, False)	1×
38	# 23 % 4 = 3; 23 % 8 = 7
39	low_card_curves["ec23_19"] = Curve(23, 9, 7, (5, 4), 19, 1, False)	1×
40	low_card_curves["ec23_31"] = Curve(23, 5, 1, (0, 1), 31, 1, False)	1×
41
42	all_curves: Dict[str, Curve] = {}	1×
43	all_curves.update(low_card_curves)	1×
44	all_curves.update(CURVES)	1×
45
46	ec23_31 = low_card_curves["ec23_31"]	1×
47
48
49	def test_exceptions() -> None:	1×
50
51	# good curve
52	Curve(13, 0, 2, (1, 9), 19, 1, False)	1×
53
54	with pytest.raises(ValueError, match="p is not prime: "):	1×
55	Curve(15, 0, 2, (1, 9), 19, 1, False)	1×
56
57	with pytest.raises(ValueError, match="negative a: "):	1×
58	Curve(13, -1, 2, (1, 9), 19, 1, False)	1×
59
60	with pytest.raises(ValueError, match="p <= a: "):	1×
61	Curve(13, 13, 2, (1, 9), 19, 1, False)	1×
62
63	with pytest.raises(ValueError, match="negative b: "):	1×
64	Curve(13, 0, -2, (1, 9), 19, 1, False)	1×
65
66	with pytest.raises(ValueError, match="p <= b: "):	1×
67	Curve(13, 0, 13, (1, 9), 19, 1, False)	1×
68
69	with pytest.raises(ValueError, match="zero discriminant"):	1×
70	Curve(11, 7, 7, (1, 9), 19, 1, False)	1×
71
72	err_msg = "Generator must a be a sequence\\[int, int\\]"	1×
73	with pytest.raises(ValueError, match=err_msg):	1×
74	Curve(13, 0, 2, (1, 9, 1), 19, 1, False) # type: ignore	1×
75
76	with pytest.raises(ValueError, match="Generator is not on the curve"):	1×
77	Curve(13, 0, 2, (2, 9), 19, 1, False)	1×
78
79	with pytest.raises(ValueError, match="n is not prime: "):	1×
80	Curve(13, 0, 2, (1, 9), 20, 1, False)	1×
81
82	with pytest.raises(ValueError, match="n not in "):	1×
83	Curve(13, 0, 2, (1, 9), 71, 1, False)	1×
84
85	with pytest.raises(ValueError, match="INF point cannot be a generator"):	1×
86	Curve(13, 0, 2, INF, 19, 1, False)	1×
87
88	with pytest.raises(ValueError, match="n is not the group order: "):	1×
89	Curve(13, 0, 2, (1, 9), 17, 1, False)	1×
90
91	with pytest.raises(ValueError, match="invalid h: "):	1×
92	Curve(13, 0, 2, (1, 9), 19, 2, False)	1×
93
94	# n=p -> weak curve
95	# missing
96
97	with pytest.raises(UserWarning, match="weak curve"):	1×
98	Curve(11, 2, 7, (6, 9), 7, 2, True)	1×
99
100
101	def test_aff_jac_conversions() -> None:	1×
102	for ec in all_curves.values():	1×
103
104	# just a random point, not INF
105	q = 1 + secrets.randbelow(ec.n - 1)	1×
106	Q = mult(q, ec.G, ec)	1×
107	QJ = _jac_from_aff(Q)	1×
108	assert Q == ec._aff_from_jac(QJ)	1×
109	x_Q = ec._x_aff_from_jac(QJ)	1×
110	assert Q[0] == x_Q	1×
111
112	assert INF == ec._aff_from_jac(_jac_from_aff(INF))	1×
113
114	# relevant for BIP340-Schnorr signature verification
115	assert not ec.has_square_y(INF)	1×
116	with pytest.raises(ValueError, match="infinity point has no x-coordinate"):	1×
117	ec._x_aff_from_jac(INFJ)	1×
118	with pytest.raises(TypeError, match="not a point"):	1×
119	ec.has_square_y("notapoint") # type: ignore	1×
120
121
122	def test_add_double_aff() -> None:	1×
123	"Test self-consistency of add and double in affine coordinates."
124	for ec in all_curves.values():	1×
125
126	# add G and the infinity point
127	assert ec._add_aff(ec.G, INF) == ec.G	1×
128	assert ec._add_aff(INF, ec.G) == ec.G	1×
129
130	# double G
131	G2 = ec._add_aff(ec.G, ec.G)	1×
132	assert G2 == ec._double_aff(ec.G)	1×
133
134	# double INF
135	assert ec._add_aff(INF, INF) == INF	1×
136	assert ec._double_aff(INF) == INF	1×
137
138	# add G and minus G
139	assert ec._add_aff(ec.G, ec.negate(ec.G)) == INF	1×
140
141	# add INF and "minus" INF
142	assert ec._add_aff(INF, ec.negate(INF)) == INF	1×
143
144
145	def test_add_double_jac() -> None:	1×
146	"Test self-consistency of add and double in Jacobian coordinates."
147	for ec in all_curves.values():	1×
148
149	# add G and the infinity point
150	assert ec._jac_equality(ec._add_jac(ec.GJ, INFJ), ec.GJ)	1×
151	assert ec._jac_equality(ec._add_jac(INFJ, ec.GJ), ec.GJ)	1×
152
153	# double G
154	GJ2 = ec._add_jac(ec.GJ, ec.GJ)	1×
155	assert ec._jac_equality(GJ2, ec._double_jac(ec.GJ))	1×
156
157	# double INF
158	assert ec._jac_equality(ec._add_jac(INFJ, INFJ), INFJ)	1×
159	assert ec._jac_equality(ec._double_jac(INFJ), INFJ)	1×
160
161	# add G and minus G
162	assert ec._jac_equality(ec._add_jac(ec.GJ, ec.negate_jac(ec.GJ)), INFJ)	1×
163
164	# add INF and "minus" INF
165	assert ec._jac_equality(ec._add_jac(INFJ, ec.negate_jac(INFJ)), INFJ)	1×
166
167
168	def test_add_double_aff_jac() -> None:	1×
169	"Test consistency between affine and Jacobian add/double methods."
170	for ec in all_curves.values():	1×
171
172	# just a random point, not INF
173	q = 1 + secrets.randbelow(ec.n - 1)	1×
174	Q = mult(q, ec.G, ec)	1×
175	QJ = _jac_from_aff(Q)	1×
176
177	# add Q and G
178	R = ec._add_aff(Q, ec.G)	1×
179	RJ = ec._add_jac(QJ, ec.GJ)	1×
180	assert R == ec._aff_from_jac(RJ)	1×
181
182	# double Q
183	R = ec._double_aff(Q)	1×
184	RJ = ec._double_jac(QJ)	1×
185	assert R == ec._aff_from_jac(RJ)	1×
186	assert R == ec._add_aff(Q, Q)	1×
187	assert ec._jac_equality(RJ, ec._add_jac(QJ, QJ))	1×
188
189
190	def test_ec_repr() -> None:	1×
191	for ec in all_curves.values():	1×
192	ec_repr = repr(ec)	1×
193	if ec in low_card_curves.values() or ec.psize < 24:	1×
194	ec_repr = ec_repr[:-1] + ", False)"	1×
195	ec2 = eval(ec_repr)	1×
196	assert str(ec) == str(ec2)	1×
197
198
199	def test_is_on_curve() -> None:	1×
200	for ec in all_curves.values():	1×
201
202	with pytest.raises(ValueError, match="point must be a tuple"):	1×
203	ec.is_on_curve("not a point") # type: ignore	1×
204
205	with pytest.raises(ValueError, match="x-coordinate not in 0..p-1: "):	1×
206	ec.y(ec.p)	1×
207
208	# just a random point, not INF
209	q = 1 + secrets.randbelow(ec.n - 1)	1×
210	Q = mult(q, ec.G, ec)	1×
211	with pytest.raises(ValueError, match="y-coordinate not in 1..p-1: "):	1×
212	ec.is_on_curve((Q[0], ec.p))	1×
213
214
215	def test_negate() -> None:	1×
216	for ec in all_curves.values():	1×
217
218	# just a random point, not INF
219	q = 1 + secrets.randbelow(ec.n - 1)	1×
220	Q = mult(q, ec.G, ec)	1×
221	minus_Q = ec.negate(Q)	1×
222	assert ec.add(Q, minus_Q) == INF	1×
223
224	# Jacobian coordinates
225	QJ = _jac_from_aff(Q)	1×
226	minus_QJ = ec.negate_jac(QJ)	1×
227	assert ec._jac_equality(ec._add_jac(QJ, minus_QJ), INFJ)	1×
228
229	# negate of INF is INF
230	minus_INF = ec.negate(INF)	1×
231	assert minus_INF == INF	1×
232
233	# negate of INFJ is INFJ
234	minus_INFJ = ec.negate_jac(INFJ)	1×
235	assert ec._jac_equality(minus_INFJ, INFJ)	1×
236
237	with pytest.raises(TypeError, match="not a point"):	1×
238	ec.negate(ec.GJ) # type: ignore	1×
239
240	with pytest.raises(TypeError, match="not a Jacobian point"):	1×
241	ec.negate_jac(ec.G) # type: ignore	1×
242
243
244	def test_symmetry() -> None:	1×
245	"""Methods to break simmetry: quadratic residue, odd/even, low/high"""
246	for ec in low_card_curves.values():	1×
247
248	# just a random point, not INF
249	q = 1 + secrets.randbelow(ec.n - 1)	1×
250	Q = mult(q, ec.G, ec)	1×
251	x_Q = Q[0]	1×
252
253	y_odd = ec.y_odd(x_Q)	1×
254	assert y_odd % 2 == 1	1×
255	y_even = ec.y_odd(x_Q, False)	1×
256	assert y_even % 2 == 0	1×
257	assert y_even == ec.p - y_odd	1×
258
259	y_low = ec.y_low(x_Q)	1×
260	y_high = ec.y_low(x_Q, False)	1×
261	assert y_low < y_high	1×
262	assert y_high == ec.p - y_low	1×
263
264	# compute quadratic residues
265	hasRoot = {1}	1×
266	for i in range(2, ec.p):	1×
267	hasRoot.add(i * i % ec.p)	1×
268
269	if ec.p % 4 == 3:	1×
270	quad_res = ec.y_quadratic_residue(x_Q)	1×
271	not_quad_res = ec.y_quadratic_residue(x_Q, False)	1×
272
273	# in this case only quad_res is a quadratic residue
274	assert quad_res in hasRoot	1×
275	root = mod_sqrt(quad_res, ec.p)	1×
276	assert quad_res == (root * root) % ec.p	1×
277	root = ec.p - root	1×
278	assert quad_res == (root * root) % ec.p	1×
279
280	assert not_quad_res == ec.p - quad_res	1×
281	assert not_quad_res not in hasRoot	1×
282	with pytest.raises(ValueError, match="no root for "):	1×
283	mod_sqrt(not_quad_res, ec.p)	1×
284	else:
285	assert ec.p % 4 == 1	1×
286	# cannot use y_quadratic_residue in this case
287	err_msg = "field prime is not equal to 3 mod 4: "	1×
288	with pytest.raises(ValueError, match=err_msg):	1×
289	ec.y_quadratic_residue(x_Q)	1×
290	with pytest.raises(ValueError, match=err_msg):	1×
291	ec.y_quadratic_residue(x_Q, False)	1×
292
293	# in this case neither or both y_Q are quadratic residues
294	neither = y_odd not in hasRoot and y_even not in hasRoot	1×
295	both = y_odd in hasRoot and y_even in hasRoot	1×
296	assert neither or both	1×
297	if y_odd in hasRoot: # both have roots	1×
NEW 298	root = mod_sqrt(y_odd, ec.p)	!
NEW 299	assert y_odd == (root * root) % ec.p	!
NEW 300	root = ec.p - root	!
NEW 301	assert y_odd == (root * root) % ec.p	!
NEW 302	root = mod_sqrt(y_even, ec.p)	!
NEW 303	assert y_even == (root * root) % ec.p	!
NEW 304	root = ec.p - root	!
NEW 305	assert y_even == (root * root) % ec.p	!
306	else:
307	err_msg = "no root for "	1×
308	with pytest.raises(ValueError, match=err_msg):	1×
309	mod_sqrt(y_odd, ec.p)	1×
310	with pytest.raises(ValueError, match=err_msg):	1×
311	mod_sqrt(y_even, ec.p)	1×
312
313	# with the last curve
314	with pytest.raises(ValueError, match="low1high0 must be bool or 1/0"):	1×
315	ec.y_low(x_Q, 2)	1×
316	with pytest.raises(ValueError, match="odd1even0 must be bool or 1/0"):	1×
317	ec.y_odd(x_Q, 2)	1×
318	with pytest.raises(ValueError, match="quad_res must be bool or 1/0"):	1×
319	ec.y_quadratic_residue(x_Q, 2)	1×
320
321
322	@pytest.mark.fourth	1×
323	def test_assorted_mult() -> None:	1×
324	ec = ec23_31	1×
325	H = second_generator(ec)	1×
326	for k1 in range(-ec.n + 1, ec.n):	1×
327	K1 = mult(k1, ec.G, ec)	1×
328	for k2 in range(ec.n):	1×
329	K2 = mult(k2, H, ec)	1×
330
331	shamir = double_mult(k1, ec.G, k2, ec.G, ec)	1×
332	assert shamir == mult(k1 + k2, ec.G, ec)	1×
333
334	shamir = double_mult(k1, INF, k2, H, ec)	1×
335	assert ec.is_on_curve(shamir)	1×
336	assert shamir == K2	1×
337
338	shamir = double_mult(k1, ec.G, k2, INF, ec)	1×
339	assert ec.is_on_curve(shamir)	1×
340	assert shamir == K1	1×
341
342	shamir = double_mult(k1, ec.G, k2, H, ec)	1×
343	assert ec.is_on_curve(shamir)	1×
344	K1K2 = ec.add(K1, K2)	1×
345	assert K1K2 == shamir	1×
346
347	k3 = 1 + secrets.randbelow(ec.n - 1)	1×
348	K3 = mult(k3, ec.G, ec)	1×
349	K1K2K3 = ec.add(K1K2, K3)	1×
350	assert ec.is_on_curve(K1K2K3)	1×
351	boscoster = multi_mult([k1, k2, k3], [ec.G, H, ec.G], ec)	1×
352	assert ec.is_on_curve(boscoster)	1×
353	assert K1K2K3 == boscoster, k3	1×
354
355	k4 = 1 + secrets.randbelow(ec.n - 1)	1×
356	K4 = mult(k4, H, ec)	1×
357	K1K2K3K4 = ec.add(K1K2K3, K4)	1×
358	assert ec.is_on_curve(K1K2K3K4)	1×
359	points = [ec.G, H, ec.G, H]	1×
360	boscoster = multi_mult([k1, k2, k3, k4], points, ec)	1×
361	assert ec.is_on_curve(boscoster)	1×
362	assert K1K2K3K4 == boscoster, k4	1×
363	assert K1K2K3 == multi_mult([k1, k2, k3, 0], points, ec)	1×
364	assert K1K2 == multi_mult([k1, k2, 0, 0], points, ec)	1×
365	assert K1 == multi_mult([k1, 0, 0, 0], points, ec)	1×
366	assert INF == multi_mult([0, 0, 0, 0], points, ec)	1×
367
368	err_msg = "mismatch between number of scalars and points: "	1×
369	with pytest.raises(ValueError, match=err_msg):	1×
370	multi_mult([k1, k2, k3, k4], [ec.G, H, ec.G], ec)	1×
371
372
373	def test_double_mult() -> None:	1×
374	H = second_generator(secp256k1)	1×
375	G = secp256k1.G	1×
376
377	# 0G + 1H
378	T = double_mult(1, H, 0, G)	1×
379	assert T == H	1×
380	T = multi_mult([1, 0], [H, G])	1×
381	assert T == H	1×
382
383	# 0G + 2H
384	exp = mult(2, H)	1×
385	T = double_mult(2, H, 0, G)	1×
386	assert T == exp	1×
387	T = multi_mult([2, 0], [H, G])	1×
388	assert T == exp	1×
389
390	# 0G + 3H
391	exp = mult(3, H)	1×
392	T = double_mult(3, H, 0, G)	1×
393	assert T == exp	1×
394	T = multi_mult([3, 0], [H, G])	1×
395	assert T == exp	1×
396
397	# 1G + 0H
398	T = double_mult(0, H, 1, G)	1×
399	assert T == G	1×
400	T = multi_mult([0, 1], [H, G])	1×
401	assert T == G	1×
402
403	# 2G + 0H
404	exp = mult(2, G)	1×
405	T = double_mult(0, H, 2, G)	1×
406	assert T == exp	1×
407	T = multi_mult([0, 2], [H, G])	1×
408	assert T == exp	1×
409
410	# 3G + 0H
411	exp = mult(3, G)	1×
412	T = double_mult(0, H, 3, G)	1×
413	assert T == exp	1×
414	T = multi_mult([0, 3], [H, G])	1×
415	assert T == exp	1×
416
417	# 0G + 5H
418	exp = mult(5, H)	1×
419	T = double_mult(5, H, 0, G)	1×
420	assert T == exp	1×
421	T = multi_mult([5, 0], [H, G])	1×
422	assert T == exp	1×
423
424	# 0G - 5H
425	exp = mult(-5, H)	1×
426	T = double_mult(-5, H, 0, G)	1×
427	assert T == exp	1×
428	T = multi_mult([-5, 0], [H, G])	1×
429	assert T == exp	1×
430
431	# 1G - 5H
432	exp = secp256k1.add(G, T)	1×
433	T = double_mult(-5, H, 1, G)	1×
434	assert T == exp	1×
435	# FIXME
436	# T = multi_mult([-5, 1], [H, G])
437	# assert T == exp

btclib-org / btclib / 754

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