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