Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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$?

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
great explanation! Thank you. –  Luis F Hernandez Jan 9 at 20:46
1  
An important alternative to euclid is exponentiation. Since you can reduce exponents modulo $\phi(p)=p-1$, computing $x^{-1}$ is equivalent to computing $x^{p-2}$. The big advantage of this technique is that the code has no branches depending on $x$, so it can be implemented in constant time, avoiding side channel attacks. –  CodesInChaos Jan 10 at 12:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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