{"id":53444,"date":"2019-12-02T00:00:00","date_gmt":"2019-12-01T21:00:00","guid":{"rendered":"https:\/\/prohoster.info\/blog\/blog_prohoster\/shema-razdeleniya-sekreta-shamira"},"modified":"2020-02-18T14:01:21","modified_gmt":"2020-02-18T11:01:21","slug":"shema-razdeleniya-sekreta-shamira","status":"publish","type":"post","link":"https:\/\/prohoster.info\/en\/blog\/administrirovanie\/shema-razdeleniya-sekreta-shamira","title":{"rendered":"Shamir's secret sharing scheme","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Let\u2019s consider a scenario where it\u2019s 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.<\/p>\n

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?<\/p>\n

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\u2019t ideal either. Doubling the number of keys also doubles the opportunities for a key to be stolen.<\/p>\n

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.
\n<\/a><\/noindex>
\nThe problem can be addressed with a series of additional keys and locks, but such an approach will quickly require many<\/i> 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.<\/p>\n

How to split a secret<\/h1>\n

\nThis type of key management scheme was conceived by Adi Shamir in 1979, when he published his work \"How to Share a Secret\"<\/a><\/noindex>. The paper briefly explains the so-called \"Shamir's threshold scheme for effectively dividing a secret value (e.g., a cryptographic key) into \"Shamir's parts. Then, when and only when at least \"Shamir's from \"Shamir's parts are gathered, the secret can be easily reconstructed. \"Shamir's.<\/p>\n

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 \"Shamir's pieces. Even having \"Shamir's pieces should not provide any information. We call this property semantic security.<\/i>.<\/p>\n

Polynomial Interpolation<\/h1>\n

\nShamir's threshold scheme \"Shamir's is built around the concept of polynomial interpolation.<\/b>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!<\/p>\n

\"Shamir's
\nThrough 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: Wikipedia<\/a><\/noindex><\/i> <\/p>\n

Let's consider a polynomial of degree one, \"Shamir's. 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, \"Shamir's. 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.<\/p>\n

The really cool thing about this property is that, given the degree of the polynomial function and at least \"Shamir's points, we can derive additional points for this polynomial function. The extrapolation of these additional points is called polynomial interpolation.<\/i>.<\/p>\n

Secret Sharing<\/h1>\n

\nYou might have already realized that the clever Shamir scheme comes into play here. Let's assume that our secret \"Shamir's \u2014 this is \"Shamir's. We can turn \"Shamir's into a point on the graph \"Shamir's and create a polynomial function of degree \"Shamir's, which satisfies this point. Remember that \"Shamir's 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.<\/p>\n

Our polynomial will take the form of \"Shamir's, where \"Shamir's and \"Shamir's \u2014 randomly chosen positive integers. We are simply constructing a polynomial of degree \"Shamir's, where the constant term \"Shamir's\u00a0is our secret \"Shamir's, and each subsequent \"Shamir's members have a randomly chosen positive coefficient. If we return to the original example and assume that \"Shamir's, then we will obtain a function \"Shamir's.<\/p>\n

At this stage, we can generate fragments by connecting \"Shamir's unique integers in \"Shamir's, where \"Shamir's (because this is our secret). In this example, we want to distribute four fragments with a threshold of three, so we randomly generate points \"Shamir's and send one point to each of the four trusted individuals, the key custodians. We also inform the individuals that \"Shamir's, as this is considered public information and is necessary for recovery \"Shamir's.<\/p>\n

Secret Recovery<\/h1>\n

\nWe have already discussed the concept of polynomial interpolation and that it underlies Shamir's threshold scheme \"Shamir's. When any three of the four trusted parties want to recover \"Shamir's, they only need to interpolate \"Shamir's with their unique points. To do this, they can determine their points \"Shamir's 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<\/code>, which multiplies all results, while sigma is for<\/code>, which sums everything up.<\/p>\n

\"Shamir's<\/p>\n

<\/p>\n

\"Shamir's<\/p>\n

\nUpon \"Shamir's we can solve this as follows and return our original polynomial function:<\/p>\n

\"Shamir's<\/p>\n

\nSince we know that \"Shamir's, recovery \"Shamir's is straightforward:<\/p>\n

\"Shamir's<\/p>\n

<\/p>\n

Using insecure integer arithmetic<\/h1>\n

\nAlthough we successfully applied the core idea of Shamir \"Shamir's, 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 \"Shamir's fragments.<\/p>\n

To demonstrate how weak the scheme with integer arithmetic is, consider a scenario in which an attacker obtained two points \"Shamir's and knows the public information that \"Shamir'sFrom this information, one can deduce \"Shamir's, equal to two, and plug known values into the formula \"Shamir's and \"Shamir's.<\/p>\n

\"Shamir's<\/p>\n

\n Then an attacker can find \"Shamir's, calculating \"Shamir's:<\/p>\n

\"Shamir's<\/p>\n

\nSince we have defined \"Shamir's as randomly chosen positive integers, there are a limited number of possible \"Shamir's. With this information, an attacker can derive \"Shamir's, since anything greater than 5 will make \"Shamir's negative. This turns out to be true, as we have defined \"Shamir's<\/p>\n

Then an attacker can calculate possible values \"Shamir's, replacing \"Shamir's downward API support (simultaneously with this in \"Shamir's:<\/p>\n

\"Shamir's<\/p>\n

\nWith a limited set of options for \"Shamir's it becomes clear how easy it is to guess and verify values \"Shamir's. There are only five options here.<\/p>\n

Solving the problem of unsafe integer arithmetic<\/h1>\n

\nTo eliminate this vulnerability, Shamir suggests using modular arithmetic by replacing \"Shamir's to \"Shamir's, where \"Shamir's and \"Shamir's \u2014 the set of all prime numbers.<\/p>\n

Let's quickly recall how modular arithmetic works. Clock hands are a familiar concept. It uses a clock that is \"Shamir's. 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 \"Shamir's, where \"Shamir's\u00a0\u2014 this is our divisor (here, \"Shamir's), \"Shamir's\u00a0\u2014 this is the coefficient (how many times the divisor fits into the original number without a remainder, here, \"Shamir's), and \"Shamir's\u00a0\u2014 this is the remainder, which is usually returned by the modulo operator call (here, \"Shamir's). Knowing all these values allows us to solve the equation for \"Shamir's, but if we skip the coefficient, we will never be able to recover the original value.<\/p>\n

We can demonstrate how this enhances the security of our scheme by applying the scheme to our previous example and using \"Shamir's. Our new polynomial function \"Shamir's, and the new points \"Shamir's. 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 \"Shamir's (e.g. \"Shamir's).<\/p>\n

Using this new example, suppose the attacker learned two of these new points, \"Shamir's, and the public information \"Shamir'sThis time, the attacker uses all the information available to him to derive the following functions, where \"Shamir's\u00a0is the set of all positive integers, and \"Shamir's represents the modulus coefficient \"Shamir's.<\/p>\n

\"Shamir's<\/p>\n

\nNow our attacker finds himself again \"Shamir's, calculating \"Shamir's:<\/p>\n

\"Shamir's<\/p>\n

\nThen he tries again to derive \"Shamir's, replacing \"Shamir's downward API support (simultaneously with this in \"Shamir's:<\/p>\n

\"Shamir's<\/p>\n

\nThis time he has a serious problem. The formula lacks values \"Shamir's, \"Shamir's and \"Shamir's. Since there are an infinite number of combinations of these variables, he cannot obtain any additional information.<\/p>\n

Security considerations<\/h1>\n

\nShamir's secret sharing scheme offers security from the perspective of information theory<\/i>. This means the mathematics is robust even against an attacker with unlimited computational power. However, the scheme still contains several known issues.<\/p>\n

For example, Shamir's scheme does not create verifiable shares<\/i>, 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 \"Shamir's at will. This issue is addressed by verifiable secret sharing schemes<\/i>, such as Feldman's scheme.<\/p>\n

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<\/i> the secret with arbitrary numbers to a fixed length.<\/p>\n

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.<\/p>\n

Demo<\/h1>\n

\nAt this page<\/a><\/noindex> There is an interactive demonstration of Shamir's secret sharing scheme. The demonstration is based on the ssss-js<\/a><\/noindex>library, which is itself a JavaScript port of the popular program ssss<\/a><\/noindex>Please note that computing large values \"Shamir's, \"Shamir's and \"Shamir's may take some time.
\n
Source: habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"

\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0441\u0446\u0435\u043d\u0430\u0440\u0438\u0439, \u043a\u043e\u0433\u0434\u0430 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0438\u0442\u044c \u0431\u0435\u0437\u043e\u043f\u0430\u0441\u043d\u043e\u0441\u0442\u044c \u0431\u0430\u043d\u043a\u043e\u0432\u0441\u043a\u043e\u0433\u043e \u0445\u0440\u0430\u043d\u0438\u043b\u0438\u0449\u0430. \u041e\u043d\u043e \u0441\u0447\u0438\u0442\u0430\u0435\u0442\u0441\u044f \u0430\u0431\u0441\u043e\u043b\u044e\u0442\u043d\u043e \u043d\u0435\u043f\u0440\u0438\u0441\u0442\u0443\u043f\u043d\u044b\u043c \u0431\u0435\u0437 \u043a\u043b\u044e\u0447\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0432\u0430\u043c \u0432\u044b\u0434\u0430\u044e\u0442 \u0432 \u043f\u0435\u0440\u0432\u044b\u0439 \u0436\u0435 \u0434\u0435\u043d\u044c \u0440\u0430\u0431\u043e\u0442\u044b. \u0412\u0430\u0448\u0430 \u0446\u0435\u043b\u044c\u00a0\u2014 \u043d\u0430\u0434\u0451\u0436\u043d\u043e \u0441\u043e\u0445\u0440\u0430\u043d\u0438\u0442\u044c \u043a\u043b\u044e\u0447. \u041f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u043c, \u0432\u044b \u0440\u0435\u0448\u0438\u043b\u0438 \u0432\u0441\u0451 \u0432\u0440\u0435\u043c\u044f \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u043a\u043b\u044e\u0447 \u043f\u0440\u0438 \u0441\u0435\u0431\u0435, \u043f\u0440\u0435\u0434\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044f \u0434\u043e\u0441\u0442\u0443\u043f \u043a \u0445\u0440\u0430\u043d\u0438\u043b\u0438\u0449\u0443 \u043f\u043e \u043c\u0435\u0440\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438. \u041d\u043e \u0432\u044b \u0431\u044b\u0441\u0442\u0440\u043e \u043f\u043e\u0439\u043c\u0451\u0442\u0435, \u0447\u0442\u043e \u0442\u0430\u043a\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u043d\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e \u043d\u0435 \u043c\u0430\u0441\u0448\u0442\u0430\u0431\u0438\u0440\u0443\u0435\u0442\u0441\u044f, […]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[688],"tags":[],"class_list":["post-53444","post","type-post","status-publish","format-standard","hentry","category-administrirovanie"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\n","aioseo_head_json":{"title":"\ud83e\udd47Shamir's Secret Sharing Scheme | ProHoster","description":"Let's consider a scenario where it is necessary to secure a bank vault. It is considered completely inaccessible without the key, which you are given on your first day of work.","canonical_url":"https:\/\/prohoster.info\/en\/blog\/administrirovanie\/shema-razdeleniya-sekreta-shamira","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"en_US","og:site_name":"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b","og:type":"article","og:title":"\ud83e\udd47\u0421\u0445\u0435\u043c\u0430 \u0440\u0430\u0437\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0441\u0435\u043a\u0440\u0435\u0442\u0430 \u0428\u0430\u043c\u0438\u0440\u0430 | ProHoster","og:description":"\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0441\u0446\u0435\u043d\u0430\u0440\u0438\u0439, \u043a\u043e\u0433\u0434\u0430 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0438\u0442\u044c \u0431\u0435\u0437\u043e\u043f\u0430\u0441\u043d\u043e\u0441\u0442\u044c \u0431\u0430\u043d\u043a\u043e\u0432\u0441\u043a\u043e\u0433\u043e \u0445\u0440\u0430\u043d\u0438\u043b\u0438\u0449\u0430. \u041e\u043d\u043e \u0441\u0447\u0438\u0442\u0430\u0435\u0442\u0441\u044f \u0430\u0431\u0441\u043e\u043b\u044e\u0442\u043d\u043e \u043d\u0435\u043f\u0440\u0438\u0441\u0442\u0443\u043f\u043d\u044b\u043c \u0431\u0435\u0437 \u043a\u043b\u044e\u0447\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0432\u0430\u043c \u0432\u044b\u0434\u0430\u044e\u0442 \u0432 \u043f\u0435\u0440\u0432\u044b\u0439 \u0436\u0435 \u0434\u0435\u043d\u044c \u0440\u0430\u0431\u043e\u0442\u044b.","og:url":"https:\/\/prohoster.info\/en\/blog\/administrirovanie\/shema-razdeleniya-sekreta-shamira","og:image":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:secure_url":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:width":350,"og:image:height":350,"article:published_time":"2019-12-01T21:00:00+00:00","article:modified_time":"2020-02-18T11:01:21+00:00","article:publisher":"https:\/\/www.facebook.com\/prohoster","article:author":"https:\/\/www.facebook.com\/prohoster"},"aioseo_meta_data":{"post_id":"53444","title":null,"description":null,"keywords":null,"keyphrases":null,"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"local_seo":null,"seo_analyzer_scan_date":"2026-01-24 07:23:42","breadcrumb_settings":null,"limit_modified_date":false,"reviewed_by":null,"ai":null,"created":"2021-02-28 20:25:27","updated":"2026-01-24 07:23:42","focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"gt_translate_keys":[{"key":"link","format":"url"}],"_links":{"self":[{"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/posts\/53444","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/comments?post=53444"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/posts\/53444\/revisions"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/media?parent=53444"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/categories?post=53444"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/tags?post=53444"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}