"""
Implementation of Elliptic-Curve Digital Signatures.
Classes and methods for elliptic-curve signatures:
private keys, public keys, signatures,
NIST prime-modulus curves with modulus lengths of
192, 224, 256, 384, and 521 bits.
Example:
# (In real-life applications, you would probably want to # protect against defects in SystemRandom.) from random import SystemRandom
randrange = SystemRandom().randrange
# Generate a public/private key pair using the NIST Curve P-192:
g = generator_192
n = g.order()
secret = randrange( 1, n )
pubkey = Public_key( g, g * secret )
privkey = Private_key( pubkey, secret )
# Signing a hash value:
hash = randrange( 1, n )
signature = privkey.sign( hash, randrange( 1, n ) )
# Verification fails if the hash value is modified:
if pubkey.verifies( hash-1, signature ):
print_("**** Demo verification failed to reject tampered hash.") else:
print_("Demo verification correctly rejected tampered hash.")
Version of 2009.05.16.
Revision history:
2005.12.31 - Initial version.
2008.11.25 - Substantial revisions introducing new classes.
2009.05.16 - Warn against using random.randrange in real applications.
2009.05.17 - Use random.SystemRandom by default.
Written in 2005 by Peter Pearson and placed in the public domain. """
from six import int2byte, b from . import ellipticcurve from . import numbertheory from .util import bit_length
class RSZeroError(RuntimeError): pass
class InvalidPointError(RuntimeError): pass
class Signature(object): """ECDSA signature. """ def __init__(self, r, s):
self.r = r
self.s = s
def recover_public_keys(self, hash, generator): """Returns two public keys for which the signature is valid
hash is signed hash
generator is the used generator of the signature """
curve = generator.curve()
n = generator.order()
r = self.r
s = self.s
e = hash
x = r
# Compute the curve point with x as x-coordinate
alpha = (pow(x, 3, curve.p()) + (curve.a() * x) + curve.b()) % curve.p()
beta = numbertheory.square_root_mod_prime(alpha, curve.p())
y = beta if beta % 2 == 0 else curve.p() - beta
# Compute the public key
R1 = ellipticcurve.PointJacobi(curve, x, y, 1, n)
Q1 = numbertheory.inverse_mod(r, n) * (s * R1 + (-e % n) * generator)
Pk1 = Public_key(generator, Q1)
# And the second solution
R2 = ellipticcurve.PointJacobi(curve, x, -y, 1, n)
Q2 = numbertheory.inverse_mod(r, n) * (s * R2 + (-e % n) * generator)
Pk2 = Public_key(generator, Q2)
return [Pk1, Pk2]
class Public_key(object): """Public key for ECDSA. """
def __init__(self, generator, point, verify=True): """
Low level ECDSA public key object.
:param generator: the Point that generates the group (the base point)
:param point: the Point that defines the public key
:param bool verify: ifTrue check if point is valid point on curve
:raises InvalidPointError: if the point parameters are invalid or
point does not lie on the curve """
self.curve = generator.curve()
self.generator = generator
self.point = point
n = generator.order()
p = self.curve.p() ifnot (0 <= point.x() < p) ornot (0 <= point.y() < p): raise InvalidPointError("The public point has x or y out of range.") if verify andnot self.curve.contains_point(point.x(), point.y()): raise InvalidPointError("Point does not lie on the curve") ifnot n: raise InvalidPointError("Generator point must have order.") # for curve parameters with base point with cofactor 1, all points # that are on the curve are scalar multiples of the base point, so # verifying that is not necessary. See Section 3.2.2.1 of SEC 1 v2 if verify and self.curve.cofactor() != 1 and \ not n * point == ellipticcurve.INFINITY: raise InvalidPointError("Generator point order is bad.")
def __eq__(self, other): if isinstance(other, Public_key): """Return True if the points are identical, False otherwise.""" return self.curve == other.curve \ and self.point == other.point return NotImplemented
def verifies(self, hash, signature): """Verify that signature is a valid signature of hash. ReturnTrueif the signature is valid. """
# From X9.62 J.3.1.
G = self.generator
n = G.order()
r = signature.r
s = signature.s if r < 1 or r > n - 1: returnFalse if s < 1 or s > n - 1: returnFalse
c = numbertheory.inverse_mod(s, n)
u1 = (hash * c) % n
u2 = (r * c) % n if hasattr(G, "mul_add"):
xy = G.mul_add(u1, self.point, u2) else:
xy = u1 * G + u2 * self.point
v = xy.x() % n return v == r
class Private_key(object): """Private key for ECDSA. """
def __init__(self, public_key, secret_multiplier): """public_key is of class Public_key;
secret_multiplier is a large integer. """
def __eq__(self, other): if isinstance(other, Private_key): """Return True if the points are identical, False otherwise.""" return self.public_key == other.public_key \ and self.secret_multiplier == other.secret_multiplier return NotImplemented
def sign(self, hash, random_k): """Return a signature for the provided hash, using the provided
random nonce. It is absolutely vital that random_k be an unpredictable
number in the range [1, self.public_key.point.order()-1]. If
an attacker can guess random_k, he can compute our private key from a
single signature. Also, if an attacker knows a few high-order
bits (or a few low-order bits) of random_k, he can compute our private
key from many signatures. The generation of nonces with adequate
cryptographic strength is very difficult and far beyond the scope
of this comment.
May raise RuntimeError, in which case retrying with a new
random value k isin order. """
G = self.public_key.generator
n = G.order()
k = random_k % n # Fix the bit-length of the random nonce, # so that it doesn't leak via timing. # This does not change that ks = k mod n
ks = k + n
kt = ks + n if bit_length(ks) == bit_length(n):
p1 = kt * G else:
p1 = ks * G
r = p1.x() % n if r == 0: raise RSZeroError("amazingly unlucky random number r")
s = (numbertheory.inverse_mod(k, n)
* (hash + (self.secret_multiplier * r) % n)) % n if s == 0: raise RSZeroError("amazingly unlucky random number s") return Signature(r, s)
def int_to_string(x): """Convert integer x into a string of bytes, as per X9.62.""" assert x >= 0 if x == 0: return b('\0')
result = [] while x:
ordinal = x & 0xFF
result.append(int2byte(ordinal))
x >>= 8
result.reverse() return b('').join(result)
def string_to_int(s): """Convert a string of bytes into an integer, as per X9.62."""
result = 0 for c in s: ifnot isinstance(c, int):
c = ord(c)
result = 256 * result + c return result
def digest_integer(m): """Convert an integer into a string of bytes, compute
its SHA-1 hash, and convert the result to an integer.""" # # I don't expect this function to be used much. I wrote # it in order to be able to duplicate the examples # in ECDSAVS. # from hashlib import sha1 return string_to_int(sha1(int_to_string(m)).digest())
def point_is_valid(generator, x, y): """Is (x,y) a valid public key based on the specified generator?"""
# These are the tests specified in X9.62.
n = generator.order()
curve = generator.curve()
p = curve.p() ifnot (0 <= x < p) ornot (0 <= y < p): returnFalse ifnot curve.contains_point(x, y): returnFalse if curve.cofactor() != 1 and \ not n * ellipticcurve.PointJacobi(curve, x, y, 1)\
== ellipticcurve.INFINITY: returnFalse returnTrue
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.
