Shamir Secret Shares and Lagrange Interpretation Constants

Shamir Secret Shares and Lagrange Interpretation Constants

In 1979, Adi Shamir (who represents the “S” in RSA) created a secret sharing algorithm that allows a secret to be split into parts, and only when a number of them are added together, we will be able to recover the secret (paper):

In this article, I will outline how Lagrange interpretation constants — and named after Joseph-Louis Lagrange — are used to recreate the secret, and will use a simple example. These Lagrange polynomial values are used for polynomial interpolation, and where we can derive a polynomial from a given number of points on the curve.

To explain the basics, let’s say that there are six generals who have control over firing a missile, and there are three bases, with two generals on each base. Unfortunately, we are worried that one of the generals might make a rash decision, so we agree that the generals will not get the secret password to fire the missile. We are also worried that a base could be taken over by a malicious force, so we agree that no two generals will be able to gain the password. So to overcome these problems we decide that a least three generals must agree together to generate the correct password to fire the missile.

In Shamir’s scheme, the number of generals can be represented by the number of shares (n), and the number of generals who are required to generate the secret is represented by the threshold (t). Thus, in this example, we have a share value of six and a threshold value of three. So we give out one of the shares to each of the generals so that none of them has the same one. We will then require three generals to put together their shares in order for them to generate the password for the missile. To solve this problem and generate the shares (and also check the answer), I’ve created this Web page [here]:

So for a password of “Fire The Missile”, with a share of six, and a threshold of three we get:

000if30kGfSjyDNilwU0Tyz5awf2uk=
001PoYDi8eMEoMI6Zkbkn2n1GABoas=
002HxjSfFEEakXLqUnfGolr27XG3Ws=
003qGMlZ/Fa9+YOyozQWch/6nnYpik=
004RHyZDtPQP9/yXgv4cojC6Zg6Ets=
0058wduFXOOonw3Pc73McnW2FQkaZk=

for which each of these can be distributed to each of the generals. Notice, that there is a “000”, “001”, “002”, “003”, “004” and “005” values at the start of the shares. These values are important, for reasons we will see later. When one, two or three of them combine their codes, the result will be:

Trying a share of 1: ‰ýôgҏ ÍŠ\Ñ<³å¬Úé
Trying a share of 2: ?D·CümQFH¤Ú¼A7™r¹Ì
Trying a share of 3: Fire The Missile

Basic theory

The basic theory relates to the number of points within a mathematical equation, that are required to reveal what the equation is (and thus determine the secret). For example, if we have a secret of 15, and can only be revealed when two people combine their information. For this, we thus need a linear equation, such as:

y=2x + 15

The two pieces of information that could be generated to reveal the equation would thus be two points on this line, such as:

(0,15) and (1,17)

If we only know one point, such as (1,17), we cannot determine the equation of the line, but knowing two points we can determine the gradient:

m = (17–15)/(1–0) =2

and from here we can determine the point it cuts the y-axis ©:

c = y -mx = 17- 2×1 = 15

and thus we have the equation (y = 2x + 15), where the secret is 15. In this example, we have only two shares, but if we require three shares we need a parabola, such as:

y = 2x² + 5x + 15

and share three points on the equation to generate the secret. If we require four shares then a cubic curve is required, and so on.

In most situations, it would be too processor intense to encrypt data with the secret share method, especially if we had a complete equation (such as using any 8 from 10 shares), so we often use symmetric encryption (such as for AES or ChaCha) to encrypt the data, and then create a share of the key. For example, if we had an 8 from 10 secret share policy, we would generate a 256-bit encryption key and then encrypt the data. Next, we would then take the 256-bit AES key and create a secret share where 8 of the 10 shares can come together to recreate the key.

https://asecuritysite.com/shares/go_sss

Lagrange interpretation constants

Shamir’s secret sharing method generates a number of shares, of which a threshold defines the number of shares which can be used to re-build the message. With this, we define a threshold value (t) and where we have n shares. For a threshold of 3, we create a polynomial which is in the form of:

f(x)=a+bx+cx² (mod p)

The secret is a . With three parties involved we then create shares for the split with f(x=1), f(x=2) and f(x=3), and where f(x=0) is the secret. With these shares, we use Lagrange interpretation constants to rebuild the secret value (f(x=0)). For each party this is computed with:

In Python, this can be coded as:

def coef(i,n):
    num=1
    denom=1
    for x in range(1, n+1):
        if (x!=i):
            num=num*x
            denom=denom*(i-x) 
    return(num/denom)

And where i is the node identifier, and n is the number of parties involved. So, for f(x)=a+bx+cx² (mod p), if we have shares of φ_1, φ_2 and φ_3, and coefficients of γ_1, γ_2 and γ_2, the secret share becomes:

The following is some sample code:

import numpy as np
import sys

def compute(poly,p,x): 
    d=(int(poly[2])+int(poly[1])*x+int(poly[0])*x*x) % p 
    return (int(d))
def coef(i,n):
    num=1
    denom=1
    for x in range(1, n+1):
        if (x!=i):
            num=num*x
            denom=denom*(i-x) 
    return(num/denom)
    
p=31
a=7
b=19
c=21
if (len(sys.argv)>1):
    a=int(sys.argv[1])
if (len(sys.argv)>2):
    b=int(sys.argv[2])
if (len(sys.argv)>3):
    c=int(sys.argv[3])
if (len(sys.argv)>4):
    p=int(sys.argv[4])
A=[c,b,a]
f_1=compute(A,p,1)
f_2=compute(A,p,2)
f_3=compute(A,p,3)
print (f"Polnomial:\n{np.poly1d(A)}")

f_0=int(( (f_1)*coef(1,3)+(f_2)*coef(2,3)+(f_3)*coef(3,3))%p)
print (f"Shares: f_1={f_1}, f_2={f_2}, f_3={f_3}") 
print (f"Lagrange Interpoltion constants:\nc_1={coef(1,3)}, c_2={coef(2,3)}, c_3={coef(3,3)}\n")
print (f"Recovered secret: f_0 (secret)={f_0}") 
if (f_0==A[2]):
    print("Successful recovery")

For a three party share and for f(x)=7+19x+21x² (mod 31) , we get shares of φ_1=16, φ_2=5 and φ_3=5, have Lagrange interpretation constants of γ_1=3, γ_2=−3.0 and γ_3=1, we get:

Polnomial:
    2
21 x + 19 x + 7
Prime: 31
Shares: f_1=16, f_2=5, f_3=5
Lagrange Interpolation constants:
c_1=3.0, c_2=-3.0, c_3=1.0
Recovered secret: f_0 (secret)=7
Successful recovery

Here are some examples:

• f(x)=7+19x+21x² (mod31) Try
• f(x)=21+19x+21x² (mod31) Try
• f(x)=500+499x+78x² (mod997) Try
• f(x)=9999+7654x+501x² (mod 65537) Try

Conclusions

Aren’t Lagrange interpretation constants wonderful? They help in creating a more secure and resilient world.