You are currently browsing the tag archive for the ‘bitcoin’ tag. ECDSA:  Elliptic Curve Signatures

This is the second post on this topic – following on from the first post here.  Read that first for more of the maths behind this!  In this post I’ll look at this from a computational angle – and make a simple Python code to create and verify Elliptic Curve Signatures.

Why Elliptical Curve Signatures?

Say I create 100 MATHSCOINS which I sell.  This MATHSCOIN only has value if it can be digitally verified to be an original issued by me.  To do this I share some data publicly – this then allows anyone who wants to check via its digital signature that this is a genuine MATHSCOIN.  Once you understand this idea you can (in theory!) create your own digital currency or NFT – complete with a digital signature that allows anyone to check that it has been issued by you.

Python code

This code will revolve around solutions mod M to the following elliptical curve: We can run a quick Python code to find these solutions for a defined M: This Python code then needs to use the algorithms for repeated addition of the base pair.  It then needs to store all the coordinate pairs in a list (one list for the x coordinates and one for the y coordinates).   These can then follow the algorithm for creating the digital signature.  Note that we need to define the mod of the curve (M), the starting base pair (a,b), the order of the base pair (n), our data to digitally sign (z1), our private key (k1) and a public key (k2).

The full code for digital signatures Running this code

I have put this code online at Replit.com here – so you can see how it works.  It should look something like this: Checking a digital signature is genuine

We might also want to work backwards to check if a digital signature is correct.  The following code will tell us this – as long as we specify all the required variables below.  Note we need the digital signature (s1, s2) as well as (r1,r2) – which is worked out by the previous code.  Running this code

You can run this code here – again on Replit.com.   You should see something like this: Try it yourself!

To create your own digital signatures you need to find a mod M and a base pair with order n, such that both M and n are prime.  Remember you can use this site to find some starting base pairs mod M.  Here are some to start off with

(1)

M =  907.  Base pair = (670,30).  n = 967

(2)

M = 79.   Base pair = (60, 10).  n = 67

(3)

M = 97.  Base pair = (85, 92).  n = 79

(4)

M = 13.  Base pair = (8,8).  n = 7

Can you run the code to create a digital signature, and then run the verification code to check that it is indeed genuine? The mathematics behind blockchain, bitcoin and NFTs.

If you’ve ever wondered about the maths underpinning cryptocurrencies and NFTs, then here I’m going to try and work through the basic idea behind the Elliptic Curve Digital Signature Algorithm (ECDSA).  Once you understand this idea you can (in theory!) create your own digital currency or NFT – complete with a digital signature that allows anyone to check that it has been issued by you.

Say I create 100 MATHSCOINS which I sell.  This MATHSCOIN only has value if it can be digitally verified to be an original issued by me.  To do this I share some data publicly – this then allows anyone who wants to check via its digital signature that this is a genuine MATHSCOIN.  So let’s get into the maths!  (Header image generated from here).

Elliptical curves

I will start with an elliptical curve and a chosen prime mod (here we work in mod arithmetic which is the remainder when dividing by a given mod).  For this example I will be in mod 13 and my curve will be: First I will work out all the integer solutions to this equation.  For example (7,5) is a solution because: The full set of integer solutions is given by: Now we define addition of 2 non equal points (p_1, p_2) and (q_1, q_2) on the curve mod M by the following algorithm: And we define the addition of 2 equal points (p_1, p_2)  on the curve mod M by the following algorithm: So  in the case of (8,8) if we want to calculate (8,8) + (8,8) this gives: This is a little tedious to do, so we can use an online generator here to calculate the full addition table of all points on the curve: This shows that (say) (7,5) + (8,5) = (11,8) etc.

I can then chose a base point to find the order of this point (how many times it can be added to itself until it reaches the point at infinity).  For example with the base point (8,8): We can also see that the order of our starting point A(8,8)  is 7 because there are 7 coordinate points (including the point at infinity) in the group when we calculate A, 2A, 3A…

ECDSA:  Elliptic Curve Signatures

So I have chosen my curve mod M (say): And I choose a base point on that curve (p_1, p_2) (say): And I know the order of this base point is 7 (n=7).  (n has to be prime).  This gives the following: I now chose a private key k_1: Let’s say: This is super-secret key.  I never share this!  I use this key to generate the following point on the curve: I can see that 5(8,8) = (11,5) from my table when repeatedly adding (8,8) together.

Next I have some data z_1 which I want to give a digital signature to – this signature will show anyone who examines it that the data is authentic, has been issued by me and has not been tampered with.  Let’s say: I choose another integer k_2 such that: Let’s say: I am now ready to create my digital signature (s_1, s_2) by using the following algorithm: Note, dividing by 2 is the same as multiplying by 4 in mod 7 (as this is the multiplicative inverse).

I can then release this digital signature alongside my MATHSCOIN (represented by the data z_1 = 100).  Anyone can now check with me that this MATHSCOIN was really issued by me.

Testing a digital signature

So someone has bought a MATHSCOIN direct from me – and later on wants to sell to another buyer.  Clearly this new buyer needs to check whether this is a genuine MATHSCOIN.  So they have check the digital signature on the data.  To allow them to do this I can share all the following data (but crucially not my private key): This gives: To verify someone then needs to do the following: To verify that the data z_1 has a valid digital signature we need: So with the shared data we have: This verifies that the data had a valid digital signature – and that the MATHSCOIN is genuine!  This is basically the foundation of all digital assets which require some stamp of authenticity.

In real life the numbers chosen are extremely large – private keys will be 256 digits long and primes very large.  This makes it computationally impossible (at current speeds) to work out a private key based on public information, but still relatively easy to check a digital signature for validity.

I have also made some simple Python code which will provide a digital signature as well as check that one is valid.  You can play around with these codes here:

(1) Digital signature code,  (2) Checking a digital signature for validity

So time to create your own digital currency! 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!

Spotting Asset Bubbles

Asset bubbles are formed when a service, product or company becomes massively over-valued only to crash, taking with it most of its investors’ money.  There are many examples of asset bubbles in history – the Dutch tulip bulb mania and the South Sea bubble are two of the most famous historical examples.  In the tulip mania bubble of 1636-37, the price of tulip bulbs became astronomically high – as people speculated that the rising prices would keep rising yet further.  At its peak a single tulip bulb was changing hands for around 10 times the annual wage of a skilled artisan, before crashing to become virtually worthless.

More recent bubble include the Dotcom crash of the early 2000s – where investors piled in trying to spot in what ways the internet would revolutionise businesses.  Huge numbers of internet companies tried to ride this wave by going public with share offerings.  This led to massive overvaluation and a crash when investors realised that many of these companies were worthless.  Pets.com is often given as an example of this exuberance – its stock collapsed from \$11 to \$0.19 in just 6 months, taking with it \$300 million of venture capital.

Therefore spotting the next bubble is something which economists take very seriously.  You want to spot the next bubble, but equally not to miss out on the next big thing – a difficult balancing act!  The graph at the top of the page is given as a classic bubble.  It contains all the key phases – an initial slow take-off, a steady increase as institutional investors like banks and hedge funds get involved, an exponential growth phase as the public get involved, followed by a crash and a return to its long term mean value.

Comparing the Bitcoin graph to an asset bubble The above graph is charting the last year of Bitcoin growth.  We can see several similarities – so let’s try and plot this on the same axis as the model.  The orange dots represent data points for the initial model – and then I’ve fitted the Bitcoin graph over the top: It’s not a bad fit – if this was going to follow the asset bubble model then it would be about to crash rapidly before returning to the long term mean of around \$4000.  Whether that happens or it continues to rise, you can guarantee that there will be thousands of economists and stock market analysts around the world doing this sort of analysis (albeit somewhat more sophisticated!) to decide whether Bitcoin really will become the future of money – or yet another example of an asset bubble to be studied in economics textbooks of the future.

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:

1. 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.
2. Original Paper 3 investigations (with full worked solutions) to develop investigative techniques and support both the exploration and the Paper 3 examination.
3. Over 150 pages of Coursework Guides to introduce students to the essentials behind getting an excellent mark on their exploration coursework.
4. 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 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. The Rise of Bitcoin

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!

Bitcoin is in the news again as it hits \$10,000 a coin – the online crypto-currency has seen huge growth over the past 1 1/2 years, and there are now reports that hedge funds are now investing part of their portfolios in the currency.   So let’s have a look at some regression techniques to predict the future price of the currency. Here the graph has been inserted into Desmos and the scales aligned.  1 on the y axis corresponds to \$1000 and 1 on the x axis corresponds to 6 months.  2013 is aligned with  (0,0). Next, I plot some points to fit the curve through. Next, we use Desmos’ regression for y = aebx+d. This gives the line above with equation:

y = 5.10 x 10-7 e1.67x + 0.432.

I included the vertical translation (d) because without it the graph didn’t fit the early data points well.

So, If I want to predict what the price will be in December 2019, I use x = 12

y = 5.10 x 10-7 e1.67(12) + 0.432 = 258

and as my scale has 1 unit on the y axis equal to \$1000, this is equal to \$258,000.

So what does this show?  Well it shows that Bitcoin is currently in a very steep exponential growth curve – which if sustained even over the next 12 months would result in astronomical returns.  However we also know that exponential growth models are very poor at predicting long term trends – as they become unfeasibly large very quickly.   The two most likely scenarios are:

1. continued growth following a polynomial rather than exponential model
2. a price crash

Predicting which of these 2 outcomes are most likely is probably best left to the experts!  If you do choose to buy bitcoins you should be prepared for significant price fluctuations – which could be down as well as up.  I’ll revisit this post in a few months and see what has happened.

If you are interested in some more of the maths behind Bitcoin, you can read about the method that is used to encrypt these currencies (a method called elliptical curve cryptography).

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:

1. 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.
2. Original Paper 3 investigations (with full worked solutions) to develop investigative techniques and support both the exploration and the Paper 3 examination.
3. Over 150 pages of Coursework Guides to introduce students to the essentials behind getting an excellent mark on their exploration coursework.
4. 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 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.

### Website Stats

• 9,374,467 views

All content on this site has been written by Andrew Chambers (MSc. Mathematics, IB Mathematics Examiner).

### New website for International teachers I’ve just launched a brand new maths site for international schools – over 2000 pdf pages of resources to support IB teachers.  If you are an IB teacher this could save you 200+ hours of preparation time.

Explore here!

### Free HL Paper 3 Questions P3 investigation questions and fully typed mark scheme.  Packs for both Applications students and Analysis students. A Super Exploration Guide with 168 pages of essential advice from a current IB examiner to ensure you get great marks on your coursework.