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