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

Pieter Wuille
  • 98,249
  • 9
  • 183
  • 287
Kaizen
  • 331
  • 1
  • 6

1 Answers1

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.

Pieter Wuille
  • 98,249
  • 9
  • 183
  • 287
  • 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 '22 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. – Pieter Wuille Oct 17 '22 at 18:50
  • 1
    Thanks, that really clears things up for me and furthers my understanding. – Kaizen Oct 18 '22 at 18:28