Join Log in
Score:2
Ottotinne avatar Crypto

Modulo p in Elliptic Curve Cryptography

vn flag
Ottotinne

To carry out Elliptic Curve Cryptography between parties, are all elliptic curve equations considered to be in the form $\bmod p$?

For example, the $secp256k1$ Bitcoin curve of the equation $y^2=x^3+7$ uses $\bmod p$, where $p=2^{256}-2^{32}-977$.

328
0 + 0
Score:5
fgrieu avatar Crypto
ng flag
fgrieu

To carry out Elliptic Curve Cryptography between parties, are all elliptic curve equations considered to be in the form $\bmod p$?

Yes for secp256k1 when it comes to point coordinates, but not for every curve.

Elliptic Curves used for cryptography are operating with coordinates in a Galois Field $\mathbb F_q$. It must hold $q=p^m$ for some prime $p$, and $m\ge1$. The $\bmod p$ case corresponds to $m=1$, and is the most common and recognized (Ed25519, secp256k1, secp256r1 are examples). Another relatively common choice is $q=2^m$, see e.g. sec2v2 section 3. Other values are also used, e.g. $q=9767^{19}$ there.

$2^m$ has speed advantages in hardware or when multiplication of integers is costly due to carry propagation across bits. More generally, $p^m$ with a balance in size of $p$ and $m$ can ease parallel implementation.

Additionally: even for curves with coordinates in $\mathbb F_p$ with $p$ prime as secp256k1, some calculations involving scalars that multiply curve points (including calculations involving the private key) are carried modulo the curve's order, often noted $n$ and prime, and different of $p$.

0 + 0
poncho avatar
my flag
poncho
Yes, you can use Elliptic Curves defined over extension fields (which, for the audience, are fields $\mathbb{F}_{p^k}$ for $k > 1$); on the other hand, the secp256k1 curve he asked about, and for that matter, for the curves we currently use 99% of the time, are prime curves - that is, curves which we can do our computations modulo $p$
1
Reply
Score:3
kelalaka avatar Crypto
in flag
kelalaka

The prime in the definition of the curve Secp256k1

The prime $p$ is part of the curve design, analysis, and definition that defines the $\mathbb{F_P}$. If someone uses a different $p$ then they have different curves that need to be analyzed then published and distributed to communicate with this curve.

In order to communicate $p$, the curve equation ( here $(a,b)$), the base point $G$, the point at infinity, the curve order $n$, and co-factor $h$ are provided in the standard.

This is the sextuple $T = (p,a,b,G,n,h)$ and for Secp256k1 is;

  • ''p'' = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
  • = $2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1$

The curve $E: y^2 = x^3+ax+b$ over $\mathbb{F}_p$ is defined by:

  • ''a'' = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
  • ''b'' = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000007

The base point G in compressed form is:

  • ''G'' = 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 and in uncompressed form is:
  • ''G'' = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8 Finally the order ''n'' of ''G'' and the cofactor are:
  • ''n'' = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
  • ''h'' = 01

The $a,b,p,G$ are enough to communicate, however, there is no need to recalculate the rest.

A small example to demonstrate that they are completely different.

K = GF(19)
E = EllipticCurve(K,[0,7])
print(E)
print(E.order())
print(E.abelian_group())

then $n = 12$ and the curve group is isomorphic to $\mathbb{Z}_6 \oplus \mathbb{Z}_2$

K = GF(31)
E = EllipticCurve(K,[0,7])
print(E)
print(E.order())
print(E.abelian_group())

then $n = 21$ and the curve group is isomorphic to $\mathbb{Z}_{21}$

Of course, it may possible to find two tuples, $(p_1,a_1,b_1)$ and $(p_2,a_2,b_2)$ such that they have the same groups of points. This is not concern, one just need the standarized sextuple.

Are we restricted to $\mathbb{F}_p$?

If you are asking we should always use prime field $\mathbb{F}_p$ then the answer is no. Any finite field $\mathbb{F}_{p^m}$ is fine as long as secure and fast. See Fgrieu's answer for details.

Curve group order

Some curves like secp256k1 are designed to have prime order ( i.e. the number of points is prime). Others like Curve25519 and Curve448 don't have prime orders. This helps them to have Montgomery representation that has fast scalar multiplication by Montgomery Ladder. Others can have a less efficient Joyce ladder.

We don't want the curve order equal to $p$ in this case the curve is an anomalous curve and it is not secure.

The modulus in Scalar multiplication

The scalar multiplication $[k]P$ this actually means adding the $P$ itself $k$-times. More formally;

let $k \in \mathbb{N}\backslash\{ 0\}$

\begin{align} [k]:& E \to E\\ &P\mapsto [k]P=\underbrace{P+P+\cdots+P}_{\text{$k$ times}}.\end{align}

and by being identity $[0]P = \mathcal{O}$.

While calculating this we use the order of point $P$, if the curve has prime order like secp256k1 then all elements except the identity have the same prime order. We have this equality

$$[k]P = [k \bmod \text{ord}(P)]P$$

and we use $P$'s with prime order to mitigate attacks.

0 + 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.