Find the git repo here Link to heading

Background Link to heading

This project was made when I was learning C++. I cant say I know C++ and this project basically doesnt use any C++ features. In reflection I should of made it a pure C program. My goal was to avoid using any fancy libaries and recreate the shamir secret sharing algorithm in a very basic form using just pure C arrays and pointers. I will likely re-code this project at somepoint from scratch as its full of terrible codingand memory issues. Despite the bad code it does work and I learnt alot about memory management and C.

The algorithm Link to heading

The shamir secret sharing algorithm works by hiding your secret as the $y$ intercept of a polynomial graph. For instance take a line of the equation $y = mx + c$, $c$ is the point of intersection with the y axis hence c is your secret. The algorithm allows splitting your secret into many shares and only once a certain number of these shares have been combined can your secret be retrieved. So taking the line example, any $2$ points on a $x$,$y$ axis define a single line with a single y intercept, so essentially these shares are just points on a graph. So one point alone cannot reconstruct the line and find the $y$ intercept but using $2$ points we can reconstruct this line. This applies for all polynomials so $3$ points perfectly reconstruct a polynomial of: $y = ax^2 + bx + c$, $4$ points: $y = ax^3 + bx^2 + cx + d$ ect ect.

So say you have a secret you set your secret as the constant value (the value which isn’t multiplied by any power of $x$) and then you can pick coefficients for the powers of $x$. These can be randomly set or derived from peoples custom passwords (wont get into the maths behind that). Say you want any combination of $3$ shares to retrieve your secret you can take values of $x$ $1$-$3$ and package these as shares aka ($1$, $10$), ($2$, $23$) and ($3$, $84$). But the neat part is that because its just a line with an infinite number of points we can make as many shares as we want. So you could distribute $6$ shares and ANY combination of $3$ of these shares can be used to find the secret.

Once given the correct number of shares how do we programatically derive the equation of the polynomial. Especially because this polynomial could be to the power of say $50$ (requiring $51$ shares to reconstruct). The answer is matrices. What you essentially get when you put these shares into the polynomial equation with unknown constant coefficients is a set of simultaneous equations. So for a polynomial of power $3$ with the example points above you get the following equations: $10 = a + b + c$ $23 = 4a + 2b + c$ $84 = 9a + 3b + c$

To find the coefficients a, b and c for us is a fairly trivial task but for a computer a certain way to do it is using matrices. You can convert these equations into the following: [$1$ $1$ $1$] [$a$] [$10$] [$4$ $2$ $1$] x [$b$] = [$23$] [$9$ $3$ $1$] [$c$] [$84$]

Inverting the first matrix and multiplying the both sides of the equation with this matrix gives you the coefficients $a$, $b$ and $c$. Then just take $x = 0$ as your input for the polynomial equation and you will get your secret back.

Doing this with arrays Link to heading

So essentially for this to be done with arrays in C we create an array of pointers each of these pointers points to another array of integers. We load all the needed values in and we first find the determinant of this matrix. This involves a recursive algorithm with a base case of a $2 \times 2$ matrix where we multiply the top left corner with the bottom right and minus the top right times the bottom left. We do this recursively for just the top row of values for the determinant. We then do the same operation to create a matrix of minors but this time replacing each of the values with the corresponding minor. Then we find the matrix of co-factors which involves applying a pattern of alternating + and - to the elements of the matrix. Then we transpose the matrix (swap the rows and columns) and multiply it by its determinant to get the inverse matrix. Multiply this by the matrix of y values and you get your coefficients.

As you can imagine doing this all with C arrays and manual memory management is quite the task ensuring no leaks or segment faults is not as easy as you might think. My implementation using only “long long int” and c arrays is only really accurate for polynomials up to a power of 7 so a maximum of 8 secret shares to reconstruct the original polynomial. Its a rough implementation and doesn’t use any modulus to make it more secure so should never actually be used in production (in addition to the bad code). But I was quite proud of the final program and the fact it actually works using only low level manually memory manages arrays and functions.

Real world usage Link to heading

Back when Paypal was still fresh and new they actually used shamir secret sharing to secure their database. This was so that not any one person had the power to decrypt their database but also to protect against a disaster such as the person who knows the decryption key dying and taking the whole company with them. So they split the decryption key into a number of shares using shamir secret sharing. A fun story arose from this as well read this post for how the password “a$$word” saved paypal

Summary Link to heading

In summary Shamir secret sharing is a very cool algorithm and I would love to re-code this in a much more stable and scalable way soon. Again I would like to do this in C, using just arrays and pointers but maybe next time use some packages for managing extremely large and extremely small numbers. Either way this exercise taught a 15 year old a lot about memory management and allowed me to get some A-level maths practice in.