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

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,): # pragma: no branch 

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 

42else: 

43 

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) 

47 

48 

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 

53 

54else: 

55 

56 def bit_length(x): 

57 return x.bit_length() or 1 

58 

59 

60def orderlen(order): 

61 return (1 + len("%x" % order)) // 2 # bytes 

62 

63 

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. 

68 

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 

86 

87 

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) 

96 

97 def __call__(self, numbytes): 

98 a = [next(self.generator) for i in range(numbytes)] 

99 

100 if PY2: # pragma: no branch 

101 return "".join(a) 

102 else: 

103 return bytes(a) 

104 

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 

113 

114 

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 

126 

127 

128def lsb_of_ones(numbits): 

129 return (1 << numbits) - 1 

130 

131 

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 

137 

138 

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) 

149 

150 

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 

163 

164 

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 

178 

179 

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 

197 

198 

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 

205 

206 

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] 

212 

213 

214def string_to_number(string): 

215 return int(binascii.hexlify(string), 16) 

216 

217 

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) 

222 

223 

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. 

227 

228 

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) 

233 

234 

235def sigencode_string(r, s, order): 

236 """ 

237 Encode the signature to raw format (:term:`raw encoding`) 

238 

239 It's expected that this function will be used as a `sigencode=` parameter 

240 in :func:`ecdsa.keys.SigningKey.sign` method. 

241 

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 

246 

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 

254 

255 

256def sigencode_der(r, s, order): 

257 """ 

258 Encode the signature into the ECDSA-Sig-Value structure using :term:`DER`. 

259 

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

261 

262 Ecdsa-Sig-Value ::= SEQUENCE { 

263 r INTEGER, 

264 s INTEGER 

265 } 

266 

267 It's expected that this function will be used as a `sigencode=` parameter 

268 in :func:`ecdsa.keys.SigningKey.sign` method. 

269 

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 

274 

275 :return: DER encoding of ECDSA signature 

276 :rtype: bytes 

277 """ 

278 return der.encode_sequence(der.encode_integer(r), der.encode_integer(s)) 

279 

280 

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) 

289 

290 

291def sigencode_string_canonize(r, s, order): 

292 if s > order / 2: 

293 s = order - s 

294 return sigencode_string(r, s, order) 

295 

296 

297def sigencode_der_canonize(r, s, order): 

298 if s > order / 2: 

299 s = order - s 

300 return sigencode_der(r, s, order) 

301 

302 

303class MalformedSignature(Exception): 

304 """ 

305 Raised by decoding functions when the signature is malformed. 

306 

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 """ 

312 

313 pass 

314 

315 

316def sigdecode_string(signature, order): 

317 """ 

318 Decoder for :term:`raw encoding` of ECDSA signatures. 

319 

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. 

323 

324 It's expected that this function will be used as the `sigdecode=` 

325 parameter to the :func:`ecdsa.keys.VerifyingKey.verify` method. 

326 

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 

331 

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

333 

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 

347 

348 

349def sigdecode_strings(rs_strings, order): 

350 """ 

351 Decode the signature from two strings. 

352 

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. 

355 

356 It's expected that this function will be used as the `sigdecode=` 

357 parameter to the :func:`ecdsa.keys.VerifyingKey.verify` method. 

358 

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 

362 

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

364 

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 

393 

394 

395def sigdecode_der(sig_der, order): 

396 """ 

397 Decoder for DER format of ECDSA signatures. 

398 

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:: 

401 

402 Ecdsa-Sig-Value ::= SEQUENCE { 

403 r INTEGER, 

404 s INTEGER 

405 } 

406 

407 It's expected that this function will be used as as the `sigdecode=` 

408 parameter to the :func:`ecdsa.keys.VerifyingKey.verify` method. 

409 

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 

414 

415 :raises UnexpectedDER: when the encoding of signature is invalid 

416 

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