5
from hashlib import sha256
7
from curves import orderlen
10
# The "unrestricted" algorithm identifier is:
11
# id-ecPublicKey OBJECT IDENTIFIER ::= {
12
# iso(1) member-body(2) us(840) ansi-X9-62(10045) keyType(2) 1 }
14
oid_ecPublicKey = (1, 2, 840, 10045, 2, 1)
15
encoded_oid_ecPublicKey = der.encode_oid(*oid_ecPublicKey)
17
def randrange(order, entropy=None):
18
"""Return a random integer k such that 1 <= k < order, uniformly
19
distributed across that range. For simplicity, this only behaves well if
20
'order' is fairly close (but below) a power of 256. The try-try-again
21
algorithm we use takes longer and longer time (on average) to complete as
22
'order' falls, rising to a maximum of avg=512 loops for the worst-case
23
(256**k)+1 . All of the standard curves behave well. There is a cutoff at
24
10k loops (which raises RuntimeError) to prevent an infinite loop when
25
something is really broken like the entropy function not working.
27
Note that this function is not declared to be forwards-compatible: we may
28
change the behavior in future releases. The entropy= argument (which
29
should get a callable that behaves like os.entropy) can be used to
30
achieve stability within a given release (for repeatable unit tests), but
31
should not be used as a long-term-compatible key generation algorithm.
33
# we could handle arbitrary orders (even 256**k+1) better if we created
34
# candidates bit-wise instead of byte-wise, which would reduce the
35
# worst-case behavior to avg=2 loops, but that would be more complex. The
36
# change would be to round the order up to a power of 256, subtract one
37
# (to get 0xffff..), use that to get a byte-long mask for the top byte,
38
# generate the len-1 entropy bytes, generate one extra byte and mask off
39
# the top bits, then combine it with the rest. Requires jumping back and
40
# forth between strings and integers a lot.
45
bytes = orderlen(order)
46
dont_try_forever = 10000 # gives about 2**-60 failures for worst case
47
while dont_try_forever > 0:
49
candidate = string_to_number(entropy(bytes)) + 1
50
if 1 <= candidate < order:
53
raise RuntimeError("randrange() tried hard but gave up, either something"
54
" is very wrong or you got realllly unlucky. Order was"
58
# this returns a callable which, when invoked with an integer N, will
59
# return N pseudorandom bytes. Note: this is a short-term PRNG, meant
60
# primarily for the needs of randrange_from_seed__trytryagain(), which
61
# only needs to run it a few times per seed. It does not provide
62
# protection against state compromise (forward security).
63
def __init__(self, seed):
64
self.generator = self.block_generator(seed)
66
def __call__(self, numbytes):
67
return "".join([self.generator.next() for i in range(numbytes)])
69
def block_generator(self, seed):
72
for byte in sha256("prng-%d-%s" % (counter, seed)).digest():
76
def randrange_from_seed__overshoot_modulo(seed, order):
77
# hash the data, then turn the digest into a number in [1,order).
79
# We use David-Sarah Hopwood's suggestion: turn it into a number that's
80
# sufficiently larger than the group order, then modulo it down to fit.
81
# This should give adequate (but not perfect) uniformity, and simple
82
# code. There are other choices: try-try-again is the main one.
83
base = PRNG(seed)(2*orderlen(order))
84
number = (int(binascii.hexlify(base), 16) % (order-1)) + 1
85
assert 1 <= number < order, (1, number, order)
88
def lsb_of_ones(numbits):
89
return (1 << numbits) - 1
90
def bits_and_bytes(order):
91
bits = int(math.log(order-1, 2)+1)
94
return bits, bytes, extrabits
96
# the following randrange_from_seed__METHOD() functions take an
97
# arbitrarily-sized secret seed and turn it into a number that obeys the same
98
# range limits as randrange() above. They are meant for deriving consistent
99
# signing keys from a secret rather than generating them randomly, for
100
# example a protocol in which three signing keys are derived from a master
101
# secret. You should use a uniformly-distributed unguessable seed with about
102
# curve.baselen bytes of entropy. To use one, do this:
103
# seed = os.urandom(curve.baselen) # or other starting point
104
# secexp = ecdsa.util.randrange_from_seed__trytryagain(sed, curve.order)
105
# sk = SigningKey.from_secret_exponent(secexp, curve)
107
def randrange_from_seed__truncate_bytes(seed, order, hashmod=sha256):
108
# hash the seed, then turn the digest into a number in [1,order), but
109
# don't worry about trying to uniformly fill the range. This will lose,
110
# on average, four bits of entropy.
111
bits, bytes, extrabits = bits_and_bytes(order)
114
base = hashmod(seed).digest()[:bytes]
115
base = "\x00"*(bytes-len(base)) + base
116
number = 1+int(binascii.hexlify(base), 16)
117
assert 1 <= number < order
120
def randrange_from_seed__truncate_bits(seed, order, hashmod=sha256):
121
# like string_to_randrange_truncate_bytes, but only lose an average of
123
bits = int(math.log(order-1, 2)+1)
124
maxbytes = (bits+7) // 8
125
base = hashmod(seed).digest()[:maxbytes]
126
base = "\x00"*(maxbytes-len(base)) + base
127
topbits = 8*maxbytes - bits
129
base = chr(ord(base[0]) & lsb_of_ones(topbits)) + base[1:]
130
number = 1+int(binascii.hexlify(base), 16)
131
assert 1 <= number < order
134
def randrange_from_seed__trytryagain(seed, order):
135
# figure out exactly how many bits we need (rounded up to the nearest
136
# bit), so we can reduce the chance of looping to less than 0.5 . This is
137
# specified to feed from a byte-oriented PRNG, and discards the
138
# high-order bits of the first byte as necessary to get the right number
139
# of bits. The average number of loops will range from 1.0 (when
140
# order=2**k-1) to 2.0 (when order=2**k+1).
142
bits, bytes, extrabits = bits_and_bytes(order)
143
generate = PRNG(seed)
147
extrabyte = chr(ord(generate(1)) & lsb_of_ones(extrabits))
148
guess = string_to_number(extrabyte + generate(bytes)) + 1
149
if 1 <= guess < order:
153
def number_to_string(num, order):
155
fmt_str = "%0" + str(2*l) + "x"
156
string = binascii.unhexlify(fmt_str % num)
157
assert len(string) == l, (len(string), l)
160
def string_to_number(string):
161
return int(binascii.hexlify(string), 16)
163
def string_to_number_fixedlen(string, order):
165
assert len(string) == l, (len(string), l)
166
return int(binascii.hexlify(string), 16)
168
# these methods are useful for the sigencode= argument to SK.sign() and the
169
# sigdecode= argument to VK.verify(), and control how the signature is packed
172
def sigencode_strings(r, s, order):
173
r_str = number_to_string(r, order)
174
s_str = number_to_string(s, order)
175
return (r_str, s_str)
177
def sigencode_string(r, s, order):
178
# for any given curve, the size of the signature numbers is
179
# fixed, so just use simple concatenation
180
r_str, s_str = sigencode_strings(r, s, order)
183
def sigencode_der(r, s, order):
184
return der.encode_sequence(der.encode_integer(r), der.encode_integer(s))
187
def sigdecode_string(signature, order):
189
assert len(signature) == 2*l, (len(signature), 2*l)
190
r = string_to_number_fixedlen(signature[:l], order)
191
s = string_to_number_fixedlen(signature[l:], order)
194
def sigdecode_strings(rs_strings, order):
195
(r_str, s_str) = rs_strings
197
assert len(r_str) == l, (len(r_str), l)
198
assert len(s_str) == l, (len(s_str), l)
199
r = string_to_number_fixedlen(r_str, order)
200
s = string_to_number_fixedlen(s_str, order)
203
def sigdecode_der(sig_der, order):
204
#return der.encode_sequence(der.encode_integer(r), der.encode_integer(s))
205
rs_strings, empty = der.remove_sequence(sig_der)
207
raise der.UnexpectedDER("trailing junk after DER sig: %s" %
208
binascii.hexlify(empty))
209
r, rest = der.remove_integer(rs_strings)
210
s, empty = der.remove_integer(rest)
212
raise der.UnexpectedDER("trailing junk after DER numbers: %s" %
213
binascii.hexlify(empty))
added
removed
ecdsa/util.py
