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.
Bitcoin Stack Exchange is a question and answer site for Bitcoin crypto-currency enthusiasts. It only takes a minute to sign up.Sign up to join this community
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
If you remember how to do point addition, the process here is very much the same.
To add two points
B, with coordinates
(A_x, A_y), (B_x, B_y), to a make a third point
C with coordinates
point addition is defined as :
slp) between the two points
C_x = slp^2 - A_x - B_x mod p
C_y = slp * (A_x - C_x) - A_y mod p
And when adding the same point to itself,
A + A (or
d == 2), point doubling is defined as:
tgt) to the curve at point
C_x = tgt^2 - 2*A_x mod p
C_y = tgt * (A_x - C_x) - A_y mod p
Now, we only need to define how to find
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
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
And this is where we use mod inverse when creating public keys, or really when adding points.
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.