Shamirs hemlighetsdelning: polynommatematik

Shamir's Secret Sharing (1979) kodar hemligheten som y-skärningen (f(0)) för ett slumpmässigt polynom av grad (k-1) över en ändlig kropp. Vilka k punkter som helst bestämmer entydigt polynomet (Lagrangeinterpolation); färre än k punkter avslöjar ingenting.

För att dela hemligheten S med tröskeln k mellan n parter: välj ett primtal p > S och n. Välj slumpmässiga koefficienter a_1, ..., a_{k-1}. Definiera f(x) = S + a_1*x + a_2*x^2 + ... + a_{k-1}*x^{k-1} (mod p). Part i får andelen (i, f(i)).

Hemlighet S=7, p=17, k=2 (linjärt polynom). Välj a_1=3. f(x)=7+3x mod 17. Andelar: (1,10), (2,13), (3,16). Vilka två punkter som helst bestämmer linjen. f(0)=7. En enda punkt: oändligt många möjliga linjer, ingen information om S.

Givet k punkter (x_1,y_1),...,(x_k,y_k), återskapas f(0) med Lagrange: S = sum_i y_i * prod_{j≠i} (0-x_j)/(x_i-x_j) mod p. All aritmetik är modulär. Inga flyttal — exakt rekonstruktion över den ändliga kroppen.

from functools import reduce def lagrange(shares, p): xs = [s[0] for s in shares] ys = [s[1] for s in shares] result = 0 for i, (xi, yi) in enumerate(shares): num = reduce(lambda a,b: a*b%p, [(-xj)%p for j,xj in enumerate(xs) if j!=i], 1) den = reduce(lambda a,b: a*b%p, [(xi-xj)%p for j,xj in enumerate(xs) if j!=i], 1) result = (result + yi * num * pow(den, p-2, p)) % p return result

För k-1 delar finns det exakt ett polynom av grad k-1 som går genom dessa k-1 punkter, för varje möjligt hemligt värde S. Om man känner till k-1 delar är därför varje värde på S i [0, p-1] lika sannolikt – ingen information avslöjas.

p måste vara större än hemligheten och n. Ett vanligt val är p = 2^127-1 (Mersenne-primtal) för 128-bitarshemligheter. Detta säkerställer att alla delar ryms på 128 bitar och att aritmetiken blir effektiv. Alternativt kan p = 2^521-1 användas för 512-bitarshemligheter.

Grundläggande SSS garanterar inte delarnas integritet: en illvillig deltagare kan skicka in en falsk del, vilket leder till att hemligheten återskapas felaktigt. Feldman VSS (Verifiable Secret Sharing) publicerar commitmenter g^{a_i} mod p, så att delar kan verifieras utan att polynomet avslöjas.

Delar kan förnyas regelbundet: generera ett nytt polynom med samma hemlighet S och distribuera nya delar; gamla delar blir ogiltiga. En angripare som tar kontroll över en deltagare efter förnyelsen får en oanvändbar gammal del. Detta används i system för långlivad nyckelhantering.

ssss (kommandorad i Linux), python-secret-sharing, hashicorp/vault använder SSS för sin förseglingsmekanism och hårdvaruplånboken Trezor använder SSS för säkerhetskopiering av plånboksseed (SLIP-39). Alla arbetar över ändliga kroppar med stora primtal.

SSS kräver en betrodd distributör för att generera och distribuera delar (distributören känner till hemligheten). Ett scenario utan distributör kräver DKG (Distributed Key Generation). Återskapandet avslöjar hemligheten för den som har k delar – detta undviks med MPC eller tröskelsignaturer.

Shamir's SSS kodar hemligheter som polynomets skärningspunkt med y-axeln. Lagrangeinterpolation återskapar hemligheten från k delar. Perfekt informationsteoretisk säkerhet för färre än k delar. Nästa avsnitt: visuell och additiv hemlighetsdelning.