8
$\begingroup$

Im currently playing around with ECC, in particular the ECDSA scheme on a brainpool P256R1 curve. While implementing the signature verification function, I've stumbled upon a few problems.

So far I've understood that there's a prime $p$ and the order of the elliptic curve $n$ (such that $n * G = \mathcal{O}$).

For the modular arithmetic functions inside my ECDSA verification function we have to use the group order $n$. But for our elliptic curve functions such as point addition and point doubling we need to use $p$. I was wondering why its the order for curve operations and the prime for the other in order to make the system work.

$\endgroup$
0

1 Answer 1

10
$\begingroup$

A possible analogy is two layers in a communication protocol, with $p$ and $n$ the maximum packet payload for the lower and upper layer. They need not be equal (in communication protocols, typically due to overhead added by the upper layer, reducing its maximum packet payload compared that of the lower layer). We use limit $p$ or $n$ depending on if we deal with payload of the lower or higher layer.

In the question's example of ECDSA with a prime field, the lower layer is the base field $(\mathbb Z/p\mathbb Z,+,\cdot)$ with $p$ prime, where $+$ is modular addition modulo $p$, and $\cdot$ is modular multiplication modulo $p$.

The higher layer is the elliptic curve group $(E,+)$ (or a subset of that generated by a particular $G$, but for the curve considered there is no such restriction and I discard it for simplicity). Elements of $E$ are points of the elliptic curve (when using rational coordinates: defined by two coordinates in the base field matching the curve's equation, or as the neutral element), and $+$ is point addition. While doing point addition, we are dealing with coordinates, which belong to the base field, and thus must use $p$ as the modulus.

The order $n$ of $E$ depends on the curve, and there's no reason that it would be exactly $p$. One way to look at it is that we are starting from $p^2$ pairs of coordinates, filtering these per the curve's equation, and adding the neutral element. We can define scalar multiplication $\times$ on that group, and the natural modulus for the scalar multiplicand is the order of the group, that is $n$, rather than $p$.

$\endgroup$
2
  • 1
    $\begingroup$ it's probably easier to say "use n when dealing with private key operations", "use p when dealing with the x/y value operations" $\endgroup$ May 30 at 16:33
  • 1
    $\begingroup$ @Erik Aronesty: that's a good way to decide the right modulus to use. But that's already stated in the last paragraph of the question, which asks why. $\endgroup$
    – fgrieu
    May 30 at 17:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.