Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/ecdsa/util.py: 48%
Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2This module includes some utility functions.
4The methods most typically used are the sigencode and sigdecode functions
5to be used with :func:`~ecdsa.keys.SigningKey.sign` and
6:func:`~ecdsa.keys.VerifyingKey.verify`
7respectively. See the :func:`sigencode_strings`, :func:`sigdecode_string`,
8:func:`sigencode_der`, :func:`sigencode_strings_canonize`,
9:func:`sigencode_string_canonize`, :func:`sigencode_der_canonize`,
10:func:`sigdecode_strings`, :func:`sigdecode_string`, and
11:func:`sigdecode_der` functions.
12"""
14from __future__ import division
16import os
17import math
18import binascii
19import sys
20from hashlib import sha256
21from six import PY2, int2byte, next
22from . import der
23from ._compat import normalise_bytes
26# RFC5480:
27# The "unrestricted" algorithm identifier is:
28# id-ecPublicKey OBJECT IDENTIFIER ::= {
29# iso(1) member-body(2) us(840) ansi-X9-62(10045) keyType(2) 1 }
31oid_ecPublicKey = (1, 2, 840, 10045, 2, 1)
32encoded_oid_ecPublicKey = der.encode_oid(*oid_ecPublicKey)
34# RFC5480:
35# The ECDH algorithm uses the following object identifier:
36# id-ecDH OBJECT IDENTIFIER ::= {
37# iso(1) identified-organization(3) certicom(132) schemes(1)
38# ecdh(12) }
40oid_ecDH = (1, 3, 132, 1, 12)
42# RFC5480:
43# The ECMQV algorithm uses the following object identifier:
44# id-ecMQV OBJECT IDENTIFIER ::= {
45# iso(1) identified-organization(3) certicom(132) schemes(1)
46# ecmqv(13) }
48oid_ecMQV = (1, 3, 132, 1, 13)
50if sys.version_info >= (3,): # pragma: no branch
52 def entropy_to_bits(ent_256):
53 """Convert a bytestring to string of 0's and 1's"""
54 return bin(int.from_bytes(ent_256, "big"))[2:].zfill(len(ent_256) * 8)
56else:
58 def entropy_to_bits(ent_256):
59 """Convert a bytestring to string of 0's and 1's"""
60 return "".join(bin(ord(x))[2:].zfill(8) for x in ent_256)
63if sys.version_info < (2, 7): # pragma: no branch
64 # Can't add a method to a built-in type so we are stuck with this
65 def bit_length(x):
66 return len(bin(x)) - 2
68else:
70 def bit_length(x):
71 return x.bit_length() or 1
74def orderlen(order):
75 return (1 + len("%x" % order)) // 2 # bytes
78def randrange(order, entropy=None):
79 """Return a random integer k such that 1 <= k < order, uniformly
80 distributed across that range. Worst case should be a mean of 2 loops at
81 (2**k)+2.
83 Note that this function is not declared to be forwards-compatible: we may
84 change the behavior in future releases. The entropy= argument (which
85 should get a callable that behaves like os.urandom) can be used to
86 achieve stability within a given release (for repeatable unit tests), but
87 should not be used as a long-term-compatible key generation algorithm.
88 """
89 assert order > 1
90 if entropy is None:
91 entropy = os.urandom
92 upper_2 = bit_length(order - 2)
93 upper_256 = upper_2 // 8 + 1
94 while True: # I don't think this needs a counter with bit-wise randrange
95 ent_256 = entropy(upper_256)
96 ent_2 = entropy_to_bits(ent_256)
97 rand_num = int(ent_2[:upper_2], base=2) + 1
98 if 0 < rand_num < order:
99 return rand_num
102class PRNG:
103 # this returns a callable which, when invoked with an integer N, will
104 # return N pseudorandom bytes. Note: this is a short-term PRNG, meant
105 # primarily for the needs of randrange_from_seed__trytryagain(), which
106 # only needs to run it a few times per seed. It does not provide
107 # protection against state compromise (forward security).
108 def __init__(self, seed):
109 self.generator = self.block_generator(seed)
111 def __call__(self, numbytes):
112 a = [next(self.generator) for i in range(numbytes)]
114 if PY2: # pragma: no branch
115 return "".join(a)
116 else:
117 return bytes(a)
119 def block_generator(self, seed):
120 counter = 0
121 while True:
122 for byte in sha256(
123 ("prng-%d-%s" % (counter, seed)).encode()
124 ).digest():
125 yield byte
126 counter += 1
129def randrange_from_seed__overshoot_modulo(seed, order):
130 # hash the data, then turn the digest into a number in [1,order).
131 #
132 # We use David-Sarah Hopwood's suggestion: turn it into a number that's
133 # sufficiently larger than the group order, then modulo it down to fit.
134 # This should give adequate (but not perfect) uniformity, and simple
135 # code. There are other choices: try-try-again is the main one.
136 base = PRNG(seed)(2 * orderlen(order))
137 number = (int(binascii.hexlify(base), 16) % (order - 1)) + 1
138 assert 1 <= number < order, (1, number, order)
139 return number
142def lsb_of_ones(numbits):
143 return (1 << numbits) - 1
146def bits_and_bytes(order):
147 bits = int(math.log(order - 1, 2) + 1)
148 bytes = bits // 8
149 extrabits = bits % 8
150 return bits, bytes, extrabits
153# the following randrange_from_seed__METHOD() functions take an
154# arbitrarily-sized secret seed and turn it into a number that obeys the same
155# range limits as randrange() above. They are meant for deriving consistent
156# signing keys from a secret rather than generating them randomly, for
157# example a protocol in which three signing keys are derived from a master
158# secret. You should use a uniformly-distributed unguessable seed with about
159# curve.baselen bytes of entropy. To use one, do this:
160# seed = os.urandom(curve.baselen) # or other starting point
161# secexp = ecdsa.util.randrange_from_seed__trytryagain(sed, curve.order)
162# sk = SigningKey.from_secret_exponent(secexp, curve)
165def randrange_from_seed__truncate_bytes(seed, order, hashmod=sha256):
166 # hash the seed, then turn the digest into a number in [1,order), but
167 # don't worry about trying to uniformly fill the range. This will lose,
168 # on average, four bits of entropy.
169 bits, _bytes, extrabits = bits_and_bytes(order)
170 if extrabits:
171 _bytes += 1
172 base = hashmod(seed).digest()[:_bytes]
173 base = "\x00" * (_bytes - len(base)) + base
174 number = 1 + int(binascii.hexlify(base), 16)
175 assert 1 <= number < order
176 return number
179def randrange_from_seed__truncate_bits(seed, order, hashmod=sha256):
180 # like string_to_randrange_truncate_bytes, but only lose an average of
181 # half a bit
182 bits = int(math.log(order - 1, 2) + 1)
183 maxbytes = (bits + 7) // 8
184 base = hashmod(seed).digest()[:maxbytes]
185 base = "\x00" * (maxbytes - len(base)) + base
186 topbits = 8 * maxbytes - bits
187 if topbits:
188 base = int2byte(ord(base[0]) & lsb_of_ones(topbits)) + base[1:]
189 number = 1 + int(binascii.hexlify(base), 16)
190 assert 1 <= number < order
191 return number
194def randrange_from_seed__trytryagain(seed, order):
195 # figure out exactly how many bits we need (rounded up to the nearest
196 # bit), so we can reduce the chance of looping to less than 0.5 . This is
197 # specified to feed from a byte-oriented PRNG, and discards the
198 # high-order bits of the first byte as necessary to get the right number
199 # of bits. The average number of loops will range from 1.0 (when
200 # order=2**k-1) to 2.0 (when order=2**k+1).
201 assert order > 1
202 bits, bytes, extrabits = bits_and_bytes(order)
203 generate = PRNG(seed)
204 while True:
205 extrabyte = b""
206 if extrabits:
207 extrabyte = int2byte(ord(generate(1)) & lsb_of_ones(extrabits))
208 guess = string_to_number(extrabyte + generate(bytes)) + 1
209 if 1 <= guess < order:
210 return guess
213def number_to_string(num, order):
214 l = orderlen(order)
215 fmt_str = "%0" + str(2 * l) + "x"
216 string = binascii.unhexlify((fmt_str % num).encode())
217 assert len(string) == l, (len(string), l)
218 return string
221def number_to_string_crop(num, order):
222 l = orderlen(order)
223 fmt_str = "%0" + str(2 * l) + "x"
224 string = binascii.unhexlify((fmt_str % num).encode())
225 return string[:l]
228def string_to_number(string):
229 return int(binascii.hexlify(string), 16)
232def string_to_number_fixedlen(string, order):
233 l = orderlen(order)
234 assert len(string) == l, (len(string), l)
235 return int(binascii.hexlify(string), 16)
238def sigencode_strings(r, s, order):
239 """
240 Encode the signature to a pair of strings in a tuple
242 Encodes signature into raw encoding (:term:`raw encoding`) with the
243 ``r`` and ``s`` parts of the signature encoded separately.
245 It's expected that this function will be used as a ``sigencode=`` parameter
246 in :func:`ecdsa.keys.SigningKey.sign` method.
248 :param int r: first parameter of the signature
249 :param int s: second parameter of the signature
250 :param int order: the order of the curve over which the signature was
251 computed
253 :return: raw encoding of ECDSA signature
254 :rtype: tuple(bytes, bytes)
255 """
256 r_str = number_to_string(r, order)
257 s_str = number_to_string(s, order)
258 return (r_str, s_str)
261def sigencode_string(r, s, order):
262 """
263 Encode the signature to raw format (:term:`raw encoding`)
265 It's expected that this function will be used as a ``sigencode=`` parameter
266 in :func:`ecdsa.keys.SigningKey.sign` method.
268 :param int r: first parameter of the signature
269 :param int s: second parameter of the signature
270 :param int order: the order of the curve over which the signature was
271 computed
273 :return: raw encoding of ECDSA signature
274 :rtype: bytes
275 """
276 # for any given curve, the size of the signature numbers is
277 # fixed, so just use simple concatenation
278 r_str, s_str = sigencode_strings(r, s, order)
279 return r_str + s_str
282def sigencode_der(r, s, order):
283 """
284 Encode the signature into the ECDSA-Sig-Value structure using :term:`DER`.
286 Encodes the signature to the following :term:`ASN.1` structure::
288 Ecdsa-Sig-Value ::= SEQUENCE {
289 r INTEGER,
290 s INTEGER
291 }
293 It's expected that this function will be used as a ``sigencode=`` parameter
294 in :func:`ecdsa.keys.SigningKey.sign` method.
296 :param int r: first parameter of the signature
297 :param int s: second parameter of the signature
298 :param int order: the order of the curve over which the signature was
299 computed
301 :return: DER encoding of ECDSA signature
302 :rtype: bytes
303 """
304 return der.encode_sequence(der.encode_integer(r), der.encode_integer(s))
307def _canonize(s, order):
308 """
309 Internal function for ensuring that the ``s`` value of a signature is in
310 the "canonical" format.
312 :param int s: the second parameter of ECDSA signature
313 :param int order: the order of the curve over which the signatures was
314 computed
316 :return: canonical value of s
317 :rtype: int
318 """
319 if s > order // 2:
320 s = order - s
321 return s
324def sigencode_strings_canonize(r, s, order):
325 """
326 Encode the signature to a pair of strings in a tuple
328 Encodes signature into raw encoding (:term:`raw encoding`) with the
329 ``r`` and ``s`` parts of the signature encoded separately.
331 Makes sure that the signature is encoded in the canonical format, where
332 the ``s`` parameter is always smaller than ``order / 2``.
333 Most commonly used in bitcoin.
335 It's expected that this function will be used as a ``sigencode=`` parameter
336 in :func:`ecdsa.keys.SigningKey.sign` method.
338 :param int r: first parameter of the signature
339 :param int s: second parameter of the signature
340 :param int order: the order of the curve over which the signature was
341 computed
343 :return: raw encoding of ECDSA signature
344 :rtype: tuple(bytes, bytes)
345 """
346 s = _canonize(s, order)
347 return sigencode_strings(r, s, order)
350def sigencode_string_canonize(r, s, order):
351 """
352 Encode the signature to raw format (:term:`raw encoding`)
354 Makes sure that the signature is encoded in the canonical format, where
355 the ``s`` parameter is always smaller than ``order / 2``.
356 Most commonly used in bitcoin.
358 It's expected that this function will be used as a ``sigencode=`` parameter
359 in :func:`ecdsa.keys.SigningKey.sign` method.
361 :param int r: first parameter of the signature
362 :param int s: second parameter of the signature
363 :param int order: the order of the curve over which the signature was
364 computed
366 :return: raw encoding of ECDSA signature
367 :rtype: bytes
368 """
369 s = _canonize(s, order)
370 return sigencode_string(r, s, order)
373def sigencode_der_canonize(r, s, order):
374 """
375 Encode the signature into the ECDSA-Sig-Value structure using :term:`DER`.
377 Makes sure that the signature is encoded in the canonical format, where
378 the ``s`` parameter is always smaller than ``order / 2``.
379 Most commonly used in bitcoin.
381 Encodes the signature to the following :term:`ASN.1` structure::
383 Ecdsa-Sig-Value ::= SEQUENCE {
384 r INTEGER,
385 s INTEGER
386 }
388 It's expected that this function will be used as a ``sigencode=`` parameter
389 in :func:`ecdsa.keys.SigningKey.sign` method.
391 :param int r: first parameter of the signature
392 :param int s: second parameter of the signature
393 :param int order: the order of the curve over which the signature was
394 computed
396 :return: DER encoding of ECDSA signature
397 :rtype: bytes
398 """
399 s = _canonize(s, order)
400 return sigencode_der(r, s, order)
403class MalformedSignature(Exception):
404 """
405 Raised by decoding functions when the signature is malformed.
407 Malformed in this context means that the relevant strings or integers
408 do not match what a signature over provided curve would create. Either
409 because the byte strings have incorrect lengths or because the encoded
410 values are too large.
411 """
413 pass
416def sigdecode_string(signature, order):
417 """
418 Decoder for :term:`raw encoding` of ECDSA signatures.
420 raw encoding is a simple concatenation of the two integers that comprise
421 the signature, with each encoded using the same amount of bytes depending
422 on curve size/order.
424 It's expected that this function will be used as the ``sigdecode=``
425 parameter to the :func:`ecdsa.keys.VerifyingKey.verify` method.
427 :param signature: encoded signature
428 :type signature: bytes like object
429 :param order: order of the curve over which the signature was computed
430 :type order: int
432 :raises MalformedSignature: when the encoding of the signature is invalid
434 :return: tuple with decoded ``r`` and ``s`` values of signature
435 :rtype: tuple of ints
436 """
437 signature = normalise_bytes(signature)
438 l = orderlen(order)
439 if not len(signature) == 2 * l:
440 raise MalformedSignature(
441 "Invalid length of signature, expected {0} bytes long, "
442 "provided string is {1} bytes long".format(2 * l, len(signature))
443 )
444 r = string_to_number_fixedlen(signature[:l], order)
445 s = string_to_number_fixedlen(signature[l:], order)
446 return r, s
449def sigdecode_strings(rs_strings, order):
450 """
451 Decode the signature from two strings.
453 First string needs to be a big endian encoding of ``r``, second needs to
454 be a big endian encoding of the ``s`` parameter of an ECDSA signature.
456 It's expected that this function will be used as the ``sigdecode=``
457 parameter to the :func:`ecdsa.keys.VerifyingKey.verify` method.
459 :param list rs_strings: list of two bytes-like objects, each encoding one
460 parameter of signature
461 :param int order: order of the curve over which the signature was computed
463 :raises MalformedSignature: when the encoding of the signature is invalid
465 :return: tuple with decoded ``r`` and ``s`` values of signature
466 :rtype: tuple of ints
467 """
468 if not len(rs_strings) == 2:
469 raise MalformedSignature(
470 "Invalid number of strings provided: {0}, expected 2".format(
471 len(rs_strings)
472 )
473 )
474 (r_str, s_str) = rs_strings
475 r_str = normalise_bytes(r_str)
476 s_str = normalise_bytes(s_str)
477 l = orderlen(order)
478 if not len(r_str) == l:
479 raise MalformedSignature(
480 "Invalid length of first string ('r' parameter), "
481 "expected {0} bytes long, provided string is {1} "
482 "bytes long".format(l, len(r_str))
483 )
484 if not len(s_str) == l:
485 raise MalformedSignature(
486 "Invalid length of second string ('s' parameter), "
487 "expected {0} bytes long, provided string is {1} "
488 "bytes long".format(l, len(s_str))
489 )
490 r = string_to_number_fixedlen(r_str, order)
491 s = string_to_number_fixedlen(s_str, order)
492 return r, s
495def sigdecode_der(sig_der, order):
496 """
497 Decoder for DER format of ECDSA signatures.
499 DER format of signature is one that uses the :term:`ASN.1` :term:`DER`
500 rules to encode it as a sequence of two integers::
502 Ecdsa-Sig-Value ::= SEQUENCE {
503 r INTEGER,
504 s INTEGER
505 }
507 It's expected that this function will be used as as the ``sigdecode=``
508 parameter to the :func:`ecdsa.keys.VerifyingKey.verify` method.
510 :param sig_der: encoded signature
511 :type sig_der: bytes like object
512 :param order: order of the curve over which the signature was computed
513 :type order: int
515 :raises UnexpectedDER: when the encoding of signature is invalid
517 :return: tuple with decoded ``r`` and ``s`` values of signature
518 :rtype: tuple of ints
519 """
520 sig_der = normalise_bytes(sig_der)
521 # return der.encode_sequence(der.encode_integer(r), der.encode_integer(s))
522 rs_strings, empty = der.remove_sequence(sig_der)
523 if empty != b"":
524 raise der.UnexpectedDER(
525 "trailing junk after DER sig: %s" % binascii.hexlify(empty)
526 )
527 r, rest = der.remove_integer(rs_strings)
528 s, empty = der.remove_integer(rest)
529 if empty != b"":
530 raise der.UnexpectedDER(
531 "trailing junk after DER numbers: %s" % binascii.hexlify(empty)
532 )
533 return r, s