I've been diving into the technical details of Bitcoin and learning Python for programming...
I created a basic program that lets you add points on the elliptic curve, like Q+Q or Q+G, and I also implemented operations like G-Q and X*G.
So, I set up a calculation for Q:1/2. When I tried it with 8G, I got back 4G, which makes sense.
But then I applied the same logic to 3G, expecting some kind of error since 1.5G isn't a valid point...
So, what am I missing here? How can I end up with results for 3G, 5G, or any odd multiple of G?
Thanks!
You need to calculate modinv(2G) and then multiply that by 3G to get half of it.
There is no such thing as fractions of a curve point, so "division" is emulated by using modinv and multiplication.
When you're calculating half of 3G like this, you are technically calculating (3*(p-2))G (mod p) because of Fermat's little theorem.
p may be a large number, but you don't have to actually add G that many times, you can convert 3*(p-2) into a bitwise (256-bits) representation, calculate G, 2G, 4G, 8G, 16G, 32G, 64G, 128G, 256G (which is 2^8G btw), 512G, ... (2^255)G and then using the distributive property of addition, add the parts together that make the coefficient equal to 3*(p-2).
You need to calculate modinv(2, N) and then multiply that by 3G to get half of it.
When you're calculating half of 3G like this, you are technically calculating (3*(2**(N-2)) mod N)G because of Fermat's little theorem.
Shortcut: 1/2 = modinv(2) = (N+1) / 2 because N is odd = 2**(-1) = 1 * 2**(-1) = 2**(N-1) * 2**(-1) = 2**(N-2) etc
My apologies, the private key operations are mod N, not mod P. Not sure why you had to copy half of my post though.
But if you're using libsecp256k1 then you don't actually have to worry about constructing an N or a P for modulus. The library will reduce the values automatically. All you have to do is use the secp256k1_fe types which you can find in the source code. Those functions are not exported though, so you're not going to find them in a compiled include header.
To observe that elliptic curve points do not have fractional values, which can cause confusion when attempting to divide or halve a point like 3G. In elliptic curve cryptography (ECC), halving a point is done through modular arithmetic, specifically the modular inverse .
For a point such as 3G, you would compute half of it by multiplying it by the modular inverse of 2 (mod N), where N is the curve order. This approach is based on Fermats Little Theorem, which allows for efficient computation of the inverse and modular operations .
In secp256k1, for instance, this can be done by calculating modinv(2) * 3G mod N, where N is the curves order. This ensures that operations remain within the field defined by the curve, ensuring consistency and avoiding errors that might arise from attempting to directly divide curve points .
By leveraging modular arithmetic, division of points on elliptic curves is avoided and operations stay within the correct field. This avoids potential pitfalls, while still allowing the manipulation of multiples of the base point, G.
How does the library "know" when to do regular inverse double 16G-->8G and when to do 7G---->SomethingG...
I am asking because every dot looks like any other dot. You do not know if multiplier*G is odd or even
That "something" is just "3.5". The choice of base point doesn't matter, if you can halve a point G, then you can halve every other point, in exactly the same way.
For example:
If you take "3.5*G", and double it, then you will get "7*G". If you want to halve a point, you can just multiply it by "1/2", which is equal to 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1 in secp256k1.
More than that: not only you can halve a point, but you can also get "one third", "one fifth", and "1/x" for any x-value, in range from 1 to 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140.
For example:
And then, if you try to multiply 034C7FF4F2BA8603998339C8E42675CEAC23EF2E9623FDB260B24B1C944A2EA1A9 by three, you will get G, as a result.
To better understand it, you can try some smaller elliptic curve, for example where "p=79, n=67, base=(1,18)". Then, it will be easier to understand, that "1/2=34" in case of this smaller curve, in exactly the same way, as "1/2=7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1" in case of secp256k1. Because "34*2=68=67+1". And that's how you can calculate the inversion: if you multiply "1/x" by "x", then you should get exactly "1", if you compute it modulo "n". It is that simple.
Exactly. And that's the reason, why elliptic curves are safe. In other case, if it would be possible to know, if a given distance between two points is "odd or even", then it would be trivial to break every possible private key.
(I was going to write a longer reply, but my iPhone screen glitched and I lost the reply force restarting. Sorry.)
Basically the types it uses are large enough to carry some overflow before it eventually runs out of bits.
BTW: the library is for point operations, so it only does mod P. There's another library, piggypiggy/fp256 on Github, for modular arithmetic with arbitrary modulus.
Don't get overwhelmed by the elliptic curve, first look at how it works from the private key perspective.
In decimal, if we have 3 divided by 2, the result is 1.5.
However, in the finite field that Secp256k1 uses, we don't use fractions. Instead, we find the modular inverse of 2 and multiply it by 3.
This operation is performed modulo n, which is the order of the field,
yielding: 57896044618658097711785492504343953926418782139537452191302581570759080747170