Number Theoretical Ciphers - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 40

Furthermore, we may not have any way of securely communicating a key! Diffie and Hellman devised a way
for two parties to securely acquire the same key over an insecure channel, where anyone could be listening.
Let's say we have two parties communicating, A and B.
1. A and B agree on a finite field F , as well as a generator g, which are both publicly known.
2. A picks a secret integer a, and B picks a secret integer b.
3. A sends to B (in the open) the number g a computed in F.
4. B sends to A (in the open) the number g b computed in F.
At the end of this exchange, A can compute ( g) b = g ab in F ,and B can compute (g b ) a = g ab in F as well, so they
both share a secret g ab known only to each other. Anybody listening would know g, F, g a ,and g b , but thanks to
the discrete logarithm being difficult, knowledge of g a and g b does not let any listener easily derive either a or
b, and the properties of the fields do not allow one to use both g a and g b to easily calculate g ab either.
2.6 Elliptic Curves 3
There has been a significant trend in cryptography over the last few years toward elliptic curve-based al-
gorithms,andawayfromnormal(integer-based)numbertheoreticalgorithms.Usingellipticcurvecryptography
gives usone primary advantage over the previous number theoretic methods: We can use much smaller numbers
(by an order of magnitude) and achieve the same level of security. Smaller numbers mean less to transmit, and
fewer operations to manipulate them. For example, 2048- and 4096-bit moduli are common for RSA, compared
to the 256- and 384-bits common for the size of prime number p of the underlying field in elliptic curves.
This will be a very elementary go-through of very basic elliptic curve theory. For a more thorough look, see
References [10], [11], and [13].
Broadly speaking, elliptic curves are sets of points formed by equations that are quadratic in the y -term and
cubic in the x -term. These equations, in the most general form, are represented by the points (x, y) that satisfy
the general equation:
ax 3 + bx 2 y + cx 2 + dxy 2 + exy + fx + gy 3 + hy 2 + iy + j = 0
where x and y are variables ranging over fields (usually the rationals, the reals, complex numbers, or a finite
field), and a, b, ... , j are elements of the same field. However, as will be explained shortly, there is always an
additional point, often called the point at infinity, denoted ∞ [14].
We are usually not concerned with every type of elliptic curve. We want curves that are easier to manipulate,
sincewewillbeusingthemforcryptographicandcryptanalytic algorithms;theprecedingformisabitunwieldy
for easy use. As such, we are concerned with elliptic curves that are simplified in what is called the Weierstrass
form of an elliptic curve [13]:
y 2 = x 3 + ax + b
Not all elliptic curves in all fields can be represented in this form, but the simplicity of this form makes up for
it. The restriction the form makes on the underlying field is that the field cannot have a characteristic of 2 or 3,
because in those fields, division by 2 or 3, respectively, is equivalent to dividing by 0 in normal arithmetic, and
we need to divide by 2 and 3 to construct the Weierstrass form.
Figure 2-4 shows some elliptic curves plotted in . Note how there are three different shapes of these elliptic
curves. The shape of the curve is dependent on the values of a and b. If 4a 3 + 27b 2 > 0, then the curve will be