Demo how to generate an ECDSA signature without knowledge of private key (in SageMath)

ECDSA_signature_without_private_key.sage

import hashlib

# ECDSA Signature without private key

# An ECDSA signature without prior commitment to the signer's key
# does not prove that the signer knows the private key
# of the pubkey for which the signature validates.

# A short demonstration:


# Setup secp256k1 curve:
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f      # prime
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141      # order of the curve
Fn = FiniteField(n)                                                         # Finite field over n
secp256k1 = EllipticCurve( GF(p), [0, 7] )

# G base point
G = secp256k1.point( (0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8) )



# Helper functions:

# Calculate hash of message for signing
def get_message_hash(msg):
    # hash with sha256 and encode to UTF-8
    msgHashAsHexString = hashlib.sha256(msg.encode(encoding = 'UTF-8')).hexdigest()
    # return hash value as Integer
    return Integer('0x' + msgHashAsHexString)

# ecdsa signature verification
def ecdsa_verify(pub_key, msg, r, s):
    w = ZZ( 1/ Fn(s) )                        # = 1/s
    u1 = get_message_hash(msg) * w            # u1 = hash_of_message * 1/s
    u2 = r * w
    P1 = Integer(u1) * G                      # G is base point
    P2 = Integer(u2) * pub_key                # pub_key is public key for which the signature should validate
    X = P1 + P2
    (x, y) = X.xy()
    v = Fn(x)
    return v == r




#
# MESSAGE to sign:  :)
#
message = 'I am Satoshi, because we all are Satoshi :-)'



# an ECDSA signature consists of 2 scalar values: (r, s)
# Let's generate a completely RANDOM signature:

#
# Choose a random x coordinate r until we find one, which also has a point on the curve:
#
found_a_point = False
while found_a_point == False:

    # create random r, will be part of the signature (r, s)
    r = randint(1, p - 1)              # is an x coordinate, thus upper bound p

    # check if there is a point at this x-coord
    found_a_point = secp256k1.is_x_coord(r)

R = secp256k1.lift_x(Integer(r))       # get the point R at x-coordinate r


#
# Generate a random s
#
s = randint(1, n - 1)      # is used in point multiplication, thus upper bound n




#
# Our signature for the message aboce is now:  (r, s)
#
print('Our message: ' + message)
print('Our (randomly generated) ECDSA Signature:')
print('r: ' + str(r))
print('s: ' + str(s))
print()


#
# And now let's calculate the public key for which this random signature will validate:
#   Q   =  (sR - hG)/r
#

h = get_message_hash(message)

Q = (s*R - h*G)  *  ZZ( 1 / Fn(r) )


# RESULT:
print('And here is the pubkey for which this signature will validate:')
print('x coordinate: ' + str(Q.x()))
print('y coordinate: ' + str(Q.y()))
print()
print('Voila.. :-)')
print()
print('Does the signature verify? ...')
ecdsa_verify(Q, message, r, s)




# Sample output:

#  Our message: I am Satoshi, because we all are Satoshi :-)
#  Our (randomly generated) ECDSA Signature:
#  s: 24828058834046652854540677321878462375477002606677988961933119664452896577927
#  r: 104150767398129614233917872756744768266909588448171424309616024326744528822140
#
#  And here is the pubkey for which this signature will validate:
#  x coordinate: 78105301398590714238102023061657833145875102847999004320934470842361111461126
#  y coordinate: 66537312592386171185922156484664526796876351425099945787863334980961115997865
#
#  Voila.. :-)
#
#  Does the signature verify? ...
#  True