2017-03-17.sagews

Math 152 - Intro to Mathematical Software

2017-03-17

Kiran Kedlaya; University of California, San Diego

adapted from lectures by William Stein, University of Washington

Lecture 28: Elliptic curve cryptography; and what next?

Announcements:

• Last lecture! Remember, there is no final exam for this course.

• Remaining office hours this week:

  • Peter: today 3-4 in APM 6132.

• Homework due Friday, 8pm. Peer grading due Sunday, 8pm.

• Last call for course evaluations (CAPE)! Evaluations close Monday, March 20 at 8am. (These are needed in part to justify rerunning this course in the future.)

Elliptic curve cryptography

So far, the public key cryptography techniques we have discussed are:

• Diffie-Hellman, whose security depends on the difficulty of computing discrete logarithms;

• RSA, whose security depends on the difficulty of integer factorization.

While these problems remain fairly difficult with standard techniques, some improvements have been made over the years. In practice, the best-performing methods for large problem sizes (for both discrete logarithms modulo a prime and integer factorization) are forms of the number field sieve (see https://en.wikipedia.org/wiki/General_number_field_sieve).

%md
For this reason, it is desirable to look for variants. One commonly used variant is *elliptic curve cryptography*. This uses concepts which are somewhat more sophisticated than the ones needed so far, but which (in various forms) have been known to mathematicians for many centuries!

For this reason, it is desirable to look for variants. One commonly used variant is elliptic curve cryptography. This uses concepts which are somewhat more sophisticated than the ones needed so far, but which (in various forms) have been known to mathematicians for many centuries!

%md
An *elliptic curve* is (in its simplest form) an equation of the form $y^2 = x^3 + Ax + B$ for some values $A$ and $B$. (Note that the plot of such a curve is not an ellipse! The name arises from the original study of these curves in connection with the computation of the *arclength* of a sector of an ellipse.)

An elliptic curve is (in its simplest form) an equation of the form $y^2 = x^3 + Ax + B$ for some values $A$ and $B$. (Note that the plot of such a curve is not an ellipse! The name arises from the original study of these curves in connection with the computation of the arclength of a sector of an ellipse.)

E = EllipticCurve([-3, 1])
E

Elliptic Curve defined by y^2 = x^3 - 3*x + 1 over Rational Field

## Plot over the real numbers
E.plot(xmin=-10000, xmax=10000)

An amazing feature of elliptic curves is the group law: there is a natural way to add points on the curve! Explaining why this works is somewhat out of scope for this course, but we can at least experiment with this in Sage. (Warning: to make this statement completely correct, we must add one point at infinity corresponding to the vertical asymptote; this point will be the identity element for the group law.)

E = EllipticCurve([1, -1])
E

Elliptic Curve defined by y^2 = x^3 + x - 1 over Rational Field

P = E(1,1)
Q = E(2,3)
P+Q, Q+P, P+Q+Q

((1 : -1 : 1), (1 : -1 : 1), (13 : -47 : 1))

# Check that these really are points on the curve again...
P+Q+Q+Q

(685/121 : 18157/1331 : 1)

To make this relevant for cryptography, instead of working over the rational numbers, we work over the integers modulo a prime number $p$. In this context, the set of solutions is finite; in fact, it has size roughly $p$. (To be precise, there is a theorem of Hasse that says that the size differs from $p+1$ by no more than $2 \sqrt{p}$.)

p = random_prime(2^128)
p
F = GF(p)
E = EllipticCurve([F.random_element(), F.random_element()])
E

6460057584366581339788582436266190171 Elliptic Curve defined by y^2 = x^3 + 919123801299171252016970288139149681*x + 145010910859049054947745517067393264 over Finite Field of size 6460057584366581339788582436266190171

We can try to imitate the mechanism of Diffie-Hellman; that mechanism used only the fact that multiplication of the nonzero residue classes modulo $p$ defines a commutative group structure. Since the elliptic curve group law has the same feature, we could try using it instead!

P = E.random_element()
a = 37
b = 101
P1 = a*P
P2 = b*P
print P1, P2

(1793336765867519976276515581053812915 : 2214008585200795838526679496801624235 : 1) (4190029942952523037184726284750459895 : 2876934177134547091892557364175563585 : 1)

print b*P1, a*P2 ## These should match!

(168033824597654909485741260817478799 : 5226523525818156730719457084031080960 : 1) (168033824597654909485741260817478799 : 5226523525818156730719457084031080960 : 1)

However, there is a catch. Remember that for Diffie-Hellman modulo a prime $p$, if $p-1$ factors nontrivially then that factorization can be used to simplify the discrete logarithm problem. (Structurally, the abelian group we are working in has a product structure, and we can compute the discrete logarithm separately on each factor of the product.)

There is a similar catch here, except that $p-1$ must be replaced by the order of the corresponding group, i.e., the number of points on the elliptic curve mod $p$ (including the point at infinity). But this isn't given by such an obvious formula...

The problem of counting these solutions was originally addressed by Gauss in certain special cases. As noted earlier, it was shown by Hasse (1930s) that the count is always $p+1$ plus an error term no bigger than $2\sqrt{p}$.

One way to compute the order is to use the "baby step-giant step" method demonstrated for discrete logarithms on Monday. Hasse's bound cuts down the runtime of this from $p^{1/2}$ to $p^{1/4}$.

There is also a more sophisticated algorithm due to Schoof (1980s) that actually makes this problem polynomial-time (in the logarithm of $p$, not in $p$). This is the tip of a very large iceberg of computational number theory, which is both interesting in its own right (at least to me) and applicable to cryptography in various ways. (Besides this construction, there is a whole field of lattice-based cryptography that uses different number-theoretic ideas to fight off attacks based on the potential feasibility of quantum computation.)

E.cardinality()

6460057584366581342493730540484357560

E.cardinality().factor()

2^3 * 5 * 211 * 10513 * 72806017920112689891208160473

E.cardinality?

File: /projects/sage/sage-7.5/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_finite_field.py
Signature : E.cardinality(self, algorithm='pari', extension_degree=1)
Docstring :
Return the number of points on this elliptic curve.

INPUT:

* "algorithm" -- string (default: "'pari'"), used only for point
  counting over prime fields:

  * "'pari'" -- use the baby-step giant-step or Schoof-Elkies-
    Atkin methods as implemented in the PARI C-library function
    "ellap"

  * "'bsgs'" -- use the baby-step giant-step method as
    implemented in Sage, with the Cremona-Sutherland version of
    Mestre's trick

  * "'all'" -- compute cardinality with both "'pari'" and
    "'bsgs'"; return result if they agree or raise a "RuntimeError"
    if they do not

* "extension_degree" -- an integer d (default: 1): if the base
  field is GF{q}, return the cardinality of "self" over the
  extension GF{q^d} of degree d.

OUTPUT:

The order of the group of rational points of "self" over its base
field, or over an extension field of degree d as above. The result
is cached.

Over prime fields, one of the above algorithms is used. Over non-
prime fields, the serious point counting is done on a standard
curve with the same j-invariant over the field GF{p}(j), then
lifted to the base field, and finally account is taken of twists.

For j = 0 and j = 1728 special formulas are used instead.

EXAMPLES:

   sage: EllipticCurve(GF(4, 'a'), [1,2,3,4,5]).cardinality()
   8
   sage: k.<a> = GF(3^3)
   sage: l = [a^2 + 1, 2*a^2 + 2*a + 1, a^2 + a + 1, 2, 2*a]
   sage: EllipticCurve(k,l).cardinality()
   29

   sage: l = [1, 1, 0, 2, 0]
   sage: EllipticCurve(k, l).cardinality()
   38

An even bigger extension (which we check against Magma):

   sage: EllipticCurve(GF(3^100, 'a'), [1,2,3,4,5]).cardinality()
   515377520732011331036459693969645888996929981504
   sage: magma.eval("Order(EllipticCurve([GF(3^100)|1,2,3,4,5]))")    # optional - magma
   '515377520732011331036459693969645888996929981504'

   sage: EllipticCurve(GF(10007), [1,2,3,4,5]).cardinality()
   10076
   sage: EllipticCurve(GF(10007), [1,2,3,4,5]).cardinality(algorithm='pari')
   10076
   sage: EllipticCurve(GF(next_prime(10**20)), [1,2,3,4,5]).cardinality()
   100000000011093199520

The cardinality is cached:

   sage: E = EllipticCurve(GF(3^100, 'a'), [1,2,3,4,5])
   sage: E.cardinality() is E.cardinality()
   True
   sage: E = EllipticCurve(GF(11^2, 'a'), [3,3])
   sage: E.cardinality()
   128
   sage: EllipticCurve(GF(11^100, 'a'), [3,3]).cardinality()
   137806123398222701841183371720896367762643312000384671846835266941791510341065565176497846502742959856128

What next?

There is currently a campus-wide initiative to develop an undergraduate degree program in data science, with Python as the primary programming language. Courses in various departments related to this program should be starting to come online in the near future (including a more permanent version of this course in the math department).

If any particular topics in this course piqued your interest, you may be able to follow up on them.

• Abstract algebra: 100A-C, 103A-B.

• Combinatorics and graph theory: 154, 184.

• Cryptography: 187A-B. In particular, 187B is a new course on "mathematics of modern cryptography" taught by Prof. Bucur (starting this spring).

• Data science: 189 (inference), or better yet the new data science major: http://www.ucsd.edu/catalog/curric/DS.html. In particular, DS10 (starting next fall) will be an introduction to Python programming.

• Number theory: 104A-C.

• Statistics: 181A-B, 183, and especially 185 (computational statistics).

For additional advice, feel free to ask me by email, or set up (also by email) an appointment to talk in person.

Some interest has been expressed in setting up an informal seminar next quarter to follow up on the use of Python in scientific computation. If this progresses further, I'll make an announcement by email.

There are lots of career opportunities for which a good handle on mathematical computation is a big asset. For example, a friend of mine who runs a biochem/comp bio/med lab in Boston is looking to hire a data scientist! Contact me for details.

Finally, thanks for being my "experimental subjects" in this course! This has been a tremendous learning opportunity for me on various fronts, and I look forward to using what I learned to developing a refined version of this course for future cohorts of students.