Difference between revisions of "Walther MA271 Fall2020 topic12" - Rhea

Latest revision as of 16:46, 30 May 2021

A Brief Overview of Elliptical Curves and their Relevance

author: Henry Eifert

1.0 Introduction

Elliptical curves are curves described by the equation y² = x³ + Ax + B with distinct roots (which is to say Δ = 4A³ + 27B² is nonzero). An additional point Ό at infinity is included in the curve. The set of points on an elliptical curve combined with a group operation (to be explained later) will form a group in any field. Elliptical curves can look something like the below image in E(R), but appearances vary wildly depending on which field the curve is through. Elliptical curves are found all over mathematics, physics, and computer science, with applications spanning complex analysis, number theory, cryptography, and string theory.

from math.brown.edu

2.0 The Group Law

Group laws, or group operations, combine two elements from a set to make a third element that satisfies the four group axioms. These axioms are the same for any group and include closure, associativity, identity, and invertibility. When an operation satisfies all four axioms, it meets the requirements to be a group operation.

• Closure - all outputs of the operation produce an element within the same set as its inputs,
• Associativity - the order in which operations are applied does not affect the final output
• Identity - An element exists in the set such that A <operation> (element) = A. For example, A + 0 = A.
• Invertibility - A generalization of negation. Inverses cancel out other elements in the set when the group operation is applied to them.

The group law for elliptical curves allows us to add two points P and Q on an elliptical curve E. This operation has a fairly straightforward geometric explanation. In order to calculate P + Q, draw a line from P to Q and find the point where it intersects E a third time. Call this point R. The point on E opposite to R, which might be called -R, is the solution to P + Q. Here is an illustration to assist in visualizing.

from math.brown.edu

This method is limited to distinct values of P and Q, however. In order to double a point on E, we must use a different method. The correction to calculate P + P, sometimes written as 2P, is to draw the tangent line to E that runs through P and find where it intersects E again. The point opposite to this one will be 2P. This solution may feel familiar considering its similarity to the formal definition of a derivative.

from math.brown.edu

Finally, we must account for P + (-P), as this will only intersect the curve E twice. By including a special point at infinity called Ό, we can solve this expression as P + (-P) = Ό.

Analytically, we are looking for the solution to (λx + v)² = x³ + Ax + B, where L: y = λx + v is our line from P to Q on the elliptical curve E: y² = x₃ + Ax + B. Here are some formulas for addition on E where P = (x₁, y₁) and Q = (x₂, y₂)

• If P != Q and x₁ = x₂, then P + Q = Ό.
• If P = Q and y₁ = 0, then P + Q = 2P = Ό.
• If P != Q (and x₁ != x₂): let λ = (y₂ - y₁) / (x₂ - x₁) and v = (y₁x₂-y₂x₁)/(x₂-x₁)
• If P = Q (and y₂ != 0): let λ = (3x₁² + A) / 2y₁ (note that this is the first derivative of E) and v = (-x³ + Ax + 2B) / 2y

Then, P + Q = (λ² - x₁ - x₂, -λ³ + λ(x₁ + x₂) - v)

2.1 Example of Point Addition where P != Q

Find P + Q over the curve y² = x³ -7x + 10 where P = (1,2) and Q = (3,4).

1. λ = (y₂ - y₁) / (x₂ - x₁) = (2 - 4) / (1 - 3) = 1
2. v = (y₁x₂-y₂x₁)/(x₂-x₁) = (2*3 - 4*1) / (3 - 1) = 1
3. P + Q = (λ² - x₁ - x₂, -λ³ + λ(x₁ + x₂) - v) = (-3, 2)

2.2 Example of Point Addition where P = Q

Find 2P over the curve y² = x³ -7x + 10 where P = (1,2).

1. λ = (3x₁² + A) / 2y₁ = (3 * 1² - 7) / (2 * 2) = -1
2. v = (-x³ + Ax + 2B) / 2y = (-1³ + (-7)(1) + 2(10)) / 2(2) = 3
3. 2P = (λ² - x₁ - x₂, -λ³ + λ(x₁ + x₂) - v) = (-1, -4)

2.3 Scalar Multiplication

We've seen how to calculate 2P, but how should we tackle the problem of multiplying P by some arbitrary integer n? Say we want to find 42P. One way we could accomplish this is by converting 42 to binary and then figuring out how many times we should double P and which values of P and 2P to add together. 42 in binary is 101010, so 42P = 2⁵P + 2³P + 2¹P.

Check out https://andrea.corbellini.name/ecc/interactive/reals-add.html, an online tool that shows point addition with custom values. A tool for scalar multiplication can be found at https://andrea.corbellini.name/ecc/interactive/modk-mul.html.

3.0 Elliptical Curves and Fields

In mathematics, fields are algebraic structures. So far we've dealt with elliptical curves in R, but this isn't the only field that elliptical curves exist in. A field is a set with operations for addition and multiplication along with inverses for those operations (subtraction, division). E(K) describes an elliptical curve in a field K, where all points on E lie in K. There isn't a general answer for how E(K) actually looks, and often it can't be represented geometrically with any meaning.

3.1 E(C)

E(C) describes an elliptical curve E in field C. C is often used to denote the field of complex numbers, as it does here. The set of points in an elliptical curve with coordinates in the complex numbers form a torus. This shape resembles the surface of a donut in three dimensions.

from: wikipedia

3.2 E(Q)

E(Q) describes an elliptical curve through the rational numbers. Research into E(Q) has been crucial to the development of many areas of number theory. It appears in the proof to Fermat's Last Theorem and the modern theory of Diophantine equations.

3.3 E(F_p)

Here, F_p describes a field of integers from 0 to p-1 where p is a prime number. Addition and multiplication over this field are taken from modular arithmetic. Multiplication in E(F_p) has a property that makes it interesting for cryptography: it is cyclic. This means that as one computes 2P, 3P, 4P... on the elliptical curve, the point values will eventually repeat after some number of multiplications n.

4.0 Cryptography

The creation of strong encryption schemes has allowed the internet to expand into what we now know. The web page you are now browsing is likely secured by HTTPS, which includes an encryption scheme (SSL) to prevent unwanted parties from intercepting private information sent to and from web servers. Researchers developing encryption schemes want to maximize the strength of their encryption algorithm while minimizing the amount of information that is required to decrypt it. This information that is used to decrypt an encrypted message is known as a key, and encryption using elliptical curves often has a smaller key size compared to competing algorithms.

4.1 Discrete Logarithm

The property of an encryption scheme using elliptical curves that makes it difficult to break is known as the Elliptical Curve Discrete Logarithm Problem. While it is widely believed that solving this problem for any encryption scheme is computationally costly, no formal proof exists for this. For more information on this matter, look into the P vs NP problem. The discrete logarithm problem for elliptical curves is similar to the DLP for other kinds of encryption. Its difficulty to solve, or hardness, seems to differ from other analogous DLPs. Because the ECDLP is more difficult than the DLP for the DSA standard of encryption, for example, the key size for encryption schemes using elliptical curves can be smaller than the key size used for DSA and be exactly as difficult to break.

The discrete logarithm problem for elliptical curves is thus: Let E be an elliptic curve defined over a finite field F_p. Let S and T be points in E(F_p). Find an integer m so that T = mS.

The smallest integer m that meets this criterion is known as the Discrete Logarithm of T with respect to S.

4.2 Solving the Discrete Logarithm for Elliptical Curves

One way to solve the ECDLP is to simply calculate mS for random values of m until a match is found where T = mS. This approach is computationally costly, however, as you may need to exhaust every multiple of S within F_p before finding the answer. We can describe the number of steps we expect a computer to make in order to complete this algorithm as O(p). A more efficient solution is to compute two lists for randomly chosen values of m₁, m₂...

• List A: m₁S, m₂S, m₃S,...
• List B: T - m₁S, T - m₂S, T - m₃S,...

until finding a collision. This method has a much faster expected running time due to the birthday paradox. It's complexity is O(sqrt(p)). A weakness of this approach is that it requires a lot of space (O(sqrt(p))) in order to store both lists. Another approach known as Pollard's p method achieves the same computational complexity as the collision method, but requires a much smaller amount of storage space. Other ways to solve the ECDLP exist, but no known method is faster than Pollard's p method. A consequence of this is that it is not possible for modern technology to solve ECDLP in E(F_q) if q is sufficiently large. For intuition, solving ECDLP with q ~= 2^160 is approximately as hard as factoring a 1000 bit number. The reward we receive for using encryption schemes with elliptical curves is that our constructions have smaller keys, smaller message blocks, and are in some cases measurably faster.

5.0 Further Reading and Applications

Simple harmonic motion is a common topic in introductory physics classes, often involving equations for the motion of a pendulum. by assuming the angle the pendulum makes against a vertical line through its center is small, one can derive the equation of the simple harmonic motion of a pendulum. To describe the motion of a pendulum with larger angles, elliptical curves are needed.

The proof of Fermat's last theorem involved converting the original equation a^p + b^p = c^p to an elliptical equation and then demonstrating that the elliptical curve is both modular and not modular, meaning that a^p + b^p = c^p has no solutions.

Strings in string theory trace out surfaces as they move through space-time. If these strings wrap around and connect to themselves, they resemble a torus, meaning that the path traced by strings look like elliptical curves. When computing averages over all possible paths, quantum physicists must compute integrals over the space of all elliptic curves.

For a less simplified look into Elliptical Equations, check out the MIT Open Course notes on elliptical curves here: https://math.mit.edu/classes/18.783/2017/Lecture1.pdf For learning with a textbook, check out Silverman, Joseph H. The arithmetic of elliptic curves. Graduate Texts in Mathematics, 106. Springer-Verlag, New York, 1986.

6.0 Sources

1. https://en.wikipedia.org/wiki/Elliptic_curve
2. https://en.wikipedia.org/wiki/Discrete_logarithm
3. https://andrea.corbellini.name/2015/05/23/elliptic-curve-cryptography-finite-fields-and-discrete-logarithms/
4. https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/
5. https://mathworld.wolfram.com/Group.html
6. https://www.math.brown.edu/johsilve/Presentations/WyomingEllipticCurve.pdf
7. https://www.math.brown.edu/~jhs/UbiquityOfEllipticCurves.ppt
8. https://www.youtube.com/watch?v=vnpZXJL6QCQ