btclib-org / btclib / 749

Committed 31 Aug 2020 - 19:43 coverage: 99.975% (-0.01%) from 99.987%

Build # 749

Build Type

Pull #44

travis-ci

Committed by

web-flow

Commit Message

Merge 16ae6c832 into f9e283887

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

Run Details

240 of 241 new or added lines in 2 files covered. (99.59%)

8137 of 8139 relevant lines covered (99.98%)

1.0 hits per line

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

99.21

/btclib/curvemult2.py

#!/usr/bin/env python3

# Copyright (C) 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.

"""Elliptic curve point multiplication functions.

The implemented algorithms are:
    - Montgomery Ladder
    - Scalar multiplication on basis 3
    - Fixed window
    - Sliding window
    - w-ary non-adjacent form (wNAF)

References:
    - https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication
    - https://cryptojedi.org/peter/data/eccss-20130911b.pdf
    - https://ecc2017.cs.ru.nl/slides/ecc2017school-castryck.pdf
    - https://cr.yp.to/bib/2003/joye-ladder.pdf

TODO:
    - Computational cost of the different multiplications
    - New alghoritms at the state-of-art:
        -https://hal.archives-ouvertes.fr/hal-00932199/document
        -https://iacr.org/workshops/ches/ches2006/presentations/Douglas%20Stebila.pdf
        -1-s2.0-S1071579704000395-main
        -https://crypto.stackexchange.com/questions/58506/what-is-the-curve-type-of-secp256k1
    - Constant time alghortims:
        -https://eprint.iacr.org/2011/338.pdf
    - Elegance in the code
    - Solve problem with wNAF and w=1
    - Multi_mult algorithm: why does it work?
"""


from typing import List

from .alias import INFJ, JacPoint
from .curvegroup import CurveGroup


def convert_number_to_base(i: int, base: int) -> List[int]:
    "Return the digits of an integer in the requested base."

    digits: List[int] = []
    while i or not digits:
        i, idx = divmod(i, base)
        digits.append(idx)
    return digits[::-1]


def mods(m: int, w: int) -> int:
    """Signed modulo function.

    FIXME:
    mods does NOT work for w=1.
    However the function in NOT really meant to be used for w=1
    For w=1 it always gives back -1 and enters an infinite loop
    """

    w2 = pow(2, w)
    M = m % w2
    return M - w2 if M >= (w2 / 2) else M


def multiples(Q: JacPoint, size: int, ec: CurveGroup) -> List[JacPoint]:
    "Return {k_i * Q} for k_i in {0, ..., size-1)"

    if size < 2:
        raise ValueError(f"size too low: {size}")
    if size == 2:
        return [INFJ, Q]

    k, odd = divmod(size, 2)

    T = [INFJ, Q, ec._double_jac(Q)]
    for i in range(2, k * 2, 2):
        T.append(ec._add_jac(T[i], Q))
        T.append(ec._double_jac(T[(i + 2) // 2]))

    if not odd:
        T.append(ec._add_jac(T[i], Q))

    return T


def _mult_mont_ladder(m: int, Q: JacPoint, ec: CurveGroup) -> JacPoint:
    """Scalar multiplication using 'Montgomery ladder' algorithm.

    This implementation uses
    'Montgomery ladder' algorithm,
    'left-to-right' binary decomposition of the m coefficient,
    Jacobian coordinates.

    It is constant-time and resistant to the FLUSH+RELOAD attack,
    (see https://eprint.iacr.org/2014/140.pdf)
    as it prevents branch prediction avoiding any if.

    The input point is assumed to be on curve and
    the m coefficient is assumed to have been reduced mod n
    if appropriate (e.g. cyclic groups of order n).
    """

    if m < 0:
        raise ValueError(f"negative m: {hex(m)}")

    # R[0] is the running resultR[1] = R[0] + Q is an ancillary variable
    R = [INFJ, Q]
    for i in [int(i) for i in bin(m)[2:]]:
        R[not i] = ec._add_jac(R[i], R[not i])
        R[i] = ec._double_jac(R[i])
    return R[0]


def _mult_base_3(m: int, Q: JacPoint, ec: CurveGroup) -> JacPoint:
    """Scalar multiplication using ternary decomposition of the scalar.

    This implementation uses
    'double & add' algorithm,
    'left-to-right' biternaryary decomposition of the m coefficient,
    Jacobian coordinates.

    The input point is assumed to be on curve and
    the m coefficient is assumed to have been reduced mod n
    if appropriate (e.g. cyclic groups of order n).
    """

    if m < 0:
        raise ValueError(f"negative m: {hex(m)}")

    # at each step one of the points in T will be added
    # T = multiples(Q, 3, ec)
    T = [INFJ, Q, ec._double_jac(Q)]

    digits = convert_number_to_base(m, 3)

    R = T[digits[0]]
    for i in digits[1:]:
        # 'triple'
        R2 = ec._double_jac(R)
        R3 = ec._add_jac(R2, R)
        # and 'add'
        R = ec._add_jac(R3, T[i])
    return R


def _mult_fixed_window(m: int, Q: JacPoint, w: int, ec: CurveGroup) -> JacPoint:
    """Scalar multiplication using "fixed window".

    It is not constant time.
    For 256-bit scalars choose w=4 or w=5.

    The input point is assumed to be on curve and
    the m coefficient is assumed to have been reduced mod n
    if appropriate (e.g. cyclic groups of order n).
    """

    if m < 0:
        raise ValueError(f"negative m: {hex(m)}")

    # a number cannot be written in basis 1 (ie w=0)
    if w <= 0:
        raise ValueError(f"non positive w: {w}")

    base = pow(2, w)

    # at each step one of the points in T will be added
    T = multiples(Q, base, ec)

    digits = convert_number_to_base(m, base)

    R = T[digits[0]]
    for i in digits[1:]:
        # multiple 'double'
        for _ in range(w):
            R = ec._double_jac(R)
        # and 'add'
        R = ec._add_jac(R, T[i])
    return R


def _mult_sliding_window(m: int, Q: JacPoint, w: int, ec: CurveGroup) -> JacPoint:
    """Scalar multiplication using "sliding window".

    It has the benefit that the pre-computation stage
    is roughly half as complex as the normal windowed method.
    It is not constant time.
    For 256-bit scalars choose w=4 or w=5.

    The input point is assumed to be on curve and
    the m coefficient is assumed to have been reduced mod n
    if appropriate (e.g. cyclic groups of order n).
    """

    if m < 0:
        raise ValueError(f"negative m: {hex(m)}")

    # a number cannot be written in basis 1 (ie w=0)
    if w <= 0:
        raise ValueError(f"non positive w: {w}")

    k = w - 1
    p = pow(2, k)

    # at each step one of the points in T will be added
    P = Q
    for _ in range(k):
        P = ec._double_jac(P)
    T = [P]
    for i in range(1, p):
        T.append(ec._add_jac(T[i - 1], Q))

    digits = convert_number_to_base(m, 2)

    R = INFJ
    i = 0
    while i < len(digits):
        if digits[i] == 0:
            R = ec._double_jac(R)
            i += 1
        else:
            j = len(digits) - i if (len(digits) - i) < w else w
            t = digits[i]
            for a in range(1, j):
                t = 2 * t + digits[i + a]

            if j < w:
                for b in range(i, (i + j)):
                    R = ec._double_jac(R)
                    if digits[b] == 1:
                        R = ec._add_jac(R, Q)
                return R
            else:
                for _ in range(w):
                    R = ec._double_jac(R)
                R = ec._add_jac(R, T[t - p])
                i += j
    return R


def _mult_w_NAF(m: int, Q: JacPoint, w: int, ec: CurveGroup) -> JacPoint:
    """Scalar multiplication in Jacobian coordinates using wNAF.

    This implementation uses the same method called "w-ary non-adjacent form" (wNAF)
    we make use of the fact that point subtraction is as easy as point addition to perform fewer operations compared to sliding-window
    In fact, on Weierstrass curves, known P, -P can be computed on the fly.

    The input point is assumed to be on curve and
    the m coefficient is assumed to have been reduced mod n
    if appropriate (e.g. cyclic groups of order n).
    """
    if m < 0:
        raise ValueError(f"negative m: {hex(m)}")

    # a number cannot be written in basis 1 (ie w=0)
    if w <= 0:
        raise ValueError(f"non positive w: {w}")

    # This exception must be kept to satisfy the following while loop
    if m == 0:
        return INFJ

    i = 0

    M: List[int] = []
    while m > 0:
        if (m % 2) == 1:
            M.append(mods(m, w))
            m -= M[i]
        else:
            M.append(0)
        m //= 2
        i += 1

    p = i

    b = pow(2, w)

    Q2 = ec._double_jac(Q)
    T = [Q]
    for i in range(1, (b // 2)):
        T.append(ec._add_jac(T[i - 1], Q2))
    for i in range((b // 2), b):
        T.append(ec.negate_jac(T[i - (b // 2)]))

    R = INFJ
    for j in range(p - 1, -1, -1):
        R = ec._double_jac(R)
        if M[j] != 0:
            if M[j] > 0:
                # It adds the element jQ
                R = ec._add_jac(R, T[(M[j] - 1) // 2])
            else:
                # In this case it adds the opposite, ie -jQ
                R = ec._add_jac(R, T[(b // 2) - ((M[j] + 1) // 2)])
    return R

1	#!/usr/bin/env python3
2
3	# Copyright (C) 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	"""Elliptic curve point multiplication functions.	1×
12
13	The implemented algorithms are:
14	- Montgomery Ladder
15	- Scalar multiplication on basis 3
16	- Fixed window
17	- Sliding window
18	- w-ary non-adjacent form (wNAF)
19
20	References:
21	- https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication
22	- https://cryptojedi.org/peter/data/eccss-20130911b.pdf
23	- https://ecc2017.cs.ru.nl/slides/ecc2017school-castryck.pdf
24	- https://cr.yp.to/bib/2003/joye-ladder.pdf
25
26	TODO:
27	- Computational cost of the different multiplications
28	- New alghoritms at the state-of-art:
29	-https://hal.archives-ouvertes.fr/hal-00932199/document
30	-https://iacr.org/workshops/ches/ches2006/presentations/Douglas%20Stebila.pdf
31	-1-s2.0-S1071579704000395-main
32	-https://crypto.stackexchange.com/questions/58506/what-is-the-curve-type-of-secp256k1
33	- Constant time alghortims:
34	-https://eprint.iacr.org/2011/338.pdf
35	- Elegance in the code
36	- Solve problem with wNAF and w=1
37	- Multi_mult algorithm: why does it work?
38	"""
39
40
41	from typing import List	1×
42
43	from .alias import INFJ, JacPoint	1×
44	from .curvegroup import CurveGroup	1×
45
46
47	def convert_number_to_base(i: int, base: int) -> List[int]:	1×
48	"Return the digits of an integer in the requested base."
49
50	digits: List[int] = []	1×
51	while i or not digits:	1×
52	i, idx = divmod(i, base)	1×
53	digits.append(idx)	1×
54	return digits[::-1]	1×
55
56
57	def mods(m: int, w: int) -> int:	1×
58	"""Signed modulo function.
59
60	FIXME:
61	mods does NOT work for w=1.
62	However the function in NOT really meant to be used for w=1
63	For w=1 it always gives back -1 and enters an infinite loop
64	"""
65
66	w2 = pow(2, w)	1×
67	M = m % w2	1×
68	return M - w2 if M >= (w2 / 2) else M	1×
69
70
71	def multiples(Q: JacPoint, size: int, ec: CurveGroup) -> List[JacPoint]:	1×
72	"Return {k_i * Q} for k_i in {0, ..., size-1)"
73
74	if size < 2:	1×
NEW 75	raise ValueError(f"size too low: {size}")	!
76	if size == 2:	1×
77	return [INFJ, Q]	1×
78
79	k, odd = divmod(size, 2)	1×
80
81	T = [INFJ, Q, ec._double_jac(Q)]	1×
82	for i in range(2, k * 2, 2):	1×
83	T.append(ec._add_jac(T[i], Q))	1×
84	T.append(ec._double_jac(T[(i + 2) // 2]))	1×
85
86	if not odd:	1×
87	T.append(ec._add_jac(T[i], Q))	1×
88
89	return T	1×
90
91
92	def _mult_mont_ladder(m: int, Q: JacPoint, ec: CurveGroup) -> JacPoint:	1×
93	"""Scalar multiplication using 'Montgomery ladder' algorithm.
94
95	This implementation uses
96	'Montgomery ladder' algorithm,
97	'left-to-right' binary decomposition of the m coefficient,
98	Jacobian coordinates.
99
100	It is constant-time and resistant to the FLUSH+RELOAD attack,
101	(see https://eprint.iacr.org/2014/140.pdf)
102	as it prevents branch prediction avoiding any if.
103
104	The input point is assumed to be on curve and
105	the m coefficient is assumed to have been reduced mod n
106	if appropriate (e.g. cyclic groups of order n).
107	"""
108
109	if m < 0:	1×
110	raise ValueError(f"negative m: {hex(m)}")	1×
111
112	# R[0] is the running resultR[1] = R[0] + Q is an ancillary variable
113	R = [INFJ, Q]	1×
114	for i in [int(i) for i in bin(m)[2:]]:	1×
115	R[not i] = ec._add_jac(R[i], R[not i])	1×
116	R[i] = ec._double_jac(R[i])	1×
117	return R[0]	1×
118
119
120	def _mult_base_3(m: int, Q: JacPoint, ec: CurveGroup) -> JacPoint:	1×
121	"""Scalar multiplication using ternary decomposition of the scalar.
122
123	This implementation uses
124	'double & add' algorithm,
125	'left-to-right' biternaryary decomposition of the m coefficient,
126	Jacobian coordinates.
127
128	The input point is assumed to be on curve and
129	the m coefficient is assumed to have been reduced mod n
130	if appropriate (e.g. cyclic groups of order n).
131	"""
132
133	if m < 0:	1×
134	raise ValueError(f"negative m: {hex(m)}")	1×
135
136	# at each step one of the points in T will be added
137	# T = multiples(Q, 3, ec)
138	T = [INFJ, Q, ec._double_jac(Q)]	1×
139
140	digits = convert_number_to_base(m, 3)	1×
141
142	R = T[digits[0]]	1×
143	for i in digits[1:]:	1×
144	# 'triple'
145	R2 = ec._double_jac(R)	1×
146	R3 = ec._add_jac(R2, R)	1×
147	# and 'add'
148	R = ec._add_jac(R3, T[i])	1×
149	return R	1×
150
151
152	def _mult_fixed_window(m: int, Q: JacPoint, w: int, ec: CurveGroup) -> JacPoint:	1×
153	"""Scalar multiplication using "fixed window".
154
155	It is not constant time.
156	For 256-bit scalars choose w=4 or w=5.
157
158	The input point is assumed to be on curve and
159	the m coefficient is assumed to have been reduced mod n
160	if appropriate (e.g. cyclic groups of order n).
161	"""
162
163	if m < 0:	1×
164	raise ValueError(f"negative m: {hex(m)}")	1×
165
166	# a number cannot be written in basis 1 (ie w=0)
167	if w <= 0:	1×
168	raise ValueError(f"non positive w: {w}")	1×
169
170	base = pow(2, w)	1×
171
172	# at each step one of the points in T will be added
173	T = multiples(Q, base, ec)	1×
174
175	digits = convert_number_to_base(m, base)	1×
176
177	R = T[digits[0]]	1×
178	for i in digits[1:]:	1×
179	# multiple 'double'
180	for _ in range(w):	1×
181	R = ec._double_jac(R)	1×
182	# and 'add'
183	R = ec._add_jac(R, T[i])	1×
184	return R	1×
185
186
187	def _mult_sliding_window(m: int, Q: JacPoint, w: int, ec: CurveGroup) -> JacPoint:	1×
188	"""Scalar multiplication using "sliding window".
189
190	It has the benefit that the pre-computation stage
191	is roughly half as complex as the normal windowed method.
192	It is not constant time.
193	For 256-bit scalars choose w=4 or w=5.
194
195	The input point is assumed to be on curve and
196	the m coefficient is assumed to have been reduced mod n
197	if appropriate (e.g. cyclic groups of order n).
198	"""
199
200	if m < 0:	1×
201	raise ValueError(f"negative m: {hex(m)}")	1×
202
203	# a number cannot be written in basis 1 (ie w=0)
204	if w <= 0:	1×
205	raise ValueError(f"non positive w: {w}")	1×
206
207	k = w - 1	1×
208	p = pow(2, k)	1×
209
210	# at each step one of the points in T will be added
211	P = Q	1×
212	for _ in range(k):	1×
213	P = ec._double_jac(P)	1×
214	T = [P]	1×
215	for i in range(1, p):	1×
216	T.append(ec._add_jac(T[i - 1], Q))	1×
217
218	digits = convert_number_to_base(m, 2)	1×
219
220	R = INFJ	1×
221	i = 0	1×
222	while i < len(digits):	1×
223	if digits[i] == 0:	1×
224	R = ec._double_jac(R)	1×
225	i += 1	1×
226	else:
227	j = len(digits) - i if (len(digits) - i) < w else w	1×
228	t = digits[i]	1×
229	for a in range(1, j):	1×
230	t = 2 * t + digits[i + a]	1×
231
232	if j < w:	1×
233	for b in range(i, (i + j)):	1×
234	R = ec._double_jac(R)	1×
235	if digits[b] == 1:	1×
236	R = ec._add_jac(R, Q)	1×
237	return R	1×
238	else:
239	for _ in range(w):	1×
240	R = ec._double_jac(R)	1×
241	R = ec._add_jac(R, T[t - p])	1×
242	i += j	1×
243	return R	1×
244
245
246	def _mult_w_NAF(m: int, Q: JacPoint, w: int, ec: CurveGroup) -> JacPoint:	1×
247	"""Scalar multiplication in Jacobian coordinates using wNAF.
248
249	This implementation uses the same method called "w-ary non-adjacent form" (wNAF)
250	we make use of the fact that point subtraction is as easy as point addition to perform fewer operations compared to sliding-window
251	In fact, on Weierstrass curves, known P, -P can be computed on the fly.
252
253	The input point is assumed to be on curve and
254	the m coefficient is assumed to have been reduced mod n
255	if appropriate (e.g. cyclic groups of order n).
256	"""
257	if m < 0:	1×
258	raise ValueError(f"negative m: {hex(m)}")	1×
259
260	# a number cannot be written in basis 1 (ie w=0)
261	if w <= 0:	1×
262	raise ValueError(f"non positive w: {w}")	1×
263
264	# This exception must be kept to satisfy the following while loop
265	if m == 0:	1×
266	return INFJ	1×
267
268	i = 0	1×
269
270	M: List[int] = []	1×
271	while m > 0:	1×
272	if (m % 2) == 1:	1×
273	M.append(mods(m, w))	1×
274	m -= M[i]	1×
275	else:
276	M.append(0)	1×
277	m //= 2	1×
278	i += 1	1×
279
280	p = i	1×
281
282	b = pow(2, w)	1×
283
284	Q2 = ec._double_jac(Q)	1×
285	T = [Q]	1×
286	for i in range(1, (b // 2)):	1×
287	T.append(ec._add_jac(T[i - 1], Q2))	1×
288	for i in range((b // 2), b):	1×
289	T.append(ec.negate_jac(T[i - (b // 2)]))	1×
290
291	R = INFJ	1×
292	for j in range(p - 1, -1, -1):	1×
293	R = ec._double_jac(R)	1×
294	if M[j] != 0:	1×
295	if M[j] > 0:	1×
296	# It adds the element jQ
297	R = ec._add_jac(R, T[(M[j] - 1) // 2])	1×
298	else:
299	# In this case it adds the opposite, ie -jQ
300	R = ec._add_jac(R, T[(b // 2) - ((M[j] + 1) // 2)])	1×
301	return R	1×

btclib-org / btclib / 749

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