1
$\begingroup$

I have been trying to understand the mathematics behind point multiplication. what i understand with ECC is that there is no division on ECC but multiplication, addition and negation. i recently figured out that using the inverse multiplier of 2 can be understood as division on ECC, here is a code on what i mean.

hex(0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1 * 42 % 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 )

the output of it is 0x15 (21 in decimal) since 42 is an even number the division happens smoothly.

in a case of odd number

hex(0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1 * 43 % 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 )

the output is 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20b6 which is the multiplicative inverse of 0x15 (21 in decimal )

how do i preform division without having to deal with the multiplicative inverse of the expected output.

and please forgive if my English is sloppy.

$\endgroup$
2

1 Answer 1

1
$\begingroup$

trying to understand the mathematics behind point multiplication

The question is not performing any point multiplication, or any elliptic curve operation. It's exclusively performing arithmetic modulo the (prime) number $n$ of elements in the common elliptic curve group secp256k1, that is $n=$0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141. Every other integer in the question is an integer modulo $n$, not an elliptic curve point.

To get from an integer $k$ to an elliptic curve point (which the question does not attempt), we can use so-called point multiplication, multiplying that integer and some elliptic curve point. If $G$ is an elliptic curve point (including but not limited to the conventional generator point for secp256k1), then $k$ times $G$ is $[k]G=\underbrace{G+G+\ldots+G}_{k\text{ terms}}$ where $+$ stands for the operation in the elliptic curve group known as point addition#.

The group has order $n$, thus $[n]G$ is the group's identity element, also known as point at infinity, noted $\mathcal O$ or $\infty$. If follows that $[k]G=[k\bmod n]G$, and $[a]G+[b]G=[a+b\bmod n]G$, and $[a]([b]G)=[a\,b\bmod n]G$, which is why arithmetic modulo $n$ is of interest in the question.

Notice that for large $k$ we can do better than performing $k$ point additions to compute $[k]G$: for example we can compute $[9]G$ by computing $[2]G=G+G$, $[4]G=[2]G+[2]G$, $[8]G=[4]G+[4]G$, $[9]G=[8]G+G$. This allows to efficiently compute $[k]G$ for very large integers $k$, by reducing $k$ modulo $n$, then performing less than $2\log_2n$ point additions.

Going from point $P$ to point $Q=P+P$ is a special case of point addition, called point doubling. That's also multiplying $P$ by $2$ to get $Q=[2]P$. Going back from $Q$ to $P$ is point halving (a less common operation for secp256k1 at least). That's also multiplying by the modular inverse of $2$ modulo $n$, that is multiplying by $u=(n+1)/2=$0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1.

If $Q=[42]G$, then halving $Q$ yields $P=[u]([42]G)=[u\times42\bmod n]G=[21]G$.

Similarly, if $Q=[43]G$, then halving $Q$ yields $P=[u]([43]G)=[u\times43\bmod n]G$. The question correctly computes $u\times43\bmod n=$0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20b6, which also is $(n+43)/2$. But the question is incorrect when stating that's the multiplicative inverse of 0x15.

how do I perform division

If that's in integers modulo $n$ (as in the question): in order to divide by $x$, multiply by the multiplicative inverse of $x$ modulo $n$. The question does just that for $x=2$, and successfully divides by $2$ first $42$ then $43$. Equivalently, to divide by $2$ an even integer modulo $n$, do just as for a normal integer. And to divide by $2$ an odd integer modulo odd $n$, add $n$ in the integers (thus yielding an even integer) then divide by $2$.

To divide an elliptic curve point $Q$ by integer $x$, compute $x'=x^{-1}\bmod n$, then compute $[x']Q$. We have an open question about how to perform that faster for $x=2$ and curves like secp256k1. Alternatively, if it's known $k$ and $G$ such that $Q=[k]G$, we can divide $k$ by $x$ modulo $n$ as in the above paragraph yielding $k'$, and the desired result is $[k']G$.


# The methods for point addition (which the question does not attempt) depend on the elliptic curve, it's underlying field, and the coordinate system. For secp256k1, it's used a prime field $\mathbb F_p$, thus arithmetic modulo the prime $p\ne n$ is involved. When using Cartesian coordinates, these standard formulas can be used.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.