You are currently browsing the tag archive for the ‘elliptical curves’ tag.
If you are a teacher then please also visit my new site: intermathematics.com for over 2000+ pdf pages of resources for teaching IB maths!
Elliptical Curve Cryptography
Elliptical curves are a very important new area of mathematics which have 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.
Andrew Wiles, who solved one of the most famous maths problems of the last 400 years, Fermat’s Last Theorem, using elliptical curves. In the last few decades there has also been a lot of research into using elliptical curves instead of RSA encryption to keep data transfer safe online. So, what are elliptical curves? On a simple level they can be regarded as curves of the form:
y² = x³ +ax + b
If we’re being a bit more accurate, we also need 4a³ + 27b² ≠ 0. This stops the graph having “singular points” which cause problems with the calculations. We also have a “point at infinity” which can be thought of as an extra point added on to the usual x,y plane representing infinity. This also helps with calculations – though we don’t need to go into this in any more detail here!
Addition of two points A and B
What makes elliptical curves so useful is that we can create a group structure using them. Groups are very important mathematical structures because of their usefulness in being applied to problem solving. A group needs to have certain properties. For example, we need to be able to combine 2 members of the group to create a 3rd member which is also in the group. This is how it is done with elliptical curves:
Take 2 points A and B on y² = x³ -4x + 1. In the example we have A = (2,1) and B = (-2,-1). We now want to find an answer for A + B which also is on the elliptical curve. If we add them as we might vectors we get (0,2) – 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. This line intersects the curve in one more place, C.
We then reflect the point C in the x axis. We then define this new point C’ = A + B. In this case this means that (2,1) + (-2,-1) = (1/4, -1/8).
Addition of 2 points when A = B
We have to also be able to cope with the situation when the point A and B are the same. Here we create the line through A which is the tangent to the curve at that point:
We then use the same transformation as before to say that A+B = C’. For example with the curve y² = x³ -12x, if we start with the point A(-2,4) then this transformation tells us that A + A = (4,-4).
Elliptical curves over finite fields
For the purposes of cryptography we often work with elliptical curves over finite fields. This means we (say) only consider integer coordinate solutions and work in modulo arithmetic (mod prime).
Say we start with the curve y² = x³ +x+1, and just look at the positive integer solutions mod 7. (Plotted using the site here).
When x = 1,
y² = 1³ +1 + 1
y² = 3
So this has no integer solution.
Next, when x = 2 we have:
y² = 2³ +2 +1 = 11.
However when we are working mod 7 we look at the remainder when 11 is divided by 7 (which is 4). So:
y² = 4 (mod 7)
y = 2 or y = -2 = 5 (mod 7)
When x = 3 we have:
y² = 3³ +3 +1 = 31
y² = 3 (mod 7)
which has no integer solutions.
In fact, all the following coordinate points satisfy the equation (mod 7):
(2,2), (0,1), (0,6), (2,5).
Addition under modulo arithmetic
Let’s look at the coordinate points we calculated before for the elliptical curve y² = x³ +x+1 (integers solutions and mod 7) – they form a group under addition. (Table generated here)
In order to calculate addition of points when dealing with elliptical curves with integer points mod prime we use the same idea as expressed above for general graphs.
The table tells us that (0,1) + (0,1) = (2,5). If we were doing this from the graph we would draw the tangent to the curve at (0,1), find where it intersects the graph again, then reflect this point in the x axis. We can do all this algebraically.
First we find the gradient of the tangent when x = 0:
Next we have to do division modulo 7 (you can use a calculator here, and you can also read more about division modulo p here).
Next we find the equation of the tangent through (0,1):
Next we find where this tangent intersects the curve again (I used Wolfram Alpha to solve this mod 7)
We then substitute the value x = 2 into the original curve to find the y coordinates:
(2,2) is the point where the tangent would touch the curve and (2,5) is the equivalent of the reflection transformation. Therefore our answer is (2,5). i.e (0,1) + (0,1) = (2,5) as required.
When adding points which are not the same we use the same idea – but have to find the gradient of the line joining the 2 points rather than the gradient of the tangent. We can also note that when we try and add points such as (2,5) and (2,2) the line joining these does not intersect the graph again and hence we affix the point an infinity as (2,5) + (2,2).
Using elliptical codes for cryptography
Even though all this might seem very abstract, these methods of calculating points on elliptical curves form the basis of elliptical cryptography. The basic idea is that it takes computers a very long time to make these sorts of calculations – and so they can be used very effectively to encrypt data.
Say for example two people wish to create an encryption key.
They decide on an elliptical curve and modulo. Let’s say they decide on y² = x³ +x+1 for integers, mod 7.
This creates the addition group
Next they choose a point of the curve. Let’s say they choose P(1,1).
Person 1 chooses a secret number n and then sends nP (openly). So say Person 1 chooses n = 2. 2(1,1) = (1,1) + (1,1) = (0,2). Person 1 sends (0,2).
Person 2 chooses a secret number m and then sends mP (openly). So say Person 2 chooses m = 3. 3(1,1) = (1,1) + (1,1) + (1,1) = (0,2) + (1,1) = (0,5). Person 2 sends (0,5).
Both Person 1 and Person 2 can easily calculate mnP (the secret key).
Person 1 receives (0,5) and so does 2(0,5) = (0,5) + (0,5) = (1,1). This is the secret key.
Person 2 receives (0,2) and so does 3(0,2) = (0,2) + (0,2) +(0,2) = (1,1). This is the same secret key.
But for a person who can see mP and nP there is no quick method for working out mnP – with a brute force approach extremely time consuming. Therefore this method can be successfully used to encrypt data.
Essential Resources for IB Teachers
If you are a teacher then please also visit my new site. This has been designed specifically for teachers of mathematics at international schools. The content now includes over 2000 pages of pdf content for the entire SL and HL Analysis syllabus and also the SL Applications syllabus. Some of the content includes:
- Original pdf worksheets (with full worked solutions) designed to cover all the syllabus topics. These make great homework sheets or in class worksheets – and are each designed to last between 40 minutes and 1 hour.
- Original Paper 3 investigations (with full worked solutions) to develop investigative techniques and support both the exploration and the Paper 3 examination.
- Over 150 pages of Coursework Guides to introduce students to the essentials behind getting an excellent mark on their exploration coursework.
- A large number of enrichment activities such as treasure hunts, quizzes, investigations, Desmos explorations, Python coding and more – to engage IB learners in the course.
There is also a lot more. I think this could save teachers 200+ hours of preparation time in delivering an IB maths course – so it should be well worth exploring!
Essential Resources for both IB teachers and IB students
1) Exploration Guides and Paper 3 Resources
I’ve put together a 168 page Super Exploration Guide to talk students and teachers through all aspects of producing an excellent coursework submission. Students always make the same mistakes when doing their coursework – get the inside track from an IB moderator! I have also made Paper 3 packs for HL Analysis and also Applications students to help prepare for their Paper 3 exams. The Exploration Guides can be downloaded here and the Paper 3 Questions can be downloaded here.
Elliptical Curve Cryptography
This post builds on some of the ideas in the previous post on elliptical curves. This blog originally appeared in a Plus Maths article I wrote here. The excellent Numberphile video above expands on some of the ideas below.
On a (slightly simplified) level elliptical curves they can be regarded as curves of the form:
y² = x³ +ax + b
So for example the curve below is an elliptical curve. This curve also has an added point at infinity though we don’t need to worry about that here. Elliptical curve cryptography is based on the difficulty in solving arithmetic problems on these curves. If you remember from the last post, we have a special way of defining the addition of 2 points.
Let’s say take 2 points A and B on y² = x³ -4x + 1. In the example we have A = (2,1) and B = (-2,1). We now want to find an answer for A + B which also is on the elliptical curve. If we add them as we might vectors we get (0,2) – 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. This line intersects the curve in one more place, C.
We then reflect the point C in the x axis. We then define this new point C’ = A + B. In this case this means that (2,1) + (-2,1) = (1/4, -1/8).
Trying another example, y² = x³ -5x + 4 (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).
We also need to have a definition when A and B define the same point on the curve. This will give us the definition of 2A. In this case we take the tangent to the curve at that point, and then as before find the intersection of this line and the curve, before reflecting the point. This probably is easier to understand with another graph:
Here we used the graph y² = x³ -5x + 4 again. This time point A = B = (-1.2, 2.88) and we have drawn the tangent to the curve at this point, which gives point D, which is then reflected in the x axis to give D’. D’ = (2.41, -2.43). Therefore we can say 2A = D’, or 2(-1.2, 2.88) = (2.41, -2.43).
Now addition of points is defined we can see how elliptical curve cryptography works. The basic idea is that given 2 points on the curve, say A and B, it takes a huge amount of computing power to work out the value a such that aA = B. For example, say I use the curve y² = x³ -25x to encrypt, and the 2 points on the curve are A = (-4,6) and B = (1681/144 , -62279/1728). Someone who wanted to break my encryption would need to find the value a such that a(-4,6) = (1681/144 , -62279/1728). The actual answer is a =2 which we can show graphically. As we want to show that 2(-4,6) = (1681/144 , -62279/1728) , we can use the previous method of finding the tangent at the point (-4,6):
We can then check with Geogebra which shows that B’ is indeed (1681/144 , -62279/1728). When a is chosen so that it is very large, this calculation becomes very difficult to attack using brute force methods – which would require checking 2(4,-6), 3(4,-6), 4(4,-6)… until the solution (1681/144 , -62279/1728) was found.
NSA and hacking data
Elliptical curve cryptography has some advantages over RSA cryptography – which is based on the difficulty of factorising large primes – 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 elliptical 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 elliptical 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 elliptical 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.
If you enjoyed this post you might also like:
RSA Encryption – the encryption system which secures the internet.
Circular inversion – learn about some other geometrical transformations used in university level mathematics.
Elliptical Curves
Elliptical curves are a very important new area of mathematics which have 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. (This blog is based on the article I wrote for Plus Maths here).
Andrew Wiles, who solved one of the most famous maths problems of the last 400 years, Fermat’s Last Theorem, using elliptical curves. In the last few decades there has also been a lot of research into using elliptical curves instead of RSA encryption to keep data transfer safe online. So, what are elliptical curves? On a simple level they can be regarded as curves of the form:
y² = x³ +ax + b
So for example the following is an elliptical curve:
If we’re being a bit more accurate, we also need 4a³ + 27b² ≠ 0. This stops the graph having “singular points” which cause problems with the calculations. We also have a “point at infinity” which can be thought of as an extra point added on to the usual x,y plane representing infinity. This also helps with calculations – though we don’t need to go into this in any more detail here!
What makes elliptical curves so useful is that we can create a group structure using them. Groups are very important mathematical structures – again because of their usefulness in being applied to problem solving. A group needs to have certain properties. For example, we need to be able to combine 2 members of the group to create a 3rd member which is also in the group. This is how it is done with elliptical curves:
Take 2 points A and B on y² = x³ -4x + 1. In the example we have A = (2,1) and B = (-2,1). We now want to find an answer for A + B which also is on the elliptical curve. If we add them as we might vectors we get (0,2) – 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. This line intersects the curve in one more place, C.
We then reflect the point C in the x axis. We then define this new point C’ = A + B. In this case this means that (2,1) + (-2,1) = (1/4, -1/8).
Trying another example, y² = x³ -5x + 4 (above), with A = (1,0) and B = (0,2) we have C = (3,-4) and C’ = (3,4). Therefore (1,0) + (0,2) = (3,4).
We can also have elliptical curves as a collection of discrete points. We start with the curve y² = x³ +x+1, above, and just look at the positive integer solutions mod 7. For example, when x = 1,
y² = 1³ +1 + 1
y² = 3
So this has no integer solution.
Next, when x = 2 we have:
y² = 2³ +2 +1 = 11.
However when we are working mod 7 we look at the remainder when 11 is divided by 7 (which is 4). So:
y² = 4 (mod 7)
y = 2
When x = 3 we have:
y² = 3³ +3 +1 = 31
y² = 3 (mod 7)
which has no integer solutions.
In fact, all the following coordinate points satisfy the equation (mod 7):
(2,2), (0,1), (0,6), (2,5).
Even though all this might seem very abstract, these methods of calculating points on elliptical curves form the basis of elliptical cryptography. The basic idea is that it takes computers a very long time to make these sorts of calculations – and so they can be used very effectively to encrypt data.
If you enjoyed this post you might also like:
RSA Encryption – the encryption system which secures the internet.
Circular inversion – learn about some other geometrical transformations used in university level mathematics.
IB Maths Resources from Intermathematics 