As Peter Wuille mentions here, the ECDSA signature values (r, s) are modulo
N (eg verifying ECDSA signatures, where
u1 = z * w % N), whereas the rest of the ECDSA functionality in Bitcoin seems to be modulo
Why is this so?
Bitcoin Stack Exchange is a question and answer site for Bitcoin crypto-currency enthusiasts. It only takes a minute to sign up.Sign up to join this community
Good question! There are two concepts here. The finite field Fp, and the EC Group defined by secp256k1.
In Fp, elements are just numbers modulo p. Addition, Subtraction, Multiplication, and Division are all defined for this finite field.
In the EC Group, however, each element is a pair of elements in Fp, such as
(f1, f2). You can add and subtract these pairs to get different pairs, but the addition and subtraction has little to do with the addition and subtraction of elements of Fp (technically it uses those operations under the hood, but it's not direct addition. That would be pretty boring if
(f1, f2) +
(g1, g2) just gave you
Also note that since these pairs are a mathematical Group, rather than a field, there's no way to multiply two pairs. You may have seen the syntax
k*G before, but this is just shorthand for adding
G to itself
k is an integer rather than another element of the EC Group defined by secp256k1.
Additionally, if you look at the ECDSA algorithm, you will see that here the final elements are (r, s), but just because it is a pair does not mean it is a pair that lives on the secp256k1 curve! This is a pair of integers mod n (the curve order), as defined by the algorithm, not a point on the curve.
The premise of your question is wrong. In fact, Pieter said the opposite:
X and Y coordinates are numbers modulo p, the field size, which is around 2^256 - 2^32 for secp256k1. The value r and s in the signature however are modulo n, the group order, which is around 2^256 - 2^128.
If things still aren't making sense to you, I would recommend reading the Wikipedia ECDSA article and SEC1, and then asking a new, clearer question. It would be nice if your question included a brief definition of every number you are talking about (like Pieter's comment did) so we can make sure we are all talking about the same things.
The Wikipedia article has a short section explaining the correctness of the algorithm, and you would probably see that the math doesn't work if you try to change the way the signature is generated.
Also, I have written an implementation of ECDSA in Ruby that should be pretty easy to read and modify if you want to try out your ideas.
However, if I assume that you just accidentally switched P and N in your question, then my answer would be:
N is defined to be the the order of the secp256k1 group. So it is the number of distinct points in the group, including the infinity point. When you have a number like r or s that is between 0 and N - 1, it is actually the index of a particular point on the curve. It's like a private key (which are between 1 and N - 1), because you can use that number to generate secp256k1 point. The secp256k1 group is isomorphic to the group of integers modulo N: adding two such integers is equivalent to adding their corresponding secp256k1 points. The number 0 is equivalent to the infinity point.
So that should explain why it might be useful to have numbers in the algorithm that are between 0 and N - 1. We use the modulus operator to convert arbitrary integers to that range.
Of course, this doesn't explain why r and s in particular are modulo N, but if you work through the math in the "Correctness of the Algorithm Section" of the Wikipedia ECDSA article you would probably see that the math doesn't work if you change the way the signature is generated.