ECDSA points where x-values are between n and p

5 replies 481 views
coin777Senior Member
Posts: 143 · Reputation: 970
#1Feb 15, 2018, 01:42 AM
This point looks valid on secp256k1, at least from what I gather. Also, for those two distinct points, we get the same r-value since point coordinates are computed modulo "p", while signatures are done modulo "n". So, does that imply that regarding malleability, there are more scenarios than just (r,s) and (r,-s), and can it be modified in some way? Or does it suggest that for the same message and signature, there could be multiple corresponding public keys?
5 Reply Quote Share
sage2018Member
Posts: 24 · Reputation: 181
#2Feb 15, 2018, 02:29 AM
Pretty sure any r that's above or equal to FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 is considered invalid by Bitcoin. Nevermind, I misunderstood. I think technically it might be a malleability, but since I assume you don't know the actual private keys behind any of the public keys, it's more a theoretical issue than practical.
3 Reply Quote Share
im_apeHero Member
Posts: 629 · Reputation: 3824
#3Feb 15, 2018, 06:47 AM
You can derive more than one possible public key from a valid ECDSA signature and message but that is not related to malleability since the public key is always locked in the script that is being spent one way or another (it is unchangeable). For example in a P2PKH script the hash of the public key is already locked in the scriptpub and if you use a different public key the transaction will be rejected on OP_EQUALVERIFY before it even reaches the signature verification step. P.S. All 3 public keys you posted are valid since they are on secp256k1 curve.
2 Reply Quote Share
Posts: 34 · Reputation: 220
#4Feb 15, 2018, 10:01 AM
According to BIP62, when the value of s is more than half of n (the total number of points), we simply take s = n - s. In other words, given this rule, any signature where the value of s is too high is considered invalid. As for public keys, there can theoretically be 4 different public keys for the same message and private key if the value of r is lower than n-p. In this case, you will have two x-coordinates (x=r and x=r+n) and two y-coordinates for each x (even and odd).
0 Reply Quote Share
LuckyCoinLegendary
Posts: 832 · Reputation: 4795
#5Feb 16, 2018, 05:16 AM
It is purely an academic discussion, as the probability of hitting any x mod n is already so low that dividing the probability by two won't make much of a difference in terms of security.
1 Reply Quote Share
byte2019Senior Member
Posts: 270 · Reputation: 1836
#6Feb 16, 2018, 09:11 AM
It is not so academic, if you note, that 02FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 and 03FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 is considered as "zero", when used as "r-value". Which means, that instead of "s=(z+rd)/k", when "r=n", then it is simplified to "s=z/k", and then, the signature no longer depends on "d-value", which means, that it can be valid, regardless of the used public key (it depends on the exact implementation, how it is handled, and if that can cause a fork or not, when one node will consider something as valid, while another node will reject it). Also, it stops being so "academic", if you note, that "Q.x==n" is not the only choice, that can cause some issues. For example, here is another valid key: 027fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0. And another one: 024ccccccccccccccccccccccccccccccc6b34757867c8fcdeb98be92a3e76ad2d. And then, even if all public keys are restricted, to have their (x,y) coordinates strictly below n-value, then there are still some dependencies inside secp256k1, which can lead you to a "weak" signature, if it was based on a "weak" value like that. Definitely, it is something to be explored on weaker curves than secp256k1, to make sure, that signatures are not too easy to tweak, and that the attacker cannot achieve any advantage, by trying to land on 02FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141, 027fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0, or similar points, for different implementations.
4 Reply Quote Share

Related topics