Discrete logarithms on elliptic curves

In many examples of attacks on public key cryptography, examples of the form $$a ^ x = b$$ are used, but I can not understand the correlation between this and the multiplication of the generator point of the elliptic curve $$Q = xP$$.

I have already read a lot, but still I can not understand this. In the case $$a ^ x = b$$, this is one number, and for an elliptic curve it is a point with coordinates $$(x, y)$$. Please explain the difference simply, as you would to a child.

• ObXKCD: xkcd.com/1364 – poncho Aug 6 at 15:26
• A number has one dimension whereas a point on EC has two dimensions. There is no multiplication on EC. In $a^x$, we have a multiplicative group and in EC we have additive. – kelalaka Aug 6 at 18:34
• thanks for the clear answer! – vbujym Aug 7 at 10:48

Well, to explain that, I have to touch lightly on what a group is, and how both operations involve a group.

A group [1] is a set of values, along with an operation (which I'll denote as $$\odot$$); with this operation, we take two values, smash them together, and generate a third one [2]. One example of a group are the numbers, along with the operation of addition $$+$$; we can take the values 1 and 3, and smash them together $$1+3$$ to get the value 4.

Now, one thing we can ask is 'if we start with a value $$a$$, how many $$a$$s do we need to smash together before we get the value we're looking for $$b$$'. That is, if we compute:

$$\underbrace{a \odot a \odot a \odot … \odot a}_{\text{x times}}$$

how large does $$x$$ need to be before we get the value $$b$$?

This is called the discrete log problem.

With some groups, this is an easy problem. For example, in the numbers and addition group I mentioned earlier, if we start with $$7$$, and ask "how many 7's do we need to add together before we get to 63, it's easy to see that the answer is 9.

Now, it turns out that both problems you mentioned are like this.

For the problem $$a^x = b$$, the $$\odot$$ operation is the act of taking two values, multiplying them together, and then taking the result modulo p (typically a large prime). Because $$a^x = \underbrace{a \times a \times a \times … \times a}_{\text{x times}}$$, this is precisely the same form as the generic problem (and in fact is why we call the generic problem the 'discrete log' problem)

For Elliptic Curves and the problem $$xP = Q$$, the $$\odot$$ operation is taking two values where are 'elliptic curve points' [3], and performing an 'elliptic curve addition' to generate a third point. That is, the problem is finding $$x$$ where $$xP = \underbrace{P + P + P + … + P}_{\text{x times}}$$ is the elliptic curve point $$Q$$; hence it is also in that same form.

Now, if the two problems are the same at the abstract level, why do we write them differently? Well, it just comes down to notation. For modular multiplication, we always write the operation as if it were multiplication, and so the obvious way to write a large number of multiplications is to write it as an exponentiation:

$$\underbrace{a \times a \times a \times … \times a}_{\text{x times}} = a^x$$

For Elliptic curves, we typically write the operation as if it were addition, and the obvious way to write a large number of additions is to write it as if we were doing a multiplication:

$$\underbrace{P + P + P + … + P}_{\text{x times}} = xP$$

This difference is just in the way we generally talk about these two grous - it has no impact on what we do with them.

[1]: That's a term that mathematicians use; don't worry, I would use that much more arcane terminology

[2]: Actually, there are a bunch of other things we require of a group - I will not mention them here.

[3]: I won't go into detail here about what an elliptic curve point is.

• I was confused by the fact that when calculating the degree of a number modulo a large prime number, we end up with a number, and in the group of points of an elliptic curve we get a map of this number in the form of x-coordinates and y-coordinates. a^x=b mod p, on ec: bP=Q, here b is the number of addition of points. It true? – vbujym Aug 7 at 10:58
• @vbujym: you're thinking about this the wrong way. In both cases, you get a value, that is, one of the members of the group. In the modular multiplication case, you get a value (which happens to be something between 1 and $p-1$), in the elliptic curve case, you get a value (which happens to be an elliptic curve point) – poncho Aug 7 at 11:33
• yes, I get the value of X in both versions, but in the case of an elliptic curve, X is modulo the order of the group(#E(Fp)) and you also need to multiply by the generator of the cyclic group to get a point on the curve, let's say there is a point Q(x,y mod p), it's not an x, but a point . – vbujym Aug 7 at 13:52
• Taking this opportunity, I would like to ask you if there is an algorithm for multiplying a point by a point without using X? For example, there are Q(x1,y1) and Z(x2,y2), calculate Q * Z = R? I still know how to get the point corresponding to any 256 bit number for 32 additions. – vbujym Aug 7 at 14:04
• @vbujym: no, there's no meaningful way to "multiply" two points, and obtain a third point (and keep the nice algebraic properties that we associate with multiplication - pairing operations come close, but what they generate is not a point). Also, I assume your "get the point with 32 additions" algorithm uses a fairly large precomputed table; the obvious one uses circa 8,000 points... – poncho Aug 7 at 15:06

The two main examples of discrete logarithms in crypto are

• the multiplicative group of a finite field: the integers modulo a prime $$p$$ with the multiplication
• elliptic curves: points with an operation to add them

For the first one, we look at the subgroup generated by a number $$g$$ called the generator : $$1, g, g^2, \ldots, g^{q-1},$$ and $$g^q = 1$$, so there are $$q$$ elements in this subgroup. Take a random element $$h$$ in this subgroup, then there exists an integer $$0 \leq x < q$$ such that $$h = g^x$$, called the discrete logarithm of $$h$$ in base $$g$$.

An elliptic curve is (most of the time) defined by an equation $$y^2 = f(x)$$ with $$f$$ a degree $$3$$ polynomial. The variables $$x$$, $$y$$ are (most of the time) integers modulo a prime $$p$$. The points of the curve are all $$(x,y)$$ that satisfy the equation. And since coordinates are integers modulo a prime $$p$$, there can't be an infinite amount of them. An operations exist on the curve: from two points $$P_1$$ and $$P_2$$ we can construct a third point $$P_3$$. The same way you can take two integers $$g_1$$ and $$g_2$$ modulo a prime $$p$$ and compute $$g_1 \times g_2$$, the operation on the elliptic curve will satisfy the same kind of properties but we call it the addition, because the additive notation is nicer. So we have $$P_1 + P_2 = P_3$$. And if you repeat the addition $$P_1 + P_1 + P_1$$ you can write $$3P_1$$.

Now let's take a point $$P$$ on the curve and we compute $$\mathcal O, P, 2P, 3P, \ldots (q-1)P,$$ and $$qP=\mathcal O$$ which is the zero for elliptic curves, called the infinity point ($$P + \mathcal O = \mathcal O + P = P$$). Those $$q$$ points is a subgroup generated by $$P$$. If we take a point $$Q$$ in it, there exists an integer $$0 \leq x < q$$ such that $$Q = xP$$.

So, there is nothing different between those two examples, except how we represent things and how the operation is described.

• thanks for the clean answer – vbujym Aug 7 at 11:06