4

Couple questions of code that I'm reviewing trying to learn schnorr sigs.

Why do we want an odd private key? I see even tests on the private key and then subtract it from the SECP256K1 Order to get an odd point?

Schnorr verify seems to need the square root of a point ,specifically this code here, why and what is this doing? I'm confused on what is happening conceptually.

def lift_x(x: int) -> Optional[Point]:
    if x >= p:
        return None
    y_sq = (pow(x, 3, p) + 7) % p #<-the curve
    y = pow(y_sq, (p + 1) // 4, p) # why is this __floordiv__ 4?
    if pow(y, 2, p) != y_sq:
        return None
    return (x, y if y & 1 == 0 else p-y) # make y odd if there is a sqrt?

Thanks

1 Answer 1

4
def lift_x(x: int) -> Optional[Point]:

This is a function that given an X coordinate, computes one of the two corresponding Y coordinates on the curve; specifically, the even one.

Every possible value in the field of coordinates (integers modulo p, where p = 2256 - 232 - 977) has exactly 0 points on the curve y2 = x3 + 7, or exactly two. In case there are two points with a given X coordinate, the corresponding Y coordinates will be each other's negation (modulo p), and one will be even, and one will be odd. This lift_x function returns the one with the even Y.

    y_sq = (pow(x, 3, p) + 7) % p #<-the curve

This computes y_sq = y2, using the fact that it equals x3 + 7 (mod p), using the curve equation.

    y = pow(y_sq, (p + 1) // 4, p) # why is this __floordiv__ 4?

This computes the square root y of the value y_sq we determined in the previous now. In general, modular square roots can be computed using the Tonelli-Shanks algorithm, but for the secp256k1 modulus, this algorithm simply boils down to computing y_sq(p+1)/4 mod p. In Python, we need to write this (p+1)/4 as (p+1)//4 because we want exact integer arithmetic. (p+1)/4 would compute an approximate floating point number only.

    if pow(y, 2, p) != y_sq:
        return None

This verifies whether the computed value y is actually the modular square root of y_sq. If the input x value was not a valid X coordinate on the curve, then x3 + 7 won't be a square, and thus won't have a square root. However, the formula y_sq(p+1)/4 always yields a result, even when y_sq doesn't have a square root. So we need to check whether y2 = y_sq. If not, we return None immediately: the input X has no corresponding Y coordinates.

    return (x, y if y & 1 == 0 else p-y) # make y odd if there is a sqrt?

This simply negates y (modulo p) if y is odd, thereby finding the other (even) solution. This guarantees returning the even Y coordinate out of the two solutions.

3
  • 1
    Thanks a lot. I think I see it now, it looks like it is for consistency. When we do ecc point add, the result will be significantly different for the point that has a 'negative' 7 than the point with a 'positive'? Or does it have something to do with key compression?
    – Kaizen
    Oct 16, 2022 at 23:09
  • 1
    Given a fixed X coordinate, the two curve points with that coordinate are each other's negation (in ECC logic, -(x,y) = (x,-y)). So the choice very much matters: point1 + lift_x_odd(x2) = point1 - lift_x(x2) (so it'd be negation instead of addition), where lift_x_odd is a hypothetical variant of lift_x which maps to the odd Y coordinate rather than the even one. Note that it's not a negative/positive 7 (changing the sign of the 7 would be changing the curve equation, rendering it entirely insecure). All we're doing is choosing which of the solutions for Y to pick. Oct 17, 2022 at 18:50
  • 1
    Thanks, that really clears things up for me and furthers my understanding.
    – Kaizen
    Oct 18, 2022 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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