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.

I found this example online:

In the elliptic curve group defined by $$y^2 = x^3 + 9x + 17 \quad \text{over } \mathbb{F}_{23},$$ what is the discrete logarithm $k$ of $Q = (4,5)$ to the base $P = (16,5)$?

One (naï­ve) way to find k is to compute multiples of $P$ until $Q$ is found. The first few multiples of $P$ are:

$P = (16,5), 2P = (20,20), 3P = (14,14), 4P = (19,20), 5P = (13,10)$, $6P = (7,3), 7P = (8,7), 8P = (12,17), 9P = (4,5)$

Since $9P = (4,5) = Q$, the discrete logarithm of $Q$ to the base $P$ is $k = 9$.

How do we get to these scalar multiples?

$P = (16,5), 2P = (20,20), 3P = (14,14), 4P = (19,20), 5P = (13,10)$, $6P = (7,3), 7P = (8,7), 8P = (12,17), 9P = (4,5)$

How can I check that $9·(16,5) = (4,5)$?

share|improve this question

4 Answers 4

up vote 5 down vote accepted

$\def\dbl{\mathrm{dbl}}$Okay, let's give the missing step between mikeazo's and poncho's answers.

I assume you've read mikeazo's answer to know how to add and double points.

Now, how do we get a scalar multiple of a point?

A simple algorithm is called "double-and-add", as it just does this.

In a simple example, we have $5 = 4 + 1 = 2·2 + 1$, and thus $5·P = (2·2+1)·P = 2·2·P + P$. So we calculate $P → \dbl(P) = 2·P → \dbl(\dbl(P)) = 4·P → 4·P + P=5·P$.

For your example of $200$, we have $200 = 128 + 64 + 8 = 2^7 +2^6+2^3$, and thus $200·P = 2^7·P + 2^6·P + 2^3·P$, which can be calculated as $\dbl(\dbl(\dbl(\dbl(\dbl(\dbl(\dbl(P))))))) + \dbl(\dbl(\dbl(\dbl(\dbl(\dbl(P)))))) + \dbl(\dbl(\dbl(P)))$. (Of course, you would calculate the common sub-terms only once.)

Alternatively, we can use the distributive law to write it this way: $200·P = 2·2·(2·2·2·(2·P + P) + P)$.

(Note that we used the binary form of the scalar factor here to decide when to add and when not to add.)

Here are two general forms of this algorithm to calculate $d·P$, when $d$ has the binary form $d_kd_{k-1}\dots d_1d_0$ (assuming d_k = 1):

Starting from the small-endian bits:

Q := 0
R := P
for i = 0 .. k:
   R = double(K)
   if(d_i = 1)
      Q = add(Q, R)
return Q

Starting from the big-endian bits:

Q := 0
for i = k ... 0:
   Q := double(Q)
   if(d_i = 1)
      Q := add(Q, P)
return Q

Note that this is actually the same algorithm you are using for modular (or other) exponentiation, just with the operations square and multiply instead (and then usually named square-and-multiply).

Also, this trivial implementation is quite vulnerable to a power analysis attack, if implemented on a smart card, as doubling and adding doesn't use quite the same amount of power, and the adding is only done when a bit in the (usually secret) exponent is set. There are measures against this, and also a bit more efficient point multiplication algorithms – any book about elliptic curves should mention some of them.

share|improve this answer
    
Yes, this is what I want, so do you mean to calculate 200P, first I convert it into binary to get 2^7 +2^6 +2^3, then next form this dbl(dbl(dbl(dbl(dbl(dbl(dbl(P)))))))+dbl(dbl(dbl(dbl(dbl(dbl(P))))))+dbl(dbl(dbl‌​(P)), until this part I can understand. Thanks for the example, and then next I need to calculate dbl(P) then dbl(dbl(P)) again untill dbl(dbl(dbl(dbl(dbl(dbl(dbl(P))))))) seven times? –  Keith Lau Si Keit Oct 1 '12 at 3:02
1  
Jes, the number of "doublings" is the exponent of your binary number - for $2^7·P$ you'll have to double $P$ seven times. –  Paŭlo Ebermann Oct 1 '12 at 8:51
    
There is a way call square and multiply can it be used to solve the question? –  Keith Lau Si Keit Oct 2 '12 at 5:52
    
@KeithLauSiKeit: square-and-multiply is an "exponentiation" algorithm (from squaring and multiplication), you need an multiplication algorithm (from adding and doubling). But as I mentioned (I'll edit to make this more clear), double-and-add is actually the same as square-and-multiply if you swap the names of the operations. –  Paŭlo Ebermann Oct 2 '12 at 16:53

I am surprised by the mixture of everything. the simple question is : how to get 200P. There is a very old binary algorithm, which can be used different ways

  • double and add : this is multiplication

  • square and multiply : this is exponentiation

  • square and add : this is mandelbrot sequence, well known in fractals. Or the trick for the primality test of a mersenne number.

  • divide and add : this is linear inverse congruential generator.

  • And so on, the list is infinite.

The logic is always the same with these 2 operations combined, and the geometric construction is at least 2000 years old.

200 = 128 + 64 + 8 = (2 + 1) * 64 + 8 = ((2 + 1) * 8 + 1) * 8

run it from left to right

For multiplication

200 * x = ((2 * x + x) * 2 * 2 * 2 + x ) * 2 * 2 * 2

this is the sequence dbl, add, dbl, dbl, dbl, add, dbl, dbl, dbl. done.

For exponentiation (** is the symbol for raising to a power)

x ** 200 = ((x ** 2 * x) ** 2 ** 2 ** 2 * x ) ** 2 ** 2 ** 2

this is the sequence squ, mul, squ, squ, squ, mul, squ, squ, squ. done.

And so on.

In any field, ring, group, .... you can define operators and elements like multiplication, addition, identity, .... . This is valid for points on an elliptic curve , which you can add to each other. Adding a point to itself is a doubling operation. and then you need that 2000-years-old binary trick to create a multiplication from the double and add.

share|improve this answer
    
Ummm, "double and add" and "square and multiply" are two ways to say the same time. Also, what's a "mandelbrot sequence" or a "divide and add" (at least, in terms of working with a group operation?). –  poncho Jul 15 at 17:00

It's not exactly clear what you're asking; whether how to do point addition (Mike covered that), how to do scalar point multiplication (e.g. how do you compute 9G=G+G+G+G+G+G+G+G+G) or how you can compute discrete logs (e.g. given points G and Q, find k such that kG = Q). My answer is applicable if you're asking the latter.

One easy-to-understand method for computing discrete logs in $O(\sqrt{N})$ time is Big-Step-Little-Step. Here's how it would work out in this case.

We know that this particular curve has 32 points on it (counting the point at infinity); if we are using a realistic sized curve (rather than this toy example), we can know this via a point-counting algorithm.

Now, if the number of points on the curve is smooth (that is, is composed of small factors), there are quite efficient ways to compute discrete logs; we never use an elliptic curve with a smooth group order, specifically because they're cryptographically weak. Hence, I'll ignore those methods, and talk about a method that applies to all curves.

So, we know that the discrete log is a value between 0 and 31. We select a size of the bigstep $b \approx \sqrt{32}$; we'll pick the value 6.

So, we compute the big steps, compute $6iG$ for various integers $i$ until $6i \ge 31$:

$0G = 0$

$6G = (7,3)$

$12G = (18,10)$

$18G = (10,16)$

$24G = (12, 6)$

$30G = (20, 3)$

Then, we compute the little steps, that is $Q - iG$ of $0 \le i < b$;

$Q - 0G = (4, 5)$

$Q - 1G = (12, 17)$

$Q - 2G = (8, 7)$

$Q - 3G = (7, 3)$

$Q - 4G = (13, 10)$

$Q - 5G = (19, 20)$

Then, we scan the two lists to search for a point in common. Here we see that both $6G$ and $Q - 3G$ is the point $(7, 3)$, and hence $6G = Q - 3G$, or $Q = 9G$

Now, in this toy example, this is actually more work than the naive method. However, if we scale the size of the group up, we quickly come to a point where this method is strictly faster.

share|improve this answer
    
I don't understand how to do scalar multiplication said above example, P = (16,5) I know using doubling to get 2P value. But when doing encryption, given random value k said 200, how to count kP= (x,y). Like your example, how did you get all (7,3) (18,10) (10,16) ... this is the part I can't figure out. –  Keith Lau Si Keit Sep 30 '12 at 11:01

Graphically, addition looks like this for two distinct points ($P+Q=R$):

enter image description here

For doing $P+P=2P$, instead you draw a line tangent to $P$. Find where it intersects, and reflect about the $x$ axis. Like this:

enter image description here

Mathematically this is done by finding the line tangent to $P$, finding where it intersects and reflecting about $x$. The trick is to remember to do your math in the given field.

So, in your example the slope tangent at $P$ is $s=(3(16)^2+9)\cdot(2\cdot 5)^{-1}\bmod{23} = 11$. The $x$ coordinate for $2P$ is $s^2-2(16)\bmod{23}=20$.

The $y$ coordinate is $-5 + s \cdot (16-20)\bmod{23} = 20$.

A good applet to see what is going on can be found here. Once you have 2P, you add P to get 3P, and so on.

share|improve this answer
    
I know how to count 2P but if said the k is big said 200P ? –  Keith Lau Si Keit Sep 29 '12 at 16:01
    
Nice! But I'm still confused with this point addition/multiplication. Does 2P+2P = 3P+P = 4P ? Or is there only one way to calculate any specific point? –  notthetup Nov 1 '12 at 11:30
1  
$2P+2P=3P+P=4P$ is correct. –  mikeazo Nov 1 '12 at 11:56

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.