Skip to main content
Home
plus.maths.org

Secondary menu

  • My list
  • About Plus
  • Sponsors
  • Subscribe
  • Contact Us
  • Log in
  • Main navigation

  • Home
  • Articles
  • Collections
  • Podcasts
  • Maths in a minute
  • Puzzles
  • Videos
  • Topics and tags
  • For

    • cat icon
      Curiosity
    • newspaper icon
      Media
    • graduation icon
      Education
    • briefcase icon
      Policy

      Popular topics and tags

      Shapes

      • Geometry
      • Vectors and matrices
      • Topology
      • Networks and graph theory
      • Fractals

      Numbers

      • Number theory
      • Arithmetic
      • Prime numbers
      • Fermat's last theorem
      • Cryptography

      Computing and information

      • Quantum computing
      • Complexity
      • Information theory
      • Artificial intelligence and machine learning
      • Algorithm

      Data and probability

      • Statistics
      • Probability and uncertainty
      • Randomness

      Abstract structures

      • Symmetry
      • Algebra and group theory
      • Vectors and matrices

      Physics

      • Fluid dynamics
      • Quantum physics
      • General relativity, gravity and black holes
      • Entropy and thermodynamics
      • String theory and quantum gravity

      Arts, humanities and sport

      • History and philosophy of mathematics
      • Art and Music
      • Language
      • Sport

      Logic, proof and strategy

      • Logic
      • Proof
      • Game theory

      Calculus and analysis

      • Differential equations
      • Calculus

      Towards applications

      • Mathematical modelling
      • Dynamical systems and Chaos

      Applications

      • Medicine and health
      • Epidemiology
      • Biology
      • Economics and finance
      • Engineering and architecture
      • Weather forecasting
      • Climate change

      Understanding of mathematics

      • Public understanding of mathematics
      • Education

      Get your maths quickly

      • Maths in a minute

      Main menu

    • Home
    • Articles
    • Collections
    • Podcasts
    • Maths in a minute
    • Puzzles
    • Videos
    • Topics and tags
    • Audiences

      • cat icon
        Curiosity
      • newspaper icon
        Media
      • graduation icon
        Education
      • briefcase icon
        Policy

      Secondary menu

    • My list
    • About Plus
    • Sponsors
    • Subscribe
    • Contact Us
    • Log in
    • Elliptic cryptography

      Andrew Chambers
      20 July, 2015
      6 comments

      Elliptic curves are a very important new area of mathematics which has been greatly explored over the past few decades. They have shown tremendous potential as a tool for solving complicated number problems and also for use in cryptography.

      In 1994 Andrew Wiles, together with his former student Richard Taylor, solved one of the most famous maths problems of the last 400 years, Fermat's Last Theorem, using elliptic curves. In the last few decades there has also been a lot of research into using elliptic curves instead of what is called RSA encryption to keep data transfer safe online.

      Public and private

      padlock

      Maths is keeping your data safe.

      Elliptic curve cryptography, just as RSA cryptography, is an example of public key cryptography. The basic idea behind this is that of a padlock. If I want to send you a secret message I can ask you to send me an open padlock to which only you have the key. I then put my message in a box, lock it with the padlock, and send it to you. The good thing about this approach is that the message can be sent over insecure channels — even if someone intercepts the box, they don't have the key — and that we don't both need a key to the box. You could even get lots of people to send you secret messages in this way, without ever having to give away a single key.

      In public key cryptography messages are encrypted using particular pieces of mathematical information, which constitute the public key — that's the open padlock and performing the encryption is like snapping the padlock shut. Decryption is only possible using a mathematical private key, which is next to impossible to determine if you only know the public key.

      In RSA cryptography the public key involves a natural number N, which is used by computers to encrypt messages. To decrypt a message, you need to know the factors of N. If N is very large, then factoring it takes such a large amount of computing power that breaking the code is practically impossible. Only people (or, realistically, computers) in possession of the private key — the factors of N — can decrypt the message easily. (You can find out more about RSA here.)

      Elliptic curves

      Elliptic curve cryptography is based on the difficulty of solving number problems involving elliptic curves. On a simple level, these can be regarded as curves given by equations of the form

      y2=x3+ax+b,

      where a and b are constants. Below are some examples. In each case the graph shows all the points with coordinates (x,y), where x and y satisfy an equation of the form shown above.

      Elliptic curves

      The elliptic curves corresponding to whole number values of a between -2 and 1 and whole number values of values of b between -1 and 2. Only the curve for a = b = 0 doesn't qualify as an elliptic curve because it has a singular point.

      For the sake of accuracy we need to say a couple of words about the constants a and b. For an equation of the form given above to qualify as an elliptic curve, we need that 4a3+27b2≠0. This ensures that the curve has no singular points. Informally, it means that the curve is nice and smooth everywhere and doesn't contain any sharp points or cusps. In the examples above the constants a and b were chosen to be whole numbers between −2 and 1, and −1 and 2 respectively. But in general they can also take on other values. (For uses in cryptography a and b are required to come from special sets of numbers called finite fields). You can find out more about elliptic curves in this article.

      Adding points

      Given an elliptic curve, we can define the addition of two points on it as in the following example.

      Let's consider the curve y2=x3−4x+1 and the two points A=(2,1) and B=(−2,−1), which both lie on the curve. We now want to find an answer for A+B which we would also like to lie on the elliptic curve. If we add them as we might vectors we get (2,1)+(−2,−1)=(0,0) – but unfortunately this is not on the curve. So we define the addition A+B through the following geometric steps. We join up the points A and B with a straight line. This line generally intersects the curve in one more place, C. We then reflect the point C in the x-axis.
      Elliptic curves

      We declare this new point, C′, to be the sum of A and B. So A+B=C′. In our example this means that (2,1)+(−2,−1)=(1/4,−1/8). Trying another example, y2=x3−5x+4 (shown below), with A=(1,0) and B=(0,2), we have C=(3,−4) and C′=(3,4). Therefore (1,0)+(0,2)=(3,4).
      Elliptic curves

      We also need a definition for the sum when B=A to understand what we mean by A+A=2A. In this case we take the tangent to the curve at the point A, and then as before find the intersection of this tangent line and the curve, before reflecting the point. This is probably easier to understand with another graph: Here we use the elliptic curve y2=x3−12x. and consider the point A=B=(−2,4). We have drawn the tangent to the curve at A, which intersects the curve at a second point C=(4,4). Reflecting in the x- axis gives C′=(4,−4). Therefore we say 2A=C′, or 2(−2,4)=(4,−4).
      Elliptic curves

      It's now possible to define what we mean by nA for any point A on the curve and any natural number n>0: 2A=A+A, 3A=2A+A, 4A=3A+A, and so on. The only situation in which our definition of A+B doesn't work is when B is the reflection of A in the x-axis (which in the case where B=A means that A itself lies on the x-axis). In this case, the line we use to define the sum is vertical and there isn't a third point at which it meets they curve.
      Elliptic curves

      We can get around this problem by adding an extra point to the usual (x,y) plane, called the point at infinity and denoted by O. To make the addition work for our exceptional situation we simply define A+B=O. For any point A we also define A+O=A — so with our new notion of addition, the point O plays the same role as the number 0 in ordinary addition. It turns out that, given two points A and B on an elliptic curve, finding a number n such that B=nA (if it exists) can take an enormous amount of computing power, especially when n is large. Elliptic curve cryptography exploits this fact: the points A and B can be used as a public key, and the number n as the private key. Anyone can encrypt a message using the publicly available public key (we won't go into the details of the encryption method here), but only the person (or computer) in possession of the private key, the number n, can decrypt them.

      NSA and hacking data

      Bitcoin

      Elliptic curve cryptography has some advantages over RSA cryptography – which is based on the difficulty of factorising large numbers – as less digits are required to create a problem of equal difficulty. Therefore data can be encoded more efficiently (and thus more rapidly) than using RSA encryption. Currently the digital currency Bitcoin uses elliptic curve cryptography, and it is likely that its use will become more widespread as more and more data is digitalised. However, it's worth noting that as yet no-one has proved that it has to be difficult to crack elliptic curves – there may be a novel approach which is able to solve the problem in a much shorter time. Indeed many mathematicians and computer scientists are working in this field.

      Government digital spy agencies like the NSA and GCHQ are also very interested in such encryption techniques. If there was a method of solving this problem quickly then overnight large amounts of encrypted data would be accessible – and for example Bitcoin currency exchange would no longer be secure. It also recently transpired that the NSA has built "backdoor" entries into some elliptic curve cryptography algorithms which have allowed them to access data that the people sending it thought was secure. Mathematics is at the heart of this new digital arms race.


      Further reading

      To find out more about the development of codes, including modern elliptic curve cryptography, and their links to mathematics, the book by William Stein, Elementary Number Theory: Primes, Congruences and Secrets is an good starting place. Numberphile have also covered the NSA's attempts to circumvent elliptic curve cryptography in one of their ever excellent videos.


      About the author

      Andrew Chambers has an MSc in mathematics and is a teacher at the British International School Phuket, Thailand. He has written news and features articles for the Guardian, Observer and Bangkok Post, and was previously shortlisted for the Guardian's International Development Journalist of the Year Awards. Combining his love of both writing and mathematics, his website ibmathsresources.com contains hundreds of ideas for mathematical investigations (and some code breaking challenges) for gifted and talented students.

      • Log in or register to post comments

      Comments

      Anonymous

      20 July 2015

      Permalink

      Nice and interesting article. Deploying such graphs and relating them to an unique expression! Well, as I see it, it's time to restart learning maths! Thank you very much!

      • Log in or register to post comments

      Anonymous

      25 August 2015

      Permalink

      In the first paragraph of "NSA and hacking data" the phrase "... the difficulty of factorising large primes... " is used!

      • Log in or register to post comments

      Anonymous

      26 August 2015

      In reply to Elliptic Cryptography by Anonymous

      Permalink

      yes - well spotted!

      missing an "into" there....

      Andrew

      • Log in or register to post comments

      Marianne

      27 August 2015

      In reply to yes - well spotted! missing by Anonymous

      Permalink

      Thanks for pointing that out! We've corrected it.

      • Log in or register to post comments

      Richard Wicks

      24 August 2017

      Permalink

      It's not clear to me what xN means, where X is some number > 2 at leat in the context of the plotted elliptical curve. I've looked for this repeatedly, and I've never seen it drawn, ever.

      It's also not clear to me why multiplication has the associative property - that is x(yN) == y(xN).

      • Log in or register to post comments

      Ali Adams

      30 November 2017

      In reply to Multiplication. by Richard Wicks

      Permalink

      Look up XOR function and how order of XORing in not important.

      • Log in or register to post comments

      Read more about...

      cryptography
      elliptic curve
      University of Cambridge logo

      Plus Magazine is part of the family of activities in the Millennium Mathematics Project.
      Copyright © 1997 - 2025. University of Cambridge. All rights reserved.

      Terms