61

I'm reading up on ECC curves and on many of them I see an illustration that looks like this

enter image description here

What does the comparable curve in Bitcoin look like, or are all curves generally the same?

Improve this question
84

I'm afraid you won't like the answer.

These curves - including the secp256k1 curve, y2 = x3 + 7 - 'look' nice when evaluated in typical fields (like the real numbers), but secp256k1 is defined over the finite field Z2256-232-977, which means the X and Y coordinates are 256-bit integers modulo a large number. Curves using such coordinates do not have any concept of continuous lines.

I've tried to plot this curve over a similar but much smaller field, Z28+1. Coordinates extend from -128 to 128.

y² = x³ + 7 over Z257, -128 through 128

Note that even though it may not make sense geometrically anymore, it still has all properties you need. A line (which means, a group of points with equation ay + bx + c = 0) that 'intersects' 2 points of the curve, will intersect a third. Tangent again has no geometric interpretation anymore, but you can still symbolically compute a derivative of the equation in a given point, which will have the property of intersecting the curve in a second point.

To show you what you'd get if this were over the real numbers, here is a plot of the same curve equation for that case. Once with coordinates -128 through 128, once with -8 through 8.

y² = x³ + 7 over R, -128 through 128 y² = x³ + 7 over R, -8 through 8

Improve this answer
13
  • 4
    Yeah, Z modulo 2^256 - 2^32 - 977. Or written differently: the integers modulo 115792089237316195423570985008687907853269984665640564039457584007908834671663. In the simplified (first) plot above, I've used the numbers modulo 257 instead.
    – Pieter Wuille
    Feb 9 '14 at 19:50
  • 7
    Actually secp256k1 is defined over a Galois field, not a ring of integers modulo a prime. Now, it turns out that the secp256k1 field is a prime field and therefore isomorphic to a ring of integers modulo a prime, but this is not true for all ECDSA curves -- in fact, the "sectXXXyZ" curves (for which much faster hardware exists than the "secpXXXyZ" curves) cannot be described using rings of integers. See this page for an explanation of why every finite field has a GF representation but only the prime fields have a a Z/pZ representation: en.wikipedia.org/wiki/Finite_field#Statement
    – eldentyrell
    Mar 7 '14 at 3:53
  • 13
    Technically, every prime field is a Galois field. There indeed exist SEC curves defined over binary GF(2^n) Galois Fields, but this one is not. I'm not sure what you're trying to say here, the Galois representation of such a prime field is just GF(p^1).
    – Pieter Wuille
    Mar 7 '14 at 8:52
  • 3
    @makerofthings7 Those rendezvous points are just nonsense. You can come up with any set of 'special' points and transformations that make those easier to find, but there is no reason why they'd be more likely than others. We also don't actively try to avoid very low number for private keys for example - yes, those are easier to find IF you start by trying to crack those, but as they are not more likely than others to generate, why would you start there?
    – Pieter Wuille
    Jun 21 '14 at 18:22
  • 3
    @carlcrott You're right - there is one exception, namely straight vertical lines intersect in only 2 points. This is solved by adding a virtual point 'at infinity' to the curve, which serves as neutral element. The result is a mathematical group.
    – Pieter Wuille
    Sep 30 '17 at 22:59
25

you can check the Bitcoin doc https://en.bitcoin.it/wiki/Secp256k1 , there you will find some technical details about the secp256k1 used in bitcoin.

Below an illustration of the secp256k1's elliptic curve y2 = x3 + 7 over the real numbers (plot using www.desmos.com/calculator/ialhd71we3)

secp256k1 plot using www.desmos.com/calculator/ialhd71we3

in the context of a finite field Zp, which greatly changes the ECC appearance but not its underlying equation or special properties. the picture below represents the same equation in a finite field F17 (the x and y values are integers between 0 and 17).

Elliptic curve over F17

and here over F59 :

enter image description here

You will find an online opensource tool here https://cdn.rawgit.com/andreacorbellini/ecc/920b29a/interactive/modk-add.html which will help you to plot the graphe and to make addition or scalar multiplication on a EC. E.g plot over F97 with P+Q.

enter image description here

another good article to read about ECDSA in Bitcoin is https://github.com/bellaj/Bitcoin_Ethereum_docs/blob/6bffb47afae6a2a70903a26d215484cf8ff03859/ecdsa_bitcoin.pdf

secp256k1 was almost never used before Bitcoin became popular, but it is now gaining in popularity due to its several nice properties. Most commonly-used curves have a random structure, but secp256k1 was constructed in a special non-random way which allows for especially efficient computation. As a result, it is often more than 30% faster than other curves if the implementation is sufficiently optimized. Also, unlike the popular NIST curves, secp256k1's constants were selected in a predictable way, which significantly reduces the possibility that the curve's creator inserted any sort of backdoor into the curve.

Improve this answer
0
1

Since the underlying field for the elliptic curve for secp256k1 is Fp where p=2256-232-977, and since p is very close to a power of 2, it makes sense to try to graph the elliptic curve y2=x3+7 over the field of 2-adic numbers or related rings. Since we only have a finite amount of room to post here, let us simply graph the elliptic curve over a ring of the form Z2n. The ring of 2-adic integers is the inverse limit of the rings of the form Z2n. Therefore, the rings Z2n can be thought of as finite approximations for the ring of 2-adic integers. Now, we want to graph the elliptic curve in such a way so that two points which are near each other with respect to the 2-adic metric are also near each other on the graphical representation of the elliptic curve.

Let f:Z2n->{0,...,2n-1} be the function where f(a020+...+an-12n-1)= an-120+...+a02n-1 whenever a0,...,an-1 are all elements of the set {0,1}. In other words, f simply reverses the bits in the binary representation of an element of Z2n. Then the white pixels in the following graph are precisely at the points with coordinates (f(x),f(y)) where y2=x3+7 mod 2n where n=9. This picture is an approximation of the image of the elliptic curve over the ring of 2-adic integers.

enter image description here

Since the field of complex numbers is isomorphic to any ultraproduct of the algebraic closures of finite fields Fp by a non-principal ultrafilter on the set of all prime numbers, one should think of the finite fields as an approximation to the set of all complex numbers. Furthermore, the field of p-adic numbers embeds into the field of complex numbers, so one may think of the finite fields as objects that approximate a field that contains the field of p-adic numbers as a sub-field. Therefore, it is appropriate to use the graphs of the elliptic curve y2=x3+7 over the reals, complex numbers, or even the p-adic numbers as a visualization for the fields used in elliptic curve cryptography. One just needs to realize that one is working in a different field for visualization purposes.

Improve this answer

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.