1

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 P.

Why is this so?

2
  • You should probably update your question to accurately state what Pieter Wuille said. His comment does not say that r, and s are modulo P, he specifically says: r and s in the signature however are modulo n, the group order.
    – morsecoder
    Aug 19 '15 at 20:09
  • I'll take a look now. I must've misspoke or misunderstood what he said Aug 20 '15 at 0:53
3

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 (f1+g1, f2+g2)).

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 times, 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.

1
  • but just because it is a pair does not mean it is a pair that lives on the secp256k1 curve! ! indeed! I was going to ask this question now, actually: see I was thinking that r,s was the x,y point on the curve: I actually was great at math but this stuff is so different from the algebra/calculus I was good with. Aug 20 '15 at 4:37
1

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.

Alternative answer assuming you switched P and N in your question

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.

1
  • Thanks mate, yeah, there was definite confusion on my part. I've edited the question title/content to reflect my intention, to wit, reversal p / n Aug 20 '15 at 4:25

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.