Let’s consider a scenario where it’s essential to secure a bank vault. It is regarded as completely inaccessible without the key, which you are issued on your first day of work. Your goal is to ensure the key's security.
Suppose you decide to keep the key with you at all times, granting access to the vault as needed. But you will quickly realize that this solution does not scale well in practice, as every time the vault needs to be opened, your physical presence is required. What about the vacation you were promised? Even more alarming is the question: what if you lose the only key?
Thinking about the vacation, you decide to make a copy of the key and entrust it to another employee. However, you understand that this isn’t ideal either. Doubling the number of keys also doubles the opportunities for a key to be stolen.
Desperate, you destroy the duplicate and decide to split the original key in half. Now, you think, two trusted individuals with key fragments must be physically present to assemble the key and unlock the vault. This means a thief needs to steal both fragments, making it twice as hard to steal one key. However, you soon realize this scheme is not much better than having a single key since if someone loses half of the key, the complete key cannot be recovered.
The problem can be addressed with a series of additional keys and locks, but such an approach will quickly require many keys and locks. You conclude that an ideal scheme should split the key so that security does not rely entirely on one person. You also conclude that there should be some threshold number of fragments, such that if one fragment is lost (or someone goes on vacation), the entire key remains functional.
How to split a secret
This type of key management scheme was conceived by Adi Shamir in 1979, when he published his work . The paper briefly explains the so-called 
threshold scheme for effectively dividing a secret value (e.g., a cryptographic key) into 
parts. Then, when and only when at least 
from 
parts are gathered, the secret can be easily reconstructed. 
.
From a security perspective, an important property of this scheme is that an attacker should not learn anything at all unless they have at least 
pieces. Even having 
pieces should not provide any information. We call this property semantic security..
Polynomial Interpolation
Shamir's threshold scheme 
is built around the concept of polynomial interpolation.If you are not familiar with this concept, it is actually quite simple. In general, if you have ever plotted points on a graph and then connected them with lines or curves, you have already used it!
Through two points, an unlimited number of degree 2 polynomials can be drawn. To select a single one from them, a third point is needed. Illustration:
Let's consider a polynomial of degree one, 
. If you want to plot this function on a graph, how many points do you need? Well, we know that it is a linear function that forms a line, so at least two points are necessary. Next, consider a polynomial function of degree two, 
. This is a quadratic function, so at least three points are required to plot the graph. How about a polynomial of degree three? At least four points. And so on and so forth.
The really cool thing about this property is that, given the degree of the polynomial function and at least 
points, we can derive additional points for this polynomial function. The extrapolation of these additional points is called polynomial interpolation..
Secret Sharing
You might have already realized that the clever Shamir scheme comes into play here. Let's assume that our secret 
— this is 
. We can turn 
into a point on the graph 
and create a polynomial function of degree 
, which satisfies this point. Remember that 
will be our threshold of required pieces, so if we set the threshold to three pieces, we need to choose a polynomial function of degree two.
Our polynomial will take the form of 
, where 
and 
— randomly chosen positive integers. We are simply constructing a polynomial of degree 
, where the constant term 
is our secret 
, and each subsequent 
members have a randomly chosen positive coefficient. If we return to the original example and assume that 
, then we will obtain a function 
.
At this stage, we can generate fragments by connecting 
unique integers in 
, where 
(because this is our secret). In this example, we want to distribute four fragments with a threshold of three, so we randomly generate points 
and send one point to each of the four trusted individuals, the key custodians. We also inform the individuals that 
, as this is considered public information and is necessary for recovery 
.
Secret Recovery
We have already discussed the concept of polynomial interpolation and that it underlies Shamir's threshold scheme 
. When any three of the four trusted parties want to recover 
, they only need to interpolate 
with their unique points. To do this, they can determine their points 
and calculate the Lagrange interpolation polynomial using the following formula. If programming is clearer to you than mathematics, then pi is essentially an operator for, which multiplies all results, while sigma is for, which sums everything up.
Upon 
we can solve this as follows and return our original polynomial function:
Since we know that 
, recovery 
is straightforward:
Using insecure integer arithmetic
Although we successfully applied the core idea of Shamir 
, we have a problem that we have ignored until now. Our polynomial function uses insecure integer arithmetic. Keep in mind that for each additional point the attacker gets on the graph of our function, fewer possibilities remain for other points. You can see this for yourself when you plot the graph with an increasing number of points for the polynomial function using integer arithmetic. This is counterproductive to our stated security goal because an attacker should not learn anything at all until they have at least 
fragments.
To demonstrate how weak the scheme with integer arithmetic is, consider a scenario in which an attacker obtained two points 
and knows the public information that 
From this information, one can deduce 
, equal to two, and plug known values into the formula 
and 
.
Then an attacker can find 
, calculating 
:
Since we have defined 
as randomly chosen positive integers, there are a limited number of possible 
. With this information, an attacker can derive 
, since anything greater than 5 will make 
negative. This turns out to be true, as we have defined 
Then an attacker can calculate possible values 
, replacing 
downward API support (simultaneously with this in 
:
With a limited set of options for 
it becomes clear how easy it is to guess and verify values 
. There are only five options here.
Solving the problem of unsafe integer arithmetic
To eliminate this vulnerability, Shamir suggests using modular arithmetic by replacing 
to 
, where 
and 
— the set of all prime numbers.
Let's quickly recall how modular arithmetic works. Clock hands are a familiar concept. It uses a clock that is 
. Once the hour hand passes twelve, it resets back to one. An interesting property of this system is that just by looking at the clock, we cannot determine how many full rotations the hour hand has made. However, if we know the hour hand has passed 12 four times, we can fully determine the number of hours that have passed with a simple formula 
, where 
— this is our divisor (here, 
), 
— this is the coefficient (how many times the divisor fits into the original number without a remainder, here, 
), and 
— this is the remainder, which is usually returned by the modulo operator call (here, 
). Knowing all these values allows us to solve the equation for 
, but if we skip the coefficient, we will never be able to recover the original value.
We can demonstrate how this enhances the security of our scheme by applying the scheme to our previous example and using 
. Our new polynomial function 
, and the new points 
. Now, the key holders can once again use polynomial interpolation to recover our function, but this time the operations of addition and multiplication must be accompanied by reduction modulo 
(e.g. 
).
Using this new example, suppose the attacker learned two of these new points, 
, and the public information 
This time, the attacker uses all the information available to him to derive the following functions, where 
is the set of all positive integers, and 
represents the modulus coefficient 
.
Now our attacker finds himself again 
, calculating 
:
Then he tries again to derive 
, replacing 
downward API support (simultaneously with this in 
:
This time he has a serious problem. The formula lacks values 
, 
and 
. Since there are an infinite number of combinations of these variables, he cannot obtain any additional information.
Security considerations
Shamir's secret sharing scheme offers security from the perspective of information theory. This means the mathematics is robust even against an attacker with unlimited computational power. However, the scheme still contains several known issues.
For example, Shamir's scheme does not create verifiable shares, meaning that individuals can freely present counterfeit shares and hinder the recovery of the correct secret. A malicious share holder with sufficient information could even produce another share by altering 
at will. This issue is addressed by verifiable secret sharing schemes, such as Feldman's scheme.
Another problem is that the length of any share is equal to the length of the corresponding secret, making it easy to determine the length of the secret. This issue is solved through trivial padding the secret with arbitrary numbers to a fixed length.
Finally, it is important to note that our security concerns may extend beyond the scheme itself. For real cryptographic applications, there is often a threat of side-channel attacks, where an attacker attempts to extract useful information from application runtime, caching, failures, etc. If this is a concern, protective measures such as constant-time functions and searches should be carefully considered during development to prevent memory from being written to disk and to think about a number of other things that go beyond this article.
Demo
At There is an interactive demonstration of Shamir's secret sharing scheme. The demonstration is based on the library, which is itself a JavaScript port of the popular program Please note that computing large values 
, 
and 
may take some time.
Source: habr.com
