ECC - Point Addition/Point Multiplication

Question

So I have a very beginner-esque knowledge of ECDSA and I'm trying to write something in python to take a private key and output the public key (Basically from what I understand just trying to do the point multiplication k number of times on the basepoint) to get a better understanding.

My two main resources are the wikipedia page and this tutorial.

While trying to program point addition, I couldn't work out how to calculate the lambda on wikipedia under point addition (Which as I understand as the "slope"). What happens if you get numbers that don't divide nicely into each other in the fraction?

One example I found in the certicom tutorial (my second resource) is with the curve $(a = 0, b = 6$ over $\mathbb F_{23})$ doing a point doubling on $P=(7,2)$. It gives $\lambda = 147/4 \mod 23$, which it then simplifies to $\lambda = (9 * 6) \mod 23$ . What happens to turn $147 / 4$ into $9 * 6$?

Answer 1

The arithmetic done during a point addition is done using the addition and multiplication operations in the field; when you are using a prime field, that is equivalent to doing addition and multiplication modulo the prime (23 in this case).

Now, because we're doing the arithmetic modulo 23, we get to notice that $147 \equiv 9 \bmod 23$, and so those refer to the same field element; that is, in any field equation, we can replace one with the other without changing anything, or in other words $147 / 4 = 9 / 4$

Now, what does division mean in this case? Well, what $a / b = c$ means is that $a = b \times c$ (and since this is done within the field, this actually means $a = b \times c \bmod 23$). What we do is define the multiplication inverse $b^{-1}$ defined by $b \times b^{-1} = 1$, and so we have $a / b = a \times b^{-1}$. And, in this case, we have $4^{-1} = 6$ (because $4 \times 6 \equiv 1 \bmod 23$).

Combing these two, we get $147 / 4 = 9 \times 4^{-1} = 9 \times 6$

Now, the obvious question that you will ask is "how do we find multiplicative inverses"? After all, when dealing we numbers between 1 and 22, it's easy enough to find it via brute force, however how do we find these when we're dealing with modulii hundreds of bits in length?

The answer to that is the extended Euclidean Method; that gives an efficient way to find such inverses.

Now, I'll leave you with one last point; the references you give might give you some background as to why the point addition operation makes sense, however there are a bunch of optimizations they don't discuss (because they get in the way of explaining the basics). On reference (that doesn't talk about the why, but considerably more about the what) is this IETF RFC; the "projective coordinate" method of representing points turns out to be considerably more efficient than more naive methods.