btclib-org / btclib / 697

Committed 29 Aug 2020 - 17:46 coverage: 99.915% (-0.07%) from 99.987%

Build # 697

Build Type

Pull #45

travis-ci

Committed by

web-flow

Commit Message

Merge 108eb07fe into d9045bfc7

Pull Request Pull Request #45: Assorted elliptic curve point multiplication (Sourcery refactored)

Run Details

398 of 398 new or added lines in 5 files covered. (100.0%)

6 existing lines in 1 file now uncovered.

8218 of 8225 relevant lines covered (99.91%)

1.0 hits per line

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

92.59

/btclib/borromean.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.

import secrets
from collections import defaultdict
from hashlib import sha256 as hf  # FIXME: any hf
from typing import Dict, List, Sequence, Tuple

from .alias import Point, String
from .curvemult import double_mult, mult
from .curves import secp256k1 as ec  # FIXME: any curve
from .secpoint import bytes_from_point
from .utils import int_from_bits


def _hash(m: bytes, R: bytes, i: int, j: int) -> bytes:
    temp = m + R
    temp += i.to_bytes(4, byteorder="big") + j.to_bytes(4, byteorder="big")
    return hf(temp).digest()


PubkeyRing = Dict[int, List[Point]]


def _get_msg_format(msg: bytes, pubk_rings: PubkeyRing) -> bytes:
    for pubk_ring in pubk_rings.values():
        for P in pubk_ring:
            msg += bytes_from_point(P, ec)
    return hf(msg).digest()


SValues = Dict[int, List[int]]


def sign(
    msg: String,
    ks: Sequence[int],
    sign_key_idx: Sequence[int],
    sign_keys: Sequence[int],
    pubk_rings: PubkeyRing,
) -> Tuple[bytes, SValues]:
    """Borromean ring signature - signing algorithm

    https://github.com/ElementsProject/borromean-signatures-writeup
    https://github.com/Blockstream/borromean_paper/blob/master/borromean_draft_0.01_9ade1e49.pdf

    inputs:
    - msg: message to be signed (bytes)
    - sign_key_idx: list of indexes representing each signing key per ring
    - sign_keys: list containing the whole set of signing keys (one per ring)
    - pubk_rings: dictionary of sequences representing single rings of pubkeys
    """

    if isinstance(msg, str):
        msg = msg.encode()
    m = _get_msg_format(msg, pubk_rings)

    e0bytes = m
    s: SValues = defaultdict(list)
    e: SValues = defaultdict(list)
    # step 1
    for i, (pubk_ring, j_star, k) in enumerate(
        zip(pubk_rings.values(), sign_key_idx, ks)
    ):
        keys_size = len(pubk_ring)
        s[i] = [0] * keys_size
        e[i] = [0] * keys_size
        start_idx = (j_star + 1) % keys_size
        R = bytes_from_point(mult(k), ec)
        if start_idx != 0:
            for j in range(start_idx, keys_size):
                s[i][j] = secrets.randbits(256)
                e[i][j] = int_from_bits(_hash(m, R, i, j), ec.nlen) % ec.n
                assert 0 < e[i][j] < ec.n, "sign fail: how did you do that?!?"
                T = double_mult(-e[i][j], pubk_ring[j], s[i][j], ec.G)
                R = bytes_from_point(T, ec)
        e0bytes += R
    e0 = hf(e0bytes).digest()
    # step 2
    for i, (j_star, k) in enumerate(zip(sign_key_idx, ks)):
        e[i][0] = int_from_bits(_hash(m, e0, i, 0), ec.nlen) % ec.n
        assert 0 < e[i][0] < ec.n, "sign fail: how did you do that?!?"
        for j in range(1, j_star + 1):
            s[i][j - 1] = secrets.randbits(256)
            T = double_mult(-e[i][j - 1], pubk_rings[i][j - 1], s[i][j - 1], ec.G)
            R = bytes_from_point(T, ec)
            e[i][j] = int_from_bits(_hash(m, R, i, j), ec.nlen) % ec.n
            assert 0 < e[i][j] < ec.n, "sign fail: how did you do that?!?"
        s[i][j_star] = k + sign_keys[i] * e[i][j_star]
    return e0, s


def verify(msg: String, e0: bytes, s: SValues, pubk_rings: PubkeyRing) -> bool:
    """Borromean ring signature - verification algorithm

    inputs:

    - msg: message to be signed (bytes)
    - e0: pinned e-value needed to start the verification algorithm
    - s: s-values, both real (one per ring) and forged
    - pubk_rings: dictionary of sequences representing single rings of pubkeys
    """

    if isinstance(msg, str):
        msg = msg.encode()

    # this is just a try/except wrapper for the Errors
    # raised by assert_as_valid
    try:
        return assert_as_valid(msg, e0, s, pubk_rings)
    except Exception:
        return False


def assert_as_valid(msg: bytes, e0: bytes, s: SValues, pubk_rings: PubkeyRing) -> bool:

    ring_size = len(pubk_rings)
    m = _get_msg_format(msg, pubk_rings)
    e: SValues = defaultdict(list)
    e0bytes = m
    for i in range(ring_size):
        keys_size = len(pubk_rings[i])
        e[i] = [0] * keys_size
        e[i][0] = int_from_bits(_hash(m, e0, i, 0), ec.nlen) % ec.n
        assert e[i][0] != 0, "invalid sig: how did you do that?!?"
        R = b"\0x00"
        for j in range(keys_size):
            T = double_mult(-e[i][j], pubk_rings[i][j], s[i][j], ec.G)
            R = bytes_from_point(T, ec)
            if j != len(pubk_rings[i]) - 1:
                h = _hash(m, R, i, j + 1)
                e[i][j + 1] = int_from_bits(h, ec.nlen) % ec.n
                assert e[i][j + 1] != 0, "invalid sig: how did you do that?!?"
            else:
                e0bytes += R
    e0_prime = hf(e0bytes).digest()
    return e0_prime == e0

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	import secrets	1×
12	from collections import defaultdict	1×
13	from hashlib import sha256 as hf # FIXME: any hf	1×
14	from typing import Dict, List, Sequence, Tuple	1×
15
16	from .alias import Point, String	1×
17	from .curvemult import double_mult, mult	1×
18	from .curves import secp256k1 as ec # FIXME: any curve	1×
19	from .secpoint import bytes_from_point	1×
20	from .utils import int_from_bits	1×
21
22
23	def _hash(m: bytes, R: bytes, i: int, j: int) -> bytes:	1×
24	temp = m + R	1×
25	temp += i.to_bytes(4, byteorder="big") + j.to_bytes(4, byteorder="big")	1×
26	return hf(temp).digest()	1×
27
28
29	PubkeyRing = Dict[int, List[Point]]	1×
30
31
32	def _get_msg_format(msg: bytes, pubk_rings: PubkeyRing) -> bytes:	1×
33	for pubk_ring in pubk_rings.values():	1×
34	for P in pubk_ring:	1×
35	msg += bytes_from_point(P, ec)	1×
36	return hf(msg).digest()	1×
37
38
39	SValues = Dict[int, List[int]]	1×
40
41
42	def sign(	1×
43	msg: String,
44	ks: Sequence[int],
45	sign_key_idx: Sequence[int],
46	sign_keys: Sequence[int],
47	pubk_rings: PubkeyRing,
48	) -> Tuple[bytes, SValues]:
49	"""Borromean ring signature - signing algorithm
50
51	https://github.com/ElementsProject/borromean-signatures-writeup
52	https://github.com/Blockstream/borromean_paper/blob/master/borromean_draft_0.01_9ade1e49.pdf
53
54	inputs:
55	- msg: message to be signed (bytes)
56	- sign_key_idx: list of indexes representing each signing key per ring
57	- sign_keys: list containing the whole set of signing keys (one per ring)
58	- pubk_rings: dictionary of sequences representing single rings of pubkeys
59	"""
60
61	if isinstance(msg, str):	1×
62	msg = msg.encode()	1×
63	m = _get_msg_format(msg, pubk_rings)	1×
64
65	e0bytes = m	1×
66	s: SValues = defaultdict(list)	1×
67	e: SValues = defaultdict(list)	1×
68	# step 1
69	for i, (pubk_ring, j_star, k) in enumerate(	1×
70	zip(pubk_rings.values(), sign_key_idx, ks)
71	):
72	keys_size = len(pubk_ring)	1×
73	s[i] = [0] * keys_size	1×
74	e[i] = [0] * keys_size	1×
75	start_idx = (j_star + 1) % keys_size	1×
76	R = bytes_from_point(mult(k), ec)	1×
77	if start_idx != 0:	1×
UNCOV 78	for j in range(start_idx, keys_size):	!
UNCOV 79	s[i][j] = secrets.randbits(256)	!
UNCOV 80	e[i][j] = int_from_bits(_hash(m, R, i, j), ec.nlen) % ec.n	!
UNCOV 81	assert 0 < e[i][j] < ec.n, "sign fail: how did you do that?!?"	!
UNCOV 82	T = double_mult(-e[i][j], pubk_ring[j], s[i][j], ec.G)	!
UNCOV 83	R = bytes_from_point(T, ec)	!
84	e0bytes += R	1×
85	e0 = hf(e0bytes).digest()	1×
86	# step 2
87	for i, (j_star, k) in enumerate(zip(sign_key_idx, ks)):	1×
88	e[i][0] = int_from_bits(_hash(m, e0, i, 0), ec.nlen) % ec.n	1×
89	assert 0 < e[i][0] < ec.n, "sign fail: how did you do that?!?"	1×
90	for j in range(1, j_star + 1):	1×
91	s[i][j - 1] = secrets.randbits(256)	1×
92	T = double_mult(-e[i][j - 1], pubk_rings[i][j - 1], s[i][j - 1], ec.G)	1×
93	R = bytes_from_point(T, ec)	1×
94	e[i][j] = int_from_bits(_hash(m, R, i, j), ec.nlen) % ec.n	1×
95	assert 0 < e[i][j] < ec.n, "sign fail: how did you do that?!?"	1×
96	s[i][j_star] = k + sign_keys[i] * e[i][j_star]	1×
97	return e0, s	1×
98
99
100	def verify(msg: String, e0: bytes, s: SValues, pubk_rings: PubkeyRing) -> bool:	1×
101	"""Borromean ring signature - verification algorithm
102
103	inputs:
104
105	- msg: message to be signed (bytes)
106	- e0: pinned e-value needed to start the verification algorithm
107	- s: s-values, both real (one per ring) and forged
108	- pubk_rings: dictionary of sequences representing single rings of pubkeys
109	"""
110
111	if isinstance(msg, str):	1×
112	msg = msg.encode()	1×
113
114	# this is just a try/except wrapper for the Errors
115	# raised by assert_as_valid
116	try:	1×
117	return assert_as_valid(msg, e0, s, pubk_rings)	1×
118	except Exception:	1×
119	return False	1×
120
121
122	def assert_as_valid(msg: bytes, e0: bytes, s: SValues, pubk_rings: PubkeyRing) -> bool:	1×
123
124	ring_size = len(pubk_rings)	1×
125	m = _get_msg_format(msg, pubk_rings)	1×
126	e: SValues = defaultdict(list)	1×
127	e0bytes = m	1×
128	for i in range(ring_size):	1×
129	keys_size = len(pubk_rings[i])	1×
130	e[i] = [0] * keys_size	1×
131	e[i][0] = int_from_bits(_hash(m, e0, i, 0), ec.nlen) % ec.n	1×
132	assert e[i][0] != 0, "invalid sig: how did you do that?!?"	1×
133	R = b"\0x00"	1×
134	for j in range(keys_size):	1×
135	T = double_mult(-e[i][j], pubk_rings[i][j], s[i][j], ec.G)	1×
136	R = bytes_from_point(T, ec)	1×
137	if j != len(pubk_rings[i]) - 1:	1×
138	h = _hash(m, R, i, j + 1)	1×
139	e[i][j + 1] = int_from_bits(h, ec.nlen) % ec.n	1×
140	assert e[i][j + 1] != 0, "invalid sig: how did you do that?!?"	1×
141	else:
142	e0bytes += R	1×
143	e0_prime = hf(e0bytes).digest()	1×
144	return e0_prime == e0	1×

btclib-org / btclib / 697

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