import sage.misc.banner # sage math version info 
rchars = "┘─│┐┌└"
smallbanner = sage.misc.banner.banner_text(full=True)
for c in rchars:
    smallbanner = smallbanner.replace(c,"") # remove ascii art box
print(smallbanner)
#banner() # full banner with box

 SageMath version 9.5, Release Date: 2022-01-30                     
 Using Python 3.10.12. Type "help()" for help.

from typing import List, Optional, Sequence, Tuple
import secrets
# import from custom path:
import sys
IMPORT_PATH='./src/sss'
if IMPORT_PATH not in sys.path:
    sys.path.append(IMPORT_PATH)
#print(sys.path)
import sss     # Plain SSS
import sssgf   # SSS over GF(256)
import ssswiki # SSS as implemented on Wikipedia, with pseudo-random feature
# reload imports on cell-rerun in case of source code modifications:
import importlib
importlib.reload(sss)
importlib.reload(sssgf)
importlib.reload(ssswiki)

<module 'ssswiki' from '/workdir/./src/sss/ssswiki.py'>

b = 16 # number of bytes of the secret to be shared
s = secrets.token_bytes(b) # randomly selecting a secret 
print(f"s in hex     = {s.hex()}")

s in hex     = 9fd47c7bd94aeca621715e359135657c

def share(s: bytes, n: int, t: int, prime: int, pseudo_random_seed: bytes=None) -> List[Tuple[int, bytes]]:
    """ Main function for creating `n` shares of a secret `s` such that any subset of at least `t` generated shares can be used to recovered the secret `s`.
    """
    b = len(s)
    if not (1 <= t <= n):
        raise ValueError("Invalid secret sharing parameters, ensure that 1 <= t <= n holds.")
    if b*8 > prime.bit_length():
        raise ValueError("Secret too large for chosen finite field prime.")
    if n > prime:
        raise ValueError("Number of shares to large for chosen finite field prime.")

    # Generate t coefficients
    c: List[bytes] = [b""] * t
    for j in range(t):
        if j == 0:
            c[j] = s
        else:
            if pseudo_random_seed:
                c[j] = get_pseudorandom(b,pseudo_random_seed)
            else:
                c[j] = get_random(b)

    # Evaluate polynomial and generate shares 
    shares: List[Tuple[int, bytes]] = []
    for i in range(1, n + 1):
        s_i = (i, eval_poly(c,i,prime))
        shares.append(s_i)
    return shares

def eval_poly(coefficients: List[bytes], x, prime):
    """ Evaluate polynomial of the finite field represented by the prime given. 
    """
    t = len(coefficients)
    if t == 0:
        return 0 
    y = int.from_bytes(coefficients[0],"big")
    xk=x
    for j in range(1,t):
        y = (y + int.from_bytes(coefficients[j],"big") * xk) % prime
        xk = (xk * x) % prime
    return y

bit_security=b*8 # bit length required for the prime number
randprime = int(random_prime(n=(2**bit_security)-1,proof=True,lbound=2**(bit_security-1)))
print(f"p as hex     = {hex(randprime)[2:]}")
print(f"p bit length = {randprime.bit_length()}")
assert randprime in Primes(),"Not a prime number"
assert int.from_bytes(s,'big') < randprime,"Prime must not be smaller than s"

p as hex     = da4de73dbe0ddf9107d5f56b50292635
p bit length = 128

print(f"Secret: \n\t{s.hex()}")
shares_sss = sss.share(s,5,3,randprime)
print(f"n shares: ")
for share in shares_sss:
    print(f"\t{share[0]}, {hex(share[1])[2:].zfill(b*2)}, {share[1].bit_length()}")

Secret: 
	9fd47c7bd94aeca621715e359135657c
n shares: 
	1, 778c6e15c4b5ae393cb8866b6d59b5a4, 127
	2, a181b808f8fb2c1cc34b679a4f28ff92, 128
	3, 43667317b80d86bfad540c56e67a1d11, 127
	4, 3788867fbffa9db302a86a0c83763456, 126
	5, 7de7f24110c270f6c34880bb261d4561, 127

def recover(shares: Sequence[Tuple[int, bytes]], prime: int) -> bytes:
    """ Function for recovering a previously shared secret from a list of given shares.
    """
    if not (1 <= len(shares)):
        raise ValueError("Invalid number of shares provided.")

    if len({xi for xi, _ in shares}) != len(shares):
        raise ValueError("Invalid shares provided, duplicate share indices detected.")
    if not all(1 <= xi for xi, _ in shares):
        raise ValueError("Invalid shares provided, out of range share index/indices detected.")

    # Compute the secret via Lagrange interpolation
    s = 0
    for xi, yi in shares:
        li = 1
        for xj, _ in shares:
            if xi != xj:
                # ( x_j / (x_j - x_i) ) * ...
                li_current = (xj * pow((xj - xi),-1,prime)) % prime
                li = (li * li_current) % prime
        s = (s + yi * li) % prime

    # return the reconstructed secret
    return s

s_recovered = sss.recover(shares_sss[:3],randprime)
assert s.hex() == hex(s_recovered)[2:],"Recovery failed!"
print(f"Recovered secret: \n\t{hex(s_recovered)[2:]}")

Recovered secret: 
	9fd47c7bd94aeca621715e359135657c

def share(s: bytes, n: int, t: int) -> List[Tuple[int, bytes]]:
    """ Main function for creating `n` shares of a secret `s` such that any subset of at least `t` generated shares
    can be used to recovered the secret `s`.
    """
    b = len(s)
    if not (1 <= t <= n <= 255):
        raise ValueError("Invalid secret sharing parameters, ensure that 1 <= t <= n <= 255 holds.")

    c: List[bytes] = [b""] * t
    for j in range(t):
        if j == 0:
            c[j] = s
        elif 0 < j < t:
            c[j] = random(b)
        else:
            raise ValueError("Invalid range for t.")

    f: List[GF256.Polynomial] = []
    for k in range(b):
        f_k = GF256.Polynomial([c[j][k] for j in range(t)])
        f.append(f_k)

    shares: List[Tuple[int, bytes]] = []
    for i in range(1, n + 1):
        s_i = (i, bytes(f[k](i) for k in range(b)))
        shares.append(s_i)

    return shares

print(f"Secret: \n\t{s.hex()}")
shares_sssgf = sssgf.share(s,5,3)
print(f"n shares: ")
for share in shares_sssgf:
    print(f"\t{share[0]},{share[1].hex()}")

Secret: 
	9fd47c7bd94aeca621715e359135657c
n shares: 
	1,4f004a9700d65ee1f526096170e191ba
	2,f905823317904f1b1688084a3964370a
	3,29d1b4dfce0cfd5cc2df5f1ed8b0c3cc
	4,0afee5f1d92cec0b69df3fba05327339
	5,da2ad31d00b05e4cbd8868eee4e687ff

def recover(shares: Sequence[Tuple[int, bytes]]) -> bytes:
    """ Main function for recovering a previously shared secret from a list of given shares.
    """
    if not (1 <= len(shares) <= 255):
        raise ValueError("Invalid number of shares provided.")

    if len({xi for xi, _ in shares}) != len(shares):
        raise ValueError("Invalid shares provided, duplicate share indices detected.")
    if not all(1 <= xi <= 255 for xi, _ in shares):
        raise ValueError("Invalid shares provided, out of range share index/indices detected.")

    b = len(shares[0][1])
    if any(len(yi) != b for _, yi in shares):
        raise ValueError("Invalid shares provided, share lengths are inconsistent.")

    # Compute the secret via Lagrange interpolation.
    s = bytearray(b)
    for xi, yi in shares:
        li = 1
        for xj, _ in shares:
            if xi != xj:
                li = GF256.multiply(li, GF256.multiply(xj, GF256.inverse(xj ^ xi)))
        for k in range(b):
            s[k] ^= GF256.multiply(yi[k], li)
    s = bytes(s)

    # return the reconstructed secret
    return s

s_recovered = sssgf.recover(shares_sssgf)
assert s == s_recovered
print(f"Recovered secret: \n\t{s_recovered.hex()}")

Recovered secret: 
	9fd47c7bd94aeca621715e359135657c

Recovery over $\mathbb{F}_p$¶

Recovery over $\text{GF}(256)$¶

Shamir Secret Sharing¶

Methods of secret sharing the secret $ s $¶

Sharing secret $ s $ at once over $\mathbb{F}_p$¶

Sharing over $\mathbb{F}_p$¶

Recovery over $\mathbb{F}_p$¶

Sharing secret $ s $ byte-per-byte over $\text{GF}(256)$¶

Sharing over $\text{GF}(256)$¶

Recovery over $\text{GF}(256)$¶