Consider the scenario when it is necessary to ensure the security of the bank vault. It is considered completely inaccessible without a key, which is given to you on the first day of work. Your goal is to securely save the key.

Suppose you decide to keep the key with you all the time, giving access to the repository as needed. But you will quickly understand that such a solution does not normally scale in practice, because every time you open your store requires your physical presence. What about the vacation you were promised? In addition, the question is even more frightening: what if you lost the only key?

With the thought of vacation, you decided 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 also double the possibility of a key theft.

In desperation, you destroy the duplicate and decide to split the source key in half. Now you think two trusted people with key fragments must be physically present in order to collect the key and open the vault. This means that a thief needs to steal two fragments, which is twice as difficult to steal one key. However, you soon realize that this scheme is not much better than just one key, because if someone loses half the key, the full key cannot be restored.

The problem can be solved with a series of additional keys and locks, but with this approach, many keys and locks are quickly required . You decide that in an ideal scheme you need to divide the key so that security does not rely entirely on one person. You also conclude that there must be a certain threshold for the number of fragments, so that if one fragment is lost (or if a person goes on vacation), the entire key remains functional.

How to share a secret

This type of key management scheme was thought by Adi Shamir in 1979 when he published his work “How to share a secret” . The article briefly explains the so-called$$ threshold scheme for effectively sharing a secret value (for example, a cryptographic key) into $$parts. Then, when and only when at least$$ of $$ parts are assembled, you can easily recover the secret $$.

From a security point of view, an important feature of this scheme is that an attacker should not learn absolutely nothing if he does not even have$$parts. Even having$$parts should not give any information. We call this property semantic security .

Polynomial interpolation

Shamir threshold scheme $$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 drawn points on a graph, and then connected them with lines or curves, you have already used it!


An unlimited number of polynomials of degree 2 can be drawn through two points. To choose one of them, a third point is needed. Illustration: Wikipedia

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 needs at least two points. Next, we consider a polynomial function with degree two,$$. This is a quadratic function, so at least three points are required for plotting. What about a polynomial with 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 infer additional points for this polynomial function. Extrapolation of these additional points is called polynomial interpolation .

Making a secret

Perhaps you have already understood that Shamir’s smart scheme comes into play here. Suppose our secret$$ - this $$. We can turn$$ to point on the chart $$ and come up with a polynomial function with degree $$which satisfies this point. Recall that$$will be our threshold for the required fragments, so if we set the threshold to three fragments, then we must choose a polynomial function with degree two.

Our polynomial will have the form$$where $$ and $$- randomly selected positive integers. We just build a polynomial with degree$$where free ratio $$ - This is our secret $$and each of the following $$members have a randomly chosen positive coefficient. If you go back to the original example and assume that$$, then we get the function $$.

At this stage, we can generate fragments by connecting$$ unique integers in $$where $$(because it is our secret). In this example, we want to distribute four fragments with a threshold of three, therefore we randomly generate points$$and send one point to each of the four trusted people, the key keepers. We also inform people that$$as it is considered public information and necessary for recovery $$.

Recovery secret

We have already discussed the concept of polynomial interpolation and the fact that it underlies the Shamir threshold scheme. $$. When any three of the four proxies want to restore$$they just need to interpolate $$with its own unique points. For 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 forthat multiplies all the results, and sigma is that forwhich adds up.

$$

$$

With $$ we can solve this as follows and return our original polynomial function:

$$

As we know that $$recovery $$ carried out simply:

$$

Using unsafe integer arithmetic

Although we successfully applied the main idea of ​​Shamir $$, we still have a problem that we have ignored until now. Our polynomial function uses insecure integer arithmetic. Keep in mind that for each additional point that an attacker receives on the graph of our function, there are fewer opportunities for other points. You can see it with your own eyes when building a graph with an increase in the number of points for a polynomial function using integer arithmetic. This is counterproductive to our stated security goal, because the attacker should absolutely not know anything until they have at least$$fragments.

To demonstrate how weak the circuit with integer arithmetic is, consider a scenario in which an attacker received two points$$ and knows public information that $$. From this information he can deduce$$equal to two, and connect to the formula the known values $$ and $$.

$$

Then the attacker can find $$by counting $$:

$$

Since we have defined $$ like randomly selected positive integers, there are a limited number of possible $$. With this information, the attacker can display$$because anything more than 5 will do $$negative. This turns out to be true, since we have identified$$

The attacker can then calculate the possible values. $$by replacing $$ at $$:

$$

With a limited set of options for $$ it becomes clear how easy it is to find and check the values $$. There are only five options.

Solving the problem of unsafe integer arithmetic

To eliminate this vulnerability, Shamir proposes using modular arithmetic, replacing $$ on $$where $$ and $$- the set of all primes.

Quickly recall how modular arithmetic works. An arrow watch is a familiar concept. She uses watches that are$$. As soon as the hour hand passes twelve, it returns to one. An interesting feature of this system is that just by looking at the clock, we cannot deduce how many turns the hour hand made. However, if we know that the hour hand has passed 12 four times, we can completely determine the number of hours elapsed using a simple formula$$where $$ - this is our divider (here $$), $$ - is the coefficient (how many times the divider without remainder goes into the original number, here $$), but $$ - this is the remainder, which usually returns the modular operator call (here $$). Knowing all of these values ​​allows us to solve the equation for$$, but if we miss the coefficient, we can never restore the original value.

You 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 new points $$. Now the key keepers can once again use polynomial interpolation to restore our function, only this time the operations of addition and multiplication must be accompanied by a reduction modulo$$ (eg $$).

Using this new example, assume that 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$$ - a set of all positive integers, and $$ represents the modulus coefficient $$.

$$

Now our attacker finds again $$by calculating $$:

$$

Then he tries again to withdraw $$by replacing $$ at $$:

$$

This time he has a serious problem. There are no values ​​in the formula.$$, $$ and $$. Since there are an infinite number of combinations of these variables, he cannot get any additional information.

Safety considerations

Shamir’s secret sharing scheme offers security in terms of information theory . This means that mathematics is resistant even against an attacker with unlimited computing power. However, the scheme still contains several known problems.

For example, the Shamir scheme does not create verifiable fragments , that is, people can freely present fake fragments and interfere with the restoration of the correct secret. A hostile fragment keeper with enough information may even produce another fragment by changing$$at its discretion. This problem is solved with the help of 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 packing of the secret with arbitrary numbers up to a fixed length.

Finally, it is important to note that our safety concerns may go beyond the scheme itself. For real-world cryptographic applications, there is often a threat of attacks via third-party channels, when an attacker tries to extract useful information from the application execution time, caching, failures, etc. If this is a concern, you should carefully consider the use of protective measures, such as functions and search with constant execution time, prevent the storage of disk space and consider a number of other things that are beyond the scope of this article.

Demo

On this page there is an interactive demonstration of the Shamir secret sharing scheme. The demonstration is based on the ssss-js library , which itself is a JavaScript port of the popular ssss program . Note that calculating large values$$, $$ and $$ may take some time.