Multiply point by scalar in elliptic curve group

445 Views Asked by At

I'm trying to understand how to multiply a point by a scalar to get a point in elliptic curve cryptography. Here's an example from my textbook.

The group is E257(0, -4). That's shorthand for y2 = x3 + 0 x - 4 (mod 257)

According to the book,

101(2, 2) = (197, 167)

How can I get from 101(2, 2) to (197, 167)? How can I get from cP to Q where c is a constant scalar and P and Q are points?

1

There are 1 best solutions below

1
On BEST ANSWER

What's multiplication? It's simply repeated addition. Instead of thinking of the problem as $101 \cdot (2, \, 2)$, where $101$ is meaningless within the context of the elliptic curve, think of the operation as $(2, \, 2) + (2, \, 2) + \underbrace{\ldots}_{98} + (2, \, 2)$.

Unfortunately, that seems like quite a lot of computations, and it is, especially in actual cryptographic contexts where the scalars become much larger. However, computing exponents in groups over finite fields can be done quite efficiently using exponentiation by squaring and its various extensions into other structures. This wikipedia page has a great run down of the different algorithms for efficient computation over elliptic curves.