Elliptical test

Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the mathematics of elliptic curves. Proponents argue that ECC can be faster and use shorter keys than older methods—such as RSA—while providing an equivalent level of security. The use of elliptic curves in cryptography was proposed independently by Neal Koblitz and Victor Miller in 1985.

Introduction

Asymmetric or public-key cryptography systems use two distinct keys: one of them is public, and the other is private. Possession of the public key does not provide enough information to determine the private key. These types of systems are based on the difficulty of finding the solution to certain mathematical problems. One of these problems is the so-called discrete logarithm. Finding the value of b given the equation $a^{b} = c$ , when a and c are known values, can be a problem of exponential complexity for certain large finite groups, whereas the inverse problem, discrete exponentiation, can be evaluated efficiently using, for example, binary exponentiation.

An elliptic curve is a plane curve defined by an equation of the form:

$y^{2} = x^{3} + a x + b$

The set of points G that make up the curve (i.e., all solutions to the equation plus a point O, called the point at infinity) together with an addition operation "+", forms an abelian group. If the coordinates x and y are chosen from a finite field, we obtain a finite abelian group. The discrete logarithm problem over this set of points (ECDLP) is believed to be much more difficult to solve than the corresponding problem over finite fields (DLP). As a result, key lengths in elliptic-curve cryptography can be shorter while maintaining a comparable level of security.

Mathematical Introduction

Let $p > 3$ be a prime number. The elliptic curve E $y^{2} = x^{3} + a x + b$ over $ℤ_{p}$ is the set of solutions $(x, y) \in ℤ_{p} \times ℤ_{p}$ to the congruence:

$y^{2} = x^{3} + a x + b (\mod p)$

where $a, b \in ℤ_{p}$ are constants such that $4 a^{3} + 27 b^{2} \neq 0 (\mod p)$ .

An addition operation is defined as follows: Suppose that

P = (x_{1}, y_{1})

and

Q = (x_{2}, y_{2})

are points on E and $𝒪$ is the point at infinity. If $x_{2} = x_{1}$ and $y_{2} = - y_{1}$ , then $P + Q = 𝒪$ ; otherwise, $P + Q = (x_{3}, y_{3})$ , where:

x_{3} = λ^{2} - x_{1} - x_{2}

,

y_{3} = λ (x_{1} - x_{3}) - y_{1}

,

and

λ = {\begin{cases} \frac{y_{2} - y_{1}}{x_{2} - x_{1}}, & if P \neq Q \\ \frac{3 x_{1}^{2} + a}{2 y_{1}}, & if P = Q \end{cases}

Finally, we define:

P + 𝒪 = 𝒪 + P = P \forall P \in E

With this, it can be shown that E is an abelian group with identity element $𝒪$ . It is worth noting that the inverse of $(x, y)$ (written as $- (x, y)$ because the operation is additive) is $(x, - y)$ for all $(x, y) \in E$ .

According to Hasse's theorem, the number of points $# E$ that E contains is close to p. More precisely, the following inequality is satisfied:

p + 1 - 2 \sqrt{p} \leq # E \leq p + 1 + 2 \sqrt{p}

Since any group of prime order is cyclic, what is required is to find a subgroup of E of order q (with q prime) to establish an isomorphism with $ℤ_{q}$ where the discrete logarithm problem is intractable. In this case, letting $α$ be a generator of the cyclic group (which can be any element of the group other than the identity $𝒪$ ), we can calculate the "powers" of $α$ (which are written as multiples of $α$ because the group operation is additive).

Example

Let E be the elliptic curve $y^{2} = x^{3} + x + 6$ over $ℤ_{11}$ . The points on E are calculated by checking the possible values of $x \in ℤ_{11}$ and then verifying if $z = x^{3} + x + 6 (\mod 11)$ is a quadratic residue. The values are tabulated in the table below:

x	$x^{3} + x + 6 (\mod 11)$	y
0	6
1	8
2	5	4, 7
3	3	5, 6
4	8
5	4	2, 9
6	8
7	4	2, 9
8	9	3, 8
9	7
10	4	2, 9

Since E has 13 points, it follows that it is cyclic and isomorphic to $ℤ_{13}$ . Considering the generator $α = (2, 7)$ , we have:

2 α = (2, 7) + (2, 7)

$λ$	$= (3 \times 2^{2} + 1) (2 \times 7)^{- 1} (\mod 11)$
	$= 2 \times 3^{- 1} (\mod 11)$
	$= 2 \times 4 (\mod 11)$
	$= 8$

Then we have:

x_{3} = 8^{2} - 2 - 2 (\mod 11) = 5

and

y_{3} = 8 (2 - 5) - 7 (\mod 11) = 2

Therefore, $2 α = (5, 2)$ .

Use in cryptography

For cryptographic use, a specific and publicly known base point G is chosen to be used with the curve E(q). A random integer k is selected as the private key, and the value P = kG is published as the public key (note that the assumed difficulty of the ECDLP implies that k is hard to derive from P). If Alice and Bob have private keys k_A and k_B, and public keys P_A and P_B, then Alice can calculate k_AP_B = (k_Ak_B)G, and Bob can obtain the same value since k_BP_A = (k_Bk_A)G.

This allows establishing a shared secret that both Alice and Bob can easily compute, but which is highly difficult for a third party to derive. Furthermore, Bob does not learn anything new about k_A during this transaction, so Alice's key remains private.

The methods used in practice to encrypt messages based on this shared secret consist of adaptations of older discrete logarithm cryptosystems originally designed for other groups. These include Diffie–Hellman, ElGamal, and the DSA (specifically ECDSA).

Performing the operations required to execute this system is slower than for a factorization or discrete logarithm system modulo an integer of the same size. However, proponents of ECC believe that the ECDLP is significantly more difficult than integer factorization or the DLP, allowing the same level of security to be achieved with much shorter key lengths using ECC—to the point where it can actually be faster than, for example, RSA. Published results tend to confirm this, though some experts remain skeptical.

ECC has been widely recognized as the strongest algorithm for a given key length, making it highly useful for links with very limited bandwidth requirements.

NIST and ANSI X9 have established minimum key size requirements of 1024 bits for RSA and DSA and 160 bits for ECC, corresponding to an 80-bit symmetric security level. NIST has published a list of recommended elliptic curves for five different key sizes (corresponding to symmetric security levels of 80, 112, 128, 192, and 256 bits). In general, ECC over a binary group requires an asymmetric key that is twice the size of the corresponding symmetric key.

Certicom is the leading commercial firm in ECC; the organization holds over 130 patents and licensed technology to the National Security Agency (NSA) for $25 million. Certicom has also sponsored several cryptographic challenges for ECC. The most complex challenge solved to date is a 109-bit key, which was broken by a team of researchers in early 2003. The team that cracked the key used a massive parallel attack based on the birthday attack, employing over 10,000 Pentium-class PCs running continuously for 540 days. It is estimated that the minimum recommended key length for ECC (163 bits) would require 10⁸ times the resources used to solve the 109-bit challenge.

References

Neal Koblitz, "Elliptic curve cryptosystems", Mathematics of Computation 48, 1987, pp. 203–209.
V. Miller, "Use of elliptic curves in cryptography", CRYPTO 85, 1985.
Blake, Seroussi, Smart, "Elliptic Curves in Cryptography", Cambridge University Press, 1999.
Hankerson, Menezes, Vanstone: "Guide to Elliptic Curve Cryptography", Springer-Verlag, 2004.

External links

This article "Elliptical test" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Elliptical test. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.