You are currently browsing the tag archive for the ‘crypto’ tag.

Screen Shot 2022-11-25 at 8.12.26 AM

(Header image generated from here).

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:

Screen Shot 2022-11-28 at 3.30.46 PM

We can run a quick Python code to find these solutions for a defined M:

Screen Shot 2022-11-28 at 3.27.55 PM

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

Screen Shot 2022-11-28 at 3.28.36 PM

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:

Screen Shot 2022-11-28 at 3.55.04 PM

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.

Screen Shot 2022-11-28 at 3.28.48 PM

Screen Shot 2022-11-28 at 3.28.56 PM

Running this code

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

Screen Shot 2022-11-28 at 3.53.13 PM

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?

Screen Shot 2022-11-25 at 8.12.26 AM

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:

Screen Shot 2022-11-25 at 8.23.23 AM

First I will work out all the integer solutions to this equation.  For example (7,5) is a solution because:

Screen Shot 2022-11-25 at 8.23.27 AM

The full set of integer solutions is given by:

Screen Shot 2022-11-25 at 8.23.35 AM

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:

Screen Shot 2022-11-25 at 8.23.51 AM

And we define the addition of 2 equal points (p_1, p_2)  on the curve mod M by the following algorithm:

Screen Shot 2022-11-25 at 8.24.08 AM

So  in the case of (8,8) if we want to calculate (8,8) + (8,8) this gives:

Screen Shot 2022-11-25 at 8.24.24 AM

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:

Screen Shot 2022-11-25 at 8.12.26 AM

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):

Screen Shot 2022-11-25 at 8.24.38 AM

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):

Screen Shot 2022-11-25 at 8.23.23 AM

And I choose a base point on that curve (p_1, p_2) (say):

Screen Shot 2022-11-25 at 8.39.59 AM

And I know the order of this base point is 7 (n=7).  (n has to be prime).  This gives the following:

Screen Shot 2022-11-25 at 9.15.25 AM

I now chose a private key k_1:

Screen Shot 2022-11-25 at 8.40.34 AM

Let’s say:

Screen Shot 2022-11-25 at 8.47.55 AM

This is super-secret key.  I never share this!  I use this key to generate the following point on the curve:

Screen Shot 2022-11-25 at 8.40.41 AM

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:

Screen Shot 2022-11-25 at 8.47.49 AM

I choose another integer k_2 such that:

Screen Shot 2022-11-25 at 8.40.54 AM

Let’s say:

Screen Shot 2022-11-25 at 8.49.52 AM

I am now ready to create my digital signature (s_1, s_2) by using the following algorithm:

Screen Shot 2022-11-25 at 8.41.32 AM

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):

Screen Shot 2022-11-25 at 8.53.44 AM

This gives:

Screen Shot 2022-11-25 at 9.07.46 AM

To verify someone then needs to do the following:

Screen Shot 2022-11-25 at 8.54.23 AM

To verify that the data z_1 has a valid digital signature we need:

Screen Shot 2022-11-25 at 8.54.28 AM

So with the shared data we have:

Screen Shot 2022-11-25 at 8.54.33 AM

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 Screen Shot 2022-11-25 at 8.54.13 AMwhich 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!

Website Stats

  • 9,171,868 views

About

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.

Available to download here

IB Maths Super Exploration Guide

A Super Exploration Guide with 168 pages of essential advice from a current IB examiner to ensure you get great marks on your coursework.

Available to download here.

Recent Posts

Follow IB Maths Resources from Intermathematics on WordPress.com