aboutsummaryrefslogtreecommitdiff
path: root/frozen_deps/ecdsa/util.py
blob: e77d61c60162ec601a487a818305abb54e37bb39 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
from __future__ import division

import os
import math
import binascii
import sys
from hashlib import sha256
from six import PY2, int2byte, b, next
from . import der
from ._compat import normalise_bytes

# RFC5480:
#   The "unrestricted" algorithm identifier is:
#     id-ecPublicKey OBJECT IDENTIFIER ::= {
#       iso(1) member-body(2) us(840) ansi-X9-62(10045) keyType(2) 1 }

oid_ecPublicKey = (1, 2, 840, 10045, 2, 1)
encoded_oid_ecPublicKey = der.encode_oid(*oid_ecPublicKey)

# RFC5480:
# The ECDH algorithm uses the following object identifier:
#      id-ecDH OBJECT IDENTIFIER ::= {
#        iso(1) identified-organization(3) certicom(132) schemes(1)
#        ecdh(12) }

oid_ecDH = (1, 3, 132, 1, 12)

# RFC5480:
# The ECMQV algorithm uses the following object identifier:
#      id-ecMQV OBJECT IDENTIFIER ::= {
#        iso(1) identified-organization(3) certicom(132) schemes(1)
#        ecmqv(13) }

oid_ecMQV = (1, 3, 132, 1, 13)

if sys.version_info >= (3,):

    def entropy_to_bits(ent_256):
        """Convert a bytestring to string of 0's and 1's"""
        return bin(int.from_bytes(ent_256, "big"))[2:].zfill(len(ent_256) * 8)


else:

    def entropy_to_bits(ent_256):
        """Convert a bytestring to string of 0's and 1's"""
        return "".join(bin(ord(x))[2:].zfill(8) for x in ent_256)


if sys.version_info < (2, 7):
    # Can't add a method to a built-in type so we are stuck with this
    def bit_length(x):
        return len(bin(x)) - 2


else:

    def bit_length(x):
        return x.bit_length() or 1


def orderlen(order):
    return (1 + len("%x" % order)) // 2  # bytes


def randrange(order, entropy=None):
    """Return a random integer k such that 1 <= k < order, uniformly
    distributed across that range. Worst case should be a mean of 2 loops at
    (2**k)+2.

    Note that this function is not declared to be forwards-compatible: we may
    change the behavior in future releases. The entropy= argument (which
    should get a callable that behaves like os.urandom) can be used to
    achieve stability within a given release (for repeatable unit tests), but
    should not be used as a long-term-compatible key generation algorithm.
    """
    assert order > 1
    if entropy is None:
        entropy = os.urandom
    upper_2 = bit_length(order - 2)
    upper_256 = upper_2 // 8 + 1
    while True:  # I don't think this needs a counter with bit-wise randrange
        ent_256 = entropy(upper_256)
        ent_2 = entropy_to_bits(ent_256)
        rand_num = int(ent_2[:upper_2], base=2) + 1
        if 0 < rand_num < order:
            return rand_num


class PRNG:
    # this returns a callable which, when invoked with an integer N, will
    # return N pseudorandom bytes. Note: this is a short-term PRNG, meant
    # primarily for the needs of randrange_from_seed__trytryagain(), which
    # only needs to run it a few times per seed. It does not provide
    # protection against state compromise (forward security).
    def __init__(self, seed):
        self.generator = self.block_generator(seed)

    def __call__(self, numbytes):
        a = [next(self.generator) for i in range(numbytes)]

        if PY2:
            return "".join(a)
        else:
            return bytes(a)

    def block_generator(self, seed):
        counter = 0
        while True:
            for byte in sha256(
                ("prng-%d-%s" % (counter, seed)).encode()
            ).digest():
                yield byte
            counter += 1


def randrange_from_seed__overshoot_modulo(seed, order):
    # hash the data, then turn the digest into a number in [1,order).
    #
    # We use David-Sarah Hopwood's suggestion: turn it into a number that's
    # sufficiently larger than the group order, then modulo it down to fit.
    # This should give adequate (but not perfect) uniformity, and simple
    # code. There are other choices: try-try-again is the main one.
    base = PRNG(seed)(2 * orderlen(order))
    number = (int(binascii.hexlify(base), 16) % (order - 1)) + 1
    assert 1 <= number < order, (1, number, order)
    return number


def lsb_of_ones(numbits):
    return (1 << numbits) - 1


def bits_and_bytes(order):
    bits = int(math.log(order - 1, 2) + 1)
    bytes = bits // 8
    extrabits = bits % 8
    return bits, bytes, extrabits


# the following randrange_from_seed__METHOD() functions take an
# arbitrarily-sized secret seed and turn it into a number that obeys the same
# range limits as randrange() above. They are meant for deriving consistent
# signing keys from a secret rather than generating them randomly, for
# example a protocol in which three signing keys are derived from a master
# secret. You should use a uniformly-distributed unguessable seed with about
# curve.baselen bytes of entropy. To use one, do this:
#   seed = os.urandom(curve.baselen) # or other starting point
#   secexp = ecdsa.util.randrange_from_seed__trytryagain(sed, curve.order)
#   sk = SigningKey.from_secret_exponent(secexp, curve)


def randrange_from_seed__truncate_bytes(seed, order, hashmod=sha256):
    # hash the seed, then turn the digest into a number in [1,order), but
    # don't worry about trying to uniformly fill the range. This will lose,
    # on average, four bits of entropy.
    bits, _bytes, extrabits = bits_and_bytes(order)
    if extrabits:
        _bytes += 1
    base = hashmod(seed).digest()[:_bytes]
    base = "\x00" * (_bytes - len(base)) + base
    number = 1 + int(binascii.hexlify(base), 16)
    assert 1 <= number < order
    return number


def randrange_from_seed__truncate_bits(seed, order, hashmod=sha256):
    # like string_to_randrange_truncate_bytes, but only lose an average of
    # half a bit
    bits = int(math.log(order - 1, 2) + 1)
    maxbytes = (bits + 7) // 8
    base = hashmod(seed).digest()[:maxbytes]
    base = "\x00" * (maxbytes - len(base)) + base
    topbits = 8 * maxbytes - bits
    if topbits:
        base = int2byte(ord(base[0]) & lsb_of_ones(topbits)) + base[1:]
    number = 1 + int(binascii.hexlify(base), 16)
    assert 1 <= number < order
    return number


def randrange_from_seed__trytryagain(seed, order):
    # figure out exactly how many bits we need (rounded up to the nearest
    # bit), so we can reduce the chance of looping to less than 0.5 . This is
    # specified to feed from a byte-oriented PRNG, and discards the
    # high-order bits of the first byte as necessary to get the right number
    # of bits. The average number of loops will range from 1.0 (when
    # order=2**k-1) to 2.0 (when order=2**k+1).
    assert order > 1
    bits, bytes, extrabits = bits_and_bytes(order)
    generate = PRNG(seed)
    while True:
        extrabyte = b("")
        if extrabits:
            extrabyte = int2byte(ord(generate(1)) & lsb_of_ones(extrabits))
        guess = string_to_number(extrabyte + generate(bytes)) + 1
        if 1 <= guess < order:
            return guess


def number_to_string(num, order):
    l = orderlen(order)
    fmt_str = "%0" + str(2 * l) + "x"
    string = binascii.unhexlify((fmt_str % num).encode())
    assert len(string) == l, (len(string), l)
    return string


def number_to_string_crop(num, order):
    l = orderlen(order)
    fmt_str = "%0" + str(2 * l) + "x"
    string = binascii.unhexlify((fmt_str % num).encode())
    return string[:l]


def string_to_number(string):
    return int(binascii.hexlify(string), 16)


def string_to_number_fixedlen(string, order):
    l = orderlen(order)
    assert len(string) == l, (len(string), l)
    return int(binascii.hexlify(string), 16)


# these methods are useful for the sigencode= argument to SK.sign() and the
# sigdecode= argument to VK.verify(), and control how the signature is packed
# or unpacked.


def sigencode_strings(r, s, order):
    r_str = number_to_string(r, order)
    s_str = number_to_string(s, order)
    return (r_str, s_str)


def sigencode_string(r, s, order):
    """
    Encode the signature to raw format (:term:`raw encoding`)

    It's expected that this function will be used as a `sigencode=` parameter
    in :func:`ecdsa.keys.SigningKey.sign` method.

    :param int r: first parameter of the signature
    :param int s: second parameter of the signature
    :param int order: the order of the curve over which the signature was
        computed

    :return: raw encoding of ECDSA signature
    :rtype: bytes
    """
    # for any given curve, the size of the signature numbers is
    # fixed, so just use simple concatenation
    r_str, s_str = sigencode_strings(r, s, order)
    return r_str + s_str


def sigencode_der(r, s, order):
    """
    Encode the signature into the ECDSA-Sig-Value structure using :term:`DER`.

    Encodes the signature to the following :term:`ASN.1` structure::

        Ecdsa-Sig-Value ::= SEQUENCE {
            r       INTEGER,
            s       INTEGER
        }

    It's expected that this function will be used as a `sigencode=` parameter
    in :func:`ecdsa.keys.SigningKey.sign` method.

    :param int r: first parameter of the signature
    :param int s: second parameter of the signature
    :param int order: the order of the curve over which the signature was
        computed

    :return: DER encoding of ECDSA signature
    :rtype: bytes
    """
    return der.encode_sequence(der.encode_integer(r), der.encode_integer(s))


# canonical versions of sigencode methods
# these enforce low S values, by negating the value (modulo the order) if
# above order/2 see CECKey::Sign()
# https://github.com/bitcoin/bitcoin/blob/master/src/key.cpp#L214
def sigencode_strings_canonize(r, s, order):
    if s > order / 2:
        s = order - s
    return sigencode_strings(r, s, order)


def sigencode_string_canonize(r, s, order):
    if s > order / 2:
        s = order - s
    return sigencode_string(r, s, order)


def sigencode_der_canonize(r, s, order):
    if s > order / 2:
        s = order - s
    return sigencode_der(r, s, order)


class MalformedSignature(Exception):
    """
    Raised by decoding functions when the signature is malformed.

    Malformed in this context means that the relevant strings or integers
    do not match what a signature over provided curve would create. Either
    because the byte strings have incorrect lengths or because the encoded
    values are too large.
    """

    pass


def sigdecode_string(signature, order):
    """
    Decoder for :term:`raw encoding`  of ECDSA signatures.

    raw encoding is a simple concatenation of the two integers that comprise
    the signature, with each encoded using the same amount of bytes depending
    on curve size/order.

    It's expected that this function will be used as the `sigdecode=`
    parameter to the :func:`ecdsa.keys.VerifyingKey.verify` method.

    :param signature: encoded signature
    :type signature: bytes like object
    :param order: order of the curve over which the signature was computed
    :type order: int

    :raises MalformedSignature: when the encoding of the signature is invalid

    :return: tuple with decoded 'r' and 's' values of signature
    :rtype: tuple of ints
    """
    signature = normalise_bytes(signature)
    l = orderlen(order)
    if not len(signature) == 2 * l:
        raise MalformedSignature(
            "Invalid length of signature, expected {0} bytes long, "
            "provided string is {1} bytes long".format(2 * l, len(signature))
        )
    r = string_to_number_fixedlen(signature[:l], order)
    s = string_to_number_fixedlen(signature[l:], order)
    return r, s


def sigdecode_strings(rs_strings, order):
    """
    Decode the signature from two strings.

    First string needs to be a big endian encoding of 'r', second needs to
    be a big endian encoding of the 's' parameter of an ECDSA signature.

    It's expected that this function will be used as the `sigdecode=`
    parameter to the :func:`ecdsa.keys.VerifyingKey.verify` method.

    :param list rs_strings: list of two bytes-like objects, each encoding one
        parameter of signature
    :param int order: order of the curve over which the signature was computed

    :raises MalformedSignature: when the encoding of the signature is invalid

    :return: tuple with decoded 'r' and 's' values of signature
    :rtype: tuple of ints
    """
    if not len(rs_strings) == 2:
        raise MalformedSignature(
            "Invalid number of strings provided: {0}, expected 2".format(
                len(rs_strings)
            )
        )
    (r_str, s_str) = rs_strings
    r_str = normalise_bytes(r_str)
    s_str = normalise_bytes(s_str)
    l = orderlen(order)
    if not len(r_str) == l:
        raise MalformedSignature(
            "Invalid length of first string ('r' parameter), "
            "expected {0} bytes long, provided string is {1} "
            "bytes long".format(l, len(r_str))
        )
    if not len(s_str) == l:
        raise MalformedSignature(
            "Invalid length of second string ('s' parameter), "
            "expected {0} bytes long, provided string is {1} "
            "bytes long".format(l, len(s_str))
        )
    r = string_to_number_fixedlen(r_str, order)
    s = string_to_number_fixedlen(s_str, order)
    return r, s


def sigdecode_der(sig_der, order):
    """
    Decoder for DER format of ECDSA signatures.

    DER format of signature is one that uses the :term:`ASN.1` :term:`DER`
    rules to encode it as a sequence of two integers::

        Ecdsa-Sig-Value ::= SEQUENCE {
            r       INTEGER,
            s       INTEGER
        }

    It's expected that this function will be used as as the `sigdecode=`
    parameter to the :func:`ecdsa.keys.VerifyingKey.verify` method.

    :param sig_der: encoded signature
    :type sig_der: bytes like object
    :param order: order of the curve over which the signature was computed
    :type order: int

    :raises UnexpectedDER: when the encoding of signature is invalid

    :return: tuple with decoded 'r' and 's' values of signature
    :rtype: tuple of ints
    """
    sig_der = normalise_bytes(sig_der)
    # return der.encode_sequence(der.encode_integer(r), der.encode_integer(s))
    rs_strings, empty = der.remove_sequence(sig_der)
    if empty != b"":
        raise der.UnexpectedDER(
            "trailing junk after DER sig: %s" % binascii.hexlify(empty)
        )
    r, rest = der.remove_integer(rs_strings)
    s, empty = der.remove_integer(rest)
    if empty != b"":
        raise der.UnexpectedDER(
            "trailing junk after DER numbers: %s" % binascii.hexlify(empty)
        )
    return r, s