Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/ecdsa/util.py: 28%
163 statements
« prev ^ index » next coverage.py v7.2.7, created at 2023-06-07 06:16 +0000
« prev ^ index » next coverage.py v7.2.7, created at 2023-06-07 06:16 +0000
1from __future__ import division
3import os
4import math
5import binascii
6import sys
7from hashlib import sha256
8from six import PY2, int2byte, b, next
9from . import der
10from ._compat import normalise_bytes
12# RFC5480:
13# The "unrestricted" algorithm identifier is:
14# id-ecPublicKey OBJECT IDENTIFIER ::= {
15# iso(1) member-body(2) us(840) ansi-X9-62(10045) keyType(2) 1 }
17oid_ecPublicKey = (1, 2, 840, 10045, 2, 1)
18encoded_oid_ecPublicKey = der.encode_oid(*oid_ecPublicKey)
20# RFC5480:
21# The ECDH algorithm uses the following object identifier:
22# id-ecDH OBJECT IDENTIFIER ::= {
23# iso(1) identified-organization(3) certicom(132) schemes(1)
24# ecdh(12) }
26oid_ecDH = (1, 3, 132, 1, 12)
28# RFC5480:
29# The ECMQV algorithm uses the following object identifier:
30# id-ecMQV OBJECT IDENTIFIER ::= {
31# iso(1) identified-organization(3) certicom(132) schemes(1)
32# ecmqv(13) }
34oid_ecMQV = (1, 3, 132, 1, 13)
36if sys.version_info >= (3,): # pragma: no branch
38 def entropy_to_bits(ent_256):
39 """Convert a bytestring to string of 0's and 1's"""
40 return bin(int.from_bytes(ent_256, "big"))[2:].zfill(len(ent_256) * 8)
42else:
44 def entropy_to_bits(ent_256):
45 """Convert a bytestring to string of 0's and 1's"""
46 return "".join(bin(ord(x))[2:].zfill(8) for x in ent_256)
49if sys.version_info < (2, 7): # pragma: no branch
50 # Can't add a method to a built-in type so we are stuck with this
51 def bit_length(x):
52 return len(bin(x)) - 2
54else:
56 def bit_length(x):
57 return x.bit_length() or 1
60def orderlen(order):
61 return (1 + len("%x" % order)) // 2 # bytes
64def randrange(order, entropy=None):
65 """Return a random integer k such that 1 <= k < order, uniformly
66 distributed across that range. Worst case should be a mean of 2 loops at
67 (2**k)+2.
69 Note that this function is not declared to be forwards-compatible: we may
70 change the behavior in future releases. The entropy= argument (which
71 should get a callable that behaves like os.urandom) can be used to
72 achieve stability within a given release (for repeatable unit tests), but
73 should not be used as a long-term-compatible key generation algorithm.
74 """
75 assert order > 1
76 if entropy is None:
77 entropy = os.urandom
78 upper_2 = bit_length(order - 2)
79 upper_256 = upper_2 // 8 + 1
80 while True: # I don't think this needs a counter with bit-wise randrange
81 ent_256 = entropy(upper_256)
82 ent_2 = entropy_to_bits(ent_256)
83 rand_num = int(ent_2[:upper_2], base=2) + 1
84 if 0 < rand_num < order:
85 return rand_num
88class PRNG:
89 # this returns a callable which, when invoked with an integer N, will
90 # return N pseudorandom bytes. Note: this is a short-term PRNG, meant
91 # primarily for the needs of randrange_from_seed__trytryagain(), which
92 # only needs to run it a few times per seed. It does not provide
93 # protection against state compromise (forward security).
94 def __init__(self, seed):
95 self.generator = self.block_generator(seed)
97 def __call__(self, numbytes):
98 a = [next(self.generator) for i in range(numbytes)]
100 if PY2: # pragma: no branch
101 return "".join(a)
102 else:
103 return bytes(a)
105 def block_generator(self, seed):
106 counter = 0
107 while True:
108 for byte in sha256(
109 ("prng-%d-%s" % (counter, seed)).encode()
110 ).digest():
111 yield byte
112 counter += 1
115def randrange_from_seed__overshoot_modulo(seed, order):
116 # hash the data, then turn the digest into a number in [1,order).
117 #
118 # We use David-Sarah Hopwood's suggestion: turn it into a number that's
119 # sufficiently larger than the group order, then modulo it down to fit.
120 # This should give adequate (but not perfect) uniformity, and simple
121 # code. There are other choices: try-try-again is the main one.
122 base = PRNG(seed)(2 * orderlen(order))
123 number = (int(binascii.hexlify(base), 16) % (order - 1)) + 1
124 assert 1 <= number < order, (1, number, order)
125 return number
128def lsb_of_ones(numbits):
129 return (1 << numbits) - 1
132def bits_and_bytes(order):
133 bits = int(math.log(order - 1, 2) + 1)
134 bytes = bits // 8
135 extrabits = bits % 8
136 return bits, bytes, extrabits
139# the following randrange_from_seed__METHOD() functions take an
140# arbitrarily-sized secret seed and turn it into a number that obeys the same
141# range limits as randrange() above. They are meant for deriving consistent
142# signing keys from a secret rather than generating them randomly, for
143# example a protocol in which three signing keys are derived from a master
144# secret. You should use a uniformly-distributed unguessable seed with about
145# curve.baselen bytes of entropy. To use one, do this:
146# seed = os.urandom(curve.baselen) # or other starting point
147# secexp = ecdsa.util.randrange_from_seed__trytryagain(sed, curve.order)
148# sk = SigningKey.from_secret_exponent(secexp, curve)
151def randrange_from_seed__truncate_bytes(seed, order, hashmod=sha256):
152 # hash the seed, then turn the digest into a number in [1,order), but
153 # don't worry about trying to uniformly fill the range. This will lose,
154 # on average, four bits of entropy.
155 bits, _bytes, extrabits = bits_and_bytes(order)
156 if extrabits:
157 _bytes += 1
158 base = hashmod(seed).digest()[:_bytes]
159 base = "\x00" * (_bytes - len(base)) + base
160 number = 1 + int(binascii.hexlify(base), 16)
161 assert 1 <= number < order
162 return number
165def randrange_from_seed__truncate_bits(seed, order, hashmod=sha256):
166 # like string_to_randrange_truncate_bytes, but only lose an average of
167 # half a bit
168 bits = int(math.log(order - 1, 2) + 1)
169 maxbytes = (bits + 7) // 8
170 base = hashmod(seed).digest()[:maxbytes]
171 base = "\x00" * (maxbytes - len(base)) + base
172 topbits = 8 * maxbytes - bits
173 if topbits:
174 base = int2byte(ord(base[0]) & lsb_of_ones(topbits)) + base[1:]
175 number = 1 + int(binascii.hexlify(base), 16)
176 assert 1 <= number < order
177 return number
180def randrange_from_seed__trytryagain(seed, order):
181 # figure out exactly how many bits we need (rounded up to the nearest
182 # bit), so we can reduce the chance of looping to less than 0.5 . This is
183 # specified to feed from a byte-oriented PRNG, and discards the
184 # high-order bits of the first byte as necessary to get the right number
185 # of bits. The average number of loops will range from 1.0 (when
186 # order=2**k-1) to 2.0 (when order=2**k+1).
187 assert order > 1
188 bits, bytes, extrabits = bits_and_bytes(order)
189 generate = PRNG(seed)
190 while True:
191 extrabyte = b("")
192 if extrabits:
193 extrabyte = int2byte(ord(generate(1)) & lsb_of_ones(extrabits))
194 guess = string_to_number(extrabyte + generate(bytes)) + 1
195 if 1 <= guess < order:
196 return guess
199def number_to_string(num, order):
200 l = orderlen(order)
201 fmt_str = "%0" + str(2 * l) + "x"
202 string = binascii.unhexlify((fmt_str % num).encode())
203 assert len(string) == l, (len(string), l)
204 return string
207def number_to_string_crop(num, order):
208 l = orderlen(order)
209 fmt_str = "%0" + str(2 * l) + "x"
210 string = binascii.unhexlify((fmt_str % num).encode())
211 return string[:l]
214def string_to_number(string):
215 return int(binascii.hexlify(string), 16)
218def string_to_number_fixedlen(string, order):
219 l = orderlen(order)
220 assert len(string) == l, (len(string), l)
221 return int(binascii.hexlify(string), 16)
224# these methods are useful for the sigencode= argument to SK.sign() and the
225# sigdecode= argument to VK.verify(), and control how the signature is packed
226# or unpacked.
229def sigencode_strings(r, s, order):
230 r_str = number_to_string(r, order)
231 s_str = number_to_string(s, order)
232 return (r_str, s_str)
235def sigencode_string(r, s, order):
236 """
237 Encode the signature to raw format (:term:`raw encoding`)
239 It's expected that this function will be used as a `sigencode=` parameter
240 in :func:`ecdsa.keys.SigningKey.sign` method.
242 :param int r: first parameter of the signature
243 :param int s: second parameter of the signature
244 :param int order: the order of the curve over which the signature was
245 computed
247 :return: raw encoding of ECDSA signature
248 :rtype: bytes
249 """
250 # for any given curve, the size of the signature numbers is
251 # fixed, so just use simple concatenation
252 r_str, s_str = sigencode_strings(r, s, order)
253 return r_str + s_str
256def sigencode_der(r, s, order):
257 """
258 Encode the signature into the ECDSA-Sig-Value structure using :term:`DER`.
260 Encodes the signature to the following :term:`ASN.1` structure::
262 Ecdsa-Sig-Value ::= SEQUENCE {
263 r INTEGER,
264 s INTEGER
265 }
267 It's expected that this function will be used as a `sigencode=` parameter
268 in :func:`ecdsa.keys.SigningKey.sign` method.
270 :param int r: first parameter of the signature
271 :param int s: second parameter of the signature
272 :param int order: the order of the curve over which the signature was
273 computed
275 :return: DER encoding of ECDSA signature
276 :rtype: bytes
277 """
278 return der.encode_sequence(der.encode_integer(r), der.encode_integer(s))
281# canonical versions of sigencode methods
282# these enforce low S values, by negating the value (modulo the order) if
283# above order/2 see CECKey::Sign()
284# https://github.com/bitcoin/bitcoin/blob/master/src/key.cpp#L214
285def sigencode_strings_canonize(r, s, order):
286 if s > order / 2:
287 s = order - s
288 return sigencode_strings(r, s, order)
291def sigencode_string_canonize(r, s, order):
292 if s > order / 2:
293 s = order - s
294 return sigencode_string(r, s, order)
297def sigencode_der_canonize(r, s, order):
298 if s > order / 2:
299 s = order - s
300 return sigencode_der(r, s, order)
303class MalformedSignature(Exception):
304 """
305 Raised by decoding functions when the signature is malformed.
307 Malformed in this context means that the relevant strings or integers
308 do not match what a signature over provided curve would create. Either
309 because the byte strings have incorrect lengths or because the encoded
310 values are too large.
311 """
313 pass
316def sigdecode_string(signature, order):
317 """
318 Decoder for :term:`raw encoding` of ECDSA signatures.
320 raw encoding is a simple concatenation of the two integers that comprise
321 the signature, with each encoded using the same amount of bytes depending
322 on curve size/order.
324 It's expected that this function will be used as the `sigdecode=`
325 parameter to the :func:`ecdsa.keys.VerifyingKey.verify` method.
327 :param signature: encoded signature
328 :type signature: bytes like object
329 :param order: order of the curve over which the signature was computed
330 :type order: int
332 :raises MalformedSignature: when the encoding of the signature is invalid
334 :return: tuple with decoded 'r' and 's' values of signature
335 :rtype: tuple of ints
336 """
337 signature = normalise_bytes(signature)
338 l = orderlen(order)
339 if not len(signature) == 2 * l:
340 raise MalformedSignature(
341 "Invalid length of signature, expected {0} bytes long, "
342 "provided string is {1} bytes long".format(2 * l, len(signature))
343 )
344 r = string_to_number_fixedlen(signature[:l], order)
345 s = string_to_number_fixedlen(signature[l:], order)
346 return r, s
349def sigdecode_strings(rs_strings, order):
350 """
351 Decode the signature from two strings.
353 First string needs to be a big endian encoding of 'r', second needs to
354 be a big endian encoding of the 's' parameter of an ECDSA signature.
356 It's expected that this function will be used as the `sigdecode=`
357 parameter to the :func:`ecdsa.keys.VerifyingKey.verify` method.
359 :param list rs_strings: list of two bytes-like objects, each encoding one
360 parameter of signature
361 :param int order: order of the curve over which the signature was computed
363 :raises MalformedSignature: when the encoding of the signature is invalid
365 :return: tuple with decoded 'r' and 's' values of signature
366 :rtype: tuple of ints
367 """
368 if not len(rs_strings) == 2:
369 raise MalformedSignature(
370 "Invalid number of strings provided: {0}, expected 2".format(
371 len(rs_strings)
372 )
373 )
374 (r_str, s_str) = rs_strings
375 r_str = normalise_bytes(r_str)
376 s_str = normalise_bytes(s_str)
377 l = orderlen(order)
378 if not len(r_str) == l:
379 raise MalformedSignature(
380 "Invalid length of first string ('r' parameter), "
381 "expected {0} bytes long, provided string is {1} "
382 "bytes long".format(l, len(r_str))
383 )
384 if not len(s_str) == l:
385 raise MalformedSignature(
386 "Invalid length of second string ('s' parameter), "
387 "expected {0} bytes long, provided string is {1} "
388 "bytes long".format(l, len(s_str))
389 )
390 r = string_to_number_fixedlen(r_str, order)
391 s = string_to_number_fixedlen(s_str, order)
392 return r, s
395def sigdecode_der(sig_der, order):
396 """
397 Decoder for DER format of ECDSA signatures.
399 DER format of signature is one that uses the :term:`ASN.1` :term:`DER`
400 rules to encode it as a sequence of two integers::
402 Ecdsa-Sig-Value ::= SEQUENCE {
403 r INTEGER,
404 s INTEGER
405 }
407 It's expected that this function will be used as as the `sigdecode=`
408 parameter to the :func:`ecdsa.keys.VerifyingKey.verify` method.
410 :param sig_der: encoded signature
411 :type sig_der: bytes like object
412 :param order: order of the curve over which the signature was computed
413 :type order: int
415 :raises UnexpectedDER: when the encoding of signature is invalid
417 :return: tuple with decoded 'r' and 's' values of signature
418 :rtype: tuple of ints
419 """
420 sig_der = normalise_bytes(sig_der)
421 # return der.encode_sequence(der.encode_integer(r), der.encode_integer(s))
422 rs_strings, empty = der.remove_sequence(sig_der)
423 if empty != b"":
424 raise der.UnexpectedDER(
425 "trailing junk after DER sig: %s" % binascii.hexlify(empty)
426 )
427 r, rest = der.remove_integer(rs_strings)
428 s, empty = der.remove_integer(rest)
429 if empty != b"":
430 raise der.UnexpectedDER(
431 "trailing junk after DER numbers: %s" % binascii.hexlify(empty)
432 )
433 return r, s