0

I am trying to create a public key whose x starts with "34" and is followed by the minimum number n such that the concatenation of "34" and n is the x of a valid point (x, y) on the elliptic curve secp256k1. Submit the concatenation of 04, x and y in hexadecimal form. This is a valid bitcoin public key, the corresponding secret key of which is not known by anyone.

I was told that the minimum number is 0.

My understanding is that the answer is supposed to be like this: '0434' + hex(n) + y_value. I am not sure how to approach this.

Is it true that x-coordinate is supposed to be 32 bytes and y coordinate 32 bytes too?

Is it true that each coordinate is represented in hex mode of 64 chars?

Is the public key represented by 130 hex chars? I have tried some online tools: e.g. https://iancoleman.io/bitcoin-key-compression/ and some python code but I always get a wrong answer.

X = '0x3400000000000000000000000000000000000000000000000000000000000000'
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
print("x coordinate = %s " % X)
x = int(X,16)
print(x)
ysquared = ((x*x*x+7) % p)
print("ysquared= %s " % ysquared)
y = pow(ysquared, (p+1)//4, p)
print("y1 = %s " % hex(y))
print("y2 = %s " % hex((y * -1 % p)))
print("-----------------")
print('04' + X[2:] + hex(y)[2:])
print('04' + X[2:] + hex((y * -1 % p))[2:])
1

I was told that the minimum number is 0.

That is correct. 0x3400000000000000000000000000000000000000000000000000000000000000 is a valid x-coordinate on secp256k1.

My understanding is that the answer is supposed to be like this: '0434' + hex(n) + y_value. I am not sure how to approach this

That is also correct. However, you will have two y-coordinates. One even and one odd and hence two uncompressed public keys. That is the reason why we append a prefix to the x-coordinate to tell us whether the y-coordinate associated with that x-coordinate is even or odd.

Is it true that x-coordinate is supposed to be 32 bytes and y coordinate 32 bytes too?

That is the maximum size. It can be below that as well.

Is it true that each coordinate is represented in hex mode of 64 chars?

Related to to above. One byte representation needs two hexadecimal characters.

Python code

I'll use the below one.

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
def modular_sqrt(n, p):
    ''' Find a quadratic residue (mod p) of 'n'. For Bitcoin p is an odd prime, that satisfies
        the identity p % 4 == 3. As a result, this is a simple solution where the modular square
        root of y^2 is : y = pow(y^2, (p + 1) // 4, p).
        If p did not satisfy that identity we would have had to use the Tonelli-Shank's algorithm
    '''
    return pow(n, (p + 1) // 4, p)

def y_coordinate_from_x(x_coordinate_with_prefix):
    public_key_x_coordinate = int(x_coordinate_with_prefix[2:], 16)
    public_key_y_coordinate_sign = int(x_coordinate_with_prefix[:2])
    y_squared = (public_key_x_coordinate**3 + 7) % int(p)
    public_key_y_coordinate = modular_sqrt(y_squared, int(p))

    # check the sign (odd or even) and match that to the sign provided by x-coordinate
    sign_check = 0 if public_key_y_coordinate_sign == 2 else 1
    if int(str(public_key_y_coordinate)[-1:]) % 2 != sign_check:
        public_key_y_coordinate = int(p) - public_key_y_coordinate

    return '%064x'%public_key_y_coordinate

x = '3400000000000000000000000000000000000000000000000000000000000000'
y1 = y_coordinate_from_x('02' + x)
y2 = y_coordinate_from_x('03' + x)

so your uncompressed public keys are '04'+x+y1 and '04'+x+y2

  • Thank you very much for your reply! Your code produces the same keys as mine though. And if x can be less than 32 bytes then is x=0x320 a valid point on the curve? I tried that too but it is not still the correct answer. – Δήμητρα Γεωργίου Jul 24 at 20:08
  • @ΔήμητραΓεωργίου Yes, x can be less than 32 bytes. However, not all points are members of the secp256k1 curve. For example, 0x32 is not a valid x-coordinate but 0x320 is. In most programs (including the one I pasted above), you will need to pad the public key hexadecimal to 32 bytes. Also what do you mean by correct answer? – Ugam Kamat Jul 25 at 5:15
  • Thank you again! My professor does not accept '0434000000000000000000000000000000000000000000000000000000000000009d143cafb07ae7ea8025f44c9cf201dc34e4cc71003869b81cca00e0844d16f4' or '04340000000000000000000000000000000000000000000000000000000000000062ebc3504f8518157fda0bb3630dfe23cb1b338effc79647e335ff1e7bb2e53b' as correct answers. Maybe this is what you say now: "pad the public key hexadecimal to 32 bytes". Could you please explain what you mean? I have really lost my mind over this. – Δήμητρα Γεωργίου Jul 25 at 6:19
  • @ΔήμητραΓεωργίου Hey, so both the keys that you mentioned are valid points on the secp256k1 curve and as such are valid Bitcoin public keys. disregard the padding, it was related to something else that might just confuse you. – Ugam Kamat Jul 25 at 6:28
  • Ok! Do you you know what is the answer to the above problem because I still don't know. Thank you again! – Δήμητρα Γεωργίου Jul 25 at 6:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.