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