Mfcttrf

I understand that the discrete log problem is defined as

$G^y bmod p = x$

Speaking generally, $G$ here is a generator for the group zp*, where $G$ is able to generate each element in the group for a given prime modulus.

My question is, in the context of elliptic curve cryptography, is the group the entire set of points that lies on the curve being used?

Assuming this is correct, does the prime used for the modulus have to be larger or smaller than this group of points, or even reside in it?

Short answer: the definition you're using (and, in particular, the notation in it) is specific to multiplicative groups modulo $p$. It makes no sense for elliptic curves, or for most other kinds of groups over which the discrete logarithm problem can be defined. In particular, for elliptic curves, there is no prime modulus $p$.

(Well, OK, for the elliptic curves used in cryptography, there is a prime modulus involved in the definition of the finite field over which the elliptic curve itself is defined. The size of this prime depends on the type of finite field used — it can be anything from $2$ up to the size of the field itself — and is only very indirectly relevant to the hardness of the discrete logarithm problem.)

Longer answer: In mathematics, a group is simply any set $G$ equipped with some binary operator $star$ that satisfies the following properties:

1. 
   Closure: For every $a, b in G$, the value $a star b$ is defined and belongs to $G$.


2. 
   Associativity: The equation $(a star b) star c = a star (b star c)$ holds for every $a, b, c in G$.


3. 
   Identity: There exists an identity element $epsilon in G$ such that $epsilon star a = a star epsilon = a$ holds for every $a in G$.


4. 
   Invertibility: For every $a in G$ there exists another element $b in G$ (called the group inverse of $a$) such that $a star b = b star a = epsilon$.

If these properties seem fairly broad and abstract, that's because they are. Indeed, math is full of things that satisfy the definition of a group. For a few examples:

• The integers $Bbb Z = …, -2, -1, 0, 1, 2, …$ equipped with the operation $+$ (i.e. addition) form a group. The identity element is $0$ and the inverse of $a$ is $-a$.




• The positive rational numbers $Bbb Q^+$ equipped with the operation $·$ (i.e. multiplication) also form a group. The identity element is $1$, and the inverse of $a$ is $1/a$.




• For any set $S$, the set of invertible functions from $S$ to $S$ form a group, with function composition ($circ$) as the group operator. This group is known as the symmetric group of $S$.




• For any $n > 0$, the numbers $0, …, n-1$ equipped with the operation $+_n$ defined as $$a +_n b = (a + b) bmod n = begincasesa + b & textif a + b < n, \ a + b - n & textotherwise endcases$$ also form a group. The identity is still $0$, but the inverse of $a ne 0$ is now $n - a$. This group is isomorphic to the (additive) group of integers modulo $n$, and indeed is one way to define that group (although a more commonly used definition uses congruence classes instead).




• For any prime $p$, the numbers $1, …, p-1$ equipped with the operation $·_p$ defined as $$a ·_p b = ab bmod p = ab - kp,$$ where $k$ is the largest integer such that $kp le ab$, also form a group. The identity is $1$, and the inverse of any element $a$ can be calculated e.g. using the extended Euclidean algorithm. This group is isomorphic to (and again, under some definitions, the same as) the multiplicative group of integers modulo $p$.

There are, however, plenty of other ways to form groups as well. For example, for any elliptic curve, it's possible to define a binary operator that makes the set of points on the curve (including the "point at infinity") into a group. The definition is somewhat complicated, so I won't attempt to summarize it here, but it can be shown to satisfy all the properties required of a group.

Now, for any group $G$ with the group operation $star$, we can define an "exponentiation" operator $uparrow$ that maps a group element $g in G$ and a non-negative integer $k in Bbb N$ into the group element $$g uparrow k = underbraceg star g star … star g_k text times.$$ (In particular, $g uparrow 0$ is defined to be the group identity element $epsilon$.)

For any group element $g in G$, the set $$g^Bbb N = epsilon, g, g star g, g star g star g, … = k in Bbb N: g uparrow k$$ of powers of $g$ forms a subgroup of $G$. This is called the subgroup generated by $g$, and also written $langle g rangle$. (For some groups, it's even possible to find a $g in G$ such that $langle g rangle = G$, i.e. $g$ generates the entire group $G$.)

For a given generator $g in G$ and an arbitrary element $a$ of the subgroup $langle g rangle subset G$ generated by $g$, it's then possible to ask the question: what is the smallest (or even any) number $k in Bbb N$ such that $g uparrow k = a$? Such a number $k$ is known as the discrete logarithm of $a$ with respect to $g$.

Now, for some groups, computing the discrete logarithm is very easy. For example, if $G = Bbb Z$ is the additive group of integers, then $g uparrow k = kg$, and the discrete logarithm of $a$ with respect to $g ne 0$ is simply $a mathbin/ g$. The additive group of integers modulo $n$ is not much harder: calculating the discrete logarithm of $a$ there just requires solving the modular congruence $a equiv kg pmod n$, which can be done using the aforementioned extended Euclidean algorithm.

However, for other groups, no easy or efficient way of calculating discrete logarithms is known. The multiplicative groups of integers modulo large primes $p$ are one example of a class of such groups; elliptic curves (over a finite field) are another.

For cryptography, the main advantage of choosing elliptic curves over multiplicative groups of integers is that the most efficient known algorithms for finding discrete logarithms over elliptic curves are even less efficient than those for multiplicative groups of integers. In other words, this means that we can use smaller groups (and thus shorter keys etc.) for the same conjectured level of security.

Of course, technically, we don't know that the discrete logarithm problem is actually hard over either kind of groups, and that there isn't some magic algorithm to solve it efficiently that we just haven't found yet. But a lot of smart people have studied this problem for both kinds of groups, trying to find such an algorithm, and so far (at least as far as publicly available academic literature goes) they haven't really found one. And so far, of the two kinds of groups, elliptic curves seem to be the harder nut to crack.