Draft:Elliptical test

This is a draft article. It is a work in progress open to editing by anyone. Please ensure core content policies are met before publishing it as a live Wikipedia article. Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL Easy tools: Citation bot (help) | Advanced: Fix bare URLs · Article logs · Draft logs. Last edited by Kowal2701 (talk | contribs) 22 hours ago. (Update) Finished drafting? Submit for review

This article may incorporate text from a large language model, which is prohibited in Wikipedia articles. It may include hallucinated information, copyright violations, claims not verified in cited sources, original research, or fictitious references. Any such material should be removed. The reason given is: Wikipedia:AI noticeboard#User:004bvan (August 2026) (Learn how and when to remove this message)

This article has an unclear citation style. The references used may be made clearer with a different or consistent style of citation and footnoting. (June 2026) (Learn how and when to remove this message)

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.

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 ${\displaystyle 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:

${\displaystyle y^{2}=x^{3}+ax+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.

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

${\displaystyle y^{2}=x^{3}+ax+b{\pmod {p}}\,}$

where ${\displaystyle a,b\in \mathbb {Z} _{p}}$ are constants such that ${\displaystyle 4a^{3}+27b^{2}\neq 0{\pmod {p}}}$.

An addition operation is defined as follows: Suppose that

${\displaystyle P=(x_{1},y_{1})}$

and

${\displaystyle Q=(x_{2},y_{2})}$

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

${\displaystyle x_{3}=\lambda ^{2}-x_{1}-x_{2}}$,

${\displaystyle y_{3}=\lambda (x_{1}-x_{3})-y_{1}}$,

and

${\displaystyle \lambda ={\begin{cases}{\cfrac {y_{2}-y_{1}}{x_{2}-x_{1}}},&{\mbox{if }}P\neq Q\\{\cfrac {3x_{1}^{2}+a}{2y_{1}}},&{\mbox{if }}P=Q\end{cases}}}$

Finally, we define:

${\displaystyle P+{\mathcal {O}}={\mathcal {O}}+P=P\ \forall P\in E}$

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

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

${\displaystyle 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 ${\displaystyle \mathbb {Z} _{q}}$ where the discrete logarithm problem is intractable. In this case, letting ${\displaystyle \alpha }$ be a generator of the cyclic group (which can be any element of the group other than the identity ${\displaystyle {\mathcal {O}}}$), we can calculate the "powers" of ${\displaystyle \alpha }$ (which are written as multiples of ${\displaystyle \alpha }$ because the group operation is additive).

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

x	${\displaystyle x^{3}+x+6{\pmod {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 ${\displaystyle \mathbb {Z} _{13}}$. Considering the generator ${\displaystyle \alpha =(2,7)}$, we have:

${\displaystyle 2\alpha =(2,7)+(2,7)}$

${\displaystyle \lambda }$	${\displaystyle =(3\times 2^{2}+1)(2\times 7)^{-1}{\pmod {11}}}$
	${\displaystyle =2\times 3^{-1}{\pmod {11}}}$
	${\displaystyle =2\times 4{\pmod {11}}}$
	${\displaystyle =8}$

Then we have:

${\displaystyle x_{3}=8^{2}-2-2{\pmod {11}}=5}$

and

${\displaystyle y_{3}=8(2-5)-7{\pmod {11}}=2}$

Therefore, ${\displaystyle 2\alpha =(5,2)}$.

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.

• 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.

• Recommended Elliptic Curves for Government Use, NIST document (PDF file)
• Certicom press release regarding 109 bit ECC challenge
• Certicom Online ECC Tutorial
• Digital Signature Standard; includes info on ECDSA
• libecc: Open source ECC library
• Demo of elliptic curve point counting and domain parameter generation
• eccGnuPG: Experimental patch for GnuPG