Consider a scenario where you need to secure a bank vault. It is considered absolutely impregnable without a key, which is given to you on the first day of work. Your goal is to securely store the key.
Suppose you decide to keep the key with you at all times, providing access to the vault as needed. But you will quickly realize that such a solution does not scale well in practice, because every time you need to be physically present to open the vault. What about the vacation you were promised? In addition, the question is even more frightening: what if you lost the only key?
With the idea of a vacation, you decide to make a copy of the key and entrust it to another employee. However, you understand that this is also not ideal. By doubling the number of keys, you have also doubled the chances of key theft.
Desperate, you destroy the duplicate and decide to split the original key in half. Now, you think two trusted people with key fragments must be physically present to collect the key and open the vault. This means that the thief needs to steal two fragments, which is twice as difficult as stealing one key. However, you soon realize that this scheme is not much better than just one key, because if someone loses half of the key, the full key cannot be recovered.
The problem can be solved with a series of additional keys and locks, but this approach will quickly require lot keys and locks. You decide that the ideal scheme is to share the key so that security doesn't rely entirely on one person. You also conclude that there must be some threshold for the number of fragments so that if one fragment is lost (or if the person goes on vacation), the entire key remains functional.
How to share a secret
This type of key management scheme was thought of by Adi Shamir in 1979 when he published his work . The article briefly explains the so-called 
thresholding scheme for effectively dividing a secret value (for example, a cryptographic key) into 
parts. Then, when and only when at least 
in the 
parts are assembled, you can easily restore the secret 
.
From a security point of view, an important property of this scheme is that an attacker should learn absolutely nothing if he does not have at least 
parts. Even the presence 
parts should not give any information. We call this property semantic security.
Polynomial Interpolation
Threshold Shamir scheme 
built around the concept polynomial interpolation. If you're not familiar with this concept, it's actually quite simple. In general, if you have ever drawn points on a chart and then connected them with lines or curves, you have already used it!
Through two points, you can draw an unlimited number of polynomials of degree 2. To choose the only one from them, you need a third point. Illustration:
Consider a polynomial with degree one, 
. If you want to plot this function on a graph, how many points do you need? Well, we know that this is a linear function that forms a line and therefore we need at least two points. Next, consider a polynomial function with degree two, 
. This is a quadratic function, so at least three points are required to plot the graph. How about a polynomial with degree three? At least four dots. 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. We call the extrapolation of these additional points polynomial interpolation.
Making a secret
You may have already figured out that this is where Shamir's clever scheme comes into play. Suppose our secret 
- Is 
. We can turn 
to the point on the graph 
and come up with a polynomial function with a degree 
, which satisfies this point. Recall that 
will be our threshold of required fragments, so if we set the threshold to three fragments, we must choose a polynomial function with a degree of two.
Our polynomial will have the form 
Where 
и 
are randomly chosen positive integers. We just build a polynomial with a degree 
, where the free coefficient 
- This is our secret 
, and each of the subsequent 
terms is a randomly chosen positive coefficient. If we return to the original example and assume that 
, then we get the function 
.
At this point, we can generate fragments by connecting 
unique integers in 
Where 
(because it's 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 people, the keepers of the key. We also tell people that 
, as it is considered public information and is necessary for recovery 
.
Secret Recovery
We have already discussed the concept of polynomial interpolation and how it underlies Shamir's thresholding scheme. 
. When any three out of four trustees want to restore 
, they only need to interpolate 
with their unique points. To do this, they can define 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, and sigma is forthat adds up everything.
For 
we can solve it like this and return our original polynomial function:
Since we know that 
, recovery 
is done simply:
Using unsafe integer arithmetic
Although we have successfully applied the basic idea of Shamir 
, we are left with a problem that we have ignored until now. Our polynomial function uses unsafe integer arithmetic. Note that for every additional point an attacker gets on our function graph, there are fewer possibilities for other points. You can see this with your own eyes when you plot an increasing number of points for a polynomial function using integer arithmetic. This is counterproductive to our stated security goal, because an attacker should know absolutely nothing until they have at least 
fragments.
To demonstrate how weak the integer arithmetic scheme is, consider a scenario in which the attacker received two points 
and knows public information that 
. From this information, he can infer 
, equal to two, and connect the known values \uXNUMXb\uXNUMXbto the formula 
и 
.
The attacker can then find 
, counting 
:
Since we have defined 
as randomly chosen positive integers, there is a limited number of possible 
. With this information, an attacker can deduce 
, because anything greater than 5 will make 
negative. This turns out to be true, since we have determined 
The attacker can then calculate the possible values 
replacing 
в 
:
With limited options for 
it becomes clear how easy it is to pick up and check values 
. There are only five options here.
Solving the problem with unsafe integer arithmetic
To fix this vulnerability, Shamir suggests using modular arithmetic by replacing 
+ 
Where 
и 
is the set of all prime numbers.
Let's quickly recall how modular arithmetic works. Hand clocks are a familiar concept. She uses a watch that is 
. As soon as the hour hand passes twelve, it returns to one. An interesting property of this system is that just by looking at the clock, we cannot deduce how many revolutions the hour hand has made. However, if we know that the hour hand has passed 12 four times, we can fully determine the number of hours that have elapsed with a simple formula 
Where 
is our divisor (here 
), 
- this is the coefficient (how many times the divisor without a remainder goes into the original number, here 
), and 
is the remainder, which usually returns a call to the modulo operator (here 
). Knowing all these values allows us to solve the equation for 
, but if we skip the coefficient, we will never be able to restore the original value.
We can demonstrate how this improves the security of our circuit by applying the circuit to our previous example and using 
. Our new polynomial function 
, and the new points 
. Now the key keepers can once again use polynomial interpolation to reconstruct our function, only this time the addition and multiplication operations must be followed by modulo reduction. 
(eg 
).
Using this new example, suppose the attacker has learned two of these new points, 
, and public information 
. This time, the attacker, based on all the information he has, displays the following functions, where 
is the set of all positive integers, and 
represents the modulus coefficient 
.
Now our intruder finds again 
, calculating 
:
Then he tries again to withdraw 
replacing 
в 
:
This time he has a serious problem. Formula missing values 
, 
и 
. Since there are an infinite number of combinations of these variables, he cannot obtain any additional information.
Security Considerations
Shamir's secret sharing scheme suggests information security. This means that the math is strong even against an attacker with unlimited computing power. However, the schema still contains several known issues.
For example, the Shamir scheme does not create fragments to be checked, that is, people are free to present fake fragments and interfere with the recovery of the correct secret. A hostile fragment keeper with enough information can even produce another fragment by changing 
at your discretion. This problem is solved with verifiable secret sharing schemes, such as the Feldman scheme.
Another problem is that the length of any fragment is equal to the length of the corresponding secret, so the length of the secret is easy to determine. This problem is solved by the trivial padding secret by arbitrary numbers up to a fixed length.
Finally, it's important to note that our security concerns may go beyond the scheme itself. For real cryptographic applications, there is often a threat of side-channel attacks, when an attacker tries to extract useful information from the application's execution time, caching, crashes, etc. If this is a concern, you should carefully consider the use of safeguards during development, such as functions and constant-time lookups, prevent saving memory to disk, and consider a number of other things that are beyond the scope of this article.
Demo
For there is an interactive demonstration of Shamir's secret sharing scheme. The demonstration was made on the basis of the library , which itself is a JavaScript port of a popular program . Note that calculating large values 
, 
и 
may take some time.
Source: habr.com
