Elliptic trapdoors

Elliptic curves are amongst a family of curves that make up the alluring surfaces of much contemporary organically-inspired architecture. They are also the basis of encryption methods that secure digital communications.

A trapdoor is a one-way portal. You can go through it easily in one direction, but it’s difficult to come out again in the reverse direction. Turnstiles are like that. If it’s a horizontal door then it relies on gravity for the one-way function. It’s easy to fall through it into the cellar below, but harder to jump or climb your way out. It’s similar to the way hunters use pits to trap prey, and some insects lure prey into a one-way system from which there’s no escape except by herculean effort. Trapdoors associate with secrets and hiddenness. A stage magician will install a secret trapdoor under a magic box. The assistant falls through the secret door before the magician opens the lid to reveal the box is now empty.

Cryptographers use the trapdoor metaphor to describe their methods. It’s easy to encrypt a message, but has to be substantially more difficult to recover it without a special key, or escape route.

Some mathematical operations are difficult to undo, e.g. you can multiply 2 arbitrary prime numbers, but it’s much more difficult to factor the resultant into those two primes again. It’s easy to get the toothpaste out of the tube, but trying to get it back in only makes a mess.

Elliptic curve encryption

The multiplication of prime numbers can be made even more difficult to un-multiply if you redefine multiplication. One method is to define addition in terms of geometrical relationships between points on a curved line. Scalar multiplication is just repeated addition. For this to work the curved line needs to have a relatively simple formula. It must also be possible to draw a straight line through two points on the curve that will only strike one other point on the same curve. Two points can be co-incident on the curve, in which case the straight line drawn from that point will be a tangent to the curve and will always be found to cross the curve at another point, or at infinity. These condition are met in the case of the curve y2 = x3 – ax + b.

This is the graph of the function y2 = x3 – ax + b, or y = (x3 – ax + b). I generated this curve using the very elegant maths function visualiser at https://www.desmos.com/calculator. I also saved an animation showing different values for a and b. (The function visualiser doesn’t calculate the negative y values so I had to do some image manipulation in Premiere Pro etc.)

Here’s how you add two points (P and Q) together. Draw a line through them. Where that line intersects the curve again drop another line to find that intersection point’s mirror reflection.

P, Q and R are each defined as x and y coordinates. Simple algebra calculates the x and y coordinates of R from the coordinates of P and Q and the curve formula. A point added to itself is simply the same operation but the straight line from P is a tangent to the curve.

To multiply P by an integer, say 4, involves adding 2P to P to produce 3P, then adding that to P again. 4P is also created by doubling 2P, i.e. drawing a tangent from 2P.

If the multiplication factor is k, then kP is derived by repeating the additive operation on P k number of times to produce a final product Q, i.e. Q = kP. It’s easy enough for a computer to calculate the coordinates of Q by iterating the additive calculation k times. You may know the coordinates of P and Q, but it’s a lot of work to derive k, especially if the coordinates of P are around 50 digits long!

It’s worth noting that if the elliptic curve is extended it tends towards a straight vertical line both above and below the x axis. You can see this by zooming out on the maths function visualiser.

This means that all straight lines in the additions and multiplications outlined above, and all tangents to the curve, will collide again with the curve somewhere along its length. The exception is the case where a line is perfectly vertical. In that case the product of the calculation is a point at infinity. That represents a limit point of the calculation.

This method of bouncing about a curve is a way of making a number k almost impossible to recover, even if you know the other parameters. I’ll attempt to explain how this facilitates the Elliptic-curve Diffie–Hellman encryption method in subsequent posts.

Reference

Note

  • Banner image is the Olympic Pool, Stratford, UK by Zaha Hadid.

3 Comments

  1. Pingback: Elliptic fields – Reflections on Technology, Media & Culture
  2. Pingback: Key exchange: It’s a wrap! – Reflections on Technology, Media & Culture
  3. Pingback: Cryptography and the Baroque – Reflections on Technology, Media & Culture

Leave a Reply