the real purpose of mod inverse in bitcoin for creating public key

Question

I understand the function of mod inverse, however I really have no idea why this is important with process of creating public key. What does this function do, what value do we get it? Can someone explain it like to a 5 year old please.

Thanks

Answer 1

Basically, when creating a public key from a private key, what you're actually doing is multiplying some number by a point on the curve. In most cases, you will be multiplying some very large number by what's called a Generator point. It's just some point everybody knows and agrees upon.

Multiplying a number d mod n by a point G, or sometimes dG is defined intuitively as :

G + G + G + G... and so on d times.

If you remember how to do point addition, the process here is very much the same. To add two points A and B, with coordinates (A_x, A_y), (B_x, B_y), to a make a third point C with coordinates(C_x, C_y), point addition is defined as :

1. Find the slope (we'll call it slp) between the two points A and B
2. C_x = slp^2 - A_x - B_x mod p
3. C_y = slp * (A_x - C_x) - A_y mod p

And when adding the same point to itself, A + A (or 2*A when d == 2), point doubling is defined as:

1. Find the tangent (we'll call it tgt) to the curve at point A
2. C_x = tgt^2 - 2*A_x mod p
3. C_y = tgt * (A_x - C_x) - A_y mod p

Now, we only need to define how to find slp and tgt, and we can start creating public keys. A slope between two points should look familiar :

B_y - A_y
---------   mod p
B_x - A_x

And a tangent to the curve at a point is :

3 * (A_x)^2 + a
---------------   mod p
    2 * A_y

* the number a is a parameter of the curve. much like n and p.

You might already see the problem here, it's that division does not make a lot of sense in modular arithmetic. Instead we sort of multiply the numerator by the modular inverse of the denominator, which makes sense. To divide two numbers, we use the mod inverse function (which in turn might use the extended euclidean algorithm for example), so what we would end up calculating would be :

(B_y - A_y) * modinv(B_x - A_x) mod p for the slope slp and :

(3 * (A_x)^2 + a) * modinv(2 * A_y) mod p for the tangent line tgt.

And this is where we use mod inverse when creating public keys, or really when adding points.

Answer 2

The answer has to do with the math involved in elliptical curve cryptography, which is the basis for the cryptography used in Bitcoin. To start with, a Bitcoin private key is simply a very large random integer. To get the public key that corresponds with the private key, a pre-defined point on a pre-defined elliptical curve is multiplied by the private key (the large integer). This elliptical curve point multiplication is where the inverse mod comes in. The algorithm for elliptical curve point multiplication is several steps, and one of the steps involves an inverse mod operation. For the details, see this article by Andrea Corbellini, or take a look at this python script by Andrea Corbellini. If you follow the python script, you'll see exactly where the inverse mod operation fits in. Finally, the Bitcoin address is derived from the public key, by way of this procedure.