0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If this notation seems unusual, just recall that when our group operation is $\cdot$, we often use exponention by a scalar: $g^n = g \cdot g \cdot \underbrace{\cdots}_{n-3} \cdot g$. So for groups where $+$ is the operation, we use multiplication by a scalar instead. $\endgroup$ – Henry Swanson Nov 3 '14 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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