0

guys need your expert guide I was doing a research on Bitcoin key space and i have found a mysterious thing that the first public which is actually the generator point is same as the last public key, in the same way 2nd public key and second last public key are same, and if we divide the range into two parts first range last public key is same as 2nd range first public key the only difference i found in these similar keys is '02' and '03' or '04' checksum. i don't understand why there are similarities in public keys?

3

This is a property of elliptic curves. It is expected, and does not meaningfully impact security.

Points on an elliptic curve have an X and Y coordinate. In the case of secp256k1, these coordinates must obey the equation y2 = x3 + 7 (mod p), where p = 2256 - 232 - 977. Whenever (x,y) is on the curve, (x,-y) is too (because y is squared, so its sign is ignored). Now, this is a negation mod p; where "signs" don't really exist; they're all just numbers between 0 and p-1. Negation corresponds to replacing y with p-y, and because p is odd, this means that every X coordinate has exactly one even Y corresponding to it, and one odd one.

To encode public keys, it is unnecessary to send the full Y coordinate. There are only two of them, and one is odd, and one is even. So, the encoding just sends 33 bytes. First one byte to indicate whether Y is even (0x02) or odd (0x03), followed by 32 bytes that encode the full X coordinate.

These two points (x,y) and (x,-y) are also each other's negation. The details are perhaps too much detail to go into here, but the elliptic curve has a "zero" point (also called the point at infinity), which when added to any point gives itself, and adding (x,y) and (x,-y) to each other gives infinity. So in a way, w.r.t. the elliptic curve point addition operation, (x,y) and (x,-y) are each other's negation.

That means that when you negate a private key, you're effectively going to end up with the negation of the corresponding public key. Private keys are numbers, but mod n, and not mod p like the curve point coefficients. n in secp256k1's case is n = 2256 - 432420386565659656852420866394968145599. Overall, this means that the public keys corresponding to a and n-a will indeed have the same X coordinate, and negated Y coordinate.

Is this a problem for security? No, because it's a well known property of elliptic curves, and when analyzing their security, this is taken into account. The best known algorithms for breaking elliptic curve security (solving the ECDLP) make use of this property, and get roughly a factor √2 speedup from it. Yet even with that speedup, the time it takes to break the security of a public key is still astronomical. It is also used for other purposes: with the upcoming Taproot activation in November 2021, BIP340 "Schnorr" signatures will be enabled on the network. These store just the X coordinate, and are only 32 bytes. The Y coordinate is implicitly even.

secp256k1 has in fact a related property too: when multiplying a private key with 78074008874160198520644763525212887401909906723592317393988542598630163514318 results in the X coordinate being multiplied with 55594575648329892869085402983802832744385952214688224221778511981742606582254 (and the Y coordinate staying the same). This property is rather special (it is called the GLV endomorphism), results in a significant speedup for certain cryptographic algorithms (including ECDSA verification), but also results in a √3 speedup for attacks. Again, even taking this speedup into account, security of the curve is very safe.

2
  • I'm curious, by what factor does GLV endomorphism speed up the relevant cryptographic algos?
    – chytrik
    Oct 6 at 3:11
  • If I remember correctly, it's around 30-40% for elliptic curve multiplication. For ECDSA verification it's around a 25% speedup (because it consists of a combination EC multiplication with two bases, and only one of them can take advantage of GLV). Oct 6 at 3:21

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.