Verifying K Value in Sagemath

[krashfire]

How do i verify if the found K value is the correct value given for an R signature and a public key?

i really need help for someone to check my code.

Code:

def verify(r, s, z, public_key, k):
    w = modinv(s, n)
    u1 = z * w % n
    u2 = r * w % n
    R = E.lift_x(r)
    # Compute the candidate public key using the known k value
    candidate_public_key = u1 * G + u2 * R
    if public_key == candidate_public_key:
        print("Signature matches")
        return True
    else:
        print("Invalid signature")
        return False

def find_k_bruteforce(r, s, z, pub):
    i = 1
    max_iterations = 1000  # Add a maximum iteration limit
    while i <= max_iterations:
        k = (r * i + z) * modinv(s, n) % n
        print("i=", i, "k==", hex(k))
        # Verify the signature using the candidate k
        if verify(r, s, z, pub, k):
            print("Found k:", hex(k))
            return k
        else:
            print(f"Attempt {i}: Incorrect k value {hex(k)}")
        i += 1  # Increment i for the next iteration
    raise Exception("Failed to find a valid k value within the maximum iterations")

how do i verify the k value found? my calculations are wrong. it verifies the wrong k value.

[1714901781]

1714901781

[1714901781]

1714901781

[1714901781]

1714901781

[mamuu]

Hello there

"R = E.lift_x(r)"
there are 2 possibilities in this line for point R
"R" or "-R"

If "public_key" is not a string but a "point" object(like G) with "E" element (Ellipric Curve)

"R= u2*public_key + u1*G"

it's the right thing to do.

Thank you.

[krashfire]

Hello there

"R = E.lift_x(r)"
there are 2 possibilities in this line for point R
"R" or "-R"

If "public_key" is not a string but a "point" object(like G) with "E" element (Ellipric Curve)

"R= u2*public_key + u1*G"

it's the right thing to do.

Thank you.

So you are saying i should instead write it like this?

Code:

 

def verify(r, s, z, public_key, k):
    # Compute modular inverse of s
    w = modinv(s, n)
    
    # Compute u1 and u2
    u1 = z * w % n
    u2 = r * w % n
    
    # Compute R using the provided x-coordinate r
    R = E.lift_x(r)
    
    # Compute the candidate public key using the provided k value
    candidate_public_key = u1 * public_key + u2 * G
    
    # Check if the x-coordinate of the computed R matches that of the candidate public key
    if R[0] == candidate_public_key[0]:
        print("Signature matches")
        return True
    else:
        print("Invalid signature")
        return False

[mamuu]

on sagemath
-------------------------------



sage:#prime [type:integer] but prime
sage:P = 115792089237316195423570985008687907853269984665640564039457584007908834671663

sage:#Elliptic Curve y2=x3+7 for P [type:curve]
sage:E = EllitpicCurve(GF(P),[0,7])

sage:#Elliptic Curve Order [type:integer]
sage:N = E.order()

sage:#Base Point G [type:point]
sage:G= E(55066263022277343669578718895168534326250603453777594175500187360389116729240,32670510020758816978083085130507043184471273380659243275938904335757337482424)

sage:# "public_key = secret*G" or "public_key = E(pubkey_x,pubkey_y)" [type:point], we know "pubkey_x,pubkey_y"
sage:public_key = E(pubkey_x,pubkey_y)

sage:# "K=random_number*G"  [type:point] than "r = K[0]" [type:integer] , you known "r"
sage:K = E.lift_x(r)

sage:#K is_correct ? we don't know

sage:r = your_value #[type:integer]
sage:s = your_value #[type:integer]
sage:z = your_value #[type:integer]


sage:w = 1/s %N
sage:u1 = z * w %N
sage:u2 = r * w %N

sage:#correct "K" point [type:point]
sage:u2*public_key + u1*G #[type:point]

sage:+K == u2*public_key + u1*G #(true or false)
sage:-K == u2*public_key + u1*G #(true or false)

sage r == Integer(+K[0]) #(true or false) [type:integer]
sage r == Integer(-K[0]) #(true or false) [type:integer]

sage:var("k x")

sage:k*s == r*x+z #[type:variable]

sage : K*s == r*public_key + z*G  #[type:point] (true or false)



this line type: point
R = E.lift_x(r)

[krashfire]

on sagemath
-------------------------------



sage:#prime [type:integer] but prime
sage:P = 115792089237316195423570985008687907853269984665640564039457584007908834671663

sage:#Elliptic Curve y2=x3+7 for P [type:curve]
sage:E = EllitpicCurve(GF(P),[0,7])

sage:#Elliptic Curve Order [type:integer]
sage:N = E.order()

sage:#Base Point G [type:point]
sage:G= E(55066263022277343669578718895168534326250603453777594175500187360389116729240,32670510020758816978083085130507043184471273380659243275938904335757337482424)

sage:# "public_key = secret*G" or "public_key = E(pubkey_x,pubkey_y)" [type:point], we know "pubkey_x,pubkey_y"
sage:public_key = E(pubkey_x,pubkey_y)

sage:# "K=random_number*G"  [type:point] than "r = K[0]" [type:integer] , you known "r"
sage:K = E.lift_x(r)

sage:#K is_correct ? we don't know

sage:r = your_value #[type:integer]
sage:s = your_value #[type:integer]
sage:z = your_value #[type:integer]


sage:w = 1/s %N
sage:u1 = z * w %N
sage:u2 = r * w %N

sage:#correct "K" point [type:point]
sage:u2*public_key + u1*G #[type:point]

sage:+K == u2*public_key + u1*G #(true or false)
sage:-K == u2*public_key + u1*G #(true or false)

sage r == Integer(+K[0]) #(true or false) [type:integer]
sage r == Integer(-K[0]) #(true or false) [type:integer]

sage:var("k x")

sage:k*s == r*x+z #[type:variable]

sage : K*s == r*public_key + z*G  #[type:point] (true or false)



this line type: point
R = E.lift_x(r)

Ok. Got it. Thank you so much! But I still need to verify the K value found. How do I do it correctly? Your method only shows whether K+ or K- is the correct one. But I still need to verify the K value by brute forcing. So how do I write the code to verify the K found?

[whanau]

Ok. Got it. Thank you so much! But I still need to verify the K value found. How do I do it correctly? Your method only shows whether K+ or K- is the correct one. But I still need to verify the K value by brute forcing. So how do I write the code to verify the K found?

# Compute the new signature point
        P = k * G   (k = your new k on test)

        # Check if the x-coordinate of the signature point matches r
        if P.x() == r:
            print(f"Found k candidate: {k:x} ")
            private_key = (s * k - z) * mod_inv(r, n) % n
            print("Private Key      : %02x " % private_key)

[krashfire]

# Compute the new signature point
        P = k * G   (k = your new k on test)

        # Check if the x-coordinate of the signature point matches r
        if P.x() == r:
            print(f"Found k candidate: {k:x} ")
            private_key = (s * k - z) * mod_inv(r, n) % n
            print("Private Key      : %02x " % private_key)

Thank You!!

[Bglhn]

Hello, what is your formula to find k? I've been looking for this too and couldn't find a solution.

[mamuu]

on sagemath
-------------------------------



sage:#prime [type:integer] but prime
sage:P = 115792089237316195423570985008687907853269984665640564039457584007908834671663

sage:#Elliptic Curve y2=x3+7 for P [type:curve]
sage:E = EllitpicCurve(GF(P),[0,7])

sage:#Elliptic Curve Order [type:integer]
sage:N = E.order()

sage:#Base Point G [type:point]
sage:G= E(55066263022277343669578718895168534326250603453777594175500187360389116729240,32670510020758816978083085130507043184471273380659243275938904335757337482424)

sage:# "public_key = secret*G" or "public_key = E(pubkey_x,pubkey_y)" [type:point], we know "pubkey_x,pubkey_y"
sage:public_key = E(pubkey_x,pubkey_y)

sage:# "K=random_number*G"  [type:point] than "r = K[0]" [type:integer] , you known "r"
sage:K = E.lift_x(r)

sage:#K is_correct ? we don't know

sage:r = your_value #[type:integer]
sage:s = your_value #[type:integer]
sage:z = your_value #[type:integer]


sage:w = 1/s %N
sage:u1 = z * w %N
sage:u2 = r * w %N

sage:#correct "K" point [type:point]
sage:u2*public_key + u1*G #[type:point]

sage:+K == u2*public_key + u1*G #(true or false)
sage:-K == u2*public_key + u1*G #(true or false)

sage r == Integer(+K[0]) #(true or false) [type:integer]
sage r == Integer(-K[0]) #(true or false) [type:integer]

sage:var("k x")

sage:k*s == r*x+z #[type:variable]

sage : K*s == r*public_key + z*G  #[type:point] (true or false)



this line type: point
R = E.lift_x(r)

+K and -K are [points], and k is [integer].

in this case

K=(x/s)*PubKey + (z/s)*G

or
K = k*G

k=randint(1,N) #i.e. a random number, you can only try to find this number. it is very difficult in this process.

You can find "k" directly with the values r,s,z
With E.lift_x(R) you get either "+K" or "-K" and this is a "point". However, you cannot find the value "k", which is an integer.

[Bglhn]

So how did you find your G spot? and p is your prime? I'm trying to learn, but I don't have enough knowledge.

[mamuu]

So how did you find your G spot? and p is your prime? I'm trying to learn, but I don't have enough knowledge.

You have to research and learn, I can't explain this situation, you can now learn by communicating with an artificial intelligence.

[vjudeu]

So how did you find your G spot?

Nobody knows that. It seems someone used 0x48ce563f89a0ed9414f5aa28ad0d96d6795f9c62 as a magic number to start with, but nobody knows why: https://www.youtube.com/watch?v=NGLR2N4EK58

And there are more magic numbers outside Bitcoin, even with reward for explaining them: https://bitcointalk.org/index.php?topic=5469657.0

you can now learn by communicating with an artificial intelligence

AI is terrible at math, try asking about block hashes and transactions, in most cases it will be completely wrong, and it can give you for example an answer, where Bitcoin transaction format is mixed with Ethereum and other altcoins.